GWCNN: A Metric Alignment Layer for Deep Shape Analysis

Deep neural networks provide a promising tool for incorporating semantic information in geometry processing applications. Unlike image and video processing, however, geometry processing requires handling unstructured geometric data, and thus data representation becomes an important challenge in this framework. Existing approaches tackle this challenge by converting point clouds, meshes, or polygon soups into regular representations using, e.g., multi‐view images, volumetric grids or planar parameterizations. In each of these cases, geometric data representation is treated as a fixed pre‐process that is largely disconnected from the machine learning tool. In contrast, we propose to optimize for the geometric representation during the network learning process using a novel metric alignment layer. Our approach maps unstructured geometric data to a regular domain by minimizing the metric distortion of the map using the regularized Gromov–Wasserstein objective. This objective is parameterized by the metric of the target domain and is differentiable; thus, it can be easily incorporated into a deep network framework. Furthermore, the objective aims to align the metrics of the input and output domains, promoting consistent output for similar shapes. We show the effectiveness of our layer within a deep network trained for shape classification, demonstrating state‐of‐the‐art performance for nonrigid shapes.     

Constructing G 1 continuous curve on a free-form surface with normal projection

In this paper, we develop a new method for G ¹ continuous interpolation of an arbitrary sequence of points on an implicit or parametric surface with a specified tangent direction at every point. Based on the normal projection method, we design a G ¹ continuous curve in three-dimensional space and then project orthogonally the curves onto the given surface. With the techniques in classical differential geometry, we derive a system of differential equations characterizing the projection curve. The resulting interpolation curve is obtained by numerically solving the initial-value problems for a system of first-order ordinary differential equations in the parametric domain associated to the surface representation for a parametric case or in three-dimensional space for an implicit case. Several shape parameters are introduced into the resulting curve, which can be used in subsequent interactive modification such that the shape of the resulting curve meets our demand. The presented method is independent of the geometry and parameterization of the base surface, and numerical experiments demonstrate that it is effective and potentially useful in surface trim, robot, patterns design on surface and other industrial and research fields.     

Differential Representations for Mesh Processing

Surface representation and processing is one of the key topics in computer graphics and geometric modeling, since it greatly affects the range of possible applications. In this paper we will present recent advances in geometry processing that are related to the Laplacian processing framework and differential representations. This framework is based on linear operators defined on polygonal meshes, and furnishes a variety of processing applications, such as shape approximation and compact representation, mesh editing, watermarking and morphing. The core of the framework is the definition of differential coordinates and new bases for efficient mesh geometry representation, based on the mesh Laplacian operator.     

Fictitious domain method and separated representations for the solution of boundary value problems on uncertain parameterized domains

A tensor-based method is proposed for the solution of partial differential equations defined on uncertain parameterized domains. It provides an accurate solution which is explicit with respect to parameters defining the shape of the domain, thus allowing efficient a posteriori probabilistic or parametric analyses. In the proposed method, a fictitious domain approach is first adopted for the reformulation of the parametric problem on a fixed domain, yielding a weak formulation in a tensor product space (product of space functions and parametric functions). The paper is limited to the case of Neumann conditions on uncertain parts of the boundary. The Proper Generalized Decomposition method is then introduced for the construction of a tensor product approximation (separated representation) of the solution. It can be seen as an a priori model reduction technique which automatically captures reduced bases of space functions and parametric functions which are optimal for the representation of the solution. This tensor-based method is made computationally tractable by introducing separated representations of variational forms, resulting from separated representations of the parameterized indicator function of the uncertain domain. For this purpose, a method is proposed for the construction of a constrained tensor product approximation which preserves positivity and therefore ensures well-posedness of problems associated with approximate indicator functions. Moreover, a regularization of the geometry is introduced to speed up the convergence of these tensor product approximations.     

Constructing up to G 2 continuous curve on freeform surface

This paper presents new methods for G ¹ and G ² continuous interpolation of an arbitrary sequence of points on an implicit or parametric surface with prescribed tangent direction and both tangent direction and curvature vector, respectively, at every point. We design a G ¹ or G ² continuous curve in three-dimensional space, construct a so-called directrix vector field using the space curve and then project a special straight line segment onto the given surface along the directrix vector field. With the techniques in classical differential geometry, we derive a system of differential equations for the projection curve. The desired interpolation curve is just the projection curve, which can be obtained by numerically solving the initial-value problems for a system of first-order ordinary differential equations in the parametric domain associated to the surface representation for the parametric case or in three-dimensional space for the implicit case. Several shape parameters are introduced into the resulting curve, which can be used in subsequent interactive modification such that the shape of the resulting curve meets our demand. The presented method is independent of the geometry and parameterization of the base surface, and numerical experiments demonstrate that it is effective and potentially useful in patterns design on surface.     

Computational procedure for optimum shape design based on chained Bezier surfaces parameterization

Optimum design introduces strong emphasis on compact geometry parameterization in order to reduce the dimensionality of the search space and consequently optimization run-time. This paper develops a decision support system for optimum shape which integrates geometric knowledge acquisition using 3D scanning and evolutionary shape re-engineering by applying genetic-algorithm based optimum search within a distributed computing workflow.A shape knowledge representation and compaction method is developed by creating 2D and 3D parameterizations based on adaptive chaining of piecewise Bezier curves and surfaces. Low-degree patches are used with adaptive subdivision of the target domain, thereby preserving locality. C¹ inter-segment continuity is accomplished by generating additional control points without increasing the number of design variables. The control points positions are redistributed and compressed towards the sharp edges contained in the data-set for better representation of areas with sharp change in slopes and curvatures. The optimal decomposition of the points cloud or target surface into patches is based on the requested modeling accuracy, which works as lossy geometric data-set compression. The proposed method has advantages in non-recursive evaluation, possibility of chaining patches of different degrees, options of prescribing fixed values at selected intermediate points while maintaining C¹ continuity, and uncoupled processing of individual patches.The developed procedure executes external application nodes using mutual communication via native data files and data mining. This adaptive interdisciplinary workflow integrates different algorithms and programs (3D shape acquisition, representation of geometry with data-set compaction using parametric surfaces, geometric modeling, distributed evolutionary optimization) such that optimized shape solutions are synthesized. 2D and 3D test cases encompassing holes and sharp edges are provided to prove the capacity and respective performance of the developed parameterizations, and the resulting optimized shapes for different load cases demonstrate the functionality of the overall distributed workflow.     

3-D Symmetry Detection and Analysis Using the Pseudo-polar Fourier Transform

Symmetry detection and analysis in 3D images is a fundamental task in a gamut of scientific fields such as computer vision, medical imaging and pattern recognition to name a few. In this work, we present a computational approach to 3D symmetry detection and analysis. Our analysis is conducted in the Fourier domain using the pseudo-polar Fourier transform. The pseudo-polar representation enables to efficiently and accurately analyze angular volumetric properties such as rotational symmetries. Our algorithm is based on the analysis of the angular correspondence rate of the given volume and its rotated and rotated-inverted replicas in their pseudo-polar representations. We also derive a novel rigorous analysis of the inherent constraints of 3D symmetries via groups-theory based analysis. Thus, our algorithm starts by detecting the rotational symmetry group of a given volume, and the rigorous analysis results pave the way to detect the rest of the symmetries. The complexity of the algorithm is O(N ³log (N)), where N×N×N is the volumetric size in each direction. This complexity is independent of the number of the detected symmetries. We experimentally verified our approach by applying it to synthetic as well as real 3D objects.     

Geometry curves: A compact representation for 3D shapes

We propose a novel compact surface representation, namely geometry curves, which record the essence of shape geometry and topology. The geometry curves mainly contain two parts: the interior and boundary lines. The interior lines, which correspond to the feature lines, record the geometry information of the 3D shapes; the boundary lines, which correspond to the boundary or fundamental polygons, record the topology information of the 3D shapes. As a vector representation, geometry curves can depict highly complex geometry details. The concept of geometry curves can be utilized in many potential applications, e.g., mesh compression, shape modeling and editing, animation, and level of details. Furthermore, we develop a procedure for automatically constructing geometry curves which obtain an excellent approximation to the original mesh.     

Feature-based ontological framework for semantic interoperability in product development

An essential requirement in integrating tasks in product development is to have a seamless exchange of product information through the entire product lifecycle. A key challenge in the integration is the exchange of shape semantics in terms of understandable labels and representations. A unified taxonomy is proposed to represent, classify, and extract shape features. This taxonomy is built using the Domain-Independent Form Feature (DIFF) model as the representation of features. All the shape features in a product model are classified under three main classes, namely, volumetric features, deformation features and free-form surface features. Shape feature ontology is developed using the unified taxonomy, which brings the shape features under a single reasoning framework. One-to-many reasoning framework is presented for mapping semantically equivalent information (label and representation) of the feature to be exchanged to target applications, and the reconstruction of the shape model automatically in that target application. An algorithm has been developed to extract the semantics of shape features and construct the model in the target application. The algorithm developed has been tested for shape models taken from literature and test cases are selected based on variations of topology and geometry. Results of exchanging product information are presented and discussed. Finally, the limitations of the proposed method for exchanging product information are explained.     

Touch-based haptics for interactive editing on point set surfaces

A modeling paradigm for haptics-based editing on point set surfaces exploits implicit surfaces, physics-based modeling, point-sampled surfaces, and haptic. We propose a point-based geometry representation that we initially designed for dynamic physics-based sculpting, but can easily generalize to other relevant applications such as data modeling and human-computer interaction. By extending the idea of the local reference domain in the moving least square (MLS) surface model to the construction of a local and global surface distance field, we naturally incorporate Hua and Qin's dynamic implicit volumetric model into our deformation of the point-based geometry, which not only facilitates topology change but also affords dynamic sculpting and deformation.     

Shape evolution with structural and topological changes usingblending

This paper describes a framework for the estimation of shape from sparse or incomplete range data. It uses a shape representation called blending, which allows for the geometric combination of shapes into a unified model - selected regions of the component shapes are cut-out and glued together. Estimation of shape by this representation is realized using a physics-based framework, and it also includes a process for deciding how to adapt the structure and topology of the model to improve the fit. The blending representation helps avoid abrupt changes in model geometry during fitting by allowing the smooth evolution of the shape, which improves the robustness of the technique. We demonstrate this framework with a series of experiments showing its ability to automatically extract structured representations from range data given both structurally and topologically complex objects     

Solid Geometry Processing on Deconstructed Domains

Many tasks in geometry processing are modelled as variational problems solved numerically using the finite element method. For solid shapes, this requires a volumetric discretization, such as a boundary conforming tetrahedral mesh. Unfortunately, tetrahedral meshing remains an open challenge and existing methods either struggle to conform to complex boundary surfaces or require manual intervention to prevent failure. Rather than create a single volumetric mesh for the entire shape, we advocate for solid geometry processing on deconstructed domains, where a large and complex shape is composed of overlapping solid subdomains. As each smaller and simpler part is now easier to tetrahedralize, the question becomes how to account for overlaps during problem modelling and how to couple solutions on each subdomain together algebraically. We explore how and why previous coupling methods fail, and propose a method that couples solid domains only along their boundary surfaces. We demonstrate the superiority of this method through empirical convergence tests and qualitative applications to solid geometry processing on a variety of popular second‐order and fourth‐order partial differential equations.     

Robust uniform triangulation algorithm for computer aided design

This paper presents a new robust uniform triangulation algorithm that can be used in CAD/CAM systems to generate and visualize geometry of 3D models. Typically, in CAD/CAM systems 3D geometry consists of 3D surfaces presented by the parametric equations (e.g. surface of revolution, NURBS surfaces) which are defined on a two dimensional domain. Conventional triangulation algorithms (e.g. ear clipping, Voronoi-Delaunay triangulation) do not provide desired quality and high level of accuracy (challenging tasks) for 3D geometry. The approach developed in this paper combines lattice tessellation and conventional triangulation techniques and allows CAD/CAM systems to obtain the required surface quality and accuracy. The algorithm uses a Cartesian lattice to divide the parametric domain into adjacent rectangular cells. These cells are used to generate polygons that are further triangulated to obtain accurate surface representation. The algorithm allows users to control the triangle distribution intensity by adjusting the lattice density. Once triangulated, the 3D model can be used not only for rendering but also in various manufacturing and design applications. The approach presented in this paper can be used to triangulate any parametric surface given in S(u,v) form, e.g. NURBS surfaces, surfaces of revolution, and produces good quality triangulation which can be used in CAD/CAM and computer graphics applications.     

3D shape acquisition and integral compact representation using optical scanning and enhanced shape parameterization

An efficient computational methodology for shape acquisition, processing and representation is developed. It includes 3D computer vision by applying triangulation and stereo-photogrammetry for high-accuracy 3D shape acquisition. Resulting huge 3D point clouds are successively parameterized into mathematical surfaces to provide for compact data-set representation, yet capturing local details sufficiently. B-spline surfaces are employed as parametric entities in fitting to point clouds resulting from optical 3D scanning. Beyond the linear best-fitting algorithm with control points as fitting variables, an enhanced non-linear procedure is developed. The set of best fitting variables in minimizing the approximation error norm between the parametric surface and the 3D cloud includes the control points coordinates. However, they are augmented by the set of position parameter values which identify the respectively closest matching points on the surface for the points in the cloud. The developed algorithm is demonstrated to be efficient on demanding test cases which encompass sharp edges and slope discontinuities originating from physical damage of the 3D objects or shape complexity.     

Multiresolution free form object modeling with point sampled geometry

In this paper an efficient framework for the creation of 3D digital content with point sampled geometry is proposed. A new hierarchy of shape representations with three levels is adopted in this framework. Based on this new hierarchical shape representation, the proposed framework offers concise integration of various volumetric- and surface-based modeling techniques, such as Boolean operation, offset, blending, free-form deformation, parameterization and texture mapping, and thus simplifies the complete modeling process. Previously to achieve the same goal, several separated algorithms had to be used independently with inconsistent volumetric and surface representations of the free-form object. Both graphics and industrial applications are presented to demonstrate the effectiveness and efficiency of the proposed framework.     

Isogeometric shape optimization of photonic crystals via Coons patches

In this paper, we present an approach that extends isogeometric shape optimization from optimization of rectangular-like NURBS patches to the optimization of topologically complex geometries. We have successfully applied this approach in designing photonic crystals where complex geometries have been optimized to maximize the band gaps.Salient features of this approach include the following: (1) multi-patch Coons representation of design geometry. The design geometry is represented as a collection of Coons patches where the four boundaries of each patch are represented as NURBS curves. The use of multiple patches is motivated by the need for representing topologically complex geometries. The Coons patches are used as a design representation so that designers do not need to specify interior control points and they provide a mechanism to compute analytical sensitivities for internal nodes in shape optimization, (2) exact boundary conversion to the analysis geometry with guaranteed mesh injectivity. The analysis geometry is a collection of NURBS patches that are converted from the multi-patch Coons representation with geometric exactness in patch boundaries. The internal NURBS control points are embedded in the parametric domain of the Coons patches with a built-in mesh rectifier to ensure the injectivity of the resulting B-spline geometry, i.e. every point in the physical domain is mapped to one point in the parametric domain, (3) analytical sensitivities. Sensitivities of objective functions and constraints with respect to design variables are derived through nodal sensitivities. The nodal sensitivities for the boundary control points are directly determined by the design parameters and those for internal nodes are obtained via the corresponding Coons patches.     

Efficiently computing geodesic offsets on triangle meshes by the extended Xin–Wang algorithm

Geodesic offset curves are important for many industrial applications, such as solid modeling, robot-path planning, the generation of tool paths for NC machining, etc. Although the offset problem is well studied in classical differential geometry and computer-aided design, where the underlying surface is sufficiently smooth, very few algorithms are available for computing geodesic offsets on discrete representation, in which the input is typically a polyline curve restricted on a piecewise linear mesh. In this paper, we propose an efficient and exact algorithm to compute the geodesic offsets on triangle meshes by extending the Xin–Wang algorithm of discrete geodesics. We define a new data structure called parallel-source windows, and extend both the “one angle one split” and the filtering theorem to maintain the window tree. Similar to the original Xin–Wang algorithm, our extended algorithm has an O(n) space complexity and an O(n²logn) asymptotic time complexity, where n is the number of vertices on the input mesh. We tested our algorithm on numerous real-world models and showed that our algorithm is exact, efficient and robust, and can be applied to large scale models with complicated geometry and topology.     

Quantifying the effect of a control point on the sign of curvature

We present a method for computing the domain, where a control point is free to move so that the corresponding planar curve is regular and of constant sign of curvature along a subinterval of its parametric domain of definition. The approach encompasses all curve representations that adopt the control-point paradigm and is illustrated for a quintic Bézier curve and a B-spline curve of degree 10.