基于边界曲线演化模型的生长骨架算法

基于距离变换的骨架算法往往不能直接用于骨架识别，且骨架的连通性难以保证.本文提出一种新型的骨架算法，由一个初始骨架点开始逐点生长出各骨架分支，同时在骨架生长过程中用离散曲线演化模型消除造成信息冗余的骨架枝，保留视觉上重要的骨架枝，实现了骨架的多尺度控制,实验证明本算法复杂度低，得到的骨架连通性得到保证，能较好地表示图形中视觉重要成分，符合人类视觉习惯，可直接用于图形识别和形状度量.     

Part‐type Segmentation of Articulated Voxel‐Shapes using the Junction Rule

We present a part‐type segmentation method for articulated voxel‐shapes based on curve skeletons. Shapes are considered to consist of several simpler, intersecting shapes. Our method is based on the junction rule: the observation that two intersecting shapes generate an additional junction in their joined curve‐skeleton near the place of intersection. For each curve‐skeleton point, we construct a piecewise‐geodesic loop on the shape surface. Starting from the junctions, we search along the curve skeleton for points whose associated loops make for suitable part cuts. The segmentations are robust to noise and discretization artifacts, because the curve skeletonization incorporates a single user‐parameter to filter spurious curve‐skeleton branches. Furthermore, segment borders are smooth and minimally twisting by construction. We demonstrate our method on several real‐world examples and compare it to existing part‐type segmentation methods.     

Consistent Volumetric Discretizations Inside Self‐Intersecting Surfaces

Decades of research have culminated in a robust geometry processing pipeline for surfaces. Most steps in this pipeline, like deformation, smoothing, subdivision and decimation, may create self‐intersections. Volumetric processing of solid shapes then becomes difficult, because obtaining a correct volumetric discretization is impossible: existing tet‐meshing methods require watertight input. We propose an algorithm that produces a tetrahedral mesh that overlaps itself consistently with the self‐intersections in the input surface. This enables volumetric processing on self‐intersecting models. We leverage conformalized mean‐curvature flow, which removes self‐intersections, and define an intrinsically similar reverse flow, which prevents them. We tetrahedralize the resulting surface and map the mesh inside the original surface. We demonstrate the effectiveness of our method with applications to automatic skinning weight computation, physically based simulation and geodesic distance computation.     

基于曲面拟合的三角形网格简化

针对有限元网格简化问题,将边折叠和三角形折叠算法相结合,提出一种基于曲面拟合的网格简化方法。根据节点离散度识别网格特征,对具有不同特征的部位采用不同的简化策略从而实现自适应变密度网格简化。按长高比最优原则对合并后的节点进行预测,运用曲面拟合技术最终确定合并后的节点,达到优化网格和保持网格特征的目的。实验结果证明,该方法能在保证网格质量的前提下有效简化网格模型,提高CAE分析速度,最多可缩短75%的计算时间。     

Effective Piecewise Linear Skeletonization of Sparse Shapes

Conventional image skeletonization techniques implicitly assume the pixel level connectivity. However, noise inside the object regions destroys the connectivity and exhibits sparseness in the image. We present a skeletonization algorithm designed for these kinds of sparse shapes. The skeletons are produced quickly by using three operations. First, initial skeleton nodes are selected by farthest point sampling with circles containing the maximum effective information. A skeleton graph of these nodes is imposed via inheriting the neighborhood of their associated pixels, followed by an edge collapse operation. Then a skeleton tting process based on feature-preserving Laplacian smoothing is applied. Finally, a re nement step is proposed to further improve the quality of the skeleton and deal with noise or different local shape scales. Numerous experiments demonstrate that our algorithm can effectively handle several disconnected shapes in an image simultaneously, and generate more faithful skeletons for shapes with intersections or different local scales than classic methods.     

Hierarchical Deformation of Locally Rigid Meshes

We propose a method for calculating deformations of models by deforming a low‐resolution mesh and adding details while ensuring that the details we add satisfy a set of constraints. Our method builds a low‐resolution representation of a mesh by using edge collapses and performs an as‐rigid‐as‐possible deformation on the simplified mesh. We then add back details by reversing edge‐collapses so that the shape of the mesh is locally preserved. While adding details, we deform the mesh to match the predicted positions of constraints so that constraints on the full‐resolution mesh are met. Our method operates on meshes with arbitrary triangulations, satisfies constraints over the full‐resolution mesh and converges quickly.     

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.     

Simplifying curve skeletons in volume images

The curve skeleton of a 3D solid object provides a useful tool for shape analysis tasks. In this paper, we use a recent skeletonization algorithm based on voxel classification that originates a nearly thin, i.e., at most two-voxel thick, curve skeleton. We introduce a novel way to compress the nearly thin curve skeleton to one-voxel thickness, as well as an efficient pruning algorithm able to remove unnecessary skeleton branches without causing excessive loss of information. To this purpose, the pruning condition is based on the distribution of significant elements along skeleton branches. The definition of significance depends on the adopted skeletonization algorithm. In our case, it is derived from the voxel classification used during skeletonization.     

Discrete Distortion in Triangulated 3‐Manifolds

We introduce a novel notion, that we call discrete distortion, for a triangulated 3‐manifold. Discrete distortion naturally generalizes the notion of concentrated curvature defined for triangulated surfaces and provides a powerful tool to understand the local geometry and topology of 3‐manifolds. Discrete distortion can be viewed as a discrete approach to Ricci curvature for singular flat manifolds. We distinguish between two kinds of distortion, namely, vertex distortion, which is associated with the vertices of the tetrahedral mesh decomposing the 3‐manifold, and bond distortion, which is associated with the edges of the tetrahedral mesh. We investigate properties of vertex and bond distortions. As an example, we visualize vertex distortion on manifold hypersurfaces in R⁴ defined by a scalar field on a 3D mesh. distance fields.     

Curve skeleton extraction by coupled graph contraction and surface clustering

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first construct an initial skeleton graph by directly copying the connectivity and geometry information from the input mesh. Graph contraction and surface clustering are then performed iteratively. The former merges certain graph nodes based on computation of an approximate centroidal Voronoi diagram, seeded by subsampling the graph nodes from the previous iteration. Meanwhile, a coupled surface clustering process serves to regularize the graph contraction. Constraints are used to ensure that extremities of the graph are not shortened undesirably, to ensure that skeleton has the correct topological structure, and that surface clustering leads to an approximately-centered skeleton of the input shape. These properties lead to a stable and reliable skeleton graph construction algorithm.Experiments demonstrate that our skeleton extraction algorithm satisfies various desirable criteria. Firstly, it produces a skeleton homotopic with the input (the genus of both shapes agree) which is both robust (results are stable with respect to noise and remeshing of the input shape) and reliable (every boundary point is visible from at least one curve-skeleton location). It can also handle point cloud data if we first build an initial skeleton graph based on k-nearest neighbors. In addition, a secondary output of our algorithm is a skeleton-to-surface mapping, which can e.g. be used directly for skinning animation.Highlights(1) An algorithm for curve skeleton extraction from 3D shapes based on coupled graph contraction and surface clustering. (2) The algorithm meets various desirable criteria and can be extended to work for incomplete point clouds.     

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.     

Skeleton‐driven Adaptive Hexahedral Meshing of Tubular Shapes

We propose a novel method for the automatic generation of structured hexahedral meshes of articulated 3D shapes. We recast the complex problem of generating the connectivity of a hexahedral mesh of a general shape into the simpler problem of generating the connectivity of a tubular structure derived from its curve‐skeleton. We also provide volumetric subdivision schemes to nicely adapt the topology of the mesh to the local thickness of tubes, while regularizing per‐element size. Our method is fast, one‐click, easy to reproduce, and it generates structured meshes that better align to the branching structure of the input shape if compared to previous methods for hexa mesh generation.     

Approximate on‐Surface Distance Computation using Quasi‐Developable Charts

There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.     

基于凸壳与有向包围盒的骨架提取方法

为获取三维模型的几何及拓扑信息,提出一种基于凸壳与有向包围盒(OBB)的线性骨架提取方法.首先将三维网格模型进行分割生成多个子网格模型;然后对各子网格中的点集求取凸壳作为该子网格点集的近似,由凸壳顶点的形心构成原始骨架点;再用OBB进行重叠计算求出相交点集,以生成关节骨架点;最后对原始骨架点与关节骨架点进行连接,经冗余检测后形成完整骨架.实验结果表明,该方法快速、有效,提取出的骨架能保证连通性与中心性且能很好地提取关节骨架点,为蒙皮关节动画、模型形状分析等提供有效信息.     

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.     

Feature Sensitive Remeshing

Remeshing artifacts are a fundamental problem when converting a given geometry into a triangle mesh. We propose a new remeshing technique that is sensitive to features. First, the resolution of the mesh is iteratively adapted by a global restructuring process which additionally optimizes the connectivity. Then a particle system approach evenly distributes the vertices across the original geometry. To exactly find the features we extend this relaxation procedure by an effective mechanism to attract the vertices to feature edges. The attracting force is imposed by means of a hierarchical curvature field and does not require any thresholding parameters to classify the features.     

Detection of Salient Curvature Features on Polygonal Surfaces

We develop an approach for stable detection of perceptually salient curvature features on surfaces approximated by dense triangle meshes. The approach explores an "area degenerating" effect of the focal surface near its singularities and combines together a new approximations of the mean and Gaussian curvatures, nonlinear averaging of curvature maps, histogram-based curvature extrema filtering, and an image processing skeletonization procedure adapted for triangular meshes. Finally we use perceptually significant curvature extrema triangles to enhance the Garland-Heckbert mesh decimation method.     

利用模板和邻域信息的静脉骨架提取新算法

为提高骨架提取的准确性和连通性,提出了一种利用模板和邻域信息的静脉骨架提取新算法,该算法首先对二值图像进行平滑,并通过自适应方法计算静脉纹路上所有像素点邻域之和,以快速区分出边缘点和中轴点,然后遍历图像找出所有符合中轴点模板的像素点,并删除其中的孤立中轴点之后,得到一些间断的中轴线段,最后从这些中轴线段的端点开始采用最大邻域点跟踪方法提取出静脉骨架。实验结果表明,该算法提取的静脉骨架与中轴线重合且平滑稳定,且具有尺度不变性,角度不变性和良好的抗噪性能,是一种有效的骨架提取算法。