Skeleton‐driven Adaptive Hexahedral Meshing of Tubular Shapes

We propose a novel method for the automatic generation of structured hexahedral meshes of articulated 3D shapes. We recast the complex problem of generating the connectivity of a hexahedral mesh of a general shape into the simpler problem of generating the connectivity of a tubular structure derived from its curve‐skeleton. We also provide volumetric subdivision schemes to nicely adapt the topology of the mesh to the local thickness of tubes, while regularizing per‐element size. Our method is fast, one‐click, easy to reproduce, and it generates structured meshes that better align to the branching structure of the input shape if compared to previous methods for hexa mesh generation.     

Geometry-aware bases for shape approximation

We introduce a new class of shape approximation techniques for irregular triangular meshes. Our method approximates the geometry of the mesh using a linear combination of a small number of basis vectors. The basis vectors are functions of the mesh connectivity and of the mesh indices of a number of anchor vertices. There is a fundamental difference between the bases generated by our method and those generated by geometry-oblivious methods, such as Laplacian-based spectral methods. In the latter methods, the basis vectors are functions of the connectivity alone. The basis vectors of our method, in contrast, are geometry-aware since they depend on both the connectivity and on a binary tagging of vertices that are "geometrically important" in the given mesh (e.g., extrema). We show that, by defining the basis vectors to be the solutions of certain least-squares problems, the reconstruction problem reduces to solving a single sparse linear least-squares problem. We also show that this problem can be solved quickly using a state-of-the-art sparse-matrix factorization algorithm. We show how to select the anchor vertices to define a compact effective basis from which an approximated shape can be reconstructed. Furthermore, we develop an incremental update of the factorization of the least-squares system. This allows a progressive scheme where an initial approximation is incrementally refined by a stream of anchor points. We show that the incremental update and solving the factored system are fast enough to allow an online refinement of the mesh geometry     

面向概念设计的零件定性模型

针对概念零件结构的定性特性,提出了支持概念设计并能指导和控制零件形状设计的概念零件结构定性模型,讨论了形体符号的定义和分类,零件符号化的基本步骤和疗法。给出了典型结构概念零件的符号表示实例．讨论了定性几何约束、定性几何约束图和定性拼合运算．并结合实例介绍了概念零件定性模型的建立过程．     

A General Approach for Dexterous Manipulation Planning Based on Configuration Space Structuring

In this paper, we propose a new method for the dexterous manipulation planning problem, under quasi-static movement assumption. This method computes both object and finger trajectories as well as finger relocation sequence and applies to every object shape and hand geometry. It relies on the exploration of the particular subspaces GS k that are the subspaces of all the grasps that can be achieved for a given set of k grasping fingers. The originality is to use continuous paths in these subspaces to directly link two configurations. The proposed approach captures the GS k connectivity in a graph structure. The answer of the manipulation planning query is then given by searching a path in the computed graph. Another specificity of our technique is that it considers manipulated object and hand as an only system, unlike most existing methods that first compute object trajectory then fingers trajectories and thus can not find a solution in all situations. Simulation experiments were conducted for different dexterous manipulation task examples to validate the proposed method.     

Curve skeleton extraction by coupled graph contraction and surface clustering

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first construct an initial skeleton graph by directly copying the connectivity and geometry information from the input mesh. Graph contraction and surface clustering are then performed iteratively. The former merges certain graph nodes based on computation of an approximate centroidal Voronoi diagram, seeded by subsampling the graph nodes from the previous iteration. Meanwhile, a coupled surface clustering process serves to regularize the graph contraction. Constraints are used to ensure that extremities of the graph are not shortened undesirably, to ensure that skeleton has the correct topological structure, and that surface clustering leads to an approximately-centered skeleton of the input shape. These properties lead to a stable and reliable skeleton graph construction algorithm.Experiments demonstrate that our skeleton extraction algorithm satisfies various desirable criteria. Firstly, it produces a skeleton homotopic with the input (the genus of both shapes agree) which is both robust (results are stable with respect to noise and remeshing of the input shape) and reliable (every boundary point is visible from at least one curve-skeleton location). It can also handle point cloud data if we first build an initial skeleton graph based on k-nearest neighbors. In addition, a secondary output of our algorithm is a skeleton-to-surface mapping, which can e.g. be used directly for skinning animation.Highlights(1) An algorithm for curve skeleton extraction from 3D shapes based on coupled graph contraction and surface clustering. (2) The algorithm meets various desirable criteria and can be extended to work for incomplete point clouds.     

Non-rigid 3D shape tracking from multiview video

We present a fast and efficient non-rigid shape tracking method for modeling dynamic 3D objects from multiview video. Starting from an initial mesh representation, the shape of a dynamic object is tracked over time, both in geometry and topology, based on multiview silhouette and 3D scene flow information. The mesh representation of each frame is obtained by deforming the mesh representation of the previous frame towards the optimal surface defined by the time-varying multiview silhouette information with the aid of 3D scene flow vectors. The whole time-varying shape is then represented as a mesh sequence which can efficiently be encoded in terms of restructuring and topological operations, and small-scale vertex displacements along with the initial model. The proposed method has the ability to deal with dynamic objects that may undergo non-rigid transformations and topological changes. The time-varying mesh representations of such non-rigid shapes, which are not necessarily of fixed connectivity, can successfully be tracked thanks to restructuring and topological operations employed in our deformation scheme. We demonstrate the performance of the proposed method both on real and synthetic sequences.     

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.     

Consistent segmentation of 3D models

This paper proposes a method to segment a set of models consistently. The method simultaneously segments models and creates correspondences between segments. First, a graph is constructed whose nodes represent the faces of every mesh, and whose edges connect adjacent faces within a mesh and corresponding faces in different meshes. Second, a consistent segmentation is created by clustering this graph, allowing for outlier segments that are not present in every mesh. The method is demonstrated for several classes of objects and used for two applications: symmetric segmentation and segmentation transfer.     

Cover geometry design using multiple convex hulls

We present a design method to create close-fitting customized covers for given three-dimensional (3D) objects such as cameras, toys and figurines. The system first computes clustering of the input vertices using multiple convex hulls, then generates multiple convex hulls using the results. It then outputs a cover geometry to set union operation of these hulls, and the resulting intersection curves are set as seam lines. However, as some of the regions created are not necessarily suitable for flattening, the user can design seam lines by drawing and erasing. The system flattens the patches of the target cover geometry after segmentation, allowing the user to obtain a corresponding 2D pattern and sew the shapes in actual fabric. This paper’s contribution lies in its proposal of a clustering method to generate multiple convex hulls, i.e., a set of convex hulls that individually cover part of the input mesh and together cover all of it. The method is based on vertex clustering to allow handling of mesh models with poor vertex connectivity such as those obtained by 3D scanning, and accommodates conventional meshes with multiple connected components and point-based models with no connectivity information. Use of the system to design actual covers confirmed that it functions as intended.     

Sparse Approximation of 3D Meshes Using the Spectral Geometry of the Hamiltonian Operator

The discrete Laplace operator is ubiquitous in spectral shape analysis, since its eigenfunctions are provably optimal in representing smooth functions defined on the surface of the shape. Indeed, subspaces defined by its eigenfunctions have been utilized for shape compression, treating the coordinates as smooth functions defined on the given surface. However, surfaces of shapes in nature often contain geometric structures for which the general smoothness assumption may fail to hold. At the other end, some explicit mesh compression algorithms utilize the order by which vertices that represent the surface are traversed, a property which has been ignored in spectral approaches. Here, we incorporate the order of vertices into an operator that defines a novel spectral domain. We propose a method for representing 3D meshes using the spectral geometry of the Hamiltonian operator, integrated within a sparse approximation framework. We adapt the concept of a potential function from quantum physics and incorporate vertex ordering information into the potential, yielding a novel data-dependent operator. The potential function modifies the spectral geometry of the Laplacian to focus on regions with finer details of the given surface. By sparsely encoding the geometry of the shape using the proposed data-dependent basis, we improve compression performance compared to previous results that use the standard Laplacian basis and spectral graph wavelets.     

面向模型验证的空间网格面的染色及显示技术

针对工程分析用的网格模型,以图论中的拓扑图为基础提出了一种空间网格面的染色算法.该算法对可平面图几何模型、非可平面图几何模型以及奇异几何模型均可染色.利用染色结果,给出了在AutoCAD平台上编程显示染色几何模型的方法.多项工程应用表明,该染色算法可靠、适应性强、染色效果好,可用于几何分析模型的验证.     

Modelling Cumulus Cloud Shape from a Single Image

Clouds are important components of the fascinating natural images. However, extracting cloud shapes from images remains a challenging task. This paper presents a calculation method for estimating the shape of a cumulus cloud from a single image suitable for flight simulations and games. The shape of the cloud is assumed to be symmetric. Based on this assumption, the intensities of pixels are correlated with the geometry of a cloud's surface via a simplified single scattering model. A propagation scheme is designed to derive the surface progressively, and mesh editing techniques are used to improve the surface. Finally, the cloud is represented by a particle system. The results show that the proposed method can generate realistic cumulus clouds that are similar to those found in the images in terms of the shape distribution.     

Priority-based encoding of triangle mesh connectivity for a known geometry

In certain practical situations, the connectivity of a triangle mesh needs to be transmitted or stored given a fixed set of 3D vertices that is known at both ends of the transaction (encoder/decoder). This task is different from a typical mesh compression scenario, in which the connectivity and geometry (vertex positions) are encoded either simultaneously or in reversed order (connectivity first), usually exploiting the freedom in vertex/triangle re-indexation. Previously proposed algorithms for encoding the connectivity for a known geometry were based on a canonical mesh traversal and predicting which vertex is to be connected to the part of the mesh that is already processed. In this paper, we take this scheme a step further by replacing the fixed traversal with a priority queue of open expansion gates, out of which in each step a gate is selected that has the most certain prediction, that is one in which there is a candidate vertex that exhibits the largest advantage in comparison with other possible candidates, according to a carefully designed quality metric. Numerical experiments demonstrate that this improvement leads to a substantial reduction in the required data rate in comparison with the state of the art.     

A Shrink Wrapping Approach to Remeshing Polygonal Surfaces

Due to their simplicity and flexibility, polygonal meshes are about to become the standard representation for surface geometry in computer graphics applications. Some algorithms in the context of multiresolution representation and modeling can be performed much more efficiently and robustly if the underlying surface tesselations have the special subdivision connectivity. In this paper, we propose a new algorithm for converting a given unstructured triangle mesh into one having subdivision connectivity. The basic idea is to simulate the shrink wrapping process by adapting the deformable surface technique known from image processing. The resulting algorithm generates subdivision connectivity meshes whose base meshes only have a very small number of triangles. The iterative optimization process that distributes the mesh vertices over the given surface geometry guarantees low local distortion of the triangular faces. We show several examples and applications including the progressive transmission of subdivision surfaces.     

Meshless thin-shell simulation based on global conformal parameterization

This paper presents a new approach to the physically-based thin-shell simulation of point-sampled geometry via explicit, global conformal point-surface parameterization and meshless dynamics. The point-based global parameterization is founded upon the rigorous mathematics of Riemann surface theory and Hodge theory. The parameterization is globally conformal everywhere except for a minimum number of zero points. Within our parameterization framework, any well-sampled point surface is functionally equivalent to a manifold, enabling popular and powerful surface-based modeling and physically-based simulation tools to be readily adapted for point geometry processing and animation. In addition, we propose a meshless surface computational paradigm in which the partial differential equations (for dynamic physical simulation) can be applied and solved directly over point samples via moving least squares (MLS) shape functions defined on the global parametric domain without explicit connectivity information. The global conformal parameterization provides a common domain to facilitate accurate meshless simulation and efficient discontinuity modeling for complex branching cracks. Through our experiments on thin-shell elastic deformation and fracture simulation, we demonstrate that our integrative method is very natural, and that it has great potential to further broaden the application scope of point-sampled geometry in graphics and relevant fields.     

Combinatorial mesh optimization

A new mesh optimization framework for 3D triangular surface meshes is presented, which formulates the task as an energy minimization problem in the same spirit as in Hoppe et al. (SIGGRAPH’93: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, 1993). The desired mesh properties are controlled through a global energy function including data attached terms measuring the fidelity to the original mesh, shape potentials favoring high quality triangles, and connectivity as well as budget terms controlling the sampling density. The optimization algorithm modifies mesh connectivity as well as the vertex positions. Solutions for the vertex repositioning step are obtained by a discrete graph cut algorithm examining global combinations of local candidates.     

Space variant image processing

This paper describes a graph-based approach to image processing, intended for use with images obtained from sensors having space variant sampling grids. The connectivity graph (CG) is presented as a fundamental framework for posing image operations in any kind of space variant sensor. Partially motivated by the observation that human vision is strongly space variant, a number of research groups have been experimenting with space variant sensors. Such systems cover wide solid angles yet maintain high acuity in their central regions. Implementation of space variant systems pose at least two outstanding problems. First, such a system must be active, in order to utilize its high acuity region; second, there are significant image processing problems introduced by the non-uniform pixel size, shape and connectivity. Familiar image processing operations such as connected components, convolution, template matching, and even image translation, take on new and different forms when defined on space variant images. The present paper provides a general method for space variant image processing, based on a connectivity graph which represents the neighbor-relations in an arbitrarily structured sensor. We illustrate this approach with the following applications: (1) Connected components is reduced to its graph theoretic counterpart. We illustrate this on a logmap sensor, which possesses a difficult topology due to the branch cut associated with the complex logarithm function. (2) We show how to write local image operators in the connectivity graph that are independent of the sensor geometry. (3) We relate the connectivity graph to pyramids over irregular tessalations, and implement a local binarization operator in a 2-level pyramid. (4) Finally, we expand the connectivity graph into a structure we call a transformation graph, which represents the effects of geometric transformations in space variant image sensors. Using the transformation graph, we define an efficient algorithm for matching in the logmap images and solve the template matching problem for space variant images. Because of the very small number of pixels typical of logarithmic structured space variant arrays, the connectivity graph approach to image processing is suitable for real-time implementation, and provides a generic solution to a wide range of image processing applications with space variant sensors.This research was supported by DARPA/ONR #N00014-90-C-0049 and AFOSR Life Sciences #88-0275. Please address all correspondence to Richard S. Wallace, NYU Robotics Research Laboratory, 715 Broadway 12th Floor, New York, NY 10003. This report is copyright ©1993 by the authors. This report is a revised draft of a report published as New York University Courant Institute of Mathematical Sciences Computer Science Technical Report (No. 589 and Robotics Report No. 256), October, 1991. Last revised October.     

Growing Self-Reconstruction Maps

In this paper, we propose a new method for surface reconstruction based on growing self-organizing maps (SOMs), called growing self-reconstruction maps (GSRMs). GSRM is an extension of growing neural gas (GNG) that includes the concept of triangular faces in the learning algorithm and additional conditions in order to include and remove connections, so that it can produce a triangular two-manifold mesh representation of a target object given an unstructured point cloud of its surface. The main modifications concern competitive Hebbian learning (CHL), the vertex insertion operation, and the edge removal mechanism. The method proposed is able to learn the geometry and topology of the surface represented in the point cloud and to generate meshes with different resolutions. Experimental results show that the proposed method can produce models that approximate the shape of an object, including its concave regions, boundaries, and holes, if any.      

A surface mesh deformation method near component intersections for high-fidelity design optimization

Aerodynamic shape optimization based on computational fluid dynamics (CFD) requires three steps: updating the geometry based on the design variables, updating the CFD surface mesh for the new geometry, and updating the CFD volume mesh based on the new surface mesh. While there are many tools available for the first and third steps, the methods available for the second step are insufficient for geometries that have intersecting components. For these geometries, the CFD surface mesh needs to be updated near component intersections to conform to the component geometries and the updated intersection curves. To address this need, we introduce a method that can deform the CFD surface mesh nodes near component intersections. The method can handle arbitrary design changes for each intersecting component as long as the geometric topology is unchanged. Furthermore, the method is suitable for gradient-based optimization because it smoothly deforms every CFD surface node without introducing topological changes in the CFD surface mesh. In this paper, we detail each step of the proposed method and visualize the range of design changes that can be achieved with this approach. Finally, we use the proposed method in an aerodynamic shape optimization problem to optimize the wing-body intersection of the DLR-F6 configuration. These results demonstrate the effectiveness of the proposed method in a high-fidelity design optimization framework. The method applies to both structured and unstructured CFD meshes and makes it possible to use computer-aided design and conceptual design geometry tools within high-fidelity design optimization.