Feature-based 3D non-manifold freeform object construction

This paper presents a novel technique for modeling a 3D non-manifold freeform model around a 3D reference model. To represent both the design abstractions and the incomplete topological information, a new non-manifold data structure is first defined. Our data structure embodies the functional vitalities of both the boundary representation data structure and the complex-based data structure. Along with our data structure, a set of topological operators is defined to manipulate the entities in the data structure. Based on the non-manifold data structure and the topological operators, we develop a technique to construct 3D freeform objects around a reference model. Intuitive 2D sketches are adopted to specify the detailed profile of the object constructed. The construction method is feature-based – every reference model has pre-defined features, and the feature template of the constructed object is related to the features of the reference model by feature node encoding. Therefore, the surfaces derived from one reference model can be regenerated automatically on another reference model with the same features. The geometry coverage of our geometric modeling approach includes both manifold and non-manifold 3D freeform objects.     

Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrary topology

In this paper, a novel approach is proposed to reliably reconstruct the geometric shape of a physically existing object based on unorganized point cloud sampled from its boundary surface. The proposed approach is composed of two steps. In the first step, triangle mesh structure is reconstructed as a continuous manifold surface by imposing explicit relationship among the discrete data points. For efficient reconstruction, a growing procedure is employed to build the 2-manifold directly without intermediate 3D representation. Local and global topological operations with ensured completeness and soundness are defined to incrementally construct the 2-manifold with arbitrary topology. In addition, a novel criterion is proposed to control the growing process for ensured geometric integrity and automatic boundary detection with a non-metric threshold. The reconstructed manifold surface captures the object topology with the built-in combinatorial structure and approximates the object geometry to the first order. In the second step, new methods are proposed to efficiently obtain reliable curvature estimation for both the object surface and the reconstructed mesh surface. The combinatorial structure of the triangle mesh is then optimized by changing its local topology to minimize the curvature difference between the two surfaces. The optimized triangle mesh achieves second order approximation to the object geometry and can serve as a basis for many applications including virtual reality, computer vision, and reverse engineering.     

Geometry-aware domain decomposition for T-spline-based manifold modeling

This paper presents a new and effective method to construct manifold T-splines of complicated topology/geometry. The fundamental idea of our novel approach is the geometry-aware object segmentation, by which an arbitrarily complicated surface model can be decomposed into a group of disjoint components that comprise branches, handles, and base patches. Such a domain decomposition simplifies objects of arbitrary topological type into a family of genus-zero/one open surfaces, each of which can be conformally parameterized into a set of rectangles. In contrast to the conventional decomposition approaches, our method can guarantee that the cutting locus are consistent on the parametric domain. As a result, the resultant T-splines of decomposed components are automatically glued and have high-order continuity everywhere except at the extraordinary points. We show that the number of extraordinary points of the domain manifold is bounded by the number of segmented components. Furthermore, the entire mesh-to-spline data conversion pipeline can be implemented with full automation, and thus, has potential in shape modeling and reverse engineering applications of complicated real-world objects.     

On surface reconstruction: A priority driven approach

To reconstruct an object surface from a set of surface points, a fast, practical, and efficient priority driven algorithm is presented. The key idea of the method is to consider the shape changes of an object at the boundary of the mesh growing area and to create a priority queue to the advancing front of the mesh area according to the changes. The mesh growing process is then driven by the priority queue for efficient surface reconstruction. New and practical triangulation criteria are also developed to support the priority driven strategy and to construct a new triangle at each step of mesh growing in real time. The quality and correctness of the created triangles will be guaranteed by the triangulation criteria and topological operations. The algorithm can reconstruct an object surface from unorganized surface points in a fast and reliable manner. Moreover, it can successfully construct the surface of the objects with complex geometry or topology. The efficiency and robustness of the proposed algorithm is validated by extensive experiments.     

Representing topological relationships for spatiotemporal objects

Several representations have been created to store topological information in normal spatial databases. Some work has also been done to represent topology for 3D objects, and such representations could be used to store topology for spatiotemporal objects. However, using 3D models has some disadvantages with regards to retrieving snapshots of the database. This paper aims at creating a spatiotemporal version of the sliced representation that supports efficient retrieval of snapshots of the past and that supports enforcing topological relationships. This paper aims to extend an earlier representation of moving objects so that it can also store and enforce some of the topological relationships between the objects. One use of such a representation is storing a changing spatial partition. As part of the effort to construct the model, an analysis of the topological relationships has been carried out to see which need to be stored explicitly and which can be computed from geometry. Both a basic time slice model and a 3D model are examined to determine how suitable they are for storing topological relationships. An extension of the time slice model is then proposed that solves some of the problems of the basic time slice model. Some algorithms for constructing the new model from snapshots of the objects along with an adjacency graph have been created. The paper also contains a short analysis on how to handle current time, as the time slice model is best at handling historical data, and on ways to speed up searches in a database in which objects of many types are connected to one another and many files therefore potentially need to be accessed.     

基于变分隐式曲面的网格融合

三维物体融合利用三维模型之间的剪贴操作从两个或多个现有的几何模型中光滑融合出新的几何模型.作为一种新的几何造型方法,它正受到越来越多的关注.提出一种基于变分隐式曲面的网格融合新方法.首先利用平面截面切出网格物体的待融合边界,然后通过构造插值待融合网格物体边界的变分隐式曲面并对其进行多边形化,得到待融合网格物体间的过渡曲面,最后通过剪切掉过渡曲面的多余部分及拓扑合并操作以实现过渡网格曲面与原始网格间的光滑融合与现有的直接连接待融合网格物体边界以实现网格融合的算法相比,该方法不仅突破了对待融合物体的拓扑限制,允许多个物体同时进行融合,而且算法计算快速、鲁棒,使用方便,展示出良好的应用前景.     

Generating cubical complexes from image data and computation of the Euler number

A number of tasks in image processing and computer vision require the computation of certain topological characteristics of objects in a given image. In this paper, we introduce a new method based on the notion of the algebraic topology complex to compute the Euler number of a given object. First, we attach a cubical complex to the object of interest, then we associate an algebraic structure on which a number of simplifying operations preserving the topology but not necessarily the geometric nature of the complex are possible. This is a unifying dimension independent approach. We show that the Euler number can be obtained directly from the cubical structure or one can perform a collapsing operation that allows to reduce the given image to a lower dimension structure with equivalent topological properties. This reduced structure can be used in a further process, in particular, for the computation of the Euler number.     

Solid modeling aspects of three-dimensional fragmentation

The ways in which the topology and geometry of a three-dimensional finite-element model may evolve as a consequence of fracture and fragmentation are enumerated, and the actions which may be taken in order to update the boundary representation of the solid so as to faithfully reflect that evolution are described. Arbitrary topological and geometrical evolution of a three-dimensional solid, not necessarily restricted to an evolution of its surface, are addressed. Solids are described by their boundary representation (BRep) and a surface and volume triangulation. Fracture processes are modeled by the introduction of cohesive elements at element interfaces. Simple rules are shown to enable the simulation of strikingly complex crack patterns. The scope and versatility of the approach is illustrated with the aid of selected examples of application.     

Detail‐Preserving Explicit Mesh Projection and Topology Matching for Particle‐Based Fluids

We propose a new explicit surface tracking approach for particle‐based fluid simulations. Our goal is to advect and update a highly detailed surface, while only computing a coarse simulation. Current explicit surface methods lose surface details when projecting on the isosurface of an implicit function built from particles. Our approach uses a detail‐preserving projection, based on a signed distance field, to prevent the divergence of the explicit surface without losing its initial details. Furthermore, we introduce a novel topology matching stage that corrects the topology of the explicit surface based on the topology of an implicit function. To that end, we introduce an optimization approach to update our explicit mesh signed distance field before remeshing. Our approach is successfully used to preserve the surface details of melting and highly viscous objects, and shown to be stable by handling complex cases involving multiple topological changes. Compared to the computation of a high‐resolution simulation, using our approach with a coarse fluid simulation significantly reduces the computation time and improves the quality of the resulting surface.     

Implicit Surface-Based Geometric Fusion

This paper introduces a general purpose algorithm for reliable integration of sets of surface measurements into a single 3D model. The new algorithm constructs a single continuous implicit surface representation which is the zero-set of a scalar field function. An explicit object model is obtained using any implicit surface polygonization algorithm. Object models are reconstructed from both multiple view conventional 2.5D range images and hand-held sensor range data. To our knowledge this is the first geometric fusion algorithm capable of reconstructing 3D object models from noisy hand-held sensor range data.This approach has several important advantages over existing techniques. The implicit surface representation allows reconstruction of unknown objects of arbitrary topology and geometry. A continuous implicit surface representation enables reliable reconstruction of complex geometry. Correct integration of overlapping surface measurements in the presence of noise is achieved using geometric constraints based on measurement uncertainty. The use of measurement uncertainty ensures that the algorithm is robust to significant levels of measurement noise. Previous implicit surface-based approaches use discrete representations resulting in unreliable reconstruction for regions of high curvature or thin surface sections. Direct representation of the implicit surface boundary ensures correct reconstruction of arbitrary topology object surfaces. Fusion of overlapping measurements is performed using operations in 3D space only. This avoids the local 2D projection required for many previous methods which results in limitations on the object surface geometry that is reliably reconstructed. All previous geometric fusion algorithms developed for conventional range sensor data are based on the 2.5D image structure preventing their use for hand-held sensor data. Performance evaluation of the new integration algorithm against existing techniques demonstrates improved reconstruction of complex geometry.     

Meshless Harmonic Volumetric Mapping Using Fundamental Solution Methods

Harmonic volumetric mapping aims to establish a smooth bijective correspondence between two solid shapes with the same topology. In this paper, we develop an automatic meshless method for creating such a mapping between two given objects. With the shell surface mapping as the boundary condition, we first solve a linear system constructed by a boundary method called the method of fundamental solution, and then represent the mapping using a set of points with different weights in the vicinity of the shell of the given model. Our algorithm is a true meshless method (without the need of any specific meshing structure within the solid interior) and the behavior of the interior region is directly determined by the boundary, which can improve the computational efficiency and robustness significantly. Therefore, our algorithm can be applied to massive volume data sets with various geometric primitives and topological types. We demonstrate the utility and efficacy of our algorithm in information transfer, shape registration, deformation sequence analysis, tetrahedral remeshing, and solid texture synthesis.      

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.     

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     

Reconstruction of edges in digital building models

Traditionally, the geometry of building components or rooms is either described by their boundary or it is defined by constructive solid models. Modeling tools are available which are based on the principle of constructing building components and of composing a building by adding building components step by step. However, topological relations are relevant besides the shape of components and rooms. These topological relationships are not necessarily explicit information in boundary representation or constructive solid models. As a consequence, they must be computed. At present time, there exists to the best knowledge of the author only a single approach in this subject area that is able to reconstruct topological relations including their geometry. The objects which need to be considered are building components, built-in components and rooms. The challenge is to calculate the three relevant aspects of geometry in digital building models completely and in an efficient way. These three relevant aspects are clashes, voids and contact faces. The existing approach to calculate these aspects is based on space partitioning concepts. Space partitioning concepts store neighboring relations explicitly. The approach presented in this paper is also based on space partitioning. One basic and novel consideration of the approach presented in this paper is to execute the reconstruction procedure in a mesh. The mesh itself is not refined anymore at a certain point during the calculations to avoid uncontrollable refinements. The second basic and novel consideration is the way of avoiding topological inconsistencies. Integer values are chosen for coordinates, and a specific algorithm is presented that guarantees that topological inconsistencies cannot occur. The research presented in this paper addresses the first step on the way to compute clashes, voids and contact faces. This is the reconstruction of edges. This paper presents the theory and a pilot implementation for the reconstruction of straight edges. Examples show the benefits of the approach presented. Open questions are discussed.     

Computer-aided design of porous artifacts

Heterogeneous structures represent an important new frontier for 21st century engineering. Human tissues, composites, ‘smart’ and multi-material objects are all physically manifest in the world as three-dimensional (3D) objects with varying surface, internal and volumetric properties and geometries. For instance, a tissue engineered structure, such as bone scaffold for guided tissue regeneration, can be described as a heterogeneous structure consisting of 3D extra-cellular matrices (made from biodegradable material) and seeded donor cells and/or growth factors.The design and fabrication of such heterogeneous structures requires new techniques for solid models to represent 3D heterogeneous objects with complex material properties. This paper presents a representation of model density and porosity based on stochastic geometry. While density has been previously studied in the solid modeling literature, porosity is a relatively new problem. Modeling porosity of bio-materials is critical for developing replacement bone tissues. The paper uses this representation to develop an approach to modeling of porous, heterogeneous materials and provides experimental data to validate the approach. The authors believe that their approach introduces ideas from the stochastic geometry literature to a new set of engineering problems. It is hoped that this paper stimulates researchers to find new opportunities that extend these ideas to be more broadly applicable for other computational geometry, graphics and computer-aided design problems.     

基于快速FCM算法的多目标分割CV模型

Chan—Vese（CV）模型是基于水平集方法演化不依赖图像梯度的算法,能很好地处理拓扑变化和弱边界,但对于目标和背景对比度低的边界以及多目标区域分割效果较差。针对上述问题提出一种基于快速模糊F均值（FCM）算法和邻域模板改进的CV模型。利用快速FCM算法提取图像特征信息,采用邻域模板闲值法对不同的目标区域分别处理,准确控制了轮廓线的分裂,能够分割出更多的目标区域。     

Hierarchical Quad Meshing of 3D Scanned Surfaces

In this paper we present a novel method to reconstruct watertight quad meshes on scanned 3D geometry. There exist many different approaches to acquire 3D information from real world objects and sceneries. Resulting point clouds depict scanned surfaces as sparse sets of positional information. A common downside is the lack of normals, connectivity or topological adjacency data which makes it difficult to actually recover a meaningful surface. The concept described in this paper is designed to reconstruct a surface mesh despite all this missing information. Even when facing varying sample density, our algorithm is still guaranteed to produce watertight manifold meshes featuring quad faces only. The topology can be set‐up to follow superimposed regular structures or align naturally to the point cloud's shape. Our proposed approach is based on an initial divide and conquer subsampling procedure: Surface samples are clustered in meaningful neighborhoods as leafs of a kd‐tree. A representative sample of the surface neighborhood is determined for each leaf using a spherical surface approximation. The hierarchical structure of the binary tree is utilized to construct a basic set of loose tiles and to interconnect them. As a final step, missing parts of the now coherent tile structure are filled up with an incremental algorithm for locally optimal gap closure. Disfigured or concave faces in the resulting mesh can be removed with a constrained smoothing operator.     

A two-level topological model for 3D features in CityGML

CityGML, as the standard for the representation and exchange of 3D city models, contains rich information in terms of geometry, semantics, topology and appearance. With respect to topology, CityGML adopts the XLink approach to represent topological relationships between different geometric aggregates or thematic features; however, it is limited to shared objects. This paper proposes a two-level model for representing 3D topological relationships in CityGML: high-level (semantic-level) topology between semantic features and low-level (geometric-level) topology between geometric primitives. Five topological relationships are adopted in this model: touch, in, equal, overlap and disjoint. The semantic-level topology is derived from the geometric-level topology on the basis of the shared geometric primitives. To maintain the 3D topology, topological consistency rules are presented. An Application Domain Extension, called TopoADE, is proposed for the implementation of the topological model. The TopoADE consists of three modules: Topology, Feature and Geometry. Finally, 3D city models with LoD1 to LoD4 are used to test this model. Experimentation on those data sets indicates a validation of the proposed topological model in CityGML.     

基于类似形原理识别平面多边形

根据仿射不变性提出了6个用来描述多边形形状的拓扑特征和几何特征，这些特征在仿射投影下是不变的；以这些特征作为约束务件给出了在仿射投影下多边形的类似形定义；提出了一种用于识别平面多边形的类似形法。对类似形应用拓扑结构进行定性分析，对噪音不敏感；应用几何结构进行定量分析，能够反应多边形形状的细微差别。实验结果表明该方法是有效的。该算法能够用于识别平面立体和工业部件等。