Edgebreaker: connectivity compression for triangle meshes

Edgebreaker is a simple scheme for compressing the triangle/vertex incidence graphs (sometimes called connectivity or topology) of three-dimensional triangle meshes. Edgebreaker improves upon the storage required by previously reported schemes, most of which can guarantee only an O(t log(t)) storage cost for the incidence graph of a mesh of t triangles. Edgebreaker requires at most 2t bits for any mesh homeomorphic to a sphere and supports fully general meshes by using additional storage per handle and hole. For large meshes, entropy coding yields less than 1.5 bits per triangle. Edgebreaker's compression and decompression processes perform identical traversals of the mesh from one triangle to an adjacent one. At each stage, compression produces an op-code describing the topological relation between the current triangle and the boundary of the remaining part of the mesh. Decompression uses these op-codes to reconstruct the entire incidence graph. Because Edgebreaker's compression and decompression are independent of the vertex locations, they may be combined with a variety of vertex-compressing techniques that exploit topological information about the mesh to better estimate vertex locations. Edgebreaker may be used to compress the connectivity of an entire mesh bounding a 3D polyhedron or the connectivity of a triangulated surface patch whose boundary need not be encoded. The paper also offers a comparative survey of the rapidly growing field of geometric compression     

Distance-Ranked Connectivity Compression of Triangle Meshes

We present a new, single-rate method for compressing the connectivity information of a connected 2-manifold triangle mesh with or without boundary. Traditional compression schemes interleave geometry and connectivity coding, and are thus typically unable to utilize information from vertices (mesh regions) they have not yet processed. With the advent of competitive point cloud compression schemes, it has become feasible to develop separate connectivity encoding schemes that can exploit complete, global vertex position information to improve performance. Our scheme demonstrates the utility of this separation of vertex and connectivity coding. By traversing the mesh edges in a consistent fashion, and using global vertex information, we can predict the position of the vertex that completes the unprocessed triangle attached to a given edge. We then rank the vertices in the neighborhood of this predicted position by their Euclidean distance. The distance rank of the correct closing vertex is stored. Typically, these rank values are small, and the set of rank values thus possesses low entropy and compresses very well. The sequence of rank values is all that is required to represent the mesh connectivity—no special split or merge codes are necessary. Results indicate improvements over traditional valence-based schemes for more regular triangulations. Highly irregular triangulations or those containing a large number of slivers are not well modelled by our current set of predictors and may yield poorer connectivity compression rates than those provided by the best valence-based schemes.     

Efficient Coding of Nontriangular Mesh Connectivity

We describe an efficient algorithm for coding the connectivity information of general polygon meshes. In contrast to most existing algorithms which are suitable only for triangular meshes, and pay a penalty for treatment of nontriangular faces, this algorithm codes the connectivity information in a direct manner. Our treatment of the special case of triangular meshes is shown to be equivalent to the Edgebreaker algorithm. Using our methods, any triangle mesh may be coded in no more than 2 bits/triangle (approximately 4 bits/vertex), a quadrilateral mesh in no more than 3.5 bits/quad (approximately 3.5 bits/vertex), and the most common case of a quad mesh with few triangles in no more than 4 bits/polygon.     

Advancing fan-front: 3D triangle mesh compression using fan based traversal

Connectivity compression techniques for very large 3D triangle meshes are based on clever traversals of the graph representing the mesh, so as to avoid the repeated references to vertices. In this paper we present a new algorithm for compressing large 3D triangle meshes through the successive conquest of triangle fans. The connectivity of vertices in a fan is implied. As each fan is traversed, the current mesh boundary is advanced by the fan-front. The process is recursively continued till the entire mesh is traversed. The mesh is then compactly encoded as a sequence of fan configuration codes. The fan configuration code comprehensively encodes the connectivity of the fan with the rest of the mesh. There is no need for any further special operators like split codes and additional vertex offsets. The number of fans is typically one-fourth of the total number of triangles. Only a few of the fan configurations occur with high frequency, enabling excellent connectivity information compression using range encoding. A simple implementation shows significant improvements, on the average, in bit-rate per vertex, compared to earlier reported techniques.     

Priority-based encoding of triangle mesh connectivity for a known geometry

In certain practical situations, the connectivity of a triangle mesh needs to be transmitted or stored given a fixed set of 3D vertices that is known at both ends of the transaction (encoder/decoder). This task is different from a typical mesh compression scenario, in which the connectivity and geometry (vertex positions) are encoded either simultaneously or in reversed order (connectivity first), usually exploiting the freedom in vertex/triangle re-indexation. Previously proposed algorithms for encoding the connectivity for a known geometry were based on a canonical mesh traversal and predicting which vertex is to be connected to the part of the mesh that is already processed. In this paper, we take this scheme a step further by replacing the fixed traversal with a priority queue of open expansion gates, out of which in each step a gate is selected that has the most certain prediction, that is one in which there is a candidate vertex that exhibits the largest advantage in comparison with other possible candidates, according to a carefully designed quality metric. Numerical experiments demonstrate that this improvement leads to a substantial reduction in the required data rate in comparison with the state of the art.     

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     

一种新的三角形网格压缩算法

现代图形应用系统需要绘制大量的几何体，这给绘制硬件带来内存、带宽等问题。解决该问题的方法之一就是在预处理阶段对静态三维几何物体进行压缩处理。本文提出了一种新的三角形网格压缩／解压缩算法，该算法将三角形网格分解成一组三角形条和序列顶点链，然后对顶点连通性进行熵缟码。该算法与已有的GTM压缩算法相比，压缩率提
高了32％，并且支持并行解压缩。本文还提出了一种平行四边形预测方法来压缩顶点坐标。     

基于小波变换的非渐进网格压缩

为了取得较好的三角形网格压缩性能，提出了一种基于小波变换的三角形网格非渐进压缩方法。该压缩方法先利用重新网格化来去除大部分连接信息，然后利用小波变换的强去相关能力来压缩几何信息。在进行重新网格化和小波变换后，再按一个确定的次序将所有的小波系数扫描为一个序列，然后对其做量化和算术编码。另外，对重新网格化得到的自适应半正规采样模式，还设计了一种自适应细分信息编码算法，以便使解码端知道每一个小波系数应该放置在哪一个顶点上。实验表明，用该压缩方法对由三维扫描仪获取的复杂网格进行压缩，取得了比Edgebreaker方法明显要好的率失真性能；10比特量化时，压缩倍数在200倍左右，为Edgebreaker方法的2倍多。     

三角形条带网格模型几何压缩方法研究

三角形条带为三角形网格提供了一种紧凑的表示方法，使快速的绘制和传输三角形网格成为可能，因此对由三角形条带构成的网格压缩进行研究具有重要的意义．本文使用Triangle Fixer方法对三角形条带构成的三维模型拓扑信息进行了压缩，并采用3阶自适应算术编码进一步提高压缩率；同时结合量化、平行四边形顶点坐标预测以及算术编码来实现三角形网格几何信息的压缩，在几何模型质量基本没有损失的情况下，获得了很好的压缩性能．     

Triangle mesh compression along the Hamiltonian cycle

This paper proposes a novel and efficient algorithm for single-rate compression of triangle meshes. The input mesh is traversed along its greedy Hamiltonian cycle in O(n) time. Based on the Hamiltonian cycle, the mesh connectivity can be encoded by a face label sequence with low entropy containing only four kinds of labels (HETS) and the transmission delay at the decoding end that frequently occurs in the conventional single-rate approaches is obviously reduced. The mesh geometry is compressed with a global coordinate concentration strategy and a novel local parallelogram error prediction scheme. Experiments on realistic 3D models demonstrate the effectiveness of our approach in terms of compression rates and run time performance compared to the leading single-rate and progressive mesh compression methods.     

Random Accessible Hierarchical Mesh Compression for Interactive Visualization

This paper presents a novel algorithm for hierarchical random accessible mesh decompression. Our approach progressively decompresses the requested parts of a mesh without decoding less interesting parts. Previous approaches divided a mesh into independently compressed charts and a base coarse mesh. We propose a novel hierarchical representation of the mesh. We build this representation by using a boundary-based approach to recursively split the mesh in two parts, under the constraint that any of the two resulting submeshes should be reconstructible independently.
In addition to this decomposition technique, we introduce the concepts of opposite vertex and context dependant numbering . This enables us to achieve seemingly better compression ratios than previous work on quad and higher degree polygonal meshes. Our coder uses about 3 bits per polygon for connectivity and 14 bits per vertex for geometry using 12 bits quantification.     

Data‐Parallel Decompression of Triangle Mesh Topology

We propose a lossless, single‐rate triangle mesh topology codec tailored for fast data‐parallel GPU decompression. Our compression scheme coherently orders generalized triangle strips in memory. To unpack generalized triangle strips efficiently, we propose a novel parallel and scalable algorithm. We order vertices coherently to further improve our compression scheme. We use a variable bit‐length code for additional compression benefits, for which we propose a scalable data‐parallel decompression algorithm. For a set of standard benchmark models, we obtain (min: 3.7, med: 4.6, max: 7.6) bits per triangle. Our CUDA decompression requires only about 15% of the time it takes to render the model even with a simple shader.     

Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem

We say a vertex v in a graph G covers a vertex w if v=w or if v and w are adjacent. A subset of vertices of G is a dominating set if it collectively covers all vertices in the graph. The dominating set problem, which is NP-hard, consists of finding a smallest possible dominating set for a graph. The straightforward greedy strategy for finding a small dominating set in a graph consists of successively choosing vertices which cover the largest possible number of previously uncovered vertices. Several variations on this greedy heuristic are described and the results of extensive testing of these variations is presented. A more sophisticated procedure for choosing vertices, which takes into account the number of ways in which an uncovered vertex may be covered, appears to be the most successful of the algorithms which are analyzed. For our experimental testing, we used both random graphs and graphs constructed by test case generators which produce graphs with a given density and a specified size for the smallest dominating set. We found that these generators were able to produce challenging graphs for the algorithms, thus helping to discriminate among them, and allowing a greater variety of graphs to be used in the experiments. Received October 27, 1998; revised March 25, 2001.     

Context‐Based Coding of Adaptive Multiresolution Meshes

Multiresolution meshes provide an efficient and structured representation of geometric objects. To increase the mesh resolution only at vital parts of the object, adaptive refinement is widely used. We propose a lossless compression scheme for these adaptive structures that exploits the parent–child relationships inherent to the mesh hierarchy. We use the rules that correspond to the adaptive refinement scheme and store bits only where some freedom of choice is left, leading to compact codes that are free of redundancy. Moreover, we extend the coder to sequences of meshes with varying refinement. The connectivity compression ratio of our method exceeds that of state‐of‐the‐art coders by a factor of 2–7. For efficient compression of vertex positions we adapt popular wavelet‐based coding schemes to the adaptive triangular and quadrangular cases to demonstrate the compatibility with our method. Akin to state‐of‐the‐art coders, we use a zerotree to encode the resulting coefficients. Using improved context modelling we enhanced the zerotree compression, cutting the overall geometry data rate by 7% below those of the successful Progressive Geometry Compression. More importantly, by exploiting the existing refinement structure we achieve compression factors that are four times greater than those of coders which can handle irregular meshes.     

A Parallel Approach to Compression and Decompression of Triangle Meshes using the GPU

Most state‐of‐the‐art compression algorithms use complex connectivity traversal and prediction schemes, which are not efficient enough for online compression of large meshes. In this paper we propose a scalable massively parallel approach for compression and decompression of large triangle meshes using the GPU. Our method traverses the input mesh in a parallel breadth‐first manner and encodes the connectivity data similarly to the well known cut‐border machine. Geometry data is compressed using a local prediction strategy. In contrast to the original cut‐border machine, we can additionally handle triangle meshes with inconsistently oriented faces. Our approach is more than one order of magnitude faster than currently used methods and achieves competitive compression rates.     

A Flexible Kernel for Adaptive Mesh Refinement on GPU

We present a flexible GPU kernel for adaptive on‐the‐fly refinement of meshes with arbitrary topology. By simply reserving a small amount of GPU memory to store a set of adaptive refinement patterns, on‐the‐fly refinement is performed by the GPU, without any preprocessing nor additional topology data structure. The level of adaptive refinement can be controlled by specifying a per‐vertex depth‐tag, in addition to usual position, normal, color and texture coordinates. This depth‐tag is used by the kernel to instanciate the correct refinement pattern, which will map a refined connectivity on the input coarse polygon. Finally, the refined patch produced for each triangle can be displaced by the vertex shader, using any kind of geometric refinement, such as Bezier patch smoothing, scalar valued displacement, procedural geometry synthesis or subdivision surfaces. This refinement engine does neither require multipass rendering nor any use of fragment processing nor special preprocess of the input mesh structure. It can be implemented on any GPU with vertex shading capabilities.     

基于邻域预测的三角形网格几何信息压缩

在现有的代表性三角形网格压缩方法中,先采用一定的网格遍历方法来压缩连接信息,同时用遍历路径上的相邻顶点来对每个顶点的几何坐标进行平行四边形预测,以压缩几何信息。它们的主要缺点是平行四边形预测不太准确,且受到所采用的遍历方法的制约。文章提出一种新的几何信息压缩方法。编码时,对每个顶点的几何坐标,采用比平行四边形预测更为准确、且与遍历方法无关的邻域预测。解码时,采用预处理共轭梯度法,联立求解所有顶点的预测公式组成的稀疏线性方程组,同时求出所有顶点的坐标。文章采用渐进解码方法来减少求解稀疏线性方程组时,用户的等待时间。     

Compressed progressive meshes

Most systems that support visual interaction with 3D models use shape representations based on triangle meshes. The size of these representations imposes limits on applications for which complex 3D models must be accessed remotely. Techniques for simplifying and compressing 3D models reduce the transmission time. Multiresolution formats provide quick access to a crude model and then refine it progressively. Unfortunately, compared to the best nonprogressive compression methods, previously proposed progressive refinement techniques impose a significant overhead when the full resolution model must be downloaded. The CPM (compressed progressive meshes) approach proposed here eliminates this overhead. It uses a new technique, which refines the topology of the mesh in batches, which each increase the number of vertices by up to 50 percent. Less than an amortized total of 4 bits per triangle encode where and how the topological refinements should be applied. We estimate the position of new vertices from the positions of their topological neighbors in the less refined mesh using a new estimator that leads to representations of vertex coordinates that are 50 percent more compact than previously reported progressive geometry compression techniques