Shape Decomposition using Modal Analysis

We introduce a novel algorithm that decomposes a deformable shape into meaningful parts requiring only a single input pose. Using modal analysis, we are able to identify parts of the shape that tend to move rigidly. We define a deformation energy on the shape, enabling modal analysis to find the typical deformations of the shape. We then find a decomposition of the shape such that the typical deformations can be well approximated with deformation fields that are rigid in each part of the decomposition. We optimize for the best decomposition, which captures how the shape deforms. A hierarchical refinement scheme makes it possible to compute more detailed decompositions for some parts of the shape.
Although our algorithm does not require user intervention, it is possible to control the process by directly changing the deformation energy, or interactively refining the decomposition as necessary. Due to the construction of the energy function and the properties of modal analysis, the computed decompositions are robust to changes in pose as well as meshing, noise, and even imperfections such as small holes in the surface.     

Planar Shape Detection and Regularization in Tandem

We present a method for planar shape detection and regularization from raw point sets. The geometric modelling and processing of man‐made environments from measurement data often relies upon robust detection of planar primitive shapes. In addition, the detection and reinforcement of regularities between planar parts is a means to increase resilience to missing or defect‐laden data as well as to reduce the complexity of models and algorithms down the modelling pipeline. The main novelty behind our method is to perform detection and regularization in tandem. We first sample a sparse set of seeds uniformly on the input point set, and then perform in parallel shape detection through region growing, interleaved with regularization through detection and reinforcement of regular relationships (coplanar, parallel and orthogonal). In addition to addressing the end goal of regularization, such reinforcement also improves data fitting and provides guidance for clustering small parts into larger planar parts. We evaluate our approach against a wide range of inputs and under four criteria: geometric fidelity, coverage, regularity and running times. Our approach compares well with available implementations such as the efficient random sample consensus–based approach proposed by Schnabel and co‐authors in 2007.     

Fair webs

Fair webs are energy-minimizing curve networks. Obtained via an extension of cubic splines or splines in tension to networks of curves, they are efficiently computable and possess a variety of interesting applications. We present properties of fair webs and their discrete counterparts, i.e., fair polygon networks. Applications of fair curve and polygon networks include fair surface design and approximation under constraints such as obstacle avoidance or guaranteed error bounds, aesthetic remeshing, parameterization and texture mapping, and surface restoration in geometric models.     

Kinematic analysis of spatial fixed-axis higher pairs using configuration spaces

We present a kinematic analysis algorithm for spatial higher pairs whose parts rotate around or translate along fixed spatial axes. The part geometry is specified in a parametric boundary representation consisting of planar, cylindrical, and spherical patches bounded by line and circle segments. Kinematic analysis is performed by configuration space construction following the method that we developed for planar pairs. The configuration space of a pair is a complete encoding of its kinematics, including contact constraints, contact changes, and part motions. The algorithm constructs contact curves for all pairs of part features, computes the induced configuration space partition, and identifies the free space components. Spatial contact analysis is far harder than planar analysis because there are 72 types of contact versus 8. We have developed a systematic analysis technique and have used it to derive low-degree equations for all cases, which are readily solvable in closed form or numerically. We demonstrate the implemented algorithm on three design scenarios involving spatial pairs and planar pairs with axis misalignment.     

Barycentric Coordinates on Surfaces

This paper introduces a method for defining and efficiently computing barycentric coordinates with respect to polygons on general surfaces. Our construction is geared towards injective polygons (polygons that can be enclosed in a metric ball of an appropriate size) and is based on replacing the linear precision property of planar coordinates by a requirement in terms of center of mass, and generalizing this requirement to the surface setting. We show that the resulting surface barycentric coordinates can be computed using planar barycentric coordinates with respect to a polygon in the tangent plane. We prove theoretically that the surface coordinates properly generalize the planar coordinates and carry some of their useful properties such as unique reconstruction of a point given its coordinates, uniqueness for triangles, edge linearity, similarity invariance, and smoothness; in addition, these coordinates are insensitive to isometric deformations and can be used to reconstruct isometries. We show empirically that surface coordinates are shape‐aware with consistent gross behavior across different surfaces, are well‐behaved for different polygon types/locations on variety of surface forms, and that they are fast to compute. Finally, we demonstrate effectiveness of surface coordinates for interpolation, decal mapping, and correspondence refinement.     

带两个参数的三角多项式曲线曲面构造

目的 为了使扩展的曲线曲面保留传统Bézier方法以及B样条方法良好性质的同时,具备保形性、形状可调性、高阶连续性以及广泛的应用性,本文在拟扩展切比雪夫空间利用开花的性质构造了一组最优规范全正基,并利用该基进行曲线曲面构造。方法 首先构造一组最优规范全正基,并给出该基生成的拟三次TC-Bézier曲线的割角算法;接着利用最优规范全正基的线性组合构造拟三次均匀TC-B样条基,根据曲线的性质假设拟三次均匀B样条基函数具有规范性和C²连续性,进而得到其表达式;然后证明拟三次均匀TC-B样条基具有全正性和高阶连续性;最后定义拟三次均匀TC-B样条曲线曲面,并证明曲线曲面的性质,给出曲线表示整圆和旋转曲面的表示方法,设计出球面和旋转曲面的直接生成方法。结果 实验表明,本文在拟扩展切比雪夫空间构造的具有全正性曲线曲面,不仅能够灵活地进行形状调整,而且具有高阶连续性、保形性。结论 本文在三角函数空间利用两个形状参数进行曲线曲面构造,大量的分析以及案例说明本文构造的曲线曲面不仅保留了传统的Bézier方法以及B样条方法的良好性质,而且具备保形性、形状可调性、高阶连续性以及广泛的应用性,适合用于曲线曲面设计。     

一种新的平面开曲线形状距离的度量

平面曲线形状识别是最基本的模式识别问题，然而这个问题至今仍然未能很好地解决。其困难在于难以给出两条曲线的形状差别的定量描述。本文为基于曲率表示的两条平面开曲线的等形下了严格的数学定义，从而找到了一种新的形状距离度量，并且证明了这种形状距离的计算问题可以转化为一个泛函的极值问题，同时给出了求解形状距离的微分方程。由于解这个微分方程是困难的，实验中采用粗略的分段匹配法。本文还介绍了算法的程序实现，尤其是离散情况下的曲线的曲率表示，并且用基于动量守恒的高斯滤波解决了曲率法表示曲线的噪声敏感性问题。实验表明本文提出的形状距离度量方法是有效的。     

Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution

We concentrate here on decomposition of 2D objects into meaningfulparts of visual form, orvisual parts. It is a simple observation that convex parts of objects determine visual parts. However, the problem is that many significant visual parts are not convex, since a visual part may have concavities. We solve this problem by identifying convex parts at different stages of a proposed contour evolution method in which significant visual parts will become convex object parts at higher stages of the evolution. We obtain a novel rule for decomposition of 2D objects into visual parts, called the hierarchical convexity rule, which states that visual parts are enclosed by maximal convex (with respect to the object) boundary arcs at different stages of the contour evolution. This rule determines not only parts of boundary curves but directly the visual parts of objects. Moreover, the stages of the evolution hierarchy induce a hierarchical structure of the visual parts. The more advanced the stage of contour evolution, the more significant is the shape contribution of the obtained visual parts.     

CustomCut: On‐demand Extraction of Customized 3D Parts with 2D Sketches

Several applications in shape modeling and exploration require identification and extraction of a 3D shape part matching a 2D sketch. We present CustomCut, an on‐demand part extraction algorithm. Given a sketched query, CustomCut automatically retrieves partially matching shapes from a database, identifies the region optimally matching the query in each shape, and extracts this region to produce a customized part that can be used in various modeling applications. In contrast to earlier work on sketch‐based retrieval of predefined parts, our approach can extract arbitrary parts from input shapes and does not rely on a prior segmentation into semantic components. The method is based on a novel data structure for fast retrieval of partial matches: the randomized compound k‐NN graph built on multi‐view shape projections. We also employ a coarse‐to‐fine strategy to progressively refine part boundaries down to the level of individual faces. Experimental results indicate that our approach provides an intuitive and easy means to extract customized parts from a shape database, and significantly expands the design space for the user. We demonstrate several applications of our method to shape design and exploration.     

Discovery of Intrinsic Primitives on Triangle Meshes

The discovery of meaningful parts of a shape is required for many geometry processing applications, such as parameterization, shape correspondence, and animation. It is natural to consider primitives such as spheres, cylinders and cones as the building blocks of shapes, and thus to discover parts by fitting such primitives to a given surface. This approach, however, will break down if primitive parts have undergone almost‐isometric deformations, as is the case, for example, for articulated human models. We suggest that parts can be discovered instead by finding intrinsic primitives, which we define as parts that posses an approximate intrinsic symmetry. We employ the recently‐developed method of computing discrete approximate Killing vector fields (AKVFs) to discover intrinsic primitives by investigating the relationship between the AKVFs of a composite object and the AKVFs of its parts. We show how to leverage this relationship with a standard clustering method to extract k intrinsic primitives and remaining asymmetric parts of a shape for a given k. We demonstrate the value of this approach for identifying the prominent symmetry generators of the parts of a given shape. Additionally, we show how our method can be modified slightly to segment an entire surface without marking asymmetric connecting regions and compare this approach to state‐of‐the‐art methods using the Princeton Segmentation Benchmark.     

CAD模型表面区域分割方法

三维模型表面区域分割技术在形状分析,尤其是局部形状分析中具有重要作用,传统的表面分割方法主要针对网格模型,而机械工程中的CAD模型通常用B-rep表达.提出一种B-rep形式的CAD模型表面区域分割方法,将模型表面划分为局部凸区域、凹区域和平区域的组合,并使得分割后的区域数量最少.为提高计算效率,提出一种二步法:首先在模型面的局部凸凹性分析的基础上,快速地将模型表面分割成初始的凸区域、凹区域和平区域;然后通过区域合并的方法对分割后的区域进行组合优化,得到一个最优的分割结果.实验结果证明,该方法能有效地分割模型的表面区域.     

Prior Knowledge for Part Correspondence

Classical approaches to shape correspondence base their computation purely on the properties, in particular geometric similarity, of the shapes in question. Their performance still falls far short of that of humans in challenging cases where corresponding shape parts may differ significantly in geometry or even topology. We stipulate that in these cases, shape correspondence by humans involves recognition of the shape parts where prior knowledge on the parts would play a more dominant role than geometric similarity. We introduce an approach to part correspondence which incorporates prior knowledge imparted by a training set of pre‐segmented, labeled models and combines the knowledge with content‐driven analysis based on geometric similarity between the matched shapes. First, the prior knowledge is learned from the training set in the form of per‐label classifiers. Next, given two query shapes to be matched, we apply the classifiers to assign a probabilistic label to each shape face. Finally, by means of a joint labeling scheme, the probabilistic labels are used synergistically with pairwise assignments derived from geometric similarity to provide the resulting part correspondence. We show that the incorporation of knowledge is especially effective in dealing with shapes exhibiting large intra‐class variations. We also show that combining knowledge and content analyses outperforms approaches guided by either attribute alone.     

Shape preserving interpolation by space curves

Shape preserving interpolation for planar data has been well studied while little has been done for shape preserving curve interpolation in space. We consider some criteria for shape preserving interpolation by space curves: convexity and inflections of the projections of the curve onto certain planes, the sign of the torsion, coplanarity and collinearity. Based upon these criteria we then derive an algorithm for interpolating given points in space with a shape preserving piecewise rational cubic curve. The scheme is local and produces curves which are unit tangent continuous and also continuous in curvature magnitude apart from some exceptional cases where the curve contains linear segments. We illustrate the scheme with some graphical examples.     

Real‐Time Symmetry‐Preserving Deformation

In this paper, we address the problem of structure‐aware shape deformation: We specifically consider deformations that preserve symmetries of the shape being edited. While this is an elegant approach for obtaining plausible shape variations from minimal assumptions, a straightforward optimization is numerically expensive and poorly conditioned. Our paper introduces an explicit construction of bases of linear spaces of shape deformations that exactly preserve symmetries for any user‐defined level of detail. This permits the construction of low‐dimensional spaces of low‐frequency deformations that preserve the symmetries. We obtain substantial speed‐ups over alternative approaches for symmetry‐preserving shape editing due to (i) the sub‐space approach, which permits low‐res editing, (ii) the removal of redundant, symmetric information, and (iii) the simplification of the numerical formulation due to hard‐coded symmetry preservation. We demonstrate the utility in practice by applying our framework to symmetry‐preserving co‐rotated iterative Laplace surface editing of models with complex symmetry structure, including partial and nested symmetry.     

Part-whole relationship categories and their application inobject-oriented analysis

Part decomposition and conversely, the construction of composite objects from individual parts have long been recognized as ubiquitous and essential mechanisms involving abstraction. This applies, in particular, in areas such as CAD, manufacturing, software development and computer graphics. Although the part-of relationship is distinguished in object oriented modeling techniques, it ranks far behind the concept of generalization/specialization and a rigorous definition of its semantics is still missing. We first show in which ways a shift in emphasis on the part-of relationship leads to analysis and design models that are easier to understand and to maintain. We then investigate the properties of part-of relationships in order to define their semantics. This is achieved by means of a categorization of part-of relationships and by associating semantic constraints with individual categories. We further suggest a precise and, compared with existing techniques, less redundant specification of constraints accompanying part-of categories based on the degree of exclusiveness and dependence of parts on composite objects. Although the approach appears generally applicable, the object oriented Unified Modeling Language (UMF) is used to present our findings. Several examples demonstrate the applicability of the categories introduced     

Estimation of orientation of a textured planar surface using projective equations and separable analysis with M-channel wavelet decomposition

Estimation of the orientation of a textured planar surface is one of the basic tasks in the area of “shape from texture”. For the solution of this task, many successful approaches were proposed. In this paper, we have examined a few unaddressed questions: First, is there a mathematical formulation that relates the spectral characteristics of the texture pattern and the orientation of an inclined planar surface in a polar-coordinate system? Second, is there a good wavelet-based approach that produces an accurate estimate of the orientation angle of the textured planar surface by analyzing the spectral behavior of one single uncalibrated image?To answer these questions at first we present the formulation of a “texture projective equation”, which relates the depth and orientation of an inclined planar surface in a polar coordinate system with the spectral properties of its image texture. A suitable imaging geometry has been considered to enable separable analysis of the effect of inclination of the texture surface. Next, a method for shape from texture is presented based on discrete wavelet analysis to estimate the orientation of the planar surface. This approach although designed mainly for M-channel wavelets, is also applicable for dyadic wavelet analysis. Texture characteristics in the subbands of wavelet decomposition are analyzed using scalograms, and quantitatively evaluated based on texture projective equations. The proposed method of estimation of the orientation of a planar texture surface is evaluated using a set of simulated and real world textured images.     

A Projective Framework for Polyhedral Mesh Modelling

We present a novel framework for polyhedral mesh editing with face‐based projective maps that preserves planarity by definition. Such meshes are essential in the field of architectural design and rationalization. By using homogeneous coordinates to describe vertices, we can parametrize the entire shape space of planar‐preserving deformations with bilinear equations. The generality of this space allows for polyhedral geometric processing methods to be conducted with ease. We demonstrate its usefulness in planar‐quadrilateral mesh subdivision, a resulting multi‐resolution editing algorithm, and novel shape‐space exploration with prescribed transformations. Furthermore, we show that our shape space is a discretization of a continuous space of conjugate‐preserving projective transformation fields on surfaces. Our shape space directly addresses planar‐quad meshes, on which we put a focus, and we further show that our framework naturally extends to meshes with faces of more than four vertices as well.     

带局部形状参数的三次均匀B样条曲线的扩展

带形状参数的B样条曲线的构造已成为计算机辅助几何设计中的热点问题.为了使形状参数具有局部修改功能,给出了两类带局部形状参数的调配函数,它们都是三次均匀B样条基函数的扩展.基于给出的调配函数,定义了两种带局部形状参数的分段多项式曲线.可以通过改变局部形状参数的取值对曲线进行局部调整.调整形状参数可使三次多项式曲线在三次均匀B样条曲线远离控制多边形的一侧摆动,而四次多项式曲线在三次均匀B样条曲线的两侧摆动.最后讨论了它们在曲线设计及曲线插值中的应用.造型实例表明,该类曲线在计算机辅助几何设计中具有重要的应用价值.     

Packable Springs

Laser cutting is an appealing fabrication process due to the low cost of materials and extremely fast fabrication. However, the design space afforded by laser cutting is limited, since only flat panels can be cut. Previous methods for manufacturing from flat sheets usually roughly approximate 3D objects by polyhedrons or cross sections. Computational design methods for connecting, interlocking, or folding several laser cut panels have been introduced; to obtain a good approximation, these methods require numerous parts and long assembly times. In this paper, we propose a radically different approach: Our approximation is based on cutting thin, planar spirals out of flat panels. When such spirals are pulled apart, they take on the shape of a 3D spring whose contours are similar to the input object. We devise an optimization problem that aims to minimize the number of required parts, thus reducing costs and fabrication time, while at the same time ensuring that the resulting spring mimics the shape of the original object. In addition to rapid fabrication and assembly, our method enables compact packaging and storage as flat parts. We also demonstrate its use for creating armatures for sculptures and moulds for filling, with potential applications in architecture or construction.     

WireWarping: A fast surface flattening approach with length-preserved feature curves

This paper presents a novel approach — WireWarping for computing a flattened planar piece with length-preserved feature curves from a 3D piecewise linear surface patch. The property of length-preservation on feature curves is very important to industrial applications for controlling the shape and dimension of products fabricated from planar pieces. WireWarping simulates warping a given 3D surface patch onto plane with the feature curves as tendon wires to preserve the length of their edges. During warping, the surface-angle variations between edges on wires are minimized so that the shape of a planar piece is similar to its corresponding 3D patch. Two schemes — the progressive warping and the global warping schemes are developed, where the progressive scheme is flexible for local shape control and the global scheme gives good performance on highly distorted patches. Experimental results show that WireWarping can successfully flatten surface patches into planar pieces while preserving the length of edges on feature curves.