A method of 3D modeling and codec

3D modeling and codec of real objects are hot issues in the field of virtual reality. In this paper, we propose an automatic registration two range images method and a cycle based automatic global registration algorithm for rapidly and automatically registering all range images and constructing a realistic 3D model. Besides, to meet the requirement of huge data transmission over Internet, we present a 3D mesh encoding/decoding method for encoding geometry, topology and attribute data with high compression ratio and supporting progressive transmission. The research results have already been applied successfully in digital museum. Supported by the National Natural Science Foundation of China (Grant Nos. 60533070, 60773153), the Key Grant Project of Chinese Ministry of Education (Grant No. 308004), the Project of Chinese Ministry of Science and Technology (Grant No. 2006BAK12B09), and the Project of Beijing Municipal Science and Technology Commission (Grant No. Z07000100560714)     

Image‐Based Surface Compression

We present a generic framework for compression of densely sampled three‐dimensional (3D) surfaces in order to satisfy the increasing demand for storing large amounts of 3D content. We decompose a given surface into patches that are parameterized as elevation maps over planar domains and resampled on regular grids. The resulting shaped images are encoded using a state‐of‐the‐art wavelet image coder. We show that our method is not only applicable to mesh‐ and point‐based geometry, but also outperforms current surface encoders for both primitives.     

R-D optimized progressive compression of 3D meshes using prioritized gate selection and curvature prediction

A rate-distortion (R-D) optimized progressive coding algorithm for three-dimensional (3D) meshes is proposed in this work. We propose the prioritized gate selection and the curvature prediction to improve the connectivity and geometry compression performance, respectively. Furthermore, based on the bit plane coding, we develop a progressive transmission method, which improves the qualities of intermediate meshes as well as that of the fully reconstructed mesh, and extend it to the view-dependent transmission method. Experiments on various 3D mesh models show that the proposed algorithm provides significantly better compression performance than the conventional algorithms, while supporting progressive reconstruction efficiently.     

三维网格压缩方法综述

针对三维网格大数据量与三维图形引擎处理能力及网络带宽限制之间的矛盾，三维网格压缩编码技术提供了一系列解决方法。本文从静态压缩和递进网格两个角度分类，以拓扑信息驱动和几何信息驱动为两条主线，归纳比较了国内外近十年来三维网格压缩的各种方法，并给出其未采发展趋势。     

一种保留特征的网格简化和压缩递进传输方法

针对数字博物馆中三维藏品网络传输及传输过程中藏品特征保留的需要,提出了一种保留拓扑及纹理特征的网格简化方法,在三角形折叠简化算法的基础之上,通过引入边界三角形和色异三角形等概念,对误差矩阵的计算和误差控制方法进行了改进,保留了原始模型的几何边界和纹理属性等特征信息;并结合递进网格和压缩编码,构造了基于八叉树编码的递进网格文件,从而实现了基于网络的三维模型递进传输系统.     

面向移动计算终端的渐进几何简化方法

在移动计算终端上进行移动三维图形计算是一个重要的课题.针对移动计算终端屏幕小、计算能力低、无线网络带宽受限等特点,研究如何进行移动三维图形的渐进显示具有十分重要的意义.提出了利用Kobbelt四边形细分算法的逆过程迭代地进行简化的方法,通过迭代地把模型分割为奇点和作为简化模型的偶点,实现了对四边形网格几何模型的渐进式简化;提出了渐进显示的模式,通过把每一层的奇点作为可添加的细节信息,可以支持在终端上渐进显示不同细节模型并实现原模型的无损还原.完整的简化方法简单快速,可以高效地实现移动三维图形的渐进简化显示.最后在型号为Mio 336的PDA上的实验结果表明,研究成果在移动计算终端上进行实时交互等方面具有很好的应用前景.     

Hybrid and forward error correction transmission techniques for unreliable transport of 3D geometry

The continual improvement in computer performance together with the prevalence of high-speed network connections having high throughput and moderate latencies enables the deployment of multimedia applications, such as collaborative virtual environments, over wide area networks (WANs). These applications can serve as simulated environments in scenarios such as emergency response training to catastrophic disasters, military training, and entertainment. Many of these systems use 3D graphics for display and may be required to distribute geometric models on demand between participants. Progressive meshes provide an attractive mechanism for such distribution. Previous uses of progressive meshes have sent data using reliable protocols (TCP). However, such protocols have disadvantages in on-demand settings, in that they: (1) use flow control, which limits performance in WANs; (2) add additional bandwidth when there is loss; (3) treat all loss as an indication of congestion; and (4) require feature-rich multicast support, which is not always available. In this paper, we modify progressive mesh models to allow reconstruction even in the event of packet loss. We use these modifications in two transmission schemes, a hybrid transmission that uses TCP and UDP to send packets and a forward error correction transmission scheme that uses redundancy to decode the information sent. We assess the performance of these transmission schemes when deployed on network testbeds that simulate wide area and wireless characteristics.Published online: 9 February 2005 Correspondence to : Bobby Bodenheimer     

一种面向移动终端的三维图形服务计算方法

提出一种基于服务计算架构的三维图形简化算法和图形在网络上的渐进传输方法。细密的网格通过逐层地删除其冗余信息,最终生成由稀疏的基网格和一系列误差值组成的渐进网格。三维图形可依据不同分辨率的需求在移动终端上重建并渲染。实验表明,算法速度快,效果好。     

Progressive compression of arbitrary textured meshes

In this paper, we present a progressive compression algorithm for textured surface meshes, which is able to handle polygonal non‐manifold meshes as well as discontinuities in the texture mapping. Our method applies iterative batched simplifications, which create high quality levels of detail by preserving both the geometry and the texture mapping. The main features of our algorithm are (1) generic edge collapse and vertex split operators suited for polygonal non‐manifold meshes with arbitrary texture seam configurations, and (2) novel geometry‐driven prediction schemes and entropy reduction techniques for efficient encoding of connectivity and texture mapping. To our knowledge, our method is the first progressive algorithm to handle polygonal non‐manifold models. For geometry and connectivity encoding of triangular manifolds and non‐manifolds, our method is competitive with state‐of‐the‐art and even better at low/medium bitrates. Moreover, our method allows progressive encoding of texture coordinates with texture seams; it outperforms state‐of‐the‐art approaches for texture coordinate encoding. We also present a bit‐allocation framework which multiplexes mesh and texture refinement data using a perceptually‐based image metric, in order to optimize the quality of levels of detail.     

Impact of vertex clustering on registration-based 3D dynamic mesh coding

3D dynamic meshes are associated with voluminous data and need to be encoded for efficient storage and transmission. We study the impact of vertex clustering on registration-based dynamic mesh coding, where compact mesh motion representation is achieved by computing correspondences for the mesh segments from the temporal reference to obtain high compression performance. Clustering algorithms segment the mesh into smaller pieces and the compression performance is directly related to how effectively these pieces can describe the mesh motion. In this paper, we demonstrate that the use of efficient vertex clustering schemes in the compression framework can bring about a 10% improvement in compression performance.     

Combined compression and simplification of dynamic 3D meshes

We present a new approach to dynamic mesh compression, which combines compression with simplification to achieve improved compression results, a natural support for incremental transmission and level of detail. The algorithm allows fast progressive transmission of dynamic 3D content. Our scheme exploits both temporal and spatial coherency of the input data, and is especially efficient for the case of highly detailed dynamic meshes. The algorithm can be seen as an ultimate extension of the clustering and local coordinate frame (LCF)‐based approaches, where each vertex is expressed within its own specific coordinate system. The presented results show that we have achieved better compression efficiency compared to the state of the art methods. Copyright © 2008 John Wiley & Sons, Ltd.     

面向移动终端的三角网格逆细分压缩算法

针对移动用户的实时显示需求,提出一种基于逆细分的三角网格压缩算法.通过改进逆Butterfly简化算法,采用逆改版Loop模式,将细密的三角网格简化生成由稀疏的基网格和一系列偏移量组成的渐进网格;然后,通过设计偏移量小波树,将渐进网格进行嵌入式零树编码压缩.实验结果表明:该算法与以往方法相比,在获得较高压缩比的同时,运行速度较快.适用于几何模型的网络渐进传输和在移动终端上的3D图形实时渲染.     

A framework for streaming geometry in VRML

We introduce a framework for streaming geometry in VRML that eliminates the need to perform complete downloads of geometric models before starting to display them. This framework for the progressive transmission of geometry has three main parts, as follows: 1) a process to generate multiple levels-of-detail (LODs); 2) a transmission process (preferably in compressed form); and 3) a data structure for receiving and exploiting the LODs generated in the first part and transmitted in the second. The processes in parts 1 and 2 have already received considerable attention. We concentrate on a solution for part 3. Our basic contribution is a flexible LOD storage scheme, which we refer to as a progressive multilevel mesh. This scheme, primarily intended as a data structure in memory, has a low memory footprint and provides easy access to the various LODs (thus suitable for efficient rendering). This representation is not tied to a particular automated polygon reduction tool. In fact, we can use the output of any polygon reduction algorithm based on vertex clustering (including the edge collapse operations used in several algorithms). The progressive multilevel mesh complements compression techniques such as those developed by M. Deering (1995), H. Hoppe (1996) or G. Taubin et al. (1998). We discuss the integration of some of these compression techniques. However, for the sake of simplicity, we use a simple file format to describe the algorithm     

Vertex data compression through vector quantization

Rendering geometrically detailed 3D models requires the transfer and processing of large amounts of triangle and vertex geometry data. Compressing the geometry bit stream can reduce bandwidth requirements and alleviate transmission bottlenecks. In this paper, we show vector quantization to be an effective compression technique for triangle mesh vertex data. We present predictive vector quantization methods using unstructured code books as well as a product code pyramid vector quantizer. The technique is compatible with most existing mesh connectivity encoding schemes and does not require the use of entropy coding. In addition to compression, our vector quantization scheme can be used for complexity reduction by accelerating the computation of linear vertex transformations. Consequently, an encoded set of vertices can be both decoded and transformed in approximately 60 percent of the time required by a conventional method without compression     

新颖的网格模型压缩算法——网格切片

针对三维(3D)网格模型的存储与网络传输问题,提出一种新颖的三维模型压缩算法。该算法基于对网格模型的切片处理,主要由以下三个步骤组成:切片顶点的计算、切片边界的均匀采样以及对切片所得图像的编码。对于一个给定的三维模型,首先,计算模型的包围盒;然后,沿包围盒长度最长的方向进行切片;同时计算切片与网格模型表面每条边的交点,构成一个多边形,这个多边形即为切片的边界;其次,对切片边界进行均匀的重采样,使每层切片具有相同的顶点数;最后,把每层的顶点坐标转化为极坐标形式,这样,所有层顶点的ρ-坐标以及θ-坐标能分别构成一张图像,原始的三维模型即能由这两张图像表示。这种表示方法具有以下两个明显的优势:第一,降低了数据的维度,有效减少了数据量;第二,具有极大的数据相关性,进一步减少了数据的熵。基于这两个优势,该算法对图像数据进行差值编码以及算术编码,最后得到压缩后的文件。与增量参数细化(IPR)方法相比,在解码模型同等质量的前提下,所提算法的编码效率提高了23%。实验结果表明,所提算法在模型存储和传输应用中能取得很好的压缩效率,有效减少了数据量。     

位移蝶形细分面片的渐进传输

随着三维激光扫描和建模技术的不断进步，三维网格模型的数据量越来越大．与此同时，无处不在的智能计算要求数据必须能够在网络上进行快速的传输，现有的三维网格渐进传输技术无论是基于任意拓扑结构网格的渐进网格技术，还是基于参数化细分面片的渐进传输技术，都存在着传输数据量大、渐进显示效果差的问题，针对这些缺点，提出了首先利用位移蝶形细分面片重建原来的网格模型，然后对于重建后的位移蝶形细分面片设计了一种新的数据简化方法，进而构造了一种渐进传输算法，该算法在减少传输数据总量的同时，提高了渐进传输的视觉效果。     

Geometric signal compression

Compression of mesh attributes becomes a challenging problem due to the great need for efficient storage and fast transmission. This paper presents a novel geometric signal compression framework for all mesh attributes, including position coordinates, normal, color, texture, etc. Within this framework, mesh attributes are regarded as geometric signals defined on mesh surfaces. A planar parameterization algorithm is first proposed to map 3D meshes to 2D parametric meshes. Geometric signals are then transformed into 2D signals, which are sampled into 2D regular signals using an adaptive sampling method. The JPEG2000 standard for still image compression is employed to effectively encode these regular signals into compact bit-streams with high rate/distortion ratios. Experimental results demonstrate the great application potentials of this framework.     

A novel progressive modelling algorithm for 3D models

This paper presents a novel progressive modelling algorithm for 3D models to generate progressive meshes. We propose a forest clustering simplification method to generate a progressive mesh of a model with the efficient and smooth transitions between meshes at different resolutions. Our approach can also integrate and balance the appearance attributes to preserve features of a model in the simplification process. We have applied our progressive modelling technique to several different kinds of input models and results show that our approach only generates efficient and smooth progressive meshes of a given model, but also preserves the features. The proposed method is very suitable for progressive transmission and real‐time rendering of 3D models in networked virtual environments. Copyright © 2002 John Wiley & Sons, Ltd.     

Non-rigid 3D shape tracking from multiview video

We present a fast and efficient non-rigid shape tracking method for modeling dynamic 3D objects from multiview video. Starting from an initial mesh representation, the shape of a dynamic object is tracked over time, both in geometry and topology, based on multiview silhouette and 3D scene flow information. The mesh representation of each frame is obtained by deforming the mesh representation of the previous frame towards the optimal surface defined by the time-varying multiview silhouette information with the aid of 3D scene flow vectors. The whole time-varying shape is then represented as a mesh sequence which can efficiently be encoded in terms of restructuring and topological operations, and small-scale vertex displacements along with the initial model. The proposed method has the ability to deal with dynamic objects that may undergo non-rigid transformations and topological changes. The time-varying mesh representations of such non-rigid shapes, which are not necessarily of fixed connectivity, can successfully be tracked thanks to restructuring and topological operations employed in our deformation scheme. We demonstrate the performance of the proposed method both on real and synthetic sequences.