A divide-and-conquer approach for automatic polycube map construction

Polycube map is a global cross-surface parameterization technique, where the polycube shape can roughly approximate the geometry of modeled objects while retaining the same topology. The large variation of shape geometry and its complex topological type in real-world applications make it difficult to effectively construct a high-quality polycube that can serve as a good global parametric domain for a given object. In practice, existing polycube map construction algorithms typically require a large amount of user interaction for either pre-constructing the polycubes with great care or interactively specifying the geometric constraints to arrive at the user-satisfied maps. Hence, it is tedious and labor intensive to construct polycube maps for surfaces of complicated geometry and topology. This paper aims to develop an effective method to construct polycube maps for surfaces with complicated topology and geometry. Using our method, users can simply specify how close the target polycube mimics a given shape in a quantitative way. Our algorithm can both construct a similar polycube of high geometric fidelity and compute a high-quality polycube map in an automatic fashion. In addition, our method is theoretically guaranteed to output a one-to-one map. To demonstrate the efficacy of our method, we apply the automatically-constructed polycube maps in a number of computer graphics applications, such as seamless texture tiling, T-spline construction, and quadrilateral mesh generation.     

Restricted trivariate polycube splines for volumetric data modeling

This paper presents a volumetric modeling framework to construct a novel spline scheme called restricted trivariate polycube splines (RTP-splines). The RTP-spline aims to generalize both trivariate T-splines and tensor-product B-splines; it uses solid polycube structure as underlying parametric domains and strictly bounds blending functions within such domains. We construct volumetric RTP-splines in a top-down fashion in four steps: 1) Extending the polycube domain to its bounding volume via space filling; 2) building the B-spline volume over the extended domain with restricted boundaries; 3) inserting duplicate knots by adding anchor points and performing local refinement; and 4) removing exterior cells and anchors. Besides local refinement inherited from general T-splines, the RTP-splines have a few attractive properties as follows: 1) They naturally model solid objects with complicated topologies/bifurcations using a one-piece continuous representation without domain trimming/patching/merging. 2) They have guaranteed semistandardness so that the functions and derivatives evaluation is very efficient. 3) Their restricted support regions of blending functions prevent control points from influencing other nearby domain regions that stay opposite to the immediate boundaries. These features are highly desirable for certain applications such as isogeometric analysis. We conduct extensive experiments on converting complicated solid models into RTP-splines, and demonstrate the proposed spline to be a powerful and promising tool for volumetric modeling and other scientific/engineering applications where data sets with multiattributes are prevalent.     

A topology-preserving optimization algorithm for polycube mapping

We present an effective optimization framework to compute polycube mapping. Composed of a set of small cubes, a polycube well approximates the geometry of the free-form model yet possesses great regularity; therefore, it can serve as a nice parametric domain for free-form shape modeling and analysis. Generally, the more cubes are used to construct the polycube, the better the shape can be approximated and parameterized with less distortion. However, corner points of a polycube domain are singularities of this parametric representation, so a polycube domain having too many corners is undesirable. We develop an iterative algorithm to seek for the optimal polycube domain and mapping, with the constraint on using a restricted number of cubes (therefore restricted number of corner points). We also use our polycube mapping framework to compute an optimal common polycube domain for multiple objects simultaneously for lowly distorted consistent parameterization.     

Manifold splines with a single extraordinary point

This paper develops a novel computational technique to define and construct manifold splines with only one singular point by employing the rigorous mathematical theory of Ricci flow. The central idea and new computational paradigm of manifold splines are to systematically extend the algorithmic pipeline of spline surface construction from any planar domain to an arbitrary topology. As a result, manifold splines can unify planar spline representations as their special cases. Despite its earlier success, the existing manifold spline framework is plagued by the topology-dependent, large number of singular points (i.e., |2g−2| for any genus-g surface), where the analysis of surface behaviors such as continuity remains extremely difficult. The unique theoretical contribution of this paper is that we devise new mathematical tools so that manifold splines can now be constructed with only one singular point, reaching their theoretic lower bound of singularity for real-world applications. Our new algorithm is founded upon the concept of discrete Ricci flow and associated techniques. First, Ricci flow is employed to compute a special metric of any manifold domain (serving as a parametric domain for manifold splines), such that the metric becomes flat everywhere except at one point. Then, the metric naturally induces an affine atlas covering the entire manifold except this singular point. Finally, manifold splines are defined over this affine atlas. The Ricci flow method is theoretically sound, and practically simple and efficient. We conduct various shape experiments and our new theoretical and algorithmic results alleviate the modeling difficulty of manifold splines, and hence, promote the widespread use of manifold splines in surface and solid modeling, geometric design, and reverse engineering.     

Polycube Simplification for Coarse Layouts of Surfaces and Volumes

Representing digital objects with structured meshes that embed a coarse block decomposition is a relevant problem in applications like computer animation, physically‐based simulation and Computer Aided Design (CAD). One of the key ingredients to produce coarse block structures is to achieve a good alignment between the mesh singularities (i.e., the corners of each block). In this paper we improve on the polycube‐based meshing pipeline to produce both surface and volumetric coarse block‐structured meshes of general shapes. To this aim we add a new step in the pipeline. Our goal is to optimize the positions of the polycube corners to produce as coarse as possible base complexes. We rely on re‐mapping the positions of the corners on an integer grid and then using integer numerical programming to reach the optimal. To the best of our knowledge this is the first attempt to solve the singularity misalignment problem directly in polycube space. Previous methods for polycube generation did not specifically address this issue. Our corner optimization strategy is efficient and requires a negligible extra running time for the meshing pipeline. In the paper we show that our optimized polycubes produce coarser block structured surface and volumetric meshes if compared with previous approaches. They also induce higher quality hexahedral meshes and are better suited for spline fitting because they reduce the number of splines necessary to cover the domain, thus improving both the efficiency and the overall level of smoothness throughout the volume.     

Optimizing polycube domain construction for hexahedral remeshing

Polycube mapping can provide regular and global parametric representations for general solid models. Automatically constructing effective polycube domains, however, is challenging. We present an algorithm for polycube construction and volumetric parameterization. The algorithm has three steps: pre-deformation, polycube construction and optimization, and mapping computation. Compared with existing polycube mapping methods, our algorithm can robustly generate desirable polycube domain shape and low-distortion volumetric parameterization. It can be used for automatic high-quality hexahedral mesh generation.     

Surface reconstruction using bivariate simplex splines on Delaunay configurations

Recently, a new bivariate simplex spline scheme based on Delaunay configuration has been introduced into the geometric computing community, and it defines a complete spline space that retains many attractive theoretic and computational properties. In this paper, we develop a novel shape modeling framework to reconstruct a closed surface of arbitrary topology based on this new spline scheme. Our framework takes a triangulated set of points, and by solving a linear least-square problem and iteratively refining parameter domains with newly added knots, we can finally obtain a continuous spline surface satisfying the requirement of a user-specified error tolerance. Unlike existing surface reconstruction methods based on triangular B-splines (or DMS splines), in which auxiliary knots must be explicitly added in advance to form a knot sequence for construction of each basis function, our new algorithm completely avoids this less-intuitive and labor-intensive knot generating procedure. We demonstrate the efficacy and effectiveness of our algorithm on real-world, scattered datasets for shape representation and computing.     

隐式二次代数曲线插值

目前,二次参数曲线在曲线曲面造型中应用非常广泛,起着至关重要的作用,因此对二次曲线的性质和应用的研究仍十分有意义。本文首先综述近年来有关二次曲线的研究,对各种方法的优缺点进行了客观的评价。然后根据三次代数曲线的构造方法,提出一种新的二次曲线的构造方法,该方法通过几何量如控制点和切线来控制二次代数曲线的形状。文章在理论上对曲线的一系列性质进行了详细说明。     

A novel constrained texture mapping method based on harmonic map

In this paper, we present a novel constrained texture mapping method based on the harmonic map. We first project the surface of a 3D model on a planar domain by an angle-based-flattening technique and perform a parametrization. The user then specifies interactively the constraints between the selected feature points on the parametric domain of the 3D model and the corresponding pixels on the texture image; the texture coordinates of other sample points on the 3D model are determined based on harmonic mapping between the parametric domain of the model and the texture image; finally we apply an adaptive local mapping refinement to improve the rendering result in real-time. Compared with other interactive methods, our method provides an analytically accurate solution to the problem, and the energy minimization characteristic of the harmonic map reduces the potential distortion that may result in the constrained texture mapping. Experimental data demonstrate good rendering effects generated by the presented algorithm.     

Computing general geometric structures on surfaces using Ricci flow

Systematically generalizing planar geometric algorithms to manifold domains is of fundamental importance in computer aided design field. This paper proposes a novel theoretic framework, geometric structure, to conquer this problem. In order to discover the intrinsic geometric structures of general surfaces, we developed a theoretic rigorous and practical efficient method, Discrete Variational Ricci flow.Different geometries study the invariants under the corresponding transformation groups. The same geometry can be defined on various manifolds, whereas the same manifold allows different geometries. Geometric structures allow different geometries to be defined on various manifolds, therefore algorithms based on the corresponding geometric invariants can be applied on the manifold domains directly.Surfaces have natural geometric structures, such as spherical structure, affine structure, projective structure, hyperbolic structure and conformal structure. Therefore planar algorithms based on these geometries can be defined on surfaces straightforwardly.Computing the general geometric structures on surfaces has been a long lasting open problem. We solve the problem by introducing a novel method based on discrete variational Ricci flow.We thoroughly explain both theoretical and practical aspects of the computational methodology for geometric structures based on Ricci flow, and demonstrate several important applications of geometric structures: generalizing Voronoi diagram algorithms to surfaces via Euclidean structure, cross global parametrization between high genus surfaces via hyperbolic structure, generalizing planar splines to manifolds via affine structure. The experimental results show that our method is rigorous and efficient and the framework of geometric structures is general and powerful.     

Multiresolution Shape Deformations for Meshes with Dynamic Vertex Connectivity

Multiresolution shape representation is a very effective way to decompose surface geometry into several levels of detail. Geometric modeling with such representations enables flexible modifications of the global shape while preserving the detail information. Many schemes for modeling with multiresolution decompositions based on splines, polygonal meshes and subdivision surfaces have been proposed recently. In this paper we modify the classical concept of multiresolution representation by no longer requiring a global hierarchical structure that links the different levels of detail. Instead we represent the detail information implicitly by the geometric difference between independent meshes. The detail function is evaluated by shooting rays in normal direction from one surface to the other without assuming a consistent tesselation. In the context of multiresolution shape deformation, we propose a dynamic mesh representation which adapts the connectivity during the modification in order to maintain a prescribed mesh quality. Combining the two techniques leads to an efficient mechanism which enables extreme deformations of the global shape while preventing the mesh from degenerating. During the deformation, the detail is reconstructed in a natural and robust way. The key to the intuitive detail preservation is a transformation map which associates points on the original and the modified geometry with minimum distortion. We show several examples which demonstrate the effectiveness and robustness of our approach including the editing of multiresolution models and models with texture.     

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.     

Free-form geometric modeling by integrating parametric and implicit PDEs

Parametric PDE techniques, which use partial differential equations (PDEs) defined over a 2D or 3D parametric domain to model graphical objects and processes, can unify geometric attributes and functional constraints of the models. PDEs can also model implicit shapes defined by level sets of scalar intensity fields. In this paper, we present an approach that integrates parametric and implicit trivariate PDEs to define geometric solid models containing both geometric information and intensity distribution subject to flexible boundary conditions. The integrated formulation of second-order or fourth-order elliptic PDEs permits designers to manipulate PDE objects of complex geometry and/or arbitrary topology through direct sculpting and free-form modeling. We developed a PDE-based geometric modeling system for shape design and manipulation of PDE objects. The integration of implicit PDEs with parametric geometry offers more general and arbitrary shape blending and free-form modeling for objects with intensity attributes than pure geometric models     

Explicit cylindrical maps for general tubular shapes

A solid cylindrical parameterization is a volumetric map between a tubular shape and a right cylinder embedded in the polar coordinate reference system. This paper introduces a novel approach to derive smooth (i.e., harmonic) cylindrical parameterizations for solids with arbitrary topology. Differently from previous approaches our mappings are both fully explicit and bi-directional, meaning that the three polar coordinates are encoded for both internal and boundary points, and that for any point within the solid we can efficiently move from the object space to the parameter space and vice-versa. To represent the discrete mapping, we calculate a tetrahedral mesh that conforms with the solid’s boundary and accounts for the periodic and singular structure of the parametric domain. To deal with arbitrary topologies, we introduce a novel approach to exhaustively partition the solid into a set of tubular parts based on a curve-skeleton. Such a skeleton can be either computed by an algorithm or provided by the user. Being fully explicit, our mappings can be readily exploited by off-the-shelf algorithms (e.g., for iso-contouring). Furthermore, when the input shape is made of tubular parts, our method produces low-distortion parameterizations whose iso-surfaces fairly follow the geometry in a natural way. We show how to exploit this characteristic to produce high-quality hexahedral and shell meshes.     

Constructing hexahedral shell meshes via volumetric polycube maps

Shells are three-dimensional structures. One dimension, the thickness, is much smaller than the other two dimensions. Shell structures can be widely found in many real-world objects. This paper presents a method to construct a layered hexahedral mesh for shell objects. Given a closed 2-manifold and the user-specified thickness, we construct the shell space using the distance field and then parameterize the shell space to a polycube domain. The volume parameterization induces the hexahedral tessellation in the object shell space. As a result, the constructed mesh is an all-hexahedral mesh in which most of the vertices are regular, i.e., the valence is 6 for interior vertices and 5 for boundary vertices. The mesh also has a layered structure, so that all layers have exactly the same tessellation. We prove that our parameterization is guaranteed to be bijective. As a result, the constructed hexahedral mesh is free of degeneracy, such as self-intersection, flip-over, etc. We also show that the iso-parametric line (in the thickness dimension) is orthogonal to the other two iso-parametric lines. We apply our algorithm to numerous real-world models of various geometry and topology. The promising experimental results demonstrate the efficacy of our algorithm. Although our main focus is to construct a hexahedral mesh by using volumetric polycube parameterization, the proposed framework is general that can be applied to other regular domains, such as cylinder and sphere, which is also demonstrated in the paper.     

Geodesic distance-weighted shape vector image diffusion

This paper presents a novel and efficient surface matching and visualization framework through the geodesic distance-weighted shape vector image diffusion. Based on conformal geometry, our approach can uniquely map a 3D surface to a canonical rectangular domain and encode the shape characteristics (e.g., mean curvatures and conformal factors) of the surface in the 2D domain to construct a geodesic distance-weighted shape vector image, where the distances between sampling pixels are not uniform but the actual geodesic distances on the manifold. Through the novel geodesic distance-weighted shape vector image diffusion presented in this paper, we can create a multiscale diffusion space, in which the cross-scale extrema can be detected as the robust geometric features for the matching and registration of surfaces. Therefore, statistical analysis and visualization of surface properties across subjects become readily available. The experiments on scanned surface models show that our method is very robust for feature extraction and surface matching even under noise and resolution change. We have also applied the framework on the real 3D human neocortical surfaces, and demonstrated the excellent performance of our approach in statistical analysis and integrated visualization of the multimodality volumetric data over the shape vector image.     

基于整数维约束的分维形状映射生成方法

把整数维图形研究方法与分数维图形研究方法相结合，提出一种基于整数维规则几何形状的约束的分维形状映射生成方法，有于描述自然界和工程中出现的且具有特定基本形状趋势的随机现象和随机过程，首先，任意选取一个具有调配函数的自由形状构造一个有序参数空间，确定有序参数的取值规律和区域，把有序参数空间与自适应神经网络，随机性相结合，构造一个随机离散参数空间，并建立起有序参数与随机离散参数之间的参数对应关系，最后，通过有序与无序的参数对应关系，建立一个独立于任意规则几何形状的统一的分形映射关系，对相应整数维的任意规则参数几何形状分形映射，生成宏观形态趋势可预见和可控制的分维形状，该提出的方法适有于任意参数几何形状的分形映射，生成分形图形，且方法简明，易于实现。     

Hierarchical B-splines on regular triangular partitions

Multivariate splines have a wide range of applications in function approximation, finite element analysis and geometric modeling. They have been extensively studied in the last several decades, and specially the theory on bivariate B-splines over regular triangular partition is well developed. However, the above mentioned splines do not have local refinement property – a property that is very important in adaptive function approximation and level of detailed representation of geometric models. In this paper, we introduce the concept of hierarchial bivariate splines over regular triangular partitions and construct basis functions of such spline space that satisfy some nice properties. We provide some examples of hierarchical splines over triangular partitions in surface fitting and in solving numerical PDEs, and the results turn out to be promising.     

闭合三角网格的优化切割与保角映射

提出一种自动地将任意闭合三角网格切开并保角映射到二维平面域的算法.通过对自动提取的模型初始切割线逐步优化得到模型切割线,优化过程由一个与保角映射扭曲度和合法性相关的成本函数控制.为了减小映射扭曲,算法中不预先固定参数域边界,而在参数化过程中自动地确定网格的自然边界.实验结果表明,该算法通过优化切割线和参数域边界有效地降低了三角形形状扭曲,并保证了参数化结果的合法性.