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.     

The progressive mesh compression based on meaningful segmentation

Nowadays, both mesh meaningful segmentation (also called shape decomposition) and progressive compression are fundamental important problems, and some compression algorithms have been developed with the help of patch-type segmentation. However, little attention has been paid to the effective combination of mesh compression and meaningful segmentation. In this paper, to accomplish both adaptive selective accessibility and a reasonable compression ratio, we break down the original mesh into meaningful parts and encode each part by an efficient compression algorithm. In our method, the segmentation of a model is obtained by a new feature-based decomposition algorithm, which makes use of the salient feature contours to parse the object. Moreover, the progressive compression is an improved degree-driven method, which adapts a multi-granularity quantization method in geometry encoding to obtain a higher compression ratio. We provide evidence that the proposed combination can be beneficial in many applications, such as view-dependent rendering and streaming of large meshes in a compressed form.     

支持随机浏览的渐进几何压缩

由于三维物体的自遮挡,浏览三维网格是一个典型的随机访问问题.如果在将网格压缩后,只传输与解码当前视点下可见区域的数据,就可以节约网络带宽和解码资源.目前的网格压缩方法基本上没有考虑随机访问.提出一种基于小波变换且支持随机访问的渐进几何压缩方法,基本思想是将网格表面分成很多块,对每块的细节信息独立进行编码,然后只传输当前视点下可见块的细节信息.代表细节信息的小波系数被组织成零树,设计了一种修正的SPIHT算法来对每棵小波零树独立进行压缩.实验结果表明,该方法取得了与PGC方法相当的压缩效率,但如果只传输可见区域的细节信息,该方法需要传输的数据量只是PGC方法的60%左右.     

基于Marching Cubes重组的外存模型渐进压缩

外存模型是指其规模远远超出内存容量的海量模型．为提高其存储、传输、显示等操作的效率，对外存模型进行渐进式的压缩是非常重要的．但当前已有的外存模型压缩算法都是单一层次的，不能做到渐进压缩．为此，该文提出一种针对外存模型的渐进压缩方法．能高效地压缩外存模型，并进行多分辨率的传输和显示．该方法首先将外存模型的包围盒空间按照八叉树形式进行剖分和层次化组织，使得最精细层次的各个立方块空间中的局部模型都能完全装入内存进行处理；然后，在各个立方块中对局部的模型进行基于Marching Cubes方式的重新拟合，并在此基础上建立各个局部的自适应八叉树；最后，基于各个局部自适应的八叉树，由粗至细渐进地遍历全局自适应八叉树的各个节点，并利用对内存模型能高效渐进压缩编码的先进方法进行编码压缩．实验表明，该方法对外存模型的压缩比达到了与处理内存模型相似的压缩比．高于目前的外存模型压缩方法，是第一个能渐进压缩外存模型的方法．     

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

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

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.     

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     

Image quality evaluation based on recognition times for fast image browsing applications

Mean squared error (MSE) and peak signal-to-noise-ratio (PSNR) are the most common methods for measuring the quality of compressed images, despite the fact that their inadequacies have long been recognized. Quality for compressed still images is sometimes evaluated using human observers who provide subjective ratings of the images. Both SNR and subjective quality judgments, however, may be inappropriate for evaluating progressive compression methods which are to be used for fast browsing applications. In this paper, we present a novel experimental and statistical framework for comparing progressive coders. The comparisons use response time studies in which human observers view a series of progressive transmissions, and respond to questions about the images as they become recognizable. We describe the framework and use it to compare several well-known algorithms (JPEG, set partitioning in hierarchical trees (SPIHT), and embedded zerotree wavelet (EZW)), and to show that a multiresolution decoding is recognized faster than a single large-scale decoding. Our experiments also show that, for the particular algorithms used, at the same PSNR, global blurriness slows down recognition more than do localized "splotch" artifacts.     

Compressed Manifold Modes for Mesh Processing

This paper introduces compressed eigenfunctions of the Laplace‐Beltrami operator on 3D manifold surfaces. They constitute a novel functional basis, called the compressed manifold basis, where each function has local support. We derive an algorithm, based on the alternating direction method of multipliers (ADMM), to compute this basis on a given triangulated mesh. We show that compressed manifold modes identify key shape features, yielding an intuitive understanding of the basis for a human observer, where a shape can be processed as a collection of parts. We evaluate compressed manifold modes for potential applications in shape matching and mesh abstraction. Our results show that this basis has distinct advantages over existing alternatives, indicating high potential for a wide range of use‐cases in mesh processing.     

Edge Transformations for Improving Mesh Quality of Marching Cubes

Marching Cubes is a popular choice for isosurface extraction from regular grids due to its simplicity, robustness, and efficiency. One of the key shortcomings of this approach is the quality of the resulting meshes, which tend to have many poorly shaped and degenerate triangles. This issue is often addressed through post processing operations such as smoothing. As we demonstrate in experiments with several datasets, while these improve the mesh, they do not remove all degeneracies, and incur an increased and unbounded error between the resulting mesh and the original isosurface. Rather than modifying the resulting mesh, we propose a method to modify the grid on which Marching Cubes operates. This modification greatly increases the quality of the extracted mesh. In our experiments, our method did not create a single degenerate triangle, unlike any other method we experimented with. Our method incurs minimal computational overhead, requiring at most twice the execution time of the original Marching Cubes algorithm in our experiments. Most importantly, it can be readily integrated in existing Marching Cubes implementations, and is orthogonal to many Marching Cubes enhancements (particularly, performance enhancements such as out-of-core and acceleration structures).     

基于Bayes-MeTiS网格划分的3D几何重构

为提升 3D模型几何重构过程的压缩效率,提出一种基于MeTiS网格划分的贝叶斯3D模型几何重构算法。首先,在编码端 采用MeTiS方法 对原始3D网格进行子网划分,采用随机线性矩阵对子网几何形状进行编码,并对边界节点的邻居节点使用伪随机数生成器进行数据序列构建;然后,利用贝叶斯算法进行几何模型重构算法的设计,在理论上给出了均值、方差矩阵以及模型参数学习规则,实现了3D模型的几何重构;最后,将其与图傅里叶光谱压缩(GFT)、最小二乘压缩(LMS)和基于压缩感知的图傅里叶光谱压缩(CSGFT)等算法进行仿真对比。结果表明,所提方法具有较高的比特率压缩指标以及较低的重构误差,计算效率明显提高。     

Mesh Sequence Morphing

Morphing is an important technique for the generation of special effects in computer animation. However, an analogous technique has not yet been applied to the increasingly prevalent animation representation, i.e. 3D mesh sequences. In this paper, a technique for morphing between two mesh sequences is proposed to simultaneously blend motions and interpolate shapes. Based on all possible combinations of the motions and geometries, a universal framework is proposed to recreate various plausible mesh sequences. To enable a universal framework, we design a skeleton‐driven cage‐based deformation transfer scheme which can account for motion blending and geometry interpolation. To establish one‐to‐one correspondence for interpolating between two mesh sequences, a hybrid cross‐parameterization scheme that fully utilizes the skeleton‐driven cage control structure and adapts user‐specified joint‐like markers, is introduced. The experimental results demonstrate that the framework, not only accomplishes mesh sequence morphing, but also is suitable for a wide range of applications such as deformation transfer, motion blending or transition and dynamic shape interpolation.     

全规整重网格化三维模型的压缩

通过保形自适应重采样,可将三维网格模型转化为规则排列的二维几何图像,从而可借鉴成熟的图像压缩技术对其进行压缩.提出了保形自适应采样算法,根据网格模型表面的有效顶点分布密度自适应地调整采样网格,并可最大限度地通过原始网格顶点进行采样.在不增加采样率的前提下,该压缩方法所得解压模型具有更小的失真度.通过大量实例对文中方法进行了验证,并与同类方法进行对比.实验结果表明该方法是切实可行的,且具有更好的压缩效果.     

Joint reversible watermarking and progressive compression of 3D meshes

A new reversible 3D mesh watermarking scheme is proposed in conjunction with progressive compression. Progressive 3D mesh compression permits a progressive refinement of the model from a coarse to a fine representation by using different levels of detail (LoDs). A reversible watermark is embedded into all refinement levels such that (1) the refinement levels are copyright protected, and (2) an authorized user is able to reconstruct the original 3D model after watermark extraction, hence reversible. The progressive compression considers a connectivity-driven algorithm to choose the vertices that are to be refined for each LoD. The proposed watermarking algorithm modifies the geometry information of these vertices based on histogram bin shifting technique. An authorized user can extract the watermark in each LoD and recover the original 3D mesh, while an unauthorized user which has access to the decompression algorithm can only reconstruct a distorted version of the 3D model. Experimental results show that the proposed method is robust to several attack scenarios while maintaining a good compression ratio.     

Preserving Shadow Silhouettes in Illumination-Driven Mesh Reduction

A main challenge for today's renderers is the ever-growing size of 3D scenes, exceeding the capacity of typically available main memory. This especially holds true for graphics processing units (GPUs) which could otherwise be used to greatly reduce rendering time. A lot of the memory is spent on detailed geometry with mostly imperceptible influence on the final image, even in a global illumination context. Illumination-driven mesh reduction, a Monte Carlo–based global illumination simulation, steers its mesh reduction towards areas with low visible contribution. While this works well for preserving high-energy light paths such as caustics, it does have problems: First, objects casting shadows while not being visible themselves are not preserved, resulting in highly inaccurate shadows. Secondly, non-transparent objects lack proper reduction guidance since there is no importance gradient on their backside, resulting in visible over-simplification. We present a solution to these problems by extending illumination-driven mesh reduction with occluder information, focusing on their silhouettes as well as combining it with commonly used error quadrics to preserve geometric features. Additionally, we demonstrate that the combined algorithm still supports iterative refinement of initially reduced geometry, resulting in an image visually similar to an unreduced rendering and enabling out-of-core operation.     

三维网格压缩方法综述

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

Mesh Snapping: Robust Interactive Mesh Cutting Using Fast Geodesic Curvature Flow

This paper considers the problem of interactively finding the cutting contour to extract components from a given mesh. Some existing methods support cuts of arbitrary shape but require careful and tedious input from the user. Others need little user input however they are sensitive to user input and need a postprocessing step to smooth the generated jaggy cutting contours. The popular geometric snake can be used to optimize the cutting contour, but it cannot deal with the topology change. In this paper, we propose a geodesic curvature flow based framework to overcome all these problems. Since in many cases the meaningful cutting contour on a 3D mesh is locally shortest in the sense of some weighted curve length, the geodesic curvature flow is an ideal tool for our problem. It evolves the cutting contour to the nearby local minimum. We should mention that the previous numerical scheme, discretized geodesic curvature flow (dGCF) is too slow and has not been applied to mesh segmentation. With a careful observation to dGCF, we devise here a fast computation scheme called fast geodesic curvature flow (FGCF), which only needs to solve a smaller and easier problem. The initial cutting contour is generated by a variant of random walks algorithm, which is very fast and gives reasonable cutting result with little user input. Experiment results on the benchmark mesh segmentation data set show that our proposed framework is robust to user input and capable of producing good results reflecting geometric features and human shape perception.     

一种适用于网络环境的三维网格压缩算法

为了使位流可以适应网络带宽的异构、时变以及各个网络终端的不同图形处理能力，提出了一种基于小波变换的三维网格分块渐进传输的压缩算法。利用细分曲面的模型表示方法，按照控制网格将几何体分块，采用嵌入式位平面编码方法对小波变换后每个小波子带的系数进行独立编码，生成多条独立的渐进压缩码流。该算法支持动态的质量可扩展性和分辨率可扩展性，能够从压缩结果中直接获得视点相关的模型表示。实验结果表明，该算法有利于提高多分辨率表示和传输效率，降低网络带宽需求。