Discrete shading of three-dimensional objects from medial axis transform

In this paper, we present a discrete shading technique using medial axis transform (MAT) of 3D binary image data based on digital generalized octagonal distances. Our method is computationally attractive as it does not require the explicit computation of surface normals. We have compared our results with images rendered from voxel and octree representations while using analytical surface rendered images as bench marks. The quality of rendering by our method is certainly superior to those obtained from voxel and octree representations.     

Constructing medial axis transform of planar domains with curved boundaries

The paper describes an algorithm for generating an approximation of the medial axis transform (MAT) for planar objects with free form boundaries. The algorithm generates the MAT by a tracing technique that marches along the object boundary rather than the bisectors of the boundary entities. The level of approximation is controlled by the choice of the step size in the tracing procedure. Criteria based on distance and local curvature of boundary entities are used to identify the junction or branch points and the search for these branch points is more efficient than while tracing the bisectors. The algorithm works for multiply connected objects as well. Results of implementation are provided.     

MATHSM: medial axis transform toward high speed machining of pockets

The pocketing operation is a fundamental procedure in NC machining. Typical pocketing schemes compute uniform successive offsets or parallel cuts of the outline of the pocket, resulting in a toolpath with C¹ discontinuities. These discontinuities render the toolpath quite impractical in the context of high speed machining (HSM).This work addresses and fully resolves the need for a C¹ continuous toolpath in HSM and offers MATHSM, a C¹ continuous toolpath for arbitrary C¹ continuous pockets. MATHSM automatically generates a C¹ continuous toolpath that consists of primarily circular arcs while maximizing the radii of the generated arcs and, therefore, minimizing the exerted radial acceleration. MATHSM is especially suited for machining of elongated narrow pockets.     

3D block-based medial axis transform and chessboard distance transform based on dominance

Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N³, our parallel algorithm can be run in O(logN) time using N³ processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size.     

New reduced discrete Euclidean nD medial axis with optimal algorithm

Skeletons have been playing an important role in shape analysis since the introduction of the medial axis in the sixties. The original medial axis definition is in the continuous Euclidean space. It is a skeleton with the following characteristics: centered, thin, homotopic (it has the same topology as the object), and reversible (sufficient for the reconstruction of the object). The discrete version of the Euclidean medial axis (MA) is also reversible and centered, but no longer homotopic nor thin. The combination of the MA with homotopic thinning algorithms can result in a topology preserving, reversible skeleton. However, such combination may generate thicker skeletons, and the choice of the thinning algorithm is not obvious. A robust and well defined framework for fast homotopic thinning available in the literature is defined in the domain of abstract complexes. Since the abstract complexes are represented in a doubled resolution grid, some authors have extended the MA to a doubled resolution grid and defined the discrete Euclidean medial axis in higher resolution (HMA). The HMA can be combined with the thinning framework defined on abstract complexes. Other authors have given an alternative definition of medial axis, which is a subset of the MA, called reduced discrete medial axis (RDMA). The RDMA is reversible, thinner than the MA, and it can be computed in optimal time. In this paper, we extend the RDMA to the doubled resolution grid and we define the high-resolution RDMA (HRDMA). We provide an optimal algorithm to compute the HRDMA. The HRDMA can be combined with the thinning framework defined on abstract complexes. The skeleton obtained by such combination is provided with strong characteristics, not found in the literature.     

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.     

Constructive generation of the medial axis for solid models

The medial axis (MA) is a simplified representation of complicated models which is widely used in current research. However, the efficient generation of the MA for complicated solid models continues to pose a challenge. In this study, a constructive approach for the generation of the MA is proposed for solid models after they are voxelized. With this method, the MA of the model constructed from two operand models via a Boolean operation is efficiently generated by merging the MAs of the operand models in a certain way, instead of regenerating them from scratch. To support the proposed method, the affected region of the resultant model is computed first using a Boolean operation. Second, only the MA in the affected region is regenerated by distance dilation. Third, the complete MA of the resultant model is constructed by combining the newly generated MA with the unchanged MAs of the operand models. In this study, the accuracy and complexity are analyzed for the final MA and some examples are given to illustrate the performance of the proposed method.     

Use of medial axis transforms for computing normals at boundary points

Medial axis transform (MAT) is well known for object representation. It is interesting to explore its use in different kinds of computations. In this paper an algorithm has been proposed for computation of normals at the boundaries of two-dimensional objects based on their MATs. In this technique, there is no requirement of linking boundary points during the computation compared to other existing techniques. The added advantage in the computation is that the computation can be restricted purely in the integer domain.     

An approach for extracting non-manifold mid-surfaces of thin-wall solids using chordal axis transform

This paper proposes an approach for extracting non-manifold mid-surfaces of thin-wall solids using the chordal axis transform (CAT) (Prasad in CNLS Newsletter—Center for Nonlinear Studies, Los Alamos National Laboratory, vol 139, 1997). There is great demand for extracting mid-surfaces as it is used in dimension reduction. Quadros and Shimada previously used CAT in extracting 2-manifold mid-surfaces of a particular type of thin-wall solids. The proposed approach is an extension of the previous approach (Quadros and Shimada in 11th international meshing roundtable, 2002) in order to extract non-manifold mid-surfaces of general thin-wall solids. The three steps involved in extracting the mid-surface of a thin-wall solid are: (1) generating a tet mesh of a thin-wall solid without inserting interior nodes; (2) generating a raw mid-surface by smart cutting of tets; and (3) remeshing the raw mid-surface via smart clean-up. In the proposed approach, a discrete model (i.e., a tet mesh without any interior nodes) is used instead of working directly on a CAD model. The smart cutting of tets using CAT yields correct topology at the non-manifold region in the raw mid-surface. As the raw mid-surface is not directly suitable for engineering purposes, it is trimmed using a smart clean-up procedure and then remeshed. The proposed approach has been implemented using C++ in commercial ALGOR finite element analysis software. The proposed approach is computationally efficient and has shown effective results on industrial models.     

Medial axis of a planar region by offset self-intersections

The medial axis (MA) of a planar region is the locus of those maximal disks contained within its boundary. This entity has many CAD/CAM applications. Approximations based on the Voronoi diagram are efficient for linear-arc boundaries, but such constructions are more difficult if the boundary is free. This paper proposes an algorithm for free-form boundaries that uses the relation between MA and offsets. It takes the curvature information from the boundary in order to find the self-intersections of successive offset curves. These self-intersection points belong to the MA and can be interpolated to obtain an approximation in Bézier form. This method also approximates the medial axis transform by using the offset distance to each self-intersection.     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

Computation of the medial axis of planar domains based on saddle point programming

This paper presents a saddle point programming approach to compute the medial axis (MA). After exploring the saddle point properties of the medial axis transform (MAT), the mathematical programming method is employed to establish the saddle point programming model of the MAT. By using the optimal conditions, i.e., the number and distribution of the tangent points between the boundary and medial axis disk, the one- and two-dimensional saddle point algorithms are developed. In order to determine the branch point, it is better to consider its generating mechanism. Here, we identify the branch point according to the sudden changes of the solutions to the one-dimensional saddle point algorithm. Hence, all the regular and irregular points of MA can be computed by a general algorithm, and it is proved to be efficient and accurate by the numerical examples.     

Blends of canal surfaces from polyhedral medial transform representations

We present a new method for constructing G¹ blending surfaces between an arbitrary number of canal surfaces. The topological relation of the canal surfaces is specified via a convex polyhedron and the design technique is based on a generalization of the medial surface transform. The resulting blend surface consists of trimmed envelopes of one- and two-parameter families of spheres. Blending the medial surface transform instead of the surface itself is shown to be a powerful and elegant approach for blend surface generation. The performance of our approach is demonstrated by several examples.     

A divide and conquer algorithm for medial surface calculation of planar polyhedra

The Medial Axis Transform surface, (or MAT or MS) is proving to be a useful tool for several applications and geometric reasoning tasks. However, calculation of the MAT is a time-consuming task and the benefits of the mathematical-based tool are offset by the cost of the calculation. This paper presents a method for medial surface calculation which uses subdivision to simplify the problem and hence speed up the calculation, a so-called ‘divide-and-conquer’ approach. The basis for this is a modification of the dual structure of the original object. As the calculation proceeds this structure is broken up into sub-pieces each representing a simpler sub-part of the MAT. Perhaps more importantly, this method creates a correct node decomposition of the dual structure. The paper goes on to demonstrate some applications of the results for geometric tasks, specifically offsetting and model subdivision, which are normally expensive but are simpler based on the MAT calculation results.     

Computation of medial axis and offset curves of curved boundaries in planar domain

In this paper, we begin our research from the generating theory of the medial axis. The normal equidistant mapping relationships between two boundaries and its medial axis have been proposed based on the moving Frenet frames and Cesaro’s approach of the differential geometry. Two pairs of adjoint curves have been formed and the geometrical model of the medial axis transform of the planar domains with curved boundaries has been established. The relations of position mapping, scale transform and differential invariants between the curved boundaries and the medial axis have been investigated. Based on this model, a tracing algorithm for the computation of the medial axis has been generated. In order to get the accurate medial axis and branch points, a Two_Tangent_Points_Circle algorithm and a Three_Tangent_Points_Circle algorithm have been generated, which use the results of the tracing algorithm as the initial values to make the iterative process effective. These algorithms can be used for the computation of the medial axis effectively and accurately. Based on the medial axis transform and the envelope theory, the trimmed offset curves of curved boundaries have been investigated. Several numerical examples are given at the end of the paper.     

一种改进的中轴骨架三维模型检索算法

针对三维模型检索算法性能较低的问题,提出了一种改进的中轴骨架三维模型检索算法。     

On the medial surface approximations of extrusions

Generating the medial surface for a general boundary representation model raises several difficulties. Problems might emerge from the complexity of the resulting equations, singularities caused by unforeseen relative boundary element positions and orientations, etc. The majority of the current algorithms are based on the topology of the boundary representation model and produce wireframes composed of straight lines regardless of the real medial surfaces. Many of the solids used in engineering can be represented by extrusions, delimited by a cross-section and an extrusion distance. This paper develops a fast and efficient method for creating the facetted approximations of the medial surfaces of extrusions generated by sweeping along the normal direction to the generating cross-section.

Medial axis transform on mesh-connected computers with hyperbus broadcasting

To represent a region of a digital image as the union of maximal upright squares contained in the region is called the medial axis transform. In this paper, we present anO(logn) time parallel algorithm for the medial axis transform of ann×n binary image on an SIMD mesh-connected computers with hyperbus broadcasting usingn ³ processors.