三角网格上的代数曲面重建

提出一种用分片代数曲面构造三角曲面片的方法,利用具有公共边的2个三角形区域的4个顶点的函数值以及公共边2个端点的外法向量来构造一个二次曲面V(g)和一个截面V(h),其交V(g,h)即为2个三角曲面片的公共边界曲线.对每个已确定了边界条件的三角片内部进一步划分成3部分,每部分各自定义一个三次代数曲面.这3个三次代数曲面不仅在其交线处光滑拼接,而且分别沿三角形的边界与V(g)光滑拼接,从而构成一个具有GC1连续性的分片代数曲面.对于只属于一个三角片的边界留有一个自由度,可对曲面形状加以控制.     

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.     

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     

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.     

Scale-aware shape manipulation

A novel representation of a triangular mesh surface using a set of scale-inva~iant measures is proposed. The measures consist of angles of the triangles （triangle angles） and dihedral angles along the edges （edge angles） which are scale and rigidity independent. The vertex coordinates for a mesh give its scale-invariant measures, unique up to scale, rotation, and translation. Based on the representation of mesh using scale-invariant measures, a two-step iterative deformation algorithm is proposed, which can arbitrarily edit the mesh through simple handles interaction. The algorithm can explicitly preserve the local geometric details as much as possible in different scales even under severe editing operations including rotation, scaling, and shearing. The efficiency and robustness of the proposed algorithm are demonstrated by examples.     

TUM.GeoFrame: automated high-order hexahedral mesh generation for shell-like structures

This paper presents a fully automated high-order hexahedral mesh generation algorithm for shell-like structures based on enhanced sweeping methods. Traditional sweeping techniques create all-hexahedral element meshes for solid structures by projecting an initial single surface mesh along a specified trajectory to a specified target surface. The work reported here enhances the traditional method for thin solids by creating conforming high-order all-hexahedral finite element meshes on an enhanced surface model with surfaces intersecting in parallel, perpendicular and skew-angled directions. The new algorithm is based on cheap projection rules separating the original surface model into a set of disjoint single surfaces and a so-called interface skeleton. The core of this process is reshaping the boundary representations of the initial surfaces, generating new sweeping templates along the intersection curves and joining the single swept hex meshes in an independently generated interface mesh.     

Discrete heat kernel determines discrete Riemannian metric

The Laplace–Beltrami operator of a smooth Riemannian manifold is determined by the Riemannian metric. Conversely, the heat kernel constructed from the eigenvalues and eigenfunctions of the Laplace–Beltrami operator determines the Riemannian metric. This work proves the analogy on Euclidean polyhedral surfaces (triangle meshes), that the discrete heat kernel and the discrete Riemannian metric (unique up to a scaling) are mutually determined by each other. Given a Euclidean polyhedral surface, its Riemannian metric is represented as edge lengths, satisfying triangle inequalities on all faces. The Laplace–Beltrami operator is formulated using the cotangent formula, where the edge weight is defined as the sum of the cotangent of angles against the edge. We prove that the edge lengths can be determined by the edge weights unique up to a scaling using the variational approach.The constructive proof leads to a computational algorithm that finds the unique metric on a triangle mesh from a discrete Laplace–Beltrami operator matrix.     

Feature aligned quad dominant remeshing using iterative local updates

In this paper we present a new algorithm which turns an unstructured triangle mesh into a quad dominant mesh with edges well aligned to the principal directions of the underlying surface. Instead of computing a globally smooth parameterization or integrating curvature lines along a tangent vector field, we simply apply an iterative relaxation scheme which incrementally aligns the mesh edges to the principal directions. We further obtain the quad dominant mesh by dropping the not-aligned diagonal edges from the triangle mesh. A post-processing stage is introduced to further improve the results. The major advantage of our algorithm is its conceptual simplicity since it is merely based on elementary mesh operations such as edge collapse, flip, and split. Various results are presented in the paper; they show a good alignment to surface features and rather uniform distribution of mesh vertices. This makes them well suited, e.g., as Catmull-Clark Subdivision control meshes.     

Surface mesh regeneration considering curvatures

This work describes an automatic algorithm for unstructured mesh regeneration on arbitrarily shaped three-dimensional surfaces. The arbitrary surface may be: a triangulated mesh, a set of points, or an analytical surface (such as a collection of NURBS patches). To be generic, the algorithm works directly in Cartesian coordinates, as opposed to generating the mesh in parametric space, which might not be available in all the cases. In addition, the algorithm requires the implementation of three generic functions that abstractly represent the supporting surface. The first, given a point location, returns the desired characteristic size of a triangular element at this position. The second method, given the current edge in the boundary-contraction algorithm, locates the ideal apex point that forms a triangle with this edge. And the third method, given a point in space and a projection direction, returns the closest point on the geometrical supporting surface. This work also describes the implementation of these three methods to re-mesh an existing triangulated mesh that might present regions of high curvature. In this implementation, the only information about the surface geometry is a set of triangles. In order to test the efficiency of the proposed algorithm of surface mesh generation and implementation of the three abstract methods, results of performance and quality of generated triangular element examples are presented.     

Structure‐Aware Mesh Decimation

We present a novel approach for the decimation of triangle surface meshes. Our algorithm takes as input a triangle surface mesh and a set of planar proxies detected in a pre‐processing analysis step, and structured via an adjacency graph. It then performs greedy mesh decimation through a series of edge collapse, designed to approximate the local mesh geometry as well as the geometry and structure of proxies. Such structure‐preserving approach is well suited to planar abstraction, i.e. extreme decimation approximating well the planar parts while filtering out the others. Our experiments on a variety of inputs illustrate the potential of our approach in terms of improved accuracy and preservation of structure.     

一个雕塑实体的布尔操作算法

给出了一个雕塑实体布尔操作的现实算法,在保证效率和精确性的同时确保鲁棒性是算法的目标,实体模型通过裁剪曲面片和半边数据结构来表达几何和拓扑信息。采用了层次求交和交线跟踪的方法来保证曲面片分割和区域分类的一致性,从而克服实践中常见的退化情况。该算法也可以方便地扩展到非流形模型的布尔操作。作为一个实体造型系统的一部分,该算法已经在ＳＧＩ工作站上实现。     

Progressive Hulls for Intersection Applications

Progressive meshes are an established tool for triangle mesh simplification. By suitably adapting the simplification process, progressive hulls can be generated which enclose the original mesh in gradually simpler, nested meshes. We couple progressive hulls with a selective refinement framework and use them in applications involving intersection queries on the mesh. We demonstrate that selectively refinable progressive hulls considerably speed up intersection queries by efficiently locating intersection points on the mesh. Concerning the progressive hull construction, we propose a new formula for assigning edge collapse priorities that significantly accelerates the simplification process, and enhance the existing algorithm with several conditions aimed at producing higher quality hulls. Using progressive hulls has the added advantage that they can be used instead of the enclosed object when a lower resolution of display can be tolerated, thus speeding up the rendering process. ACM CSS: I.3.3 Computer Graphics—Picture/Image Generation, I.3.5 Computer Graphics—Computational Geometry and Object Modeling, I.3.7 Computer Graphics—Three‐Dimensional Graphics and Realism     

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.     

空间网格面片可见边界提取方法研究与应用

在计算机视觉和图形学中广泛应用三角网格来表示空间曲面，在许多应用领域基于边缘检测的2维图像处理技术已非常成熟，但空间三角网格面片边界提取，特别是沿某一方向可见边界提取方法还没有得到很好发展。本文提出一种求解三角网格面片可见边界算法，该算法根据光线方向和三角网格对应的法向量判断三角网格的可见性，从而确定三角网格面片的可见边界，再由各个三角网格具有可见边界边的数目标识三角网格的类型，接着依据三角网格类型确定面片的可见边界，该算法的时间复杂度为O（n）。最后以实例说明了该算法的可行性和有效性，并将该算法应用于卫星构型分析中的太阳翼遮挡分析计算模块，其计算速度、精度能满足工程实践要求。     

Feature sensitive multiscale editing on surfaces

A novel editing method for large triangular meshes is presented. We detect surface features, such as edge and corners, by computing local zero and first surface moments, using a robust and noise resistant method. The feature detection is encoded in a finite element matrix, passed to an algebraic multigrid (AMG) algorithm. The AMG algorithm generates a matrix hierarchy ranging from fine to coarse representations of the initial fine grid matrix. This hierarchy comes along with a corresponding multiscale of basis functions, which reflect the surface features on all hierarchy levels. We consider either these basis functions or distinct sets from an induced multiscale domain decomposition as handles for surface manipulation. We present a multiscale editor which enables Boolean operations on this domain decomposition and simply algebraic operations on the basis functions. Users can interactively design their favorite surface handles by simple grouping operations on the multiscale of domains. Several applications on large meshes underline the effectiveness and flexibility of the presented tool.     

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.     

运动曲面求交优化算法

运动曲面求交通常采用曲面求交算法，通过反复迭代求取曲面交线，没有考虑运动曲面自身的特性进行求交简化．由于运动曲面不同运动瞬间的曲面交线之间存在必然联系，因此通过对曲面内在属性分析，提出了运用运动曲面不同运动瞬间曲面交线相似性进行运动曲面求交的优化算法．首先对两个运动曲面的基曲面进行预处理。获取表征曲面交线拓扑的特征点；根据特征点分布图确定不同运动瞬间曲面交线起始点搜索策略，采用跟踪法动态调整步长和跟踪方向求解整个交线环．采用文中方法可以有效地解决运动曲面的子环、奇点遗漏、分支跳跃、乱序跟踪和初始点求取问题，精确、鲁棒、快速地计算出交线．     

Direct (Re)Meshing for Efficient Surface Processing

We propose a novel surface remeshing algorithm. While many remeshing algorithms are based on global parametrization or local mesh optimization, our algorithm is closely related to surface reconstruction techniques and it requires no explicit parameterization. Our approach is based on the advancing‐front paradigm, and it can be used to both incrementally remesh the complete surface, or simply to remesh a portion of it with a high‐quality mesh. It is accurate, fast, robust, and suitable for use with interactive mesh processing applications that require local remeshing. We show a number of applications, including matching the resolution of meshes when doing Boolean operations such as unions and intersections. We also show how to adapt the algorithm to blend and merge mixed‐mode objects — for example, to compute the union of a point‐set surface and a triangle mesh.     

Signed distance computation using the angle weighted pseudonormal

The normals of closed, smooth surfaces have long been used to determine whether a point is inside or outside such a surface. It is tempting to also use this method for polyhedra represented as triangle meshes. Unfortunately, this is not possible since, at the vertices and edges of a triangle mesh, the surface is not C/sup 1/ continuous, hence, the normal is undefined at these loci. In this paper, we undertake to show that the angle weighted pseudonormal (originally proposed by Thurmer and Wuthrich and independently by Sequin) has the important property that it allows us to discriminate between points that are inside and points that are outside a mesh, regardless of whether a mesh vertex, edge, or face is the closest feature. This inside-outside information is usually represented as the sign in the signed distance to the mesh. In effect, our result shows that this sign can be computed as an integral part of the distance computation. Moreover, it provides an additional argument in favor of the angle weighted pseudonormals being the natural extension of the face normals. Apart from the theoretical results, we also propose a simple and efficient algorithm for computing the signed distance to a closed C/sup 0/ mesh. Experiments indicate that the sign computation overhead when running this algorithm is almost negligible.     

On surface reconstruction: A priority driven approach

To reconstruct an object surface from a set of surface points, a fast, practical, and efficient priority driven algorithm is presented. The key idea of the method is to consider the shape changes of an object at the boundary of the mesh growing area and to create a priority queue to the advancing front of the mesh area according to the changes. The mesh growing process is then driven by the priority queue for efficient surface reconstruction. New and practical triangulation criteria are also developed to support the priority driven strategy and to construct a new triangle at each step of mesh growing in real time. The quality and correctness of the created triangles will be guaranteed by the triangulation criteria and topological operations. The algorithm can reconstruct an object surface from unorganized surface points in a fast and reliable manner. Moreover, it can successfully construct the surface of the objects with complex geometry or topology. The efficiency and robustness of the proposed algorithm is validated by extensive experiments.