Geometry of 3D MAT and its application to moulding surfaces

This paper investigates the differential geometry of 3D MAT (medial axis transform) using the moving frame and differential form. After constructing the mapping relation and moving frames around both the MA (medial axis) point and the associated boundary points, various curves are defined to serve as carriers for the study. Based on analysis of the infinitesimal translation and rotation of the moving frames, the relations of distance differentials, rotation vectors and differential invariants are derived. Furthermore, a special case in the 3D MAT, the normal form, is defined for the moulding surfaces, where the 3D problem can be converted into a 2D one.     

Skeletonisation of three-dimensional object using generalized potential field

In this paper, the potential-based skeletonization approach for 2D medial axis transform (MAT), which identifies object skeleton as potential valleys using a Newtonian potential model in place of the distance function, is generalized to three dimensions. The generalized potential functions given by Chung (1998), which decay faster with distance than the Newtonian potential, is used for the 3D case. The efficiency of the proposed approach results from the fact that these functions and their gradients can be obtained in closed forms for polyhedral surfaces. According to the simulation results, the skeletons obtained with the proposed approach are closely related to the corresponding MAT skeletons. While the medial axis (surface) is 2D in general for a 3D object, the potential valleys, being one-dimensional, form a more realistic skeleton. Other desirable attributes of the algorithm include stability against perturbations of the object boundary, the flexibility to obtain partial skeleton directly, and low time complexity.     

A medial axis transformation for grayscale pictures

Blum's medial axis transformation (MAT) for binary pictures yields medial axis points that lie midway between opposite borders of a region or along angle bisectors. This note discusses a generalization of the MAT in which a score is computed for each point P of a grayscale picture based on the gradient magnitudes at pairs of points that have P as their midpoint. These scores are high at points that lie midway between pairs of antiparallel edges or along angle bisectors, so that they define a MAT-like ``skeleton,' which we may call the GRADMAT. However, this skeleton is rather sensitive to the presence of noise edges or to irregularities in the region edges, and it also is subject to artifacts created by pairs of edges belonging to different objects.     

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.     

Skewed rotational symmetry detection from a 2D line drawing of a 3D polyhedral object

This paper introduces a new algorithm for detecting skewed rotational symmetry in a 2D line drawing of a 3D polyhedral object by locating the possibly-multiple symmetry axes. The drawing is converted into an edge–vertex graph from which the algorithm finds the faces of the object and the sets of topologically symmetric edges and vertices. It then checks that each set of vertices is rotationally symmetric geometrically by analyzing the distribution of the vertices around the circumference of the best-fit ellipse. The object is rotationally skewed symmetric if the best fit ellipses of all the vertex sets have parallel axes, equal ratio of major radius to minor radius and centers on the axis of rotation. A tolerance is used in the calculation to allow for inaccuracies in the line drawings. A set of experimental results is presented showing that the algorithm works well.     

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to improve their approximations. Voronoi diagrams turn out to be useful for this approximation. Although it is known that Voronoi vertices for a sample of points from a curve in 2D approximate its medial axis, a similar result does not hold in 3D. Recently, it has been discovered that only a subset of Voronoi vertices converge to the medial axis as sample density approaches infinity. However, most applications need a nondiscrete approximation as opposed to a discrete one. To date no known algorithm can compute this approximation straight from the Voronoi diagram with a guarantee of convergence. We present such an algorithm and its convergence analysis in this paper. One salient feature of the algorithm is that it is scale and density independent. Experimental results corroborate our theoretical claims.     

Shape transformation by boundary representation interpolation: A recursive approach to establishing face correspondences

The issues relating to the shape transformation problem are discussed and a new algorithm is presented for computing the transformation of one shape into another. In this algorithm, the boundary definitions of the two initial shapes are used and a mapping is established between the vertices and edges of the respective objects. New vertices and edges are introduced into the object definitions when necessary to establish a one-to-one vertex correspondence and to match connectivity relationships between vertices. These can then be used to do a vertex-to-vertex interpolation that maintains valid polyhedral topologies for all of the intermediate shapes. The algorithm establishes a mapping between areas of the object such that adjacency relationships are preserved. These areas are recursively subdivided so that adjacency relationships of subareas are also preserved. During subdivision, vertices and edges are added to the boundaries of subareas so that a one-to-one mapping is established between them. Subdivision continues until each subarea consists of a single face. The algorithm presented works for objects that are topologically equivalent to spheres and can easily be extended to other pairs of objects as long as they are topologically equivalent to each other.     

Approximate medial axis as a Voronoi subcomplex

Medial axis as a compact representation of shapes has evolved as an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to approximate them. One line of research considers the point cloud representation of the boundary surface of a solid and then attempts to compute an approximate medial axis from this point sample. It is known that the Voronoi vertices converge to the medial axis for a curve in 2D as the sample density approaches infinity. Unfortunately, the same is not true in 3D. Recently, it is discovered that a subset of Voronoi vertices called poles converge to the medial axis in 3D. However, in practice, a continuous approximation as opposed to a discrete one is sought.Recently few algorithms have been proposed which use the Voronoi diagram and its derivatives to compute this continuous approximation. These algorithms are scale or density dependent. Most of them do not have convergence guarantees, and one of them computes it indirectly from the power diagram of the poles. Recently, we proposed a new algorithm that approximates the medial axis straight from the Voronoi diagram in a scale and density independent manner with convergence guarantees. In this paper, we present several experimental results with this algorithm that support our theoretical claims and also show its effectiveness on practical data sets.     

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to improve their approximations. Voronoi diagrams turn out to be useful for this approximation. Although it is known that Voronoi vertices for a sample of points from a curve in 2D approximate its medial axis, a similar result does not hold in 3D. Recently, it has been discovered that only a subset of Voronoi vertices converge to the medial axis as sample density approaches infinity. However, most applications need a nondiscrete approximation as opposed to a discrete one. To date no known algorithm can compute this approximation straight from the Voronoi diagram with a guarantee of convergence. We present such an algorithm and its convergence analysis in this paper. One salient feature of the algorithm is that it is scale and density independent. Experimental results corroborate our theoretical claims.     

增量式精确多面体可见外壳

提出一种新的增量式计算精确多面体可见外壳的算法IEPVH。首先,在新视图的图像平面,计算旧可见外壳的边被新光椎切割得到的交点。然后,恢复旧可见外壳的边上交点的局部方向信息并同时获得新光椎边上的交点。接着,恢复新光椎边上交点的局部方向信息。最后,新可见外壳的多边形面片通过一次遍历网格的边的过程被识别出来,并为了便于显示而被划分为三角面片。与EPVH等其他算法相比,IEPVH不但能够让用户更多地参与基于图像3维重建的过程,而且具有空间计算复杂度小。实验证明此算法的高效和鲁棒性。IEPVH的特点使其更易于在移动设备中得到应用。     

Linear one-sided stability of MAT for weakly injective 3D domain

Despite its usefulness in many applications, the medial axis transform (MAT) is very sensitive to the change of the boundary in the sense that, even if a shape is perturbed only slightly, the Hausdorff distance between the MATs of the original shape and the perturbed one may be large. However, it is known that MATs of 2D domains are stable if we view this phenomenon with the one-sided Hausdorff distance. This result depends on the fact that MATs are stable if the differences between them are measured with the recently introduced hyperbolic Hausdorff distance. In this paper, we extend the result for the one-sided stability of the MAT to a class of 3D domains called weakly injective, which contains many important 3D shapes typically appearing in solid modeling. Especially, the weakly injective 3D domains can have sharp features like corners or edges. In fact, by using the stability of the MAT under the hyperbolic Hausdorff distance, we obtain an explicit bound for the one-sided Hausdorff distance of the MAT of a weakly injective 3D domain with respect to that of a perturbed domain, which is linear with respect to the domain perturbation. We discuss some consequences of this result concerning the computation and the approximation of the MAT of 3D objects.     

Overcoming superstrictness in line drawing interpretation

Presents an algorithm for correcting incorrect line drawings-incorrect projections of a polyhedral scene. Such incorrect drawings arise, e.g., when an image of a polyhedral world is taken, the edges and vertices are extracted, and a drawing is synthesized. Along the way, the true positions of the vertices in the 2D projection are perturbed due to digitization errors and the preprocessing. As most available algorithms for interpreting line drawings are "superstrict," they judge these noisy inputs as incorrect and fail to reconstruct a three-dimensional scene from them. The presented method overcomes this problem by moving the positions of all vertices until a very close correct drawing is found. The closeness criterion is to minimize the sum of squared distances from each vertex in the input drawing to its corrected position. With this tool, any superstrict method for line drawing interpretation is now practical, as it can be applied to the corrected version of the input drawing     

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.     

Constructing a wire-frame from views on arbitrary view planes for objects with conic sections inclined to all view planes

A new and efficient approach to construct a 3D wire-frame of an object from its orthographic projections is described. The input projections can be two or more and can include regular and complete auxiliary views. Each view may contain linear, circular and other conic sections. The output is a 3D wire-frame that is consistent with the input views.The approach can handle auxiliary views containing curved edges. This generality derives from a new technique to construct 3D vertices from the input 2D vertices (as opposed to matching coordinates that is prevalent in current art). 3D vertices are constructed by projecting the 2D vertices in a pair of views on the common line of the two views. The construction of 3D edges also does not require the addition of silhouette and tangential vertices and subsequently splitting edges in the views. The concepts of complete edges and n-tuples are introduced to obviate this need. Entities corresponding to the 3D edge in each view are first identified and the 3D edges are then constructed from the information available with the matching 2D edges. This allows the algorithm to handle conic sections that are not parallel to any of the viewing directions. The localization of effort in constructing 3D edges is the source of efficiency of the construction algorithm as it does not process all potential 3D edges.Working of the algorithm on typical drawings is illustrated.     

基于Delaunay三角化的噪声点云非均匀采样

针对基于Delaunay三角化曲面重建方法要求点云密度满足ε-sample条件,提出了一种基于Delaunay三角化的噪声点云非均匀采样算法。首先,利用k-邻近点的Voronoi顶点计算出各点的负极点来逼近曲面中轴(MA);然后,根据近似中轴估计出曲面局部特征尺度(LFS);最后,结合Bound Cocone算法,删除多余的非边界点。实例表明,该算法可以准确、稳健地简化噪声点云,同时可以很好地保留曲面边界特征,经简化后的点云适用于基于Delaunay三角化的曲面重建方法。     

Boolean set operations on non-manifold boundary representation objects

For Boolean operations on geometric models, we have developed an intersection algorithm for non-manifold boundary models with vertices, linear edges, planar faces, and volumetric regions. The algorithm operates by intersecting entities in an ordered manner, from vertex to edge, then to face elements. Singular intersections are systematically handled by determining if an entity in one object is within a tolerance region of the entity in the other object. The algorithm performs Boolean operations between objects of different dimensionality as well as solids. An implementation of the proposed algorithm and the experimental results are briefly discussed.     

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.