A Moving Grid Framework for Geometric Deformable Models

Geometric deformable models based on the level set method have become very popular in the last decade. To overcome an inherent limitation in accuracy while maintaining computational efficiency, adaptive grid techniques using local grid refinement have been developed for use with these models. This strategy, however, requires a very complex data structure, yields large numbers of contour points, and is inconsistent with the implementation of topology-preserving geometric deformable models (TGDMs). In this paper, we investigate the use of an alternative adaptive grid technique called the moving grid method with geometric deformable models. In addition to the development of a consistent moving grid geometric deformable model framework, our main contributions include the introduction of a new grid nondegeneracy constraint, the design of a new grid adaptation criterion, and the development of novel numerical methods and an efficient implementation scheme. The overall method is simpler to implement than using grid refinement, requiring no large, complex, hierarchical data structures. It also offers an extra benefit of automatically reducing the number of contour vertices in the final results. After presenting the algorithm, we demonstrate its performance using both simulated and real images. This work was supported in part by NSF/ERC Grant CISST#9731748 and by NIH/NINDS Grant R01NS37747.     

A level-set approach for the metamorphosis of solid models

We present a new approach to 3D shape metamorphosis. We express the interpolation of two shapes as a process where one shape deforms to maximize its similarity with another shape. The process incrementally optimizes an objective function while deforming an implicit surface model. We represent the deformable surface as a level set (iso-surface) of a densely sampled scalar function of three dimensions. Such level-set models have been shown to mimic conventional parametric deformable surface models by encoding surface movements as changes in the grayscale values of a volume data set. Thus, a well-founded mathematical structure leads to a set of procedures that describes how voxel values can be manipulated to create deformations that are represented as a sequence of volumes. The result is a 3D morphing method that offers several advantages over previous methods, including minimal need for user input, no model parameterization, flexible topology, and subvoxel accuracy     

Adaptive physics based tetrahedral mesh generation using level sets

We present a tetrahedral mesh generation algorithm designed for the Lagrangian simulation of deformable bodies. The algorithm’s input is a level set (i.e., a signed distance function on a Cartesian grid or octree). First a bounding box of the object is covered with a uniform lattice of subdivision-invariant tetrahedra. The level set is then used to guide a red green adaptive subdivision procedure that is based on both the local curvature and the proximity to the object boundary. The final topology is carefully chosen so that the connectivity is suitable for large deformation and the mesh approximates the desired shape. Finally, this candidate mesh is compressed to match the object boundary. To maintain element quality during this compression phase we relax the positions of the nodes using finite elements, masses and springs, or an optimization procedure. The resulting mesh is well suited for simulation since it is highly structured, has topology chosen specifically for large deformations, and is readily refined if required during subsequent simulation. We then use this algorithm to generate meshes for the simulation of skeletal muscle from level set representations of the anatomy. The geometric complexity of biological materials makes it very difficult to generate these models procedurally and as a result we obtain most if not all data from an actual human subject. Our current method involves using voxelized data from the Visible Male [1] to create level set representations of muscle and bone geometries. Given this representation, we use simple level set operations to rebuild and repair errors in the segmented data as well as to smooth aliasing inherent in the voxelized data.     

Sub-Voxel Topology Control for Level-Set Surfaces

Active contour models are an efficient, accurate, and robust tool for the segmentation of 2D and 3D image data.In particular, geometric deformable models (GDM) that represent an active contour as the level set of an implicitfunction have proven to be very effective. GDMs, however, do not provide any topology control, i.e. contours maymerge or split arbitrarily and hence change the genus of the reconstructed surface. This behavior is inadequate insettings like the segmentation of organic tissue or other objects whose genus is known beforehand. In this paperwe describe a novel method to overcome this limitation while still preserving the favorable properties of the GDMsetup. We achieve this by adding (sparse) topological information to the volume representation at locations whereit is necessary to locally resolve topological ambiguities. Since the sparse topology information is attached to theedges of the voxel grid, we can reconstruct the interfaces where the deformable surface touches itself at sub-voxelaccuracy. We also demonstrate the efficiency and robustness of our method.     

Hierarchical topology-preserving simplification of terrains

We present an algorithm for simplifying terrain data that preserves topology. We use a decimation algorithm that simplifies the given data set using hierarchical clustering. Topology constraints, along with local error metrics, are used to ensure topology-preserving simplification and to compute precise error bounds in the simplified data. The earths mover distance is used as a global metric to compute the degradation in topology as the simplification proceeds. Experiments with both analytic and real terrain data are presented. Results indicate that one can obtain significant simplification with low errors without losing topology information.     

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.     

蒙太奇网格融合

三维物体融合是一种新的几何造型方法,它利用三维模型之间的剪贴操作从两个或多个现有的几何模型中光滑融合出新的几何模型.提出了一种基于局部调和映射的三维网格蒙太奇融合新方法.首先利用网格上的近似等距线算法来抽取出待融合区域,然后对两个待融合区域进行带内孔的调和映射参数化,最后通过拓扑合并和融合控制来实现网格的光滑融合.与原有的基于全局调和映射的融合方法相比,新方法的算法效率大幅度提升,求解时间不再随融合模型顶点数的增加而呈指数增长;减少了二维网格拓扑合并中奇异情况出现的概率,提高了算法的稳定性;被剪切网格的细节得到完整保留;消除了原算法对融合区域拓扑的限制.实验结果表明,此方法可以用来生成许多三维动画中的特殊夸张造型效果,在影视动画中具有应用价值.     

A tolerant approach to reconstruct topology from unorganized trimmed surfaces

Presented in this paper is a topology reconstruction algorithm from a set of unorganized trimmed surfaces. Error-prone small geometric elements are handled to give proper topological information. It gives complete topology to topologically complete models, and it is also tolerant to incomplete models. The proposed algorithm is vertex-based in that clues for topological information are searched from the set of vertices first, not from that of edges.     

Topology-preserving simplification of 2D nonmanifold meshes with embedded structures

Mesh simplification has received tremendous attention over the years. Most of the previous work in this area deals with a proper choice of error measures to guide the simplification. Preserving the topological characteristics of the mesh and possibly of data attached to the mesh is a more recent topic and the subject of this paper. We introduce a new topology-preserving simplification algorithm for triangular meshes, possibly nonmanifold, with embedded polylines. In this context, embedded means that the edges of the polylines are also edges of the mesh. The paper introduces a robust test to detect if the collapse of an edge in the mesh modifies either the topology of the mesh or the topology of the embedded polylines. This validity test is derived using combinatorial topology results. More precisely, we define a so-called extended complex from the input mesh and the embedded polylines. We show that if an edge collapse of the mesh preserves the topology of this extended complex, then it also preserves both the topology of the mesh and the embedded polylines. Our validity test can be used for any 2-complex mesh, including nonmanifold triangular meshes, and can be combined with any previously introduced error measure. Implementation of this validity test is described. We demonstrate the power and versatility of our method with scientific data sets from neuroscience, geology, and CAD/CAM models from mechanical engineering.