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.     

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.     

An efficient, accurate approach to medial axis transforms of pockets with closed free-form boundaries

Medial axis transform of a pocket with free-form closed boundaries is a completed, compact representation of the pocket geometric shape and topology. It is very useful to multiple cutters selection and their tool paths generation for CNC machining of complex pockets. In the past decades, much research has been successfully conducted on the topic of finding the medial axis of a shape domain bounded with a polygon or simple geometries, e.g., lines and circles. Currently, more pockets with free-form boundaries are adopted in mechanical parts; however, the prior medial axis generation methods cannot handle this type of pockets well, resulting in long computation time and low medial axis accuracy. To address this problem, an efficient, accurate approach to calculating the medial axis transforms of these pockets is proposed in this work. An original optimization model of bisectors is established, and a new optimization method—the hybrid global optimization method—is developed to efficiently and accurately solve the optimization model of bisectors. The new optimization model and solver have been applied to many examples, and the testing results have demonstrated the advantages of this innovative approach over the prior medial axis methods. It can be an effective solution to the medial axis transforms of complex pockets.     

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.     

Medial axis computation for planar free-form shapes

We present a simple, efficient, and stable method for computing—with any desired precision—the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm.     

Computing a compact spline representation of the medial axis transform of a 2D shape

We present a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in 3D to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. Our results on various 2D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D shapes.     

Research on 3D medial axis transform via the saddle point programming method

The present paper investigates the 3D medial axis transform of objects bounded by freeform surfaces via the saddle point programming method, a mathematical programming approach used to identify the saddle points of a function. After exploring the local geometry and saddle point property of 3D medial axis transform, the mathematical programming method is employed to construct the saddle point programming models. Based on the optimality conditions that the optimal solutions should satisfy, a generic algorithm for computing various medial axis points is developed. In order to identify the junction points and localize the problem, the boundary and the skeletal curves are divided into skeletal segments, and it is proved to be efficient and accurate by numerical examples.     

一种用于手写数字分割的滴水算法的改进

在分析传统滴水算法针对共用粘连字符分割存在不足的基础上,提出一种改进的渗漏过程.该方法首先对字符的笔划粘连部分利用距离变换提取出中心线,并通过计算字符笔划的倾斜角度来指导水滴在中心线上端和下端的渗漏方向,最终形成一条较长倾斜的分割路径,避免了因垂直分割而造成的字符断裂.实验结果中分割效果较好,表明该方法的有效性.     

Computing the medial axis transform in parallel with eight scanoperations

The main result of this paper shows that the block-based digital medial axis transform can be computed in parallel by a constant number of calls to scan (parallel prefix) operations. This gives time- and/or work-optimal parallel implementations for the distance-based and the block-based medial axis transform in a wide variety of parallel architectures. Since only eight scan operations plus a dozen local operations are performed, the algorithm is very easy to program and use. The originality of our approach is the use of the notion of a derived grid and the oversampling of the image in order to reduce the computation of the block-based medial axis transform in the original grid to the much easier task of computing the distance based medial axis transform of the oversampling of the image on the derived grid     

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.     

二维复杂限定Delaunay三角化算法

针对包括曲线边界和内部带有曲线限定条件的二维Delaunay三角化问题,提出了一种细化算法.首先给出了曲线段的逼近边定义,以保证限定曲线在网格中的存在;然后证明了该算法的收敛性和最终曲线的逼近边集合与原曲线的拓扑一致性,并且生成的网格符合Delaunay优化准则;最后给出了算法的应用实例,验证了其有效性.     

A local adaptation-based generation method of medial axis for efficient engineering analysis

Currently engineering analysis is regarded as an integrated part of design process and medial axis (MA) is often utilized. However, the generation of MA of complicated models is computation intensive since it is always generated from scratch even if a tiny modification is imposed. A novel local adaptation-based approach to generating the MA for efficient engineering analysis is proposed in this study. With this method, the MA of a resultant model constructed from two other models via a Boolean operation or parameter modification is generated by adapting the MAs of the operand models in a certain way, instead of regenerating the MA from scratch. First, several new properties of the MA which are the fundamental basis of the proposed method are investigated. Then, the boundaries that will vanish from or be added into the resultant model during the Boolean operation or parameter modification are found, and the region in which the MA segments (MASs) need to be regenerated is determined. Finally, the new MASs are generated for the region using an improved tracing method. The final MA of the resultant model is thus constructed by combining the newly generated MASs with the reserved MASs of the operated model(s). Some examples are given to illustrate the high computational efficiency of the proposed method for engineering analysis.     

Improvements on the computation of boundaries in QFT

Quantitative feedback theory (QFT) is an engineering design technique of uncertain feedback systems that uses frequency domain specifications. A key step in QFT is the mapping of these specifications into regions of the Nichols plane, whose borders are usually referred to as boundaries. Boundaries computation is a key design step, thus a precise and efficient computation is critical for both obtaining low bandwidth feedback compensators and simplification of the design process. In this work, the problem of boundaries computation is analysed, introducing a new algorithm based on the computation of level curves of a three‐dimensional surface. Besides magnitude boundaries, associated with some specification over the magnitude of a closed‐loop transfer function, phase boundaries are also considered. In addition, comparison with previous published algorithms is done in terms of precision and computational efficiency. Copyright © 2006 John Wiley & Sons, Ltd.     

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     

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.     

A Rendering Equation for Specular Transfers and Its Integration into Global Illumination

In this paper, we present a rigorous theoretical formulation of the fundamental problem—indirect illumination from area sources via curved ideal specular surfaces. Intensity and area factors are introduced to clarify this problem and to rectify the radiance from these specular surfaces. They take surface geometry, such as Gaussian curvature, into account. Based on this formulation, an algorithm for integrating ideal specular transfers into global illumination is also presented. This algorithm can deal with curved specular reflectors and transmitters. An implementation is described based on wavefront tracing and progressive radiosity. Sample images generated by this method are presented.     

基于扫描跟踪元的快速碰撞检测

针对扫描实体在碰撞检测中的应用,提出一种基于扫描跟踪元的快速碰撞检测算法.首先根据运动模型上的采样点构造扫描元曲线群;然后沿着运动路径建立截平面,通过截平面与扫描元曲线群的交点构建特殊平面网格,提取出该平面网格的外轮廓顶点集;最后通过外轮廓点集构造扫描跟踪元.通过扫描跟踪元与环境的相交性检测,能快速、有效地检测出碰撞区域和碰撞时间.实验结果表明,该算法能在保证高精度检测的前提下有效地减少计算量,提高工作效率,因而具有较高的应用价值.