Blowing Bubbles for Multi-Scale Analysis and Decomposition of Triangle Meshes

Tools for the automatic decomposition of a surface into shape features will facilitate the editing, matching, texturing, morphing, compression and simplification of three-dimensional shapes. Different features, such as flats, limbs, tips, pits and various blending shapes that transition between them, may be characterized in terms of local curvature and other differential properties of the surface or in terms of a global skeletal organization of the volume it encloses. Unfortunately, both solutions are extremely sensitive to small perturbations in surface smoothness and to quantization effects when they operate on triangulated surfaces. Thus, we propose a multi-resolution approach, which not only estimates the curvature of a vertex over neighborhoods of variable size, but also takes into account the topology of the surface in that neighborhood. Our approach is based on blowing a spherical bubble at each vertex and studying how the intersection of that bubble with the surface evolves. We describe an efficient approach for computing these characteristics for a sampled set of bubble radii and for using them to identify features, based on easily formulated filters, that may capture the needs of a particular application.     

Deformation similarity measurement in quasi-conformal shape space

This paper presents a novel approach based on the shape space concept to classify deformations of 3D models. A new quasi-conformal metric is introduced which measures the curvature changes at each vertex of each pose during the deformation. The shapes with similar deformation patterns follow a similar deformation curve in shape space. Energy functional of the deformation curve is minimized to calculate the geodesic curve connecting two shapes on the shape space manifold. The geodesic distance illustrates the similarity between two shapes, which is used to compute the similarity between the deformations. We applied our method to classify the left ventricle deformations of myopathic and control subjects, and the sensitivity and specificity of our method were 88.8% and 85.7%, which are higher than other methods based on the left ventricle cavity, which shows our method can quantify the similarity and disparity of the left ventricle motion well.     

结合拓扑持续性和热扩散理论的3维模型分割

目的 针对已有的3维模型分割方法人为设定过多参数的问题,提出了一种基于拓扑持续性和热亲和度矩阵的3维模型分割方法,只需给定分割部件数即可自动完成分割。方法 首先通过拓扑持续性处理3维模型的热核签名,选取生存期最长的几个特征点作为模型被分割部件的显著特征点,对于模型躯干等无法通过生长周期选取特征点的部件,则选取热核签名的最小值所对应的顶点作为显著特征点,从而获得模型的初始聚类中心;然后使用不同的扩散时间所对应的热亲和度矩阵进行k-means聚类,并根据聚类中心的偏移距离等参数筛选聚类结果,从而获得3维模型的分割结果。结果 选取人体模型进行分割实验,并与其他方法进行对比分析。结果表明,所提出的热亲和度的计算时间明显优于常用的测地距离和幂指数核;相比基于拓扑持续性和基于测地距离的聚类,本文方法可以正确分割模型的各个部件并获得恰当的分割边界。此外,本文方法针对姿态不同的同一非刚体3维模型可以取得一致性的分割结果,而且对模型表面噪声具有较好的鲁棒性。结论 和已有方法相比,本文的基于拓扑持续性和热亲和度矩阵的3维模型分割方法可以在给定分割部件的前提下自动选定聚类中心并获得恰当的分割边界,并广泛适用于常见动物模型的分割。     

具有特殊效果的混合细分方法

提出了基于三角形和四边形的混合控制网格的细分曲面尖锐特征、半尖锐特征生成和控制方法,避免了已有方法仅局限于初始控制网格为单一的三角形或单一的四边形网格的缺陷.通过局部修改混合细分规则,在光滑混合曲面上产生了刺、尖、折痕、角的尖锐特征效果,并对尖锐特征处局部细分矩阵进行了详细的特征分析,讨论了极限曲面的收敛性及光滑性.同时,用特征处的离散曲率来控制特征处的尖锐程度,实现了半尖锐的特征效果,并通过自适应细分方法,把尖锐特征、半尖锐特征的生成统一起来.该方法具有多分辨率表示能力强、局部性好、简单易操作的特点.实验结果表明,该算法效果好,成功地解决了混合曲面特殊效果生成问题.     

视觉特征保持的网格模型简化算法

针对二次误差测度算法存在几何特征消失等缺陷,提出了基于顶点视觉特 征度的新的网格模型简化算法。该算法采用半边折叠,通过引入顶点视觉特征度来优化了二 次误差测度,从而改变边折叠的顺序,使模型中的突出视觉特征更多的被保留下来。视觉特 征度通过顶点平均曲率熵来定义,它反映了顶点中心区域的视觉变化情况。实验表明,该算 法高效、可靠、能很好保持模型的视觉特征。     

Contour-driven Sumi-e rendering of real photos

We propose a sketch-based system for rendering oriental brush strokes on complex shapes. While previous research has focused on methods for converting user-specified trajectories into oriental ink painting (Sumi-e) strokes, we propose an approach that takes as input the contours of complex shapes, estimates automatically the sizes of the brush footprints, their orientations, and the brush trajectory. Then, it renders them into oriental ink paintings. The approach performs in three steps; first complex shapes are decomposed into elementary shapes that can be rendered with a single brush stroke. Second, the brush trajectory estimation is formulated as the minimization of an energy function that measures the quality of the trajectory. Finally, the estimated trajectories are rendered into brush strokes by mapping on them footprint textures scanned from real images. We demonstrate that the proposed contour-driven approach is particularly suitable for converting real images into Sumi-e paintings with minimum interaction. To this end we develop a system where images are either interactively or automatically segmented into elementary shapes and converted into Sumi-e paintings. For the automatic segmentation, we observe that the strokes in Sumi-e paintings are nearly parallel to the edge tangent flow (ETF). We propose a segmentation procedure that is based on clustering the curves obtained by integrating the ETF of real images. Experiments on complex shapes show that the proposed contour-based approach produces a large variety of complex strokes compared to trajectory-based approaches.     

Shape recognition based on Kernel-edit distance

In this paper a kernel method for shape recognition is proposed. The approach is based on the edit distance between pairs of shapes after transforming them into symbol strings. The transformation of shapes into symbol strings is invariant to similarity transforms and can handle partial occlusions. Representation of shape contours uses the shape contexts and applies dynamic programming for finding the correspondence between points over shape contours. Corresponding points are then transformed into symbolic representation and the normalized edit distance computes the dissimilarity between pairs of strings in the database. Obtained distances are then transformed into suitable kernels which are classified using support vector machines. Experimental results over a variety of shape databases show that the proposed approach is suitable for shape recognition.     

2D shape morphing via automatic feature matching and hierarchical interpolation

The paper presents a new method to interpolate a pair of 2D shapes that are represented by piecewise linear curves. The method addresses two key problems in 2D shape morphing process: feature correspondence and path interpolation. First, a robust feature metric is defined to measure the similarity of a pair of 2D shapes in terms of visual appearance, orientation and relative size. Based on the metric, an optimal problem is defined and solved to associate the features on the source shape with the corresponding ones on the target shape. Then, a two-level hierarchical approach is proposed to solve the corresponding features interpolation trajectory problem. The algorithm decomposes the input shapes into a pair of corresponding coarse polygons and several pairs of corresponding features. Then the corresponding coarse polygons are interpolated in an as-rigid-as-possible plausible way; meanwhile the corresponding features are interpolated using the intrinsic method. Thus interior distortions of the intermediate shapes could be avoided and the feature details on the input shapes could be well preserved. Experimental results show that the method can generate smooth, natural and visually pleasing 2D shape morphing effects.     

基于离散曲率的三角形折叠简化算法

以三角形折叠算法为基础，提出了一种新的基于离散曲率的三角网格简化算法。该算法以网格表面的加权离散曲率为依据，对三角形进行折叠操作，给出了基于离散曲率和球面近似的新顶点的获取方法。实验结果证明了本文算法的有效性。     

关节特征约束的3维模型骨架提取算法

根据多分辨率Reeb图（MRG）的原理,提出一种基于关节特征约束的骨架优化算法。它克服了基于曲率约束提取骨架方法中逐点计算顶点的曲率约束轮廓的低效性,通过分析网格顶点的离散高斯曲率,获取模型表面上具有凹陷特性的双曲极值点作为约束点, 进行关节特征区域的有效提取。进而增加关节特性点,优化MRG骨架。实验结果表明,本方法有效地突出了模型的拓扑分支特征以及模型表面的细节,提高了骨架提取的精度和效率。     

Two Simple Methods for Improving a Triangle Mesh Surface

We present two simple and efficient local methods that reposition vertices of a triangle mesh surface with the goal of producing good triangle shapes while preserving the enclosed volume and sharp features. The methods involve minimizing a quadratic energy functional with respect to variations in a tangent plane (or in the direction of a crease) at each free vertex. One of the methods is aimed at producing uniform angles, while the other method is designed to produce uniform triangle areas, or more generally, to force relative triangle areas to conform to curvature estimates or estimates of local feature size so that vertex density is low in flat spots and relatively high in regions of large curvature. Test results demonstrate the effectiveness of both methods, especially when combined.     

A new feature-preserving mesh-smoothing algorithm

We present a novel mesh denoising and smoothing method in this paper. Our approach starts by estimating the principal curvatures and mesh saliency value for each vertex. Then, we calculate the uniform principal curvature of each vertex based on the weighted average of local principal curvatures. After that, we use the weighted bi-quadratic Bézier surface to fit the neighborhood of each vertex using the least-square method and obtain the new vertex position by adjusting the parameters of the fitting surface. Experiments show that our smoothing method preserves the geometric feature of the original mesh model efficiently. Our approach also prevents the volume shrinkage of the input mesh and obtains smooth boundaries for non-closed mesh models.     

Shape transformation by boundary representation interpolation: A recursive approach to establishing face correspondences

The issues relating to the shape transformation problem are discussed and a new algorithm is presented for computing the transformation of one shape into another. In this algorithm, the boundary definitions of the two initial shapes are used and a mapping is established between the vertices and edges of the respective objects. New vertices and edges are introduced into the object definitions when necessary to establish a one-to-one vertex correspondence and to match connectivity relationships between vertices. These can then be used to do a vertex-to-vertex interpolation that maintains valid polyhedral topologies for all of the intermediate shapes. The algorithm establishes a mapping between areas of the object such that adjacency relationships are preserved. These areas are recursively subdivided so that adjacency relationships of subareas are also preserved. During subdivision, vertices and edges are added to the boundaries of subareas so that a one-to-one mapping is established between them. Subdivision continues until each subarea consists of a single face. The algorithm presented works for objects that are topologically equivalent to spheres and can easily be extended to other pairs of objects as long as they are topologically equivalent to each other.     

Shape feature control in structural topology optimization

A variational approach to shape feature control in topology optimization is presented in this paper. The method is based on a new class of surface energies known as higher-order energies as opposed to the conventional energies for problem regularization, which are linear. In employing a quadratic energy functional in the objective of the topology optimization, non-trivial interactions between different points on the structural boundary are introduced, thus favoring a family of shapes with strip-like (or beam) features. In addition, the quadratic energy functional can be seamlessly integrated into the level set framework that represents the geometry of the structure implicitly. The shape gradient of the quadratic energy functional is fully derived in the paper, and it is incorporated in the level set approach for topology optimization. The approach is demonstrated with benchmark examples of structure optimization and compliant mechanism design. The results presented show that this method is capable of generating strip-like (or beam) designs with specified feature width, which have highly desirable characteristics and practical benefits and uniquely distinguish the proposed method.     

基于视觉曲率估算的文物线图绘制方法

针对表面富含噪声的文物三维模型特征线的有效提取问题,分析了预处理阶段导致纹理细节丢失的原因,提出了一种基于视觉曲率估算的文物线图自动绘制方法。首先,对三角网格模型顶点的高度函数空间进行均匀采样,通过统计高度函数中极值点的个数,实现对模型顶点的视觉曲率估算;然后,根据多尺度约束下模型顶点的视觉曲率分布,将模型划分为平坦区域和特征区域;接着,依据考古领域均值对特征区域的顶点进行锐化滤波,计算出新的三角网格模型的顶点坐标;最后,对三角网格模型提取特征轮廓线,实现对文物线图的自动绘制。实验结果表明,基于视觉曲率的特征轮廓线在保留文物模型表面纹理细节的同时,有效避免了简单脊线/谷线法绘制线图呈现的尖锐现象。     

A dynamic balanced flow for filtering point-sampled geometry

3D point data acquisition has become a practical approach for generating complex 3D shapes. Subsequent smoothing or denoising operations on these raw data sets are required before performing sophisticated modeling operations. Based on covariance analysis and constructed directional curvature, a new approach of anisotropic curvature flow is developed for filtering the point data set. By introducing a forcing term, a balanced flow equation is constructed, which allows the anisotropic diffusion flow to be restricted in the flow diffusion band of the original surface. Thus, the common problem of shape shrinkage that puzzles most current denoising approaches for point-sampled geometry is avoided. Applying dynamic balance techniques, the equation converges to the solution quickly with appealing physical interpretations. The algorithms operate directly on the discrete sample points, requiring no vertex connectivity information. They are shown to be computationally efficient, robust and simple to implement.     

反向工程中三角网格的加工特征识别

为实现反向工程中的特征重构,提出一种在三角网格上由Morse-Smale复形转换为分割面属性邻接图进行加工特征提取的算法.首先通过移动最小二乘曲面法计算网格顶点曲率,构建曲率特性指标函数,消除因网格连接引起的误差,达到降噪的作用;然后在三角网格上建立和简化Morse-Smale复形,精确提取特征线,将网格分割为边界清晰连续的区域,并获得各区域的邻接关系;最后判断关键点和特征线的性质,将Morse-Smale复形直接转换为分割面属性邻接图进行加工特征识别.实验结果表明,该算法准确、高效,而且不需要人工干预,对于反向工程中大规模、带噪声的网格具有较好的识别效果.     

A Curvature and Density‐based Generative Representation of Shapes

This paper introduces a generative model for 3D surfaces based on a representation of shapes with mean curvature and metric, which are invariant under rigid transformation. Hence, compared with existing 3D machine learning frameworks, our model substantially reduces the influence of translation and rotation. In addition, the local structure of shapes will be more precisely captured, since the curvature is explicitly encoded in our model. Specifically, every surface is first conformally mapped to a canonical domain, such as a unit disk or a unit sphere. Then, it is represented by two functions: the mean curvature half‐density and the vertex density, over this canonical domain. Assuming that input shapes follow a certain distribution in a latent space, we use the variational autoencoder to learn the latent space representation. After the learning, we can generate variations of shapes by randomly sampling the distribution in the latent space. Surfaces with triangular meshes can be reconstructed from the generated data by applying isotropic remeshing and spin transformation, which is given by Dirac equation. We demonstrate the effectiveness of our model on datasets of man‐made and biological shapes and compare the results with other methods.     

Non-rigid 3D shape tracking from multiview video

We present a fast and efficient non-rigid shape tracking method for modeling dynamic 3D objects from multiview video. Starting from an initial mesh representation, the shape of a dynamic object is tracked over time, both in geometry and topology, based on multiview silhouette and 3D scene flow information. The mesh representation of each frame is obtained by deforming the mesh representation of the previous frame towards the optimal surface defined by the time-varying multiview silhouette information with the aid of 3D scene flow vectors. The whole time-varying shape is then represented as a mesh sequence which can efficiently be encoded in terms of restructuring and topological operations, and small-scale vertex displacements along with the initial model. The proposed method has the ability to deal with dynamic objects that may undergo non-rigid transformations and topological changes. The time-varying mesh representations of such non-rigid shapes, which are not necessarily of fixed connectivity, can successfully be tracked thanks to restructuring and topological operations employed in our deformation scheme. We demonstrate the performance of the proposed method both on real and synthetic sequences.