Medial Axis Construction in Three Dimensions and its Application to Mesh Generation

An algorithm for the construction of the medial axis of a three-dimensional body given by a triangulation of its bounding surface is described. The indirect construction is based on the Delaunay-triangulation of a set of sample points on the bounding surface. The point set is refined automatically so as to capture the correct topology of the medial axis. The computed medial axis (or better medial surface) is then used for hex-dominant mesh generation. Quad-dominant meshes are generated on the medial subfaces first and extruded to the boundary of the body at both sides. The resulting single cell layer is subdivided in direction normal to the boundary, yielding columns of hexahedral and three-sided prismatic cells. The resulting volume mesh is orthogonal at the boundary and ‘semi-structured’ between boundary and medial surface. Mixed cell types (tets, pyramids, degenerate hexahedra) may result along the medial surface. An advancing front algorithm (paving) is used for meshing the subfaces of the medial surface. Development of the mesh generator has not been fully completed with respect to degenerate parts of the medial axis. First medium-complexity bodies have been meshed, however, showing moderate meshing times.     

Deformable M-Reps for 3D Medical Image Segmentation

M-reps (formerly called DSLs) are a multiscale medial means for modeling and rendering 3D solid geometry. They are particularly well suited to model anatomic objects and in particular to capture prior geometric information effectively in deformable models segmentation approaches. The representation is based on figural models, which define objects at coarse scale by a hierarchy of figures—each figure generally a slab representing a solid region and its boundary simultaneously. This paper focuses on the use of single figure models to segment objects of relatively simple structure.A single figure is a sheet of medial atoms, which is interpolated from the model formed by a net, i.e., a mesh or chain, of medial atoms (hence the name m-reps), each atom modeling a solid region via not only a position and a width but also a local figural frame giving figural directions and an object angle between opposing, corresponding positions on the boundary implied by the m-rep. The special capability of an m-rep is to provide spatial and orientational correspondence between an object in two different states of deformation. This ability is central to effective measurement of both geometric typicality and geometry to image match, the two terms of the objective function optimized in segmentation by deformable models. The other ability of m-reps central to effective segmentation is their ability to support segmentation at multiple levels of scale, with successively finer precision. Objects modeled by single figures are segmented first by a similarity transform augmented by object elongation, then by adjustment of each medial atom, and finally by displacing a dense sampling of the m-rep implied boundary. While these models and approaches also exist in 2D, we focus on 3D objects.The segmentation of the kidney from CT and the hippocampus from MRI serve as the major examples in this paper. The accuracy of segmentation as compared to manual, slice-by-slice segmentation is reported.     

HEXHOOP: Modular Templates for Converting a Hex-Dominant Mesh to an ALL-Hex Mesh

This paper presents a new mesh conversion template called HEXHOOP, which fully automates a con-version from a hex-dominant mesh to an all-hex mesh. A HEXHOOP template subdivides a hex/prism/pyramid element into a set of smaller hex elements while main-taining the topological conformity with neighboring elements. A HEXHOOP template is constructed by assembling sub-templates, cores and caps. A dicing template for a hex and a prism is constructed by choosing the appropriate combination of a core and caps. A template that dices a pyramid without losing conformity to the adjacent element is derived from a HEXHOOP template. Some experimental results show that the HEXHOOP templates successfully convert a hex-dominant mesh into an all-hex mesh. ID="A1" Correspondence and offprint requests to: K. Shimada, Department of Mechanical Engineering, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213–3890, USA. E-mail: shimada@cmu.edu     

Distance functions and skeletal representations of rigid and non-rigid planar shapes

Shape skeletons are fundamental concepts for describing the shape of geometric objects, and have found a variety of applications in a number of areas where geometry plays an important role. Two types of skeletons commonly used in geometric computations are the straight skeleton of a (linear) polygon, and the medial axis of a bounded set of points in the k-dimensional Euclidean space. However, exact computation of these skeletons of even fairly simple planar shapes remains an open problem.In this paper we propose a novel approach to construct exact or approximate (continuous) distance functions and the associated skeletal representations (a skeleton and the corresponding radius function) for solid 2D semi-analytic sets that can be either rigid or undergoing topological deformations. Our approach relies on computing constructive representations of shapes with R-functions that operate on real-valued halfspaces as logic operations. We use our approximate distance functions to define a new type of skeleton, i.e, the C-skeleton, which is piecewise linear for polygonal domains, generalizes naturally to planar and spatial domains with curved boundaries, and has attractive properties. We also show that the exact distance functions allow us to compute the medial axis of any closed, bounded and regular planar domain. Importantly, our approach can generate the medial axis, the straight skeleton, and the C-skeleton of possibly deformable shapes within the same formulation, extends naturally to 3D, and can be used in a variety of applications such as skeleton-based shape editing and adaptive motion planning.     

Mesh Movement and Metamorphosis

Mesh coarsening and mesh enrichment are combined with a r-refinement scheme to produce a flexible approach for mesh adaptation of time evolving domains. The robustness of this method depends heavily upon maintaining mesh quality during each adaptation cycle. This in turn is inlfuenced by the ability to identify and remove badly shaped elements after the r-refinement stage. Measures of both element quality and element deformation can be defined in terms of unitarily invariant matrix norms. The construction of these element deformation and quality measures is described, and details are provided of the three stages of the adaptation cycle. ID="A1" Correspondence and offprint requests to: Dr Timothy J. Baker, Room D302, Mechanical and Aerospace Engineering Department, Engineering Quadrangle, Princeton University, Princeton, NJ 08544, USA. E-mail: baker@tornado.princeton.edu     

LSMAT Least Squares Medial Axis Transform

The medial axis transform has applications in numerous fields including visualization, computer graphics, and computer vision. Unfortunately, traditional medial axis transformations are usually brittle in the presence of outliers, perturbations and/or noise along the boundary of objects. To overcome this limitation, we introduce a new formulation of the medial axis transform which is naturally robust in the presence of these artefacts. Unlike previous work which has approached the medial axis from a computational geometry angle, we consider it from a numerical optimization perspective. In this work, we follow the definition of the medial axis transform as ‘the set of maximally inscribed spheres’. We show how this definition can be formulated as a least squares relaxation where the transform is obtained by minimizing a continuous optimization problem. The proposed approach is inherently parallelizable by performing independent optimization of each sphere using Gauss–Newton, and its least‐squares form allows it to be significantly more robust compared to traditional computational geometry approaches. Extensive experiments on 2D and 3D objects demonstrate that our method provides superior results to the state of the art on both synthetic and real‐data.     

Automatic Reconstruction of Unstructured 3D Data: Combining a Medial Axis and Implicit Surfaces

This paper presents a new method that combines a medial axis and implicit surfaces in order to reconstruct a 3D solid from an unstructured set of points scattered on the object's surface. The representation produced is based on iso-surfaces generated by skeletons, and is a particularly compact way of defining a smooth free-form solid. The method is based on the minimisation of an energy representing a “distance” between the set of data points and the iso-surface, resembling previous reserach¹⁹. Initialisation, however, is more robust and efficient since there is computation of the medial axis of the set of points. Instead of subdividing existing skeletons in order to refine the object's surface, a new reconstruction algorithm progressively selects skeleton-points from the pre- computed medial axis using an heuristic principle based on a “local energy” criterion. This drastically speeds up the reconstruction process. Moreover, using the medial axis allows reconstruction of objects with complex topology and geometry, like objects that have holes and branches or that are composed of several connected components. This process is fully automatic. The method has been successfully applied to both synthetic and real data.     

Two-Dimensional Parallel Thinning Algorithms Based on Critical Kernels

Critical kernels constitute a general framework in the category of abstract complexes for the study of parallel thinning in any dimension. The most fundamental result in this framework is that, if a subset Y of X contains the critical kernel of X, then Y is guaranteed to have “the same topology as X”. Here, we focus on 2D structures in spaces of two and three dimensions. We introduce the notion of crucial pixel, which permits to link this work with the framework of digital topology. We prove simple local characterizations, which allow us to express thinning algorithms by way of sets of masks. We propose several new parallel algorithms, which are both fast and simple to implement, that yield symmetrical or non-symmetrical skeletons of 2D objects in 2D or 3D grids. We prove some properties of these skeletons, related to topology preservation, to minimality, and to the inclusion of the topological axis. The latter may be seen as a generalization of the medial axis. We also show how to use critical kernels in order to provide simple proofs of the topological soundness of existing thinning schemes. Finally, we clarify the link between critical kernels, minimal non-simple sets, and P-simple points.

Parallel Algorithm Oriented Mesh Database

In this paper, we present a new point of view for efficiently managing general parallel mesh representations. Taking as a slarting point the Algorithm Oriented Mesh Database (AOMD) of [1] we extend the concepts to a parallel mesh representation. The important aspects of parallel adaptivity and dynamic load balancing are discussed. We finally show how AOMD can be effectively interfaced with mesh adaptive partial differential equation solvers. Results of the calculation of an elasticity problem and of a transient fluid dynamics problem involving thousands of mesh refinements, and load balancings are finally presented. ID="A1" Correspondence and offprint requests to: J. Remacle, Scientific Computation Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA. E-mail: remacle@scorec.rpi.edu     

Mixed Dimensional Coupling in Finite Element Stress Analysis

Many analysis models utilize finite elements of reduced dimension. However, to capture stress concentrations at local details, it would be desirable to combine the reduced dimensional element types with higher dimensional elements in a single finite element model. It is therefore important in such cases to integrate into the analyses some scheme for coupling the element types that conforms to the governing equations of the problem. In this paper, a novel method that can correctly couple beams to solids, beams to shells and shells to solids for elastic problems is presented. The approach adopted is to equate the work done on either side of the interface between dimensions, and this leads to multi-point constraint equations, thus providing a relationship among nodal degrees of freedom between the differing element types. Example results show that the proposed technique does not introduce any spurious stresses at the dimensional interfaces. ID="A1" Correspondence and offprint requests to: C. G. Armstrong, School of Mechanical and Manufacturing Engineering, The Queen's University of Belfast, Ashby Building, Stranmillis Road, Belfast BT9 5AH, Northern Ireland. E-mail: c.armstrong@qub.ac.uk     

An algorithm for the medial axis transform of 3D polyhedral solids

The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another, even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of the axis are found by traversing closed loops of vertices and edges. Representation of the MA and its associated radius function is addressed, and pseudocode for the algorithm is given along with recommended optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes     

Dimensional Reduction of Surface Models for Analysis

This paper describes a set of procedures by which an analyst can idealise slender 2D shell structures for linear static analysis using reduced-dimensional beam finite elements. The first step is the development of the topological operations that are necessary to achieve the desired dimensionally reduced representation. Next, the automatic derivation of necessary geometric and physical properties of the reduced dimensional entities are described, together with the application of appropriate coupling constraints between dimensions. Dimensional reduction of shell models involves finding areas of the geometric model whose dimensions are such that this region may be represented in an analysis model with a 1D beam. Using the medial axis transform, geometric measures are defined for identifying such areas in the geometric model. However, topological features of the model and its medial axis were also identified as significant in the automation of dimensional reduction. The application of the medial axis transform to automatic dimensional reduction is described and example models given.     

Computing medial axes of generic 3D regions bounded by B-spline surfaces

A new approach is presented for computing the interior medial axes of generic regions in R³ bounded by C⁽⁴⁾-smooth parametric B-spline surfaces. The generic structure of the 3D medial axis is a set of smooth surfaces along with a singular set consisting of edge curves, branch curves, fin points and six junction points. In this work, the medial axis singular set is first computed directly from the B-spline representation using a collection of robust higher order techniques. Medial axis surfaces are computed as a time trace of the evolving self-intersection set of the boundary under the the eikonal (grassfire) flow, where the bounding surfaces are dynamically offset along the inward normal direction. The eikonal flow results in special transition points that create, modify or annihilate evolving curve fronts of the (self-) intersection set. The transition points are explicitly identified using the B-spline representation. Evolution of the (self-) intersection set is computed by adapting a method for tracking intersection curves of two different surfaces deforming over generalized offset vector fields. The proposed algorithm accurately computes connected surfaces of the medial axis as well its singular set. This presents a complete solution along with accurate topological structure.     

Mesh size functions for implicit geometries and PDE-based gradient limiting

Mesh generation and mesh enhancement algorithms often require a mesh size function to specify the desired size of the elements. We present algorithms for automatic generation of a size function, discretized on a background grid, by using distance functions and numerical PDE solvers. The size function is adapted to the geometry, taking into account the local feature size and the boundary curvature. It also obeys a grading constraint that limits the size ratio of neighboring elements. We formulate the feature size in terms of the medial axis transform, and show how to compute it accurately from a distance function. We propose a new Gradient Limiting Equation for the mesh grading requirement, and we show how to solve it numerically with Hamilton–Jacobi solvers. We show examples of the techniques using Cartesian and unstructured background grids in 2D and 3D, and applications with numerical adaptation and mesh generation for images.

Generating subdivision surfaces from profile curves

The construction of freeform models has always been a challenging task. A popular approach is to edit a primitive object such that its projections conform to a set of given planar curves. This process is tedious and relies very much on the skill and experience of the designer in editing 3D shapes. This paper describes an intuitive approach for the modeling of freeform objects based on planar profile curves. A freeform surface defined by a set of orthogonal planar curves is created by blending a corresponding set of sweep surfaces. Each of the sweep surfaces is obtained by sweeping a planar curve about a computed axis. A Catmull-Clark subdivision surface interpolating a set of data points on the object surface is then constructed. Since the curve points lying on the computed axis of the sweep will become extraordinary vertices of the subdivision surface, a mesh refinement process is applied to adjust the mesh topology of the surface around the axis points. In order to maintain characteristic features of the surface defined with the planar curves, sharp features on the surface are located and are retained in the mesh refinement process. This provides an intuitive approach for constructing freeform objects with regular mesh topology using planar profile curves.     

Top-k queries on temporal data

The database community has devoted extensive amount of efforts to indexing and querying temporal data in the past decades. However, insufficient amount of attention has been paid to temporal ranking queries. More precisely, given any time instance t, the query asks for the top-k objects at time t with respect to some score attribute. Some generic indexing structures based on R-trees do support ranking queries on temporal data, but as they are not tailored for such queries, the performance is far from satisfactory. We present the Seb-tree, a simple indexing scheme that supports temporal ranking queries much more efficiently. The Seb-tree answers a top-k query for any time instance t in the optimal number of I/Os in expectation, namely, O(log_B \fracNB+\frackB){O\left({\rm log}_B\,\frac{N}{B}+\frac{k}{B}\right)} I/Os, where N is the size of the data set and B is the disk block size. The index has near-linear size (for constant and reasonable k _max values, where k _max is the maximum value for the possible values of the query parameter k), can be constructed in near-linear time, and also supports insertions and deletions without affecting its query performance guarantee. Most of all, the Seb-tree is especially appealing in practice due to its simplicity as it uses the B-tree as the only building block. Extensive experiments on a number of large data sets, show that the Seb-tree is more than an order of magnitude faster than the R-tree based indexes for temporal ranking queries.