统一的数字几何处理框架

随着三维几何模型在工业界的广泛应用，处理几信号的算法变得越来越重要。尽管近几年数字几何处理研究有了很大的进展，仍然缺乏一个类似于数字图像处理的统一解决方案。该文提出了任意网格的数字信号处理框架，很好地满足了这一需求。该框架的核心思想是通过为任意网格模型构造一个全局球面（或平面）参数化，把模型的所有属性转化为定义在球面（或平面）上的信号，然后采用球面（或平面）正交分析工具对这些信号做分析处理。在这两个框架下，所有的数字图像处理技术都可以被扩展到网格模型。该文还给出了包括滤波、多分辨率编辑和压缩在内的几种典型应用的实现方法和试验结果。     

Wavelet-based multiresolution analysis of irregular surface meshes

We extend Lounsbery's multiresolution analysis wavelet-based theory for triangular 3D meshes, which can only be applied to regularly subdivided meshes and thus involves a remeshing of the existing 3D data. Based on a new irregular subdivision scheme, the proposed algorithm can be applied directly to irregular meshes, which can be very interesting when one wants to keep the connectivity and geometry of the processed mesh completely unchanged. This is very convenient in CAD (computer-assisted design), when the mesh has attributes such as texture and color information, or when the 3D mesh is used for simulations, and where a different connectivity could lead to simulation errors. The algorithm faces an inverse problem for which a solution is proposed. For each level of resolution, the simplification is processed in order to keep the mesh as regular as possible. In addition, a geometric criterion is used to keep the geometry of the approximations as close as possible to the original mesh. Several examples on various reference meshes are shown to prove the efficiency of our proposal.     

Reconstruction Algorithms as a Suitable Basis for Mesh Connectivity Compression

During a highly productive period running from 1995 to about 2002, the research in lossless compression of surface meshes mainly consisted in a hard battle for the best bitrates. However, for a few years, compression rates seem stabilized around 1.5 bit per vertex for the connectivity coding of usual triangular meshes, and more and more work is dedicated to remeshing, lossy compression, or gigantic mesh compression, where memory access and CPU optimizations are the new priority. However, the size of 3D models keeps growing, and many application fields keep requiring lossless compression. In this paper, we present a new contribution for single-rate lossless connectivity compression, which first brings improvement over current state of the art bitrates, and second, does not constraint the coding of the vertex positions, offering therefore a good complementarity with the best performing geometric compression methods. The initial observation having motivated this work is that very often, most of the connectivity part of a mesh can be automatically deduced from its geometric part using reconstruction algorithms. This has already been used within the limited framework of projectable objects (essentially, terrain models and GIS), but finds here its first generalization to arbitrary triangular meshes, without any limitation regarding the topological genus, the number of connected components, the manifoldness or the regularity. This can be obtained by constraining and guiding a Delaunay-based reconstruction algorithm so that it outputs the initial mesh to be coded. The resulting rates seem extremely competitive when the meshes are fully included in Delaunay, and are still good compared to the state-of-the-art in the case of scanned models.      

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.     

Prediction-based realistic 3D model compression

The benefit of using the geometry image to represent an arbitrary 3D mesh is that the 3D mesh can be re-sampled as a completely regular structure and coded efficiently by common image compression methods. For geometry image-based 3D mesh compression, we need to code the normal-map images while coding geometry images to improve the subjective quality and realistic effects of the reconstructed model. In traditional methods, a geometry image and a normal-map image are coded independently. However a strong correlation exists between these two kinds of images, because both of them are generated from the same 3D mesh and share the same parameterization. In this paper we propose a predictive coding framework, in which the normal-map image is predicted based on the geometric correlation between them. Additionally we utilize the strong geometric correlation among three components of normal-map image to improve the predicting accuracy. The experimental results show the proposed coding framework improves the coding efficiency of normal-map image, meanwhile the realistic effect of a 3D mesh is significantly enhanced.     

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.     

Partwise cross-parameterization via nonregular convex hull domains

In this paper, we propose a novel partwise framework for cross-parameterization between 3D mesh models. Unlike most existing methods that use regular parameterization domains, our framework uses nonregular approximation domains to build the cross-parameterization. Once the nonregular approximation domains are constructed for 3D models, different (and complex) input shapes are transformed into similar (and simple) shapes, thus facilitating the cross-parameterization process. Specifically, a novel nonregular domain, the convex hull, is adopted to build shape correspondence. We first construct convex hulls for each part of the segmented model, and then adopt our convex-hull cross-parameterization method to generate compatible meshes. Our method exploits properties of the convex hull, e.g., good approximation ability and linear convex representation for interior vertices. After building an initial cross-parameterization via convex-hull domains, we use compatible remeshing algorithms to achieve an accurate approximation of the target geometry and to ensure a complete surface matching. Experimental results show that the compatible meshes constructed are well suited for shape blending and other geometric applications.     

Implementation of 3D mesh streaming and compression techniques in NVEs

In this paper, we present a framework that integrates three‐dimensional (3D) mesh streaming and compression techniques and algorithms into our EVE‐II networked virtual environments (NVEs) platform, in order to offer support for large‐scale environments as well as highly complex world geometry. This framework allows the partial and progressive transmission of 3D worlds as well as of separate meshes, achieving reduced waiting times for the end‐user and improved network utilization. We also present a 3D mesh compression method focused on network communication, which is designed to support progressive mesh transmission, offering a fast and effective means of reducing the storage and transmission needs for geometrical data. This method is integrated in the above framework and utilizes prediction to achieve efficient lossy compression of 3D geometry. Copyright © 2006 John Wiley & Sons, Ltd.     

A computational framework for automating generation of sizing function in assembly meshing via disconnected skeletons

This paper proposes a framework for generating mesh sizing functions for assembly models. Size control is crucial in obtaining a high-quality mesh with a reduced number of elements. The reduction in the number of elements will decrease computation time and memory use during mesh generation and analysis. The framework consists of a background octree lattice for storing the sizing function, a set of source entities for providing sizing information based on geometric information, and an interpolation module for calculating the sizing on the background octree lattice using the source entities. Source entities are generated by performing a detailed systematic study to identify all the geometric factors of an assembly. Disconnected skeletons are extracted and used as tools to measure 3D proximity and 2D proximity, which are two of the geometric factors. The framework facilitates the generation of a variety of meshes with a low computational cost, to meet industry needs. The framework has been tested on many industrial parts, and sizing control on a few typical assemblies has been presented to demonstrate the effectiveness of the proposed framework.     

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     

一种基于小波变换的三维网格模型水印算法

提出了一种基于小波变换的强壮三维网格模型数字水印算法。首先采用一种平面参数化算法将三维网格模型映射为二维参数网格，三维网格模型表面的几何信号相应转换为二维信号，然后采用一种自适应小波水印算法加入水印。实验结果显示该水印算法能够抵抗各种几何信号处理攻击。     

GEncode: Geometry-driven compression for General Meshes

Performances of actual mesh compression algorithms vary significantly depending on the type of model it encodes. These methods rely on prior assumptions on the mesh to be efficient, such as regular connectivity, simple topology and similarity between its elements. However, these priors are implicit in usual schemes, harming their suitability for specific models. In particular, connectivity‐driven schemes are difficult to generalize to higher dimensions and to handle topological singularities. GEncode is a new single‐rate, geometry‐driven compression scheme where prior knowledge of the mesh is plugged into the coder in an explicit manner. It encodes meshes of arbitrary dimension without topological restrictions, but can incorporate topological properties, such as manifoldness, to improve the compression ratio. Prior knowledge of the geometry is taken as an input of the algorithm, represented by a function of the local geometry. This suits particularly well for scanned and remeshed models, where exact geometric priors are available. Compression results surfaces and volumes are competitive with existing schemes.     

基于几何特征的3维网格模型零水印算法

由于3维网格模型对水印嵌入强度高度敏感,为避免外观视觉效果严重失真,如今多数水印算法只能采用低强度的嵌入策略,从而导致其鲁棒性能下降。为了解决水印鲁棒性和透明性之间的矛盾问题,提出了一种不对网格模型数据进行任何改动的零水印算法。该方法首先对网格模型的几何数据进行校准预处理,然后对网格按顶点包围盒进行分割来提取几何数据空域特征,进而再应用3维DCT变换在变换域中进一步集中能量,其水印由若干DCT大值系数构造生成,并在IPR数据库注册获得版权保护,该水印的检测过程无需原始网格模型数据的参与。实验结果表明,该算法构造的水印不仅能抵抗顶点重排序、平移、旋转、各向一致缩放等攻击,而且对加噪、网格简化、网格滤波和二次水印等也表现出一定的鲁棒性。     

基于整体映射的不规则三维模型多细节层次描述

针对无孔洞、有边界的不规则三维模型,提出一种整体映射的多细节层次描述方法：先通过整体映射变换,将三维网格无遮挡、均匀地映射到平面正方形中;再通过正方形中初始网格的自动细化和重采样,得到所需的网格简化模型;获取不同层次简化模型,从而构建多细节层次描述。相对于传统的几何元素删除型网格简化局部型算法,以及新近的基于几何图像描述的整体型算法,该方法算法快速、简单、稳定,描述效果也较好。     

Pattern computation for compression garment by a physical/geometric approach

This paper addresses the problem of computing planar patterns for compression garments. In the garment industry, the compression garment has been increasingly widely used to retain the shape of a human body, where certain strain (or normal pressure) is designed at some places on the compression garment. Variant values and distribution of strain can only be generated by sewing different two-dimensional (2D) patterns and warping them onto the body. We present a physical/geometric approach for computing 2D meshes that, when folded onto the three-dimensional (3D) body, can generate a user-defined strain distribution through proper distortion. This is opposite to the widely studied mesh parameterization problem, whose objective is to minimize the distortion between the 2D and 3D meshes in angle, area or length.     

Motorcycle Graphs: Canonical Quad Mesh Partitioning

We describe algorithms for canonically partitioning semi‐regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions—we prove that optimizing this number is NP‐hard, but it can be efficiently approximated.     

基于二维轮廓序列的膝关节三维重建

提出了一个基于二维轮廓序列的四面体网格生成方法,用于医学图像三维几何模型重构.该方法首先对各选定的断层图像提取目标轮廓并做分支匹配等处理,然后生成各轮廓内部平面域的三角网格,最后在相邻断层之间根据三角网格连接四面体单元.该方法被应用于人体膝关节虚拟手术系统的三维几何建模,得到的膝部股骨模型包含494个节点和2 046个四面体单元,膝部脂肪模型包含2 854个节点和14011个四面体单元,这些模型被成功地应用于膝关节手术仿真,从而证明了该三维模型重建方法的可行性和有效性.     

Hierarchical grid conversion

Hierarchical grids appear in various applications in computer graphics such as subdivision and multiresolution surfaces, and terrain models. Since the different grid types perform better at different tasks, it is desired to switch between regular grids to take advantages of these grids. Based on a 2D domain obtained from the connectivity information of a mesh, we can define simple conversions to switch between regular grids. In this paper, we introduce a general framework that can be used to convert a given grid to another and we discuss the properties of these refinements such as their transformations. This framework is hierarchical meaning that it provides conversions between meshes at different level of refinement. To describe the use of this framework, we define new regular and near-regular refinements with good properties such as small factors. We also describe how grid conversion enables us to use patch-based data structures for hexagonal cells and near-regular refinements. To do so, meshes are converted to a set of quadrilateral patches that can be stored in simple structures. Near-regular refinements are also supported by defining two sets of neighborhood vectors that connect a vertex to its neighbors and are useful to address connectivity queries.     

Fun sheet matching: towards automatic block decomposition for hexahedral meshes

Depending upon the numerical approximation method that may be implemented, hexahedral meshes are frequently preferred to tetrahedral meshes. Because of the layered structure of hexahedral meshes, the automatic generation of hexahedral meshes for arbitrary geometries is still an open problem. This layered structure usually requires topological modifications to propagate globally, thus preventing the general development of meshing algorithms such as Delaunay??s algorithm for tetrahedral meshes or the advancing-front algorithm based on local decisions. To automatically produce an acceptable hexahedral mesh, we claim that both global geometric and global topological information must be taken into account in the mesh generation process. In this work, we propose a theoretical classification of the layers or sheets participating in the geometry capture procedure. These sheets are called fundamental, or fun-sheets for short, and make the connection between the global layered structure of hexahedral meshes and the geometric surfaces that are captured during the meshing process. Moreover, we propose a first generation algorithm based on fun-sheets to deal with 3D geometries having 3- and 4-valent vertices.     

Compressing the Property Mapping of Polygon Meshes

Many polygon meshes have properties such as shading normals, colors, texture coordinates, or material attributes that are associated with the vertices, faces, or corners of the mesh. While current research in mesh compression has focused on connectivity and geometry coding, the compression of properties has received less attention. There are two kinds of information to compress. One specifies each individual property—the property values. The other describes how the properties are attached to the mesh—the property mapping. In this paper, we introduce a predictive compression scheme for the property mapping that is two to three times more compact than previously reported methods.