Feature-Preserving Offset Mesh Generation from Topology-Adapted Octrees

We introduce a reliable method to generate offset meshes from input triangle meshes or triangle soups. Our method proceeds in two steps. The first step performs a Dual Contouring method on the offset surface, operating on an adaptive octree that is refined in areas where the offset topology is complex. Our approach substantially reduces memory consumption and runtime compared to isosurfacing methods operating on uniform grids. The second step improves the output Dual Contouring mesh with an offset-aware remeshing algorithm to reduce the normal deviation between the mesh facets and the exact offset. This remeshing process reconstructs concave sharp features and approximates smooth shapes in convex areas up to a user-defined precision. We show the effectiveness and versatility of our method by applying it to a wide range of input meshes. We also benchmark our method on the Thingi10k dataset: watertight and topologically 2-manifold offset meshes are obtained for 100% of the cases.     

Polynomial surfaces interpolating arbitrary triangulations

Triangular Bezier patches are an important tool for defining smooth surfaces over arbitrary triangular meshes. The previously introduced 4-split method interpolates the vertices of a 2-manifold triangle mesh by a set of tangent plane continuous triangular Bezier patches of degree five. The resulting surface has an explicit closed form representation and is defined locally. In this paper, we introduce a new method for visually smooth interpolation of arbitrary triangle meshes based on a regular 4-split of the domain triangles. Ensuring tangent plane continuity of the surface is not enough for producing an overall fair shape. Interpolation of irregular control-polygons, be that in 1D or in 2D, often yields unwanted undulations. Note that this undulation problem is not particular to parametric interpolation, but also occurs with interpolatory subdivision surfaces. Our new method avoids unwanted undulations by relaxing the constraint of the first derivatives at the input mesh vertices: The tangent directions of the boundary curves at the mesh vertices are now completely free. Irregular triangulations can be handled much better in the sense that unwanted undulations due to flat triangles in the mesh are now avoided.     

Template-based quadrilateral mesh generation from imaging data

This paper describes a novel template-based meshing approach for generating good quality quadrilateral meshes from 2D digital images. This approach builds upon an existing image-based mesh generation technique called Imeshp, which enables us to create a segmented triangle mesh from an image without the need for an image segmentation step. Our approach generates a quadrilateral mesh using an indirect scheme, which converts the segmented triangle mesh created by the initial steps of the Imesh technique into a quadrilateral one. The triangle-to-quadrilateral conversion makes use of template meshes of triangles. To ensure good element quality, the conversion step is followed by a smoothing step, which is based on a new optimization-based procedure. We show several examples of meshes generated by our approach, and present a thorough experimental evaluation of the quality of the meshes given as examples.     

Manifold-guaranteed out-of-core simplification of large meshes with controlled topological type

In this paper, a simple and efficient algorithm is proposed for manifold-guaranteed out-of-core simplification of large meshes with controlled topological type. By dual-sampling the input large mesh model, the proposed algorithm utilizes a set of Hermite data (sample points with normals) as an intermediate model representation, which allows the topological structure of the mesh model to be encoded implicitly and thus makes it particularly suitable for out-of-core mesh simplification. Benefiting from the construction of an in-core signed distance field, the proposed algorithm possesses a set of features including manifoldness of the simplified meshes, toleration of nonmanifold mesh data input, topological noise removal, topological type control and, sharp features and boundary preservation. A novel, detailed implementation of the proposed algorithm is presented, and experimental results demonstrate that very large meshes can be simplified quickly on a low-cost off-the-shelf PC with tightly bounded approximation errors and with time and space efficiency.     

Reconstructing Animated Meshes from Time‐Varying Point Clouds

In this paper, we describe a novel approach for the reconstruction of animated meshes from a series of time‐deforming point clouds. Given a set of unordered point clouds that have been captured by a fast 3‐D scanner, our algorithm is able to compute coherent meshes which approximate the input data at arbitrary time instances. Our method is based on the computation of an implicit function in ?⁴ that approximates the time‐space surface of the time‐varying point cloud. We then use the four‐dimensional implicit function to reconstruct a polygonal model for the first time‐step. By sliding this template mesh along the time‐space surface in an as‐rigid‐as‐possible manner, we obtain reconstructions for further time‐steps which have the same connectivity as the previously extracted mesh while recovering rigid motion exactly. The resulting animated meshes allow accurate motion tracking of arbitrary points and are well suited for animation compression. We demonstrate the qualities of the proposed method by applying it to several data sets acquired by real‐time 3‐D scanners.     

High-Resolution Volumetric Computation of Offset Surfaces with Feature Preservation

We present a new algorithm for the efficient and reliable generation of offset surfaces for polygonal meshes. The algorithm is robust with respect to degenerate configurations and computes (self‐)intersection free offsets that do not miss small and thin components. The results are correct within a prescribed ε‐tolerance. This is achieved by using a volumetric approach where the offset surface is defined as the union of a set of spheres, cylinders, and prisms instead of surface‐based approaches that generally construct an offset surface by shifting the input mesh in normal direction. Since we are using the unsigned distance field, we can handle any type of topological inconsistencies including non‐manifold configurations and degenerate triangles. A simple but effective mesh operation allows us to detect and include sharp features (shocks) into the output mesh and to preserve them during post‐processing (decimation and smoothing). We discretize the distance function by an efficient multi‐level scheme on an adaptive octree data structure. The problem of limited voxel resolutions inherent to every volumetric approach is avoided by breaking the bounding volume into smaller tiles and processing them independently. This allows for almost arbitrarily high voxel resolutions on a commodity PC while keeping the output mesh complexity low. The quality and performance of our algorithm is demonstrated for a number of challenging examples.     

Hybrid Booleans

In this paper, we present a novel method to compute Boolean operations on polygonal meshes. Given a Boolean expression over an arbitrary number of input meshes we reliably and efficiently compute an output mesh which faithfully preserves the existing sharp features and precisely reconstructs the new features appearing along the intersections of the input meshes. The term "hybrid" applies to our method in two ways: First, our algorithm operates on a hybrid data structure which stores the original input polygons (surface data) in an adaptively refined octree (volume data). By this we combine the robustness of volumetric techniques with the accuracy of surface-oriented techniques. Second, we generate a new triangulation only in a close vicinity around the intersections of the input meshes and thus preserve as much of the original mesh structure as possible (hybrid mesh). Since the actual processing of the Boolean operation is confined to a very small region around the intersections of the input meshes, we can achieve very high adaptive refinement resolutions and hence very high precision. We demonstrate our method on a number of challenging examples.     

A Semi‐Lagrangian Closest Point Method for Deforming Surfaces

We present an Eulerian method for the real‐time simulation of intrinsic fluid dynamics effects on deforming surfaces. Our method is based on a novel semi‐Lagrangian closest point method for the solution of partial differential equations on animated triangle meshes. We describe this method and demonstrate its use to compute and visualize flow and wave propagation along such meshes at high resolution and speed. Underlying our technique is the efficient conversion of an animated triangle mesh into a time‐dependent implicit representation based on closest surface points. The proposed technique is unconditionally stable with respect to the surface deformation and, in contrast to comparable Lagrangian techniques, its precision does not depend on the level of detail of the surface triangulation.     

拓扑结构可变的动态多细节层次模型

研究多细节层次技术在虚拟环境中的广泛应用.提出了一种新的动态多细节层次结 构,这个结构不仅可以适用于多种不同的拓扑结构保持的网格简化方法,还适用于拓扑可变 的网格简化方法,可应用于任意网格模型.在此基础上还设计了一种基于拓扑结构可变的网 格简化算法;顶点合并.通过顶点合并和顶点分裂两个对偶操作,实现不同细节层次模型之间 的平滑转换,并能够自适应地改变模型的拓扑结构.     

一种基于视觉特性的三角网格简化算法

在计算机图形学和几何造型中,实体模型经常采用多边形网格描述,由于绘制时间和存储量与网格的数量成正比,因此复杂的网格模型通常并不实用,从而必须进行模型简化。因为任意多边形可以很方便地被剖分为三角形,由此该文提出一种新的基于视觉特性的三角形网格简化算法。该算法基于人类的视觉特性对三角形网格进行重要性分析,模型细节的选择取决于整个模型对视觉效果的贡献程度,在用户指定的尺度范围内,通过采用收缩三角形以达到迅速简化的目的,以较小的图形生成代价获取丰富的图形视觉效果。实验结果表明,该算法具有实现简单,速度快的特点,能有效地支持细节层次模型的表示。     

Efficiently using connectivity information between triangles in a mesh for real-time rendering

Triangle meshes are the most popular standard model used to represent polygonal surfaces. Drawing these meshes as a set of independent triangles involves sending a vast amount of information to the graphics system. Taking advantage of the connectivity information between the triangles in a mesh dramatically diminishes the amount of information the graphics system must handle. Multiresolution Triangle Strips (MTS) represent a triangle mesh as a collection of multiresolution triangles strips. These strips are the basis of both the storage and the rendering stage. The coherence between the extraction of two levels of detail is used in the model in order to decrease the visualisation time.     

GEOMPACK — a software package for the generation of meshes using geometric algorithms

We describe the mathematical software package GEOMPACK, which contains standard Fortran 77 routines for the generation of two-dimensional triangular and three-dimensional tetrahedral finite element meshes using efficient geometric algorithms. This package results from our research into mesh generation and geometric algorithms. It contains routines for constructing two- and three-dimensional Delaunay triangulations, decomposing a general polygonal region into simple or convex polygons, constructing the visibility polygon of a simple polygon from a viewpoint, and other geometric algorithms, from which our mesh generation method is built and others can be implemented. Our method generates meshes in polygonal or polyhedral regions specified by their boundary representation and possible interfaces between subregions.     

Sketch-based garment design with quad meshes

Garment creation continues to be the most tedious part of the virtual clothing process. In this paper, we present an easy to use sketch-based cloth modeling approach. Contours can be easily sketched on a mannequin to generate quad meshes to represent pieces of cloth already fitted and draped. Typically, the clothing process depends greatly on the meshing scheme that has to infer its geometry from the input boundary. Our quad meshing scheme is based on discrete Coons patches but with arbitrary boundary input. We also apply the permanence principle to our topological solution to allow more control over the influence of the input boundary polyline on the interior output polygonal mesh. This facilitates the creation of folds that are strongest in curvature at the boundary and which diminish towards the interior. The generated garments can then be easily animated in a simulation system based on finite elements, using a rediscretization of the generated mesh and a reconstructed metric of the cloth surface.     

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     

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     

Generating a smooth voxel-based model from an irregular polygon mesh

A method for generating a smooth voxelbased model from an arbitrary polygon mesh is presented. It is based on a polygonal subdivision process which takes an irregular polygon mesh as input and creates a finer and smoother mesh. The mesh is recursively refined down to or close to the voxel level, and then voxelized (digitized) into a voxel-based representation. A local subdivision approach has been developed in order to ease the computationally expensive subdivision process. The voxelization of the mesh maintains topological and fidelity requirements which are pre-defined and application dependent.     

Fitting polynomial surfaces to triangular meshes with Voronoi squared distance minimization

This paper introduces Voronoi squared distance minimization (VSDM), an algorithm that fits a surface to an input mesh. VSDM minimizes an objective function that corresponds to a Voronoi-based approximation of the overall squared distance function between the surface and the input mesh (SDM). This objective function is a generalization of the one minimized by centroidal Voronoi tessellation, and can be minimized by a quasi-Newton solver. VSDM naturally adapts the orientation of the mesh elements to best approximate the input, without estimating any differential quantities. Therefore, it can be applied to triangle soups or surfaces with degenerate triangles, topological noise and sharp features. Applications of fitting quad meshes and polynomial surfaces to input triangular meshes are demonstrated.     

Carving for topology simplification of polygonal meshes

The topological complexity of polygonal meshes has a large impact on the performance of various geometric processing algorithms, such as rendering and collision detection algorithms. Several approaches for simplifying topology have been discussed in the literature. These methods operate locally on models, which makes their effect on the topology hard to predict and analyze. Most existing methods tend to exhibit several disturbing artifacts, such as shrinking of the input and splitting of its components. We propose a novel top-down approach for topology simplification that avoids most problems that are common in existing methods. We start with a simple, genus-zero mesh that bounds the input and gradually introduce topologic features by a series of carving operations. This process yields a multiresolution stream of meshes with increasing topologic level of detail. We further present a carving algorithm that is based on constrained Delaunay tetrahedralization. The algorithm first constructs the tetrahedral mesh of the complement of the input with respect to its convex hull. It then proceeds to eliminate tetrahedra in a prioritized manner. We present quality results for two families of meshes that are difficult to simplify by all existing methods known to us: topologically complex meshes and highly clustered meshes.     

Finding and defining the generators of genus-n objects for constructing topological and cut graphs

The topology of an object is commonly represented through a topological graph or a cut graph (polygonal scheme). Over the past few years, many studies have focused on extracting the topological and cut graphs of complex freeform objects that are represented by meshes. For an object with genus-n, the topological graph has n cycles, while the cut graph contains 2n cycles. These loops, however, do not always explicitly represent the holes in the objects. That is, a cycle in the graph can be a cycle around a solid (meridian), a cycle around a hole (longitude), or almost any combination of the two. The task of classifying the cycles (generators) as cycles around holes (longitude) and cycles around solids (meridians) on the mesh is not straightforward. Every closed orientable 2-manifold with genus-n can be seen as a collection of n toruses stitched together, so that each hole in the object can be referred to as a torus with two generators. This paper proposes a method that extracts the generators from which the longitudes and the meridians are found. The topological graph is defined by the longitudes and by a spanning tree constructed between them. The cut graph is constructed using the same concept. The advantage of the proposed method over other methods is that each loop in the topological graph explicitly represents a hole in the object.