Patch‐type Segmentation of Voxel Shapes using Simplified Surface Skeletons

We present a new method for decomposing a 3D voxel shape into disjoint segments using the shape's simplified surface‐skeleton. The surface skeleton of a shape consists of 2D manifolds inside its volume. Each skeleton point has a maximally inscribed ball that touches the boundary in at least two contact points. A key observation is that the boundaries of the simplified fore‐ and background skeletons map one‐to‐one to increasingly fuzzy, soft convex, respectively concave, edges of the shape. Using this property, we build a method for segmentation of 3D shapes which has several desirable properties. Our method segments both noisy shapes and shapes with soft edges which vanish over low‐curvature regions. Multiscale segmentations can be obtained by varying the simplification level of the skeleton. We present a voxel‐based implementation of our approach and illustrate it on several realistic examples.     

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.     

骨架驱动的三维模型变形方法

为发展三维网格模型的变形技术,研究了多种三维模型变形算法,通过对骨架驱动变形算法的深入研究,针对现行算法多是以单一骨架驱动变形的不足,提出了一种新的基于多骨架点驱动的交互式局部变形方法.有效结合模型的骨架图结构,确定各骨架点对应的局部区域.并将骨架点拟合为二次Bézier曲线,通过交互式拖动任意骨架点计算与之相连的多骨架点的动态变化,实现模型局部区域的自然形变.实验结果表明了该算法的有效性和直观性.     

B‐Mesh: A Modeling System for Base Meshes of 3D Articulated Shapes

This paper presents a novel modeling system, called B‐Mesh, for generating base meshes of 3D articulated shapes. The user only needs to draw a one‐dimensional skeleton and to specify key balls at the skeletal nodes. The system then automatically generates a quad dominant initial mesh. Further subdivision and evolution are performed to refine the initial mesh and generate a quad mesh which has good edge flow along the skeleton directions. The user can also modify and manipulate the shape by editing the skeleton and the key balls and can easily compose new shapes by cutting and pasting existing models in our system. The mesh models generated in our system greatly benefit the sculpting operators for sculpting modeling and skeleton‐based animation.     

Hierarchical part-type segmentation using voxel-based curve skeletons

We present an effective framework for segmenting 3D shapes into meaningful components using the curve skeleton. Our algorithm identifies a number of critical points on the efficiently computed curve skeleton, either fully automatically as the junctions of the curve skeleton, or based on user input. We use these points to construct a partitioning of the object surface using geodesics. Because the segmentation is based on the curve skeleton, it intrinsically reflects the shape symmetry and articulation, and can handle shapes with tunnels. We describe a voxel-based implementation of our method which is robust and noise resistant, able to handle shapes of complex articulation and topology, produces smooth segment borders, and delivers hierarchical level-of-detail segmentations. We demonstrate the framework on various real-world 3D shapes. Additionally, we discuss the use of both curve and surface skeletons to produce part-type and patch-type, respectively, segmentations of 3D shapes.     

Skeleton‐Intrinsic Symmetrization of Shapes

Enhancing the self‐symmetry of a shape is of fundamental aesthetic virtue. In this paper, we are interested in recovering the aesthetics of intrinsic reflection symmetries, where an asymmetric shape is symmetrized while keeping its general pose and perceived dynamics. The key challenge to intrinsic symmetrization is that the input shape has only approximate reflection symmetries, possibly far from perfect. The main premise of our work is that curve skeletons provide a concise and effective shape abstraction for analyzing approximate intrinsic symmetries as well as symmetrization. By measuring intrinsic distances over a curve skeleton for symmetry analysis, symmetrizing the skeleton, and then propagating the symmetrization from skeleton to shape, our approach to shape symmetrization is skeleton‐intrinsic. Specifically, given an input shape and an extracted curve skeleton, we introduce the notion of a backbone as the path in the skeleton graph about which a self‐matching of the input shape is optimal. We define an objective function for the reflective self‐matching and develop an algorithm based on genetic programming to solve the global search problem for the backbone. The extracted backbone then guides the symmetrization of the skeleton, which in turn, guides the symmetrization of the whole shape. We show numerous intrinsic symmetrization results of hand drawn sketches and artist‐modeled or reconstructed 3D shapes, as well as several applications of skeleton‐intrinsic symmetrization of shapes.     

Skeleton-based intrinsic symmetry detection on point clouds

We present a skeleton-based algorithm for intrinsic symmetry detection on imperfect 3D point cloud data. The data imperfections such as noise and incompleteness make it difficult to reliably compute geodesic distances, which play essential roles in existing intrinsic symmetry detection algorithms. In this paper, we leverage recent advances in curve skeleton extraction from point clouds for symmetry detection. Our method exploits the properties of curve skeletons, such as homotopy to the input shape, approximate isometry-invariance, and skeleton-to-surface mapping, for the detection task. Starting from a curve skeleton extracted from an input point cloud, we first compute symmetry electors, each of which is composed of a set of skeleton node pairs pruned with a cascade of symmetry filters. The electors are used to vote for symmetric node pairs indicating the symmetry map on the skeleton. A symmetry correspondence matrix (SCM) is constructed for the input point cloud through transferring the symmetry map from skeleton to point cloud. The final symmetry regions on the point cloud are detected via spectral analysis over the SCM. Experiments on raw point clouds, captured by a 3D scanner or the Microsoft Kinect, demonstrate the robustness of our algorithm. We also apply our method to repair incomplete scans based on the detected intrinsic symmetries.     

Automatic 3D Shape Co-Segmentation Using Spectral Graph Method

Co-analyzing a set of 3D shapes is a challenging task considering a large geometrical variability of the shapes. To address this challenge, this paper proposes a new automatic 3D shape co-segmentation algorithm by using spectral graph method.Our method firstly represents input shapes as a set of weighted graphs and extracts multiple geometric features to measure the similarities of faces in each individual shape.Secondly all graphs are embedded into the spectral domain to find meaningful correspondences across the set.After that we build a joint weighted matrix for the graph set and then apply normalized cut criterion to find optimal co-segmentation of the input shapes.Finally we evaluate our approach on different categories of 3D shapes, and the experimental results demonstrate that our method can accurately co-segment a wide variety of shapes, which may have different poses and significant topology changes.     

Fitting Sharp Features with Loop Subdivision Surfaces

Various methods have been proposed for fitting subdivision surfaces to different forms of shape data (e.g., dense meshes or point clouds), but none of these methods effectively deals with shapes with sharp features, that is, creases, darts and corners. We present an effective method for fitting a Loop subdivision surface to a dense triangle mesh with sharp features. Our contribution is a new exact evaluation scheme for the Loop subdivision with all types of sharp features, which enables us to compute a fitting Loop subdivision surface for shapes with sharp features in an optimization framework. With an initial control mesh obtained from simplifying the input dense mesh using QEM, our fitting algorithm employs an iterative method to solve a nonlinear least squares problem based on the squared distances from the input mesh vertices to the fitting subdivision surface. This optimization framework depends critically on the ability to express these distances as quadratic functions of control mesh vertices using our exact evaluation scheme near sharp features. Experimental results are presented to demonstrate the effectiveness of the method.     

边收缩池化的网格变分自编码器

目的 3D形状分析是计算机视觉和图形学的一个重要研究课题。虽然现有方法使用基于图的卷积将基于图像的深度学习推广到3维网格,但缺乏有效的池化操作限制了其网络的学习能力。针对具有相同连通性,但几何形状不同的网格模型数据集,本文利用网格简化的边收缩操作建立网格层次结构,提出了一种新的网格池化操作。方法 本文改进了传统的网格简化方法,以避免生成高度不规则的三角形,利用改进的网格简化方法定义了新的网格池化操作。网格简化的边收缩操作建立的网格层次结构之间存在对应关系,有利于网格池化的定义。新定义的池化操作有效地编码了层次结构中较粗糙和较稠密网格之间的对应关系。最后提出了一种带有边收缩池化和图卷积的变分自编码器（variational auto-encoder,VAE）结构,以探索3D形状的隐空间并用于3D形状的生成。结果 由于引入了新定义的池化操作和图卷积操作,提出的网络结构比原始MeshVAE需要的参数更少,因此可以处理更稠密的网格模型。结论 实验表明提出的方法具有更好的泛化能力,并且在各种应用中更可靠,包括形状生成、形状插值和形状嵌入。     

高效鲁棒三维结构化重建

目的结构化重建,即从离散点云或者原始三角网格中提取几何平面并将其拼接成紧凑的参数化3维模型,一直是计算机图形学领域中极具挑战性的问题。现有方法通常面临着两个挑战。一是传统的形状检测方法通常只考虑物体的局部特征,无法保证整体结果的准确性。二是现有的形状拼接算法往往受限于计算复杂度,从而只能处理由一百多个几何平面组成的物体,极大地限制了算法的应用场景。针对这些问题,提出了一种快速、鲁棒的结构化重建算法以自动地生成轻量的多边形网格。方法提出了一种多源区域增长算法,全局地从原始3维数据中提取特征平面。该策略保证了原始数据可以被正确地聚类到所属的平面区域。为了减轻几何平面分割3维空间带来的计算负担,采用了一种基于二叉空间分割树的结构将3维空间切分为凸多面体。提出了一种基于光线射击的马尔可夫能量方程以提取水密、无自相交的多边形网格。结果实验结果表明,本文方法可以在没有并行化方案的标准计算机上处理由上万个几何平面组成的物体。与传统的全相交分割相比,本文方法得到的多面体数目和运行时间都降低了至少两个数量级,总耗时可控制在5 s/万点以内。此外,模型化简前后的均方根误差平均控制在1%以内,面片化简比例控...     

Mean Curvature Skeletons

Inspired by recent developments in contraction‐based curve skeleton extraction, we formulate the skeletonization problem via mean curvature flow (MCF). While the classical application of MCF is surface fairing, we take advantage of its area‐minimizing characteristic to drive the curvature flow towards the extreme so as to collapse the input mesh geometry and obtain a skeletal structure. By analyzing the differential characteristics of the flow, we reveal that MCF locally increases shape anisotropy. This justifies the use of curvature motion for skeleton computation, and leads to the generation of what we call “mean curvature skeletons”. To obtain a stable and efficient discretization, we regularize the surface mesh by performing local remeshing via edge splits and collapses. Simplifying mesh connectivity throughout the motion leads to more efficient computation and avoids numerical instability arising from degeneracies in the triangulation. In addition, the detection of collapsed geometry is facilitated by working with simplified mesh connectivity and monitoring potential non‐manifold edge collapses. With topology simplified throughout the flow, minimal post‐processing is required to convert the collapsed geometry to a curve. Formulating skeletonization via MCF allows us to incorporate external energy terms easily, resulting in a constrained flow. We define one such energy term using the Voronoi medial skeleton and obtain a medially centred curve skeleton. We call the intermediate results of our skeletonization motion meso‐skeletons; these consist of a mixture of curves and surface sheets as appropriate to the local 3D geometry they capture.     

SkelTre

Terrestrial laser scanners capture 3D geometry of real world objects as a point cloud. This paper reports on a new algorithm developed for the skeletonization of a laser scanner point cloud. The skeletonization algorithm proposed in this paper consists of three steps: (i) extraction of a graph from an octree organization, (ii) reduction of the graph to a skeleton, and (iii) embedding of the skeleton into the point cloud. For these three steps, only one input parameter is required. The results are validated on laser scanner point clouds representing 2 classes of objects; first on botanic trees as a special application and secondly on popular arbitrary objects. The presented skeleton found its first application in obtaining botanic tree parameters like length and diameter of branches and is presented here in a new, generalized version. Its definition as Reeb Graph, proofs the usefulness of the skeleton for applications like shape analysis. In this paper we show that the resulting skeleton contains the Reeb Graph and investigate the practically relevant parameters: centeredness and topological correctness. The robustness of this skeletonization method against undersampling, varying point density and systematic errors of the point cloud is demonstrated on real data examples.     

基于曲率法线流的树点云骨架提取方法

针对树木点云拓扑结构复杂、特征细节繁多等问题,提出一种基于点云收缩提取曲线骨架的算法。首先,为了在点云表面直接应用网格收缩算法,对点云进行局部主成分分析和Delaunay三角剖分;其次,针对树木点云拓扑结构复杂和末枝细节繁多等问题,用曲率法线流算子对点云进行收缩,针对树木枝条细长且弯曲幅度平缓等特点,利用改进后的QEM网格简化方法将三角网格折叠成一维曲线骨架;最后,将得到的曲线骨架进行连通和居中处理。该算法直接在点云上进行操作,不需要额外的信息和预处理操作,对噪声和残缺点云有良好的鲁棒性。实验证明,该算法提取的树木点云骨架充分表达了树木在自然环境下的生物性结构和特征,相对于rosa、L1-中轴等经典算法,在树木点云的骨架提取速度上提高3倍以上,枝条重建度提高25%。     

The shape variational autoencoder: A deep generative model of part‐segmented 3D objects

We introduce a generative model of part‐segmented 3D objects: the shape variational auto‐encoder (ShapeVAE). The ShapeVAE describes a joint distribution over the existence of object parts, the locations of a dense set of surface points, and over surface normals associated with these points. Our model makes use of a deep encoder‐decoder architecture that leverages the part‐decomposability of 3D objects to embed high‐dimensional shape representations and sample novel instances. Given an input collection of part‐segmented objects with dense point correspondences the ShapeVAE is capable of synthesizing novel, realistic shapes, and by performing conditional inference enables imputation of missing parts or surface normals. In addition, by generating both points and surface normals, our model allows for the use of powerful surface‐reconstruction methods for mesh synthesis. We provide a quantitative evaluation of the ShapeVAE on shape‐completion and test‐set log‐likelihood tasks and demonstrate that the model performs favourably against strong baselines. We demonstrate qualitatively that the ShapeVAE produces plausible shape samples, and that it captures a semantically meaningful shape‐embedding. In addition we show that the ShapeVAE facilitates mesh reconstruction by sampling consistent surface normals.     

Efficient Homology-Preserving Simplification of High-Dimensional Simplicial Shapes

Simplicial complexes are widely used to discretize shapes. In low dimensions, a 3D shape is represented by discretizing its boundary surface, encoded as a triangle mesh, or by discretizing the enclosed volume, encoded as a tetrahedral mesh. High-dimensional simplicial complexes have recently found their application in topological data analysis. Topological data analysis aims at studying a point cloud P, possibly embedded in a high-dimensional metric space, by investigating the topological characteristics of the simplicial complexes built on P. Analysing such complexes is not feasible due to their size and dimensions. To this aim, the idea of simplifying a complex while preserving its topological features has been proposed in the literature. Here, we consider the problem of efficiently simplifying simplicial complexes in arbitrary dimensions. We provide a new definition for the edge contraction operator, based on a top-based data structure, with the objective of preserving structural aspects of a simplicial shape (i.e., its homology), and a new algorithm for verifying the link condition on a top-based representation. We implement the simplification algorithm obtained by coupling the new edge contraction and the link condition on a specific top-based data structure, that we use to demonstrate the scalability of our approach.     

On-the-fly Curve-skeleton Computation for 3D Shapes

The curve-skeleton of a 3D object is an abstract geometrical and topological representation of its 3D shape. It maps the spatial relation of geometrically meaningful parts to a graph structure. Each arc of this graph represents a part of the object with roughly constant diameter or thickness, and approximates its centerline. This makes the curve-skeleton suitable to describe and handle articulated objects such as characters for animation. We present an algorithm to extract such a skeleton on-the-fly, both from point clouds and polygonal meshes. The algorithm is based on a deformable model evolution that captures the object's volumetric shape. The deformable model involves multiple competing fronts which evolve inside the object in a coarse-to-fine manner. We first track these fronts' centers, and then merge and filter the resulting arcs to obtain a curve-skeleton of the object. The process inherits the robustness of the reconstruction technique, being able to cope with noisy input, intricate geometry and complex topology. It creates a natural segmentation of the object and computes a center curve for each segment while maintaining a full correspondence between the skeleton and the boundary of the object.