Optimized Edgebreaker encoding for large and regular triangle meshes

We present a technique aiming to improve the compression of the Edgebreaker CLERS string for large and regular meshes, where regularity is understood as the compactness of the distribution of vertex degrees. Our algorithm uses a specially designed context-based coding to compress the CLERS sequence. It is exceptionally simple to implement and can easily be incorporated into any existing Edgebreaker implementation which uses the Spirale Reversi algorithm for decompression. Even for irregular meshes, it does not carry considerable overhead when compared to the original Edgebreaker encoding. Experimental results show that our procedure is very fast (600000 triangles per second on a PIII 650 MHz for decompression) and leads to compression rates which are, in most cases, superior to those previously reported for large meshes of high regularity.     

Zipper: A compact connectivity data structure for triangle meshes

We propose Zipper, a compact representation of incidence and adjacency for manifold triangle meshes with fixed connectivity. Zipper uses on average only 6 bits per triangle, can be constructed in linear space and time, and supports all standard random-access and mesh traversal operators in constant time. Similarly to the previously proposed LR (Laced Ring) approach, the Zipper construction reorders vertices and triangles along a nearly Hamiltonian cycle called the ring. The 4.4× storage reduction of Zipper over LR results from three contributions. (1) For most triangles, Zipper stores a 2-bit delta (plus three additional bits) rather than a full 32-bit reference. (2) Zipper modifies the ring to reduce the number of exceptional triangles. (3) Zipper encodes the remaining exceptional triangles using 2.5× less storage. In spite of these large savings in storage, we show that Zipper offers comparable performance to LR and other data structures in mesh processing applications. Zipper may also serve as a compact indexed format for rendering meshes, and hence is valuable even in applications that do not require adjacency information.     

Wavelet-based progressive compression scheme for triangle meshes: wavemesh

We propose a new lossy to lossless progressive compression scheme for triangular meshes, based on a wavelet multiresolution theory for irregular 3D meshes. Although remeshing techniques obtain better compression ratios for geometric compression, this approach can be very effective when one wants to keep the connectivity and geometry of the processed mesh completely unchanged. The simplification is based on the solving of an inverse problem. Optimization of both the connectivity and geometry of the processed mesh improves the approximation quality and the compression ratio of the scheme at each resolution level. We show why this algorithm provides an efficient means of compression for both connectivity and geometry of 3D meshes and it is illustrated by experimental results on various sets of reference meshes, where our algorithm performs better than previously published approaches for both lossless and progressive compression.     

Hierarchical Laplacian-based compression of triangle meshes

In this paper, we present an algorithm for efficient encoding of triangle meshes. The algorithm preserves the local relations between vertices by encoding their Laplacian coordinates, while at the same time, it uses a hierarchy of additional vertex constraints that provides global rigidity and low absolute error, even for large meshes. Our scheme outperforms traversal based as well as Laplacian-based compression schemes in terms of both absolute and perceived distortion at a given data rate.     

Perception-driven adaptive compression of static triangle meshes

Mesh compression is an important task in geometry processing. It exploits geometric coherence of the data to reduce the amount of space needed to store a surface mesh. Most techniques perform compression employing a uniform data quantization over the whole surface. Research in shape perception, however, suggests that there are parts of the mesh that are visually more relevant than others. We present a novel technique that performs an adaptive compression of a static mesh, using the largest part of the bit budget on the relevant vertices while saving space on encoding the less significant ones. Our technique can be easily adapted to work with any perception-based error metric. The experiments show that our adaptive approach is at least comparable with other state-of-the-art techniques, while in some cases it provides a significant reduction of the bitrate of up to 15%. Additionally, our approach provides much faster decoding times than comparable perception-motivated compression algorithms.     

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.     

Dihedral Angle Mesh Error: a fast perception correlated distortion measure for fixed connectivity triangle meshes

In computer graphics, triangle meshes are ubiquitous as a representation of surface models. Processing of this kind of data, such as compression or watermarking, often involves an unwanted distortion of the surface geometry. Advanced processing algorithms are continuously being proposed, aiming at improving performance (compression ratio, watermark robustness and capacity), while minimizing the introduced distortion. In most cases, the final resulting mesh is intended to be viewed by a human observer, and it is therefore necessary to minimise the amount of distortion perceived by the human visual system. However, only recently there have been studies published on subjective experiments in this field, showing that previously used objective error measures exhibit rather poor correlation with the results of subjective experiments. In this paper, we present results of our own large subjective testing aimed at human perception of triangle mesh distortion. We provide an independent confirmation of the previous result by Lavoué et al. that most current metrics perform poorly, with the exception of the MSDM/MSDM2 metrics. We propose a novel metric based on measuring the distortion of dihedral angles, which provides even higher correlation with the results of our experiments and experiments performed by other researchers. Our metric is about two orders of magnitude faster than MSDM/MSDM2, which makes it much more suitable for usage in iterative optimisation algorithms.     

Constructing hierarchies for triangle meshes

We present a method to produce a hierarchy of triangle meshes that can be used to blend different levels of detail in a smooth fashion. The algorithm produces a sequence of meshes M₀, M₁, M ₂..., M_n, where each mesh M_i can be transformed to mesh M_i+1 through a set of triangle-collapse operations. For each triangle, a function is generated that approximates the underlying surface in the area of the triangle, and this function serves as a basis for assigning a weight to the triangle in the ordering operation and for supplying the points to which the triangles are collapsed. The algorithm produces a limited number of intermediate meshes by selecting, at each step, a number of triangles that can be collapsed simultaneously. This technique allows us to view a triangulated surface model at varying levels of detail while insuring that the simplified mesh approximates the original surface well     

Random-accessible compressed triangle meshes

With the exponential growth in size of geometric data, it is becoming increasingly important to make effective use of multilevel caches, limited disk storage, and bandwidth. As a result, recent work in the visualization community has focused either on designing sequential access compression schemes or on producing cache-coherent layouts of (uncompressed) meshes for random access. Unfortunately combining these two strategies is challenging as they fundamentally assume conflicting modes of data access. In this paper, we propose a novel order-preserving compression method that supports transparent random access to compressed triangle meshes. Our decompression method selectively fetches from disk, decodes, and caches in memory requested parts of a mesh. We also provide a general mesh access API for seamless mesh traversal and incidence queries. While the method imposes no particular mesh layout, it is especially suitable for cache-oblivious layouts, which minimize the number of decompression I/O requests and provide high cache utilization during access to decompressed, in-memory portions of the mesh. Moreover, the transparency of our scheme enables improved performance without the need for application code changes. We achieve compression rates on the order of 20:1 and significantly improved I/O performance due to reduced data transfer. To demonstrate the benefits of our method, we implement two common applications as benchmarks. By using cache-oblivious layouts for the input models, we observe 2?6 times overall speedup compared to using uncompressed meshes.     

Dynamically refining animated triangle meshes for rendering

We present a method to dynamically apply local refinements to an irregular triangle mesh as it deforms in real time. The method increases surface smoothness in regions of high deformation by splitting triangles in a fashion similar to one or two steps of Loop subdivision. The refinement is computed for an arbitrary triangle mesh, and the subdivided triangles are simply passed to the rendering engine, leaving the mesh itself unchanged. The algorithm can thus be easily plugged into existing systems to enhance the visual appearance of animated meshes. The refinement step has very low computational overhead and is easy to implement. We demonstrate the use of the algorithm in a physics-based facial animation system.     

一种三角网格模型的轮廓生成方法

从三维网格模型中提取轮廓信息是一个具有挑战性的过程.现有的方法一般是基于局部形状特征分析,如曲面的曲率和相邻面法向之间的夹角,但其特性通常对模型中的局部特征变化敏感.为了解决这个问题,提出一种基于三维形状几何近似的轮廓提取方法.利用完善的变分几何分割算法来得到一套完整的描述性特征曲线,首先基于变分几何近似方法划分模型为...     

User-assisted simplification method for triangle meshes preserving boundaries

This paper proposes a user-assisted mesh simplification method applied to CAD models converted to triangle meshes. This work offers the possibility of simplifying each subobject independently and at different levels of detail. This way, the user can simplify the whole model and then modify some parts, by simplifying more or by refining the desired subobjects. This can be performed while the total number of triangles in the simplified model is maintained. In this method any error metric based on an edge collapse operation can be used. Boundaries between subobjects are preserved and important attributes in the final aspect of simplified models, like normals and texture coordinates, are also considered.     

Obtuse triangle suppression in anisotropic meshes

Anisotropic triangle meshes are used for efficient approximation of surfaces and flow data in finite element analysis, and in these applications it is desirable to have as few obtuse triangles as possible to reduce the discretization error. We present a variational approach to suppressing obtuse triangles in anisotropic meshes. Specifically, we introduce a hexagonal Minkowski metric, which is sensitive to triangle orientation, to give a new formulation of the centroidal Voronoi tessellation (CVT) method. Furthermore, we prove several relevant properties of the CVT method with the newly introduced metric. Experiments show that our algorithm produces anisotropic meshes with much fewer obtuse triangles than using existing methods while maintaining mesh anisotropy.     

Biorthogonal wavelet construction for hybrid quad/triangle meshes

Ever since its introduction by Stam and Loop, the quad/triangle subdivision scheme, which is a generalization of the well-known Catmull–Clark subdivision and Loop subdivision, has attracted a great deal of interest due to its flexibility of allowing both quads and triangles in the same model. In this paper, we present a novel biorthogonal wavelet—constructed through the lifting scheme—that accommodates the quad/triangle subdivision. The introduced wavelet smoothly unifies the Catmull–Clark subdivision wavelet (for quadrilateral meshes) and the Loop subdivision wavelet (for triangular meshes) in a single framework. It can be used to flexibly and efficiently process any complicated semi-regular hybrid meshes containing both quadrilateral and triangular regions. Because the analysis and synthesis algorithms of the wavelet are composed of only local lifting operations allowing fully in-place calculations, they can be performed in linear time. The experiments demonstrate sufficient stability and fine fitting quality of the presented wavelet, which are similar to those of the Catmull–Clark subdivision wavelet and the Loop subdivision wavelet. The wavelet analysis can be used in various applications, such as shape approximation, progressive transmission, data compression and multiresolution edit of complex models.

An optimization-driven approach for computing geodesic paths on triangle meshes

There are many application scenarios where we need to refine an initial path lying on a surface to be as short as possible. A typical way to solve this problem is to iteratively shorten one segment of the path at a time. As local approaches, they are conceptually simple and easy to implement, but they converge slowly and have poor performance on large scale models. In this paper, we develop an optimization driven approach to improve the performance of computing geodesic paths. We formulate the objective function as the total length and adopt the L-BFGS solver to minimize it. Computational results show that our method converges with super-linear rate, which significantly outperforms the existing methods. Moreover, our method is flexible to handle anisotropic metric, non-uniform density function, as well as additional user-specified constraints, such as coplanar geodesics and equally-spaced geodesic helical curves, which are challenging to the existing local methods.     

Streaming compression of hexahedral meshes

We describe a method for streaming compression of hexahedral meshes. Given an interleaved stream of vertices and hexahedra our coder incrementally compresses the mesh in the presented order. Our coder is extremely memory efficient when the input stream also documents when vertices are referenced for the last time (i.e. when it contains topological finalization tags). Our coder then continuously releases and reuses data structures that no longer contribute to compressing the remainder of the stream. This means in practice that our coder has only a small fraction of the whole mesh in memory at any time. We can therefore compress very large meshes—even meshes that do not fit in memory. Compared to traditional, non-streaming approaches that load the entire mesh and globally reorder it during compression, our algorithm trades a less compact compressed representation for significant gains in speed, memory, and I/O efficiency. For example, on the 456k hexahedra “blade” mesh, our coder is twice as fast and uses 88 times less memory (only 3.1 MB) with the compressed file increasing about 3% in size. We also present the first scheme for predictive compression of properties associated with hexahedral cells.     

可调自适应三角网格的细分曲面造型方法

为了研究一种简单的有效的细分曲面方法使生成的曲面不仅光滑而且可调,提出了一种面向三角网格的可调自适应细分曲面造型法,该方法通过在传统的Loop细分模式中加入形状控制因子以使生成的曲面形状可调,同时引入二面角作为控制误差来判断相邻三角形夹角是否满足给定的阈值,以此实现自适应细分过程。模拟算例结果表明,该方法不仅能用较少网格获得性能良好的曲面,而且可以通过选取不同的值调整生成曲面形状,满足工程需要。     

A hybrid approach to feature segmentation of triangle meshes

Segmentation of a polygonal mesh is a method of breaking the mesh down into ‘meaningful’ connected subsets of meshes called regions or features. Several methods have been proposed in the past and they are either vertex based or edge based. The vertex method used here is based on the watershed segmentation scheme which appears prominently in the image segmentation literature and was later applied to the 3D segmentation problem [9] and [10]. Its main drawback is that it is a vertex based method and no hard boundaries (edges) are created for the features or regions. Edge based methods rely on the dihedral angle between polygon faces to determine if the common edge should be classified as a Feature Edge. However, this method results in many disconnected edges and thereby incomplete feature loops.We propose a hybrid method which takes advantage of both methods mentioned earlier and create regions with complete feature loops. Satisfactory results have been achieved for both CAD parts as well as other laser scanned objects such as bones and ceramic vessels.     

A double layer method for constructing signed distance fields from triangle meshes

A new algorithm is proposed for constructing signed distance fields (SDF) from triangle meshes. In our approach, both the internal and external distance fields for the triangle mesh are computed first. Then the desired SDF is computed directly from these two distance fields. As only points are used to generate the distance fields, some complicated operations, such as the computation of the distance from a point to a triangle, are avoided. Our algorithm is in a very simple form and is straightforward to parallelize. Actually, we have implemented it by use of the OpenCL API and a CPU-to-GPU speedup ratio of 10–40 is obtained. Further, this method is validated by our numerical results.