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     

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     

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.     

Robust Spherical Parameterization of Triangular Meshes

Parameterization of 3D mesh data is important for many graphics and mesh processing applications, in particular for texture mapping, remeshing and morphing. Closed, manifold, genus-0 meshes are topologically equivalent to a sphere, hence this is the natural parameter domain for them. Parameterizing a 3D triangle mesh onto the 3D sphere means assigning a 3D position on the unit sphere to each of the mesh vertices, such that the spherical triangles induced by the mesh connectivity do not overlap. This is called a spherical triangulation. In this paper we formulate a set of necessary and sufficient conditions on the spherical angles of the spherical triangles for them to form a spherical triangulation. We formulate and solve an optimization procedure to produce spherical triangulations which reflect the geometric properties of a given 3D mesh in various ways.     

Delphi: geometry-based connectivity prediction in triangle mesh compression

Delphi is a new geometry-guided predictive scheme for compressing the connectivity of triangle meshes. Both compression and decompression algorithms traverse the mesh using the EdgeBreaker state machine. However, instead of encoding the EdgeBreaker clers symbols that capture connectivity explicitly, they estimate the location of the unknown vertex, v , of the next triangle. If the predicted location lies sufficiently close to the nearest vertex, w , on the boundary of the previously traversed portion of the mesh, then Delphi estimates that v coincides with w . When the guess is correct, a single confirmation bit is encoded. Otherwise, additional bits are used to encode the rectification of that prediction. When v coincides with a previously visited vertex that is not adjacent to the parent triangle (EdgeBreaker S case), the offset, which identifies the vertex v , must be encoded, mimicking the cut-border machine compression proposed by Gumhold and Strasser. On models where 97% of Delphi predictions are correct, the connectivity is compressed down to 0.19 bits per triangle. Compression rates decrease with the frequency of wrong predictors, but remains below 1.50 bits per triangle for all models tested.     

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.     

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

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

基于插值多项式的可验证随机数

信息安全协议中使用的随机数通常由协议参与者任意选取,其他参与方无法验证,从而影响协议的公平性。针对上述问题,提出一个基于插值多项式的可验证随机数生成方案。该方案无需可信任的第三方,计算中心只承担计算职责,不承担可信任第三方的验证职责,并且方案中任意参与者都能验证随机数的随机性,保证了协议的公平性。     

基于距离场的三维模型网格重建

根据任意亏格和任意边界的3D网格模型,给出一种网格重建算法。该算法通过对原始网格进行一系列自适应的局部修改操作,改进网格中三角形的质量和顶点位置分布。为减少优化过程中误差的累积,提出基于距离场的算法将新生成的顶点保留到原始网格曲面上,该算法实现简单,不需要复杂的全局参数化操作。实验结果表明,该算法有效、快速、稳定。     

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.     

任意拓扑三角形网格的全局参数化

提出了一种零亏格的任意拓扑流形三角形网格自动全局参数化方法 .算法首先采用顶点对合并的网格简化方法构造一个网格的累进表示 ,在进行网格简化的同时 ,对被删除的顶点相对于顶点合并操作所得到的新顶点的邻域进行局部参数化 ,由此得到一个带局部参数化信息的累进网格 ;然后将网格简化所得到的基网格进行中心投影到一个单位球面上 ,并采用累进恢复的方法将删除的顶点按与删除时相反的顺序逐次添加回网格上来 ,所添加顶点的坐标不再是其删除前的坐标值 ,而是由局部参数化信息计算得到 ,并且保证是位于单位球面上的 .由此得到原始网格的单位球面参数化网格     

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

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

Compressing Triangulated Irregular Networks

We address the problem of designing compact data structures for encoding a Triangulated Irregular Network (TIN). In particular, we study the problem of compressing connectivity, i.e., the information describing the topological structure of the TIN, and we propose two new compression methods which have different purposes. The goal of the first method is to minimize the number of bits needed to encode connectivity information: it encodes each vertex once, and at most two bits of connectivity information for each edge of a TIN; algorithms for coding and decoding the corresponding bitstream are simple and efficient. A practical evaluation shows compression rates of about 4.2 bits per vertex, which are comparable with those achieved by more complex methods. The second method compresses a TIN at progressive levels of detail and it is based on a strategy which iteratively removes a vertex from a TIN according to an error-based criterion. Encoding and decoding algorithms are presented and compared with other approaches to progressive compression. Our method can encode more general types of triangulations, such as those constrained by topographic features, at the cost of a slightly longer bitstream.     

Valence-Driven Connectivity Encoding for 3D Meshes

In this paper, we propose a valence-driven, single-resolution encoding technique for lossless compression of triangle mesh connectivity. Building upon a valence-based approach pioneered by Touma and Gotsman²² , we design a new valence-driven conquest for arbitrary meshes that always guarantees smaller compression rates than the original method. Furthermore, we provide a novel theoretical entropy study of our technique, hinting the optimality of the valence-driven approach. Finally, we demonstrate the practical efficiency of this approach (in agreement with the theoretical prediction) on a series of test meshes, resulting in the lowest compression ratios published so far, for both irregular and regular meshes, small or large.     

三维网格单一位率压缩统一框架的设计与实现

三维网格单一位率压缩技术将网格的几何信息和拓扑连接信息分开独立压缩.进行连接信息压缩时,通常对某种结构表示的网格连接信息进行某种形式的遍历,对遍历过程进行信息编码压缩;压缩几何信息时,一般需要经过量化、预测和熵编码3个处理过程.通过对该类算法进行研究总结,提出并设计了一个针对三角网格的单一位率压缩统一模式框架,并基于OpenGL和Visual C 6.0,以Edgebreaker算法为例进行了实验.     

三维图形数据的压缩与网上浏览

尽管互联网上存在着大量的压缩图像,但互联网上的三维图形数据却很少,其中一个重要原因就是三维图形数据的数据量比较大,所以要进行高效的压缩,以节约存储空间和网络带宽。文章结合Edgebreaker连接关系编码算法、平行四边形顶点坐标预测以及算术编码,来实现三角形网格的压缩,得到了50倍左右的压缩比;然后设计了一种存储压缩三维图形数据的eb文件格式,实现了一个支持网上浏览压缩三维图形数据的IE浏览器插件,可用于三维网页、数字博物馆等应用中。     

Progressive 3D mesh compression using MOG-based Bayesian entropy coding and gradual prediction

A progressive 3D triangular mesh compression algorithm built on the MOG-based Bayesian entropy coding and the gradual prediction scheme is proposed in this work. For connectivity coding, we employ MOG models to estimate the posterior probabilities of topology symbols given vertex geometries. Then, we encode the topology symbols using an arithmetic coder with different contexts, which depend on the posterior probabilities. For geometry coding, we propose the gradual prediction labeling and the dual-ring prediction to divide vertices into groups and predict later groups more efficiently using the information in already encoded groups. Simulation results demonstrate that the proposed algorithm provides significantly better performance than the conventional wavemesh coder, with the average bit rate reduction of about 16.9 %.     

边界简化与多目标优化相结合的高质量四边形网格生成

目的 高质量四边形网格生成是计算机辅助设计、等几何分析与图形学领域中一个富有挑战性的重要问题。针对这一问题,提出一种基于边界简化与多目标优化的高质量四边形网格生成新框架。方法 首先针对亏格非零的平面区域,提出一种将多连通区域转化为单连通区域的方法,可生成高质量的插入边界;其次,提出"可简化角度"和"可简化面积比率"两个阈值概念,从顶点夹角和顶点三角形面积入手,将给定的多边形边界简化为粗糙多边形;然后对边界简化得到的粗糙多边形进行子域分解,并确定每个子域内的网格顶点连接信息;最后提出四边形网格的均匀性和正交性度量目标函数,并通过多目标非线性优化技术确定网格内部顶点的几何位置。结果 在同样的离散边界下,本文方法与现有方法所生成的四边网格相比,所生成的四边网格顶点和单元总数目较少,网格单元质量基本类似,计算时间成本大致相同,但奇异点数目可减少70% 80%,衡量网格单元质量的比例雅克比值等相关指标均有所提高。结论 本文所提出的四边形网格生成方法能够有效减少网格中的奇异点数目,并可生成具有良好光滑性、均匀性和正交性的高质量四边形网格,非常适用于工程分析和动画仿真。     

A Weighted Delaunay Triangulation Framework for Merging Triangulations in a Connectivity Oblivious Fashion

Simplicial meshes are useful as discrete approximations of continuous spaces in numerical simulations. In some applications, however, meshes need to be modified over time. Mesh update operations are often expensive and brittle, making the simulations unstable. In this paper we propose a framework for updating simplicial meshes that undergo geometric and topological changes. Instead of explicitly maintaining connectivity information, we keep a collection of weights associated with mesh vertices, using a Weighted Delaunay Triangulation (WDT). These weights implicitly define mesh connectivity and allow direct merging of triangulations. We propose two formulations for computing the weights, and two techniques for merging triangulations, and finally illustrate our results with examples in two and three dimensions.