ERCIM News No.44 - January 2001 [contents]
ERCIM News No.44 - January 2001 [contents]
by G·bor Renner
Medial surfaces as skeletons of three-dimensional objects are geometric abstractions of solids, that facilitate volumetric and shape reasoning in many areas of engineering computations. In the Geometric Modelling Laboratory of SZTAKI fast and robust methods have been developed to calculate the medial surfaces of solids starting from their boundary representation.
The medial surface or medial axis transform is a skeleton of a three dimensional object, which is defined as the locus of the centres of the interior spheres with maximal radius. Together with the radius of the maximal spheres as a scalar function it reflects the topological and geometrical features of an object in a very compact form. Moreover this representation is unique for each ëvalidí (ie manifold) solid object. It can be invertible, and the object can be reconstructed from the skeleton.
The boundary representation of a solid - which is used in commercial CAD/CAM systems - builds up a complete topological structure of the object, defining the connectivity relationships between the faces, edges and vertices. These are associated with corresponding geometric entities describing their shape. While many practical engineering tasks can be solved using this mechanism, there are important questions which can only be answered using very cumbersome and time-consuming procedures. Such topics are, eg to recover proximity relations of some parts of the object or to obtain an overall view of the object. Based on the skeleton these questions can be answered easily, and a number of geometric operations (eg proximity calculations, shape decomposition) can be performed very efficiently. This is the reason why skeletons can be used in many engineering applications with a great benefit. Such areas are for example NC process planning, design of robot trajectories, recognition and creation of geometric features, subdivision of a solid into simpler parts for example for automatic finite element mesh generation.
In spite of the above advantages of medial surfaces, there is no commercial CAD/CAM or geometric modelling system, which is based on the skeletons or at least supports the calculation of them. This is mainly due to the computational complexity inherent in medial surface computations based on the usual boundary representation of real three-dimensional objects. As a consequence, to develop a robust, efficient and at the same time user friendly algorithm is very important. A realistic simplification of the starting geometric model or the skeleton to be computed ñ or both ñ is generally needed in order to overcome the tremendous amount of computation and to obtain results with acceptable computational costs.
In our research we concentrate on the medial surface computation of faceted objects. This means that curved faces of the object are approximated by planar facets and curved edges by several straight lines. This kind of approximation can easily be generated automatically in many solid modelers. We have developed an algorithm, which is based on the dual structure of the skeleton, and determines the spatial location of the vertices of the skeleton, together with their topological connections. One of our main improvements is the increase of speed and robustness of geometric calculations.
To compute the vertex positions of the skeleton, a highly nonlinear system of equations must generally be solved. For the numerical solution of the system a general nonlinear solver may be used, which proves to be a slow and unstable process. We have carefully analysed the system of equations from analytic and geometric points of view. It can be concluded that in a great majority of geometric situations a solution can be computed with analytic tools. In the remaining cases, specific geometric situations (that occur frequently with technical objects) can be detected, where again analytic solution is possible. Thus the use of a nonlinear system solver can considerably be reduced which results in fast and stable computations.
To illustrate the efficiency of the above case analysis a part with the corresponding medial surface is shown on the figure. The object was approximated by 94 facets, and the total number of skeleton vertex calculations was 121925, out of which only 305 (0.25%) required nonlinear system solving.
The speed and stability of medial surface calculations can be greatly increased by special topological considerations. Our research concentrated on the elimination of redundant calculations by analysing the structure of the object in a preprocessing step (by applying multiple start-points), and the development of a new algorithm to reduce the size of the problem by subdivision (divide-and-conquer algorithm).
Development of programs and methods is continuing in collaboration with the Ecole Polytechnique Fédérale in Lausanne, Switzerland.
Please contact:
Gábor Renner - SZTAKI
Tel: 36 1 3868782
E-mail: renner@sztaki.hu