Authors: Mark Price, Clive Stops, Geoffrey Butlin Transcendata Europe Ltd
Transcendata Europe Medial Object - Contents
- Summary
- Introduction
- Medial Object
- Medial Object Toolkit
- Applications
- Subdivision For Quadrilateral and Hexahedral Mesh Generation
- Isolation Of Extruded Regions
- Shelling
- Dimensional Reduction and Detail Suppression
- Conclusions
- Acknowledgements
- References
Summary
The medial object of a solid is a skeletal representation providing a rich source of information for a variety of geometric reasoning applications. It has been used for the subdivision of complex solids into simpler pieces for automatic mesh generation and also for the generation of simpler idealised models such as shells and beams for stress analysis. Although computation of the medial object itself is not trivial there are now sufficiently robust and reliable algorithms available for its generation. Since this has been achieved its use can be made accessible to users without requiring expert knowledge in the mathematical techniques for generating it. This is done through the provision of a set of tools for accessing the data contained in the medial object through an Application Programmers Interface (API). These tools present the data in a readily understandable form such as aspect ratio and minimum thickness values. In this paper a set of such tools for accessing information provided by the medial object of a solid object is described. The application of these tools to problems in analysis modelling is then presented, illustrating the versatility and potential of the toolkit.
Contents . . .
Introduction
Many CAD/CAM applications, and in particular those in analysis modelling, require the recognition of features in the object but the diverse nature of the problems being considered has often meant that a 'feature' can have different definitions in each application. The traditional boundary representations of solids in CAD systems do not provide the essential shape information necessary for all these diverse applications. High level descriptions such as 'boss' or 'pocket' are often required in applications, but these terms, so familiar to engineers, are less easily related to the low level descriptions such as 'vertex', 'edge' or 'face' which are directly obtainable from CAD systems. Even with parametric systems the features which are used to drive the generation of the model are not in this readily usable form. A flexible tool for recognising features in the form required for these diverse applications can be found in the medial object. The medial object provides information relating to the original solid and indicates features such as constrictions, holes and concavities.Although the medial object was originally proposed many years ago (ref 1) and has been the subject of research in diverse fields such as pattern recognition (ref 2), robotic motion planning (ref 3) and finite element mesh generation (ref 4,5,6) little progress was made in developing a robust implementation in 3D which could be of practical use. However more recently there has been significant impetus for developing the medial surface for use in automatic mesh generation, and this has resulted in more successful algorithms being produced (ref 7,8), some of which are sufficiently robust and reliable to become commercial products, moreover all of the example medial objects illustrated in this paper were generated using one such product (ref 9).
All of these diverse applications use information which can be provided by the medial surface. Although there has been difficulty in developing algorithms to generate the medial surface, once given the medial surface, it is not difficult to use the information effectively in all these applications. It is the aim of this paper to show how a small set of functions can be provided in the form of a toolkit and which can be used for applications in analysis modelling.
This paper describes the basic toolkit of functions for exploiting the information provided by the medial surface. The functions are made accessible through an application programmers interface (API) to enable use in a wide range of applications.
The next section provides a brief overview of the medial surface, with some basic definitions and descriptions. This is followed by a description of the toolkit detailing the functions provided, and outlines of several applications including hexahedral mesh generation.
Contents . . .
Medial Object
The term 'medial object' is used here to include both the medial axis of a surface and the medial surface of a solid. These have been referred to in the literature collectively as the medial axis transform (MAT), symmetric axis, and skeleton. The term medial object is chosen here because this term emphasises the generic nature of this representation, and also that it is an alternative representation of an object capable of providing all the information contained in the solid object.
skeleton representation of an object: medial abstraction of face geometry is stick-like: medial abstraction of solid geometry is sheet-like: ie it is a lower dimensional representation of an object
The medial surface of a solid is formed by the locus of an inscribed sphere of maximal diameter as it rolls around the interior of the solid. A sphere is maximal if no other sphere contains it completely. If the sphere touches two object faces then it has two degrees of freedom and its centre lies on a surface, referred to as a medial face, which is equidistant from those two object faces. If the sphere touches three object faces then it has only one degree of freedom and the locus of its centre forms an edge of the medial surface. This is known as a medial edge. If the sphere touches four object faces then its centre forms a vertex on the medial surface and is called a medial vertex. The sphere may also touch a surface at more than one point for example as it rolls along the axis of a cylinder, or it may touch more than four surfaces, as in a five sided prism. A more detailed description of the medial surface and techniques for its computation can be found in Sheehy (ref 7,8).
The medial axis of a surface is the 2D equivalent of the medial surface and is formed by the locus of an inscribed disc of maximal diameter as it rolls around the interior of the surface. For curved surfaces the inscribed circle is mapped into the embedded geometry of the surface providing geodesically equidistant loci.
Formation of the medial axis by rolling disc
Formation of the medial surface by a rolling ball
The radius of the inscribed sphere at any point gives the thickness of the object in that particular area. The variation of radius over the medial surface is described by the radius function. The original object may be exactly reproduced from the medial surface and the radius function. The medial object implicitly includes the radius function.
The medial object can be calculated for the outside as well as the inside of an object
Skeleton representation consisting of edges and vertices eg in 2D objects
Skeleton representation - with associated properties
All medial faces are calculated including 'flaps'to every sharp edge
but primary faces are more useful and therefore usually highlighted in our pictures
Current 2D capability of our medial object software
calculates medial axis of face arbitrary geometry: flat or sculptured NURBS, analytic or blend surfaces
with arbitrary topology: cellular, non-manifold, with point and line scratches
Current 3D capability of our medial object software
calculates medial faces of solid geometry (excepting finite contact): b-rep bounded by flat or sculptured NURBS,analytic or blend surfaces
with general topology:cellular, non-manifold,with point, line and face scratches
3D example of medial object computation
3D example of medial object computation - again showing only primary faces of medial object (although all are computed)
view large image of original object view large image of medial object
The next section considers in detail the information contained in the medial object and describes a set of functions which can be used to extract this information.
Contents . . .
Medial Object Toolkit
The API toolkit described here provides direct access to simple functions which provide information in a form familiar to developers. Given such a comprehensive set of tools the medial object is easy to use as a source of information.
The functions described in this section are separated into three categories, low level, intermediate level and high level. Low and intermediate level functions are basic functions for obtaining data directly from the medial object whereas high level functions are full applications such as those described later in this paper. The following sections provide a description of the low and intermediate level functions.
Low Level Functions
The medial object is generated as a fully connected line or surface model, with separate but associated geometry and topology. It can therefore be assumed that the standard functions used in solid modelling for topology traversal and accessing geometry are available. These include functions for obtaining topological information such as the next/previous vertex in loop, next/previous edge in loop, next/previous loop in face, tangent to edge at a given point, and functions to obtain geometrical information such as surface geometry including 1st and 2nd derivatives. In addition to these there are remarkably few low level functions required for accessing medial object data. The functions given below are a minimal set providing enough information for many applications as described in the following sections.(1) Radius Function Value at a Point.
This function takes as input a point which lies on the medial surface and returns the radius of the inscribed sphere at that point.
The radius of the sphere at a given point gives the minimum distance from the point to the object boundary. This is a good indication of the thickness of the object local to the given point.
(2) Medial Edge Length
This function takes as input a medial edge and returns the length of that medial edge. It can have simple forms returning straight edge lengths but in general should return true 3D curved edge lengths. Variations on this function could return the edge length in parameter space, or, for Finite element applications, the edge length in element space (that is the number of elements along the edge). This function can have applications in estimating the aspect ratio of a region, as described later on.
(3) Surface Area of a Medial Face
This function takes as input a medial face and returns the area of that medial face. This can be considered as the natural extension of the function for obtaining the length of a medial edge to dealing with surfaces. For a given medial surface face the function returns a real number which is the area of the face. A variation on this routine could return the element area (that is the number of elements covering the face).
The function can have uses in estimating the thinness, or volume, of a solid region, in conjunction with the radius function values, as is described later on.
(4) Defining Entities Of a Medial Surface Vertex, Edge or Face
This function takes as input a medial entity (edge, face or vertex) and returns a list of the object entities (edges, faces, or vertices) which are used to define that medial entity.
This is used for example in subdivision for hex meshing for deciding which boundaries to make cuts between or simply in response to an enquiry 'what parts of the boundary are closest at this point?'.
(5) Medial Entities associated with an Object Entity
This function takes as input an object entity (edge, face or vertex) and returns a list of the medial entities (edge, faces, or vertices) which it helps define.
This can be used in finding the influence of a particular object entity on the medial surface, and can help improve efficiency when searching the medial surface for other entities also defined by the given one.
(6) Touching Points of Inscribed Sphere
This routine takes as input a medial entity (edge, face or vertex) and a point on that entity, and returns a list of the touching points of the inscribed sphere centred at that point.
The position of the touching points of the inscribed sphere are the closest points on the object boundary to a given point on the medial surface, and these co-ordinates are useful in many applications and can be given in Cartesian form, or even in parameter or element metric spaces as desired.
These six functions are the complete set of functions required and may be used directly in applications, or as basic building bricks for intermediate level functions as described in the next section.
Intermediate Level Functions
The intermediate level functions are enhancements of the basic functions that provide higher level information. Moreover they are constructed from the low level functions.(1) Maximum/Minimum Sphere Radius
This function takes as input a medial edge or face and obtains the maximum or minimum radius of the inscribed sphere along that medial edge or across that medial face. As an extension of the basic radius enquiry function, this function is useful in identifying constrictions in the object along a given medial edge or even in the interior of a medial face.
Minimum radius of a medial edge.
(2) Aspect Ratio
This function takes as input a medial edge and returns the aspect ratio of the region along the direction of the medial edge. The aspect ratio of the region can be defined as the medial edge radius divided by medial edge length. This can be done in several ways, for example by using an average value of radius, or by using the maximum value of radius, either at the endpoints of the medial edge or by sampling points along the medial edge. Aspect ratios can also be determined for object edges, as medial edge radius divided by object edge length and this has useful applications in dimensional reduction and detail suppression (ref 12).
Aspect ratio of a medial edge.
(3) Taper
This function takes as input a medial edge and returns the taper ratio of the region along the direction of the medial edge. This can be estimated as the radius of the sphere at one point divided by the radius of the sphere at another. As an alternative to the aspect ratio of a region, taper can provide information about how fast the object is constricting or expanding in the given region. Again this can be done along a medial edge or across a medial face.
Figure 5 Measuring the taper of a region around a medial edge.
These three intermediate level functions have been used in a range of analysis modelling applications, as is illustrated in the next section. The requirements for these applications indicate that this set is sufficient for a wide range of problems. However it is possible to have variations of these functions, since it is possible to have variations on the definitions of taper and aspect ratio. For example aspect ratio can be based on the maximum radius along a medial edge, or the average radius along a medial edge or the minimum radius along a medial edge. This set of functions is easily extended to use variations on these themes.
Contents . . .
Applications
This section contains example applications using the medial object toolkit, illustrating the type of data which can be accessed through the API, and also a variety of analysis applications for which the medial object can be used. It can be seen from these examples that common to all applications is the recognition of features which influence the behaviour of the object for the particular analysis type. The same toolkit functions are used in different ways to identify these features but subsequent treatment then depends entirely on the analysis type.
Subdivision For Quadrilateral and Hexahedral Mesh Generation
Subdivision for automatic quadrilateral and hexahedral mesh generation is now a well established application for the medial object (ref 4,5,6). The medial object is used to obtain information about object edges and faces which are in geometric proximity in any given locality. This information is then directly used to subdivide the target object into simple pieces, called kernels, which are more readily meshed.
The toolkit functions are used to obtain the required information. The defining entities of medial edges and vertices are used to determine what boundary faces are in proximity in any given locality and are obtained from low level function 4. Cuts are inserted between these defining entities at one radius distance from the medial vertex. The radius value of the vertex is obtained from low level function 1. The vertices of the cutting edge/surface being created are computed using the co-ordinates of the sphere touching points at the medial vertex (low level function 6) and the medial edge tangents at that vertex. In 2D use is also made of the minimum radius value along a medial edge to obtain minimum length cuts, and this is obtained from intermediate level function 1. The figure below shows a 2D object subdivided into meshable kernels highlighting selected places where various toolkit functions are used.
Subdivision of a 2D object.
In 3D the topology of medial faces is also used in the subdivision process to indicate where there are through holes or where the region is a 2D extruded region requiring subdivision. If this is the case then the same functions are applied to carry out subdivision of the medial face, these surface subdivisions being used in the formation of the cuts for the 3D region. Details of the algorithms for medial object subdivision can be found in the literature (ref 5,6,13).
This reduction in complexity by medial object subdivision is useful for most types of meshing. For tet meshing using such subdivision provides a degree of locality and removes the need to remesh the whole object when changes are made to mesh density, object shape or physical properties.
These hex-meshable kernels can also be used to prepare regions that suit CFD body-fitted meshing algorithms, removing the need for manual subdivision. Auto-subdivision is also relevant to plastering type hex meshing, because at the very least a complex object can be reduced to simple connectivity, leaving the plastering algorithm with a simpler class of object that it has to deal with. An example of an object subdivided using medial object subdivision and meshed with hexahedral elements is shown below.
Auto-subdivision based on medial obect
Contents . . .
Isolation Of Extruded Regions
Isolation of thin regions in an object is readily achieved through the use of the medial object toolkit. Each medial face is defined by two object faces and this information can be used to indicate possible extruded regions. Thus areas may be identified which can be meshed using extruded 2D meshes, or which can be abstracted to a model of reduced dimensionality. The remaining thick regions can be meshed using any appropriate meshing technique, such as plastering or Delaunay based tet meshing.Candidate medial faces are found by searching the medial object. The defining entities of each medial face are obtained using low level function 4. If both defining entities are faces then the medial face indicates an extruded region. Having found a candidate medial face it is then tested for 'thinness'. This can be evaluated by obtaining the aspect ratio of that medial face (a variation of intermediate function 2). If the aspect ratio is above a certain threshold then the region can be considered thin. This threshold value may be dependent on the application, or the meshing algorithms available, or even may be set to zero in which case all extruded regions will be recognised regardless of their thinness.
To remove an extruded region the procedure is to cut out around a medial face. In order to prevent interference with neighbouring regions the cuts are inserted one radius from the bounding medial edges. The values of the radius function at the bounding medial vertices and at sample points along the bounding medial edges are obtained from low level function 1 and used to help generate the edges of the cutting surfaces. This procedure is identical to that used in subdivision for hexahedral mesh generation.
Feature recognition can also be applied here to reduce the number of cuts inserted. For example at the end of a hexahedral region no cuts are necessary. The defining entities of each medial edge are obtained from low level function 4. The solid topology is then checked to see if these faces are connected as an end region, and if so no cuts are inserted. Figure 8 shows an object subdivided in this manner with the thin extruded regions cut off from the thicker 3D regions.
Isolation of thin extruded regions
Contents . . .
Shelling
Shelling is a procedure where a skin of a certain thickness is added to the boundary of an object, so that the original object plus its shell can be used for analysis purposes. This technique has a natural application in the casting of turbine blades where a wax pattern is encased in a ceramic shell. Simulation of this casting process demands a shelling technique for the solid model of the wax blade. Another application is in the determination of the lightening strike characteristics of objects, particularly aircraft. For this a standard technique for finding the critical areas on the target object surface involves finding the locus of the centre of a large sphere as it rolls around the outside surface of the object, that is finding a thick shell on the surface of which small features of the object are attenuated, or altogether suppressed. The area of the shell surface relative to the area of the defining target surface is an indication of the importance of the region in the analysis.
Shelling of a 2D region.
It is possible to compute a shell by offsetting the boundary, and extending and intersecting these offset surfaces, however this can be problematic in the general case. The medial object provides a general solution to the shelling problem coping with recesses and pockets naturally. The following is a brief overview of a 2D shelling algorithm.
A shell of thickness D of a face S1 (shaded) is constructed by framing S1 in another surface S2 (outer rectangle), at a distance greater than 2D away from S1, and constructing the medial axis of the space between them, (S2 - S1). The medial radius R of the medial axis is thus always greater than D except where the medial axis is defined by two parts of the same surface which are close together.
Along portions of the medial axis of radius (obtained from low level function 1) greater than D, the shell can be constructed from the locus of points which are between the medial axis and the corresponding defining (low level function 4) points on S1, and which are (R - D) from the medial axis. Each medial vertex thus generates a shell vertex between it and each of its defining points on S1; each medial edge generates one shell edge if it runs between S1 and S2, or zero or two shell edges if it runs between two different parts of S1.
At convex corners of S1, the medial axis curves around S1 and so the shell entities will also curve around. Where the medial radius R shrinks to D, the shell entities formed on either side of the medial axis meet. This occurs where there is a constriction or notch in S1's boundary, and will result in a sharp concave corner in the shell - this could be rounded off afterwards if the application demanded. Medial entities of R < D will not generate any shell entities - effectively, they lie within the shell.
The algorithm is the same in principle when extended to 3D. The body to be shelled must be enclosed in another body and the medial object of the region between the two computed and interrogated, as before. Medial vertices are used to make "shell vertices," medial edges to form "shell edges" and medial faces to create "shell faces" analogously. Points at which the medial radius shrinks to D have to be carefully identified, as in the two-dimensional case, to find the limits of the shell at notches in the original body. The figure below shows an example of this algorithm in action.
Multiple thickness shells computed with the medial axis
In terms of the lightning strike application, use of the medial object defining entities (low level function 4) and medial face surface area (low level function 3) are enough to provide the necessary information to compute strike probability.
Contents . . .
Dimensional Reduction and Detail Suppression
As analyses become more complex and are carried out on bigger models there is a requirement for model idealisation and abstraction. This abstraction process currently relies on engineering judgement to produce models of appropriate complexity and accuracy. Two of the main ways of reducing the complexity of models are detail suppression, otherwise known as defeaturing, and dimensional reduction. Defeaturing involves suppressing small features which do not influence the macro behaviour of the object. Dimensional reduction is another way that engineering approximations can be applied to improve the effectiveness of computational resources, for example representing a long slender solid by a beam model. Dimensionally reduced models are often used in applications where analysis requires plate and shell elements, such as the design of injection mouldings.In detail suppression the size of a feature relative to the surrounding region may indicate that the feature is unimportant in the analysis to be carried out. Such small features can easily be recognised using the medial object. For example in 2D the aspect ratio (intermediate level function 2) of the loop of medial edges surrounding an internal hole indicates the relative size of the hole. If the aspect ratio is large then the radius of the rolling ball is much bigger that the total distance around the perimeter of the hole, and so the hole is small and therefore can be removed. To determine this loop aspect ratio the aspect ratio of each medial edge around the loop is needed, and these medial edges are all those which have an object edge in the perimeter of the hole as a defining entity (low level function 4). This test for hole size applies regardless of the shape of the hole boundary (ref 12) and hence removes the need for further detailed feature recognition on that hole.
In dimensional reduction if the aspect ratio of a medial face ( intermediate level function 2 ) is sufficiently small then that region may be regarded as thin and may be modelled using plate, shell or membrane elements. The medial face itself can then be used as the mid-plane of these 2D elements. The physical properties of the elements, namely their thicknesses, can be determined from the radius function, and this could be done for each individual nodes allowing variable thickness to be easily included in the finite element model. Similarly the aspect ratio of a 2D region can indicate that the region should be represented by a bar or beam element and again the physical properties can be computed using information such as radius.
The finite element modelling group at Queen's University Belfast is investigating the use of the medial object in model abstraction and detail suppression for stress analysis models. Small features can be identified and suppressed, or reduced to alternative appropriate representations such as beams.
Contents . . .
Conclusions
The medial object has been presented as a tool in analysis modelling applications and a toolkit of functions for accessing the data contained in the medial object has been described. This toolkit is easy to use, consisting of simple functions which can be incorporated into a wide range of applications. The use of the toolkit does not require expert knowledge of the medial object or how it may be generated. Applications illustrating the use of the toolkit have been shown, demonstrating the versatility of the tools.
Contents . . .
Acknowledgements
The authors would like to thank the other members of the development team at Transcendata Europe for their help in preparing this paper. Transcendata Europe collaborates in the work on dimensional reduction and detail suppression which is carried out by the Finite Element Modelling group at Queen's University Belfast. Their co-operation and help in this work has been greatly appreciated. This project with QUB is also supported by the Engineering and Physical Sciences Research Council (UK). Their support has been greatly appreciated.
This paper is based on A Medial Object Toolkit for Meshing and Other Apllications presented by Mark Price at the International Meshing Roundtable Conference at Sandia National Laboratories Oct 16-17 1995 Albuquerque NM USA.
Contents . . .
References
(1) H. Blum "A Transformation for Extracting New Descriptors of Shape", Models for the Perception of Speech and Visual Form, W. Wathen-Dunn (ed.), M.I.T. Press, 362-380, 1967.
(2) D.T. Lee "Medial Axis Transformation of a Planar Shape", IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-4, No. 4, 363-369, July 1982
(3) M.Held, G. Lukacs, L. Andor "Pocket Machining Based on Contour-Parallel Tool Paths Generated by Means of Proximity Maps", Computer Aided Design, Vol 26, Number 3, march 1994.
(4) H.N. Gursoy, N.M. Patrikalakis "Automated Interrogation and Adaptive Subdivision of Shape Using Medial Axis Transform", Advances in Engineering Software, Vol. 13, 5/6, pp 287-302, Sept/Nov 1991.
(5) T. Tam, C.G. Armstrong "2D Finite Element Mesh Generation By Medial Axis Subdivision', Advances in Engineering Software, Vol 13, 5/6, pp312-324, Sept/Nov 1991.
(6) M.A. Price, C.G. Armstrong, M.A. Sabin "Hexahedral Mesh Generation By Medial Surface Subdivision: Part 1. Solids with Convex Edges", International Journal for Numerical Methods in Engineering, to appear.
(7) D.J. Sheehy, C.G. Armstrong, D.J. Robinson "Numerical Computation of Medial Surface Vertices", IMA Conference on Mathematics of Surfaces VI, Brunel University, England, 1994.
(8) D.J. Sheehy, C.G. Armstrong, D.J. Robinson "Computing the Medial Surface of a Solid from a Domain Delaunay Triangulation", ACM/IEEE Symposium on Solid Modelling and Applications, Salt Lake City, Utah, May 1995.
(9) FAM - Field Analysis Modeller, Transcendata Europe Ltd., Version 3.9, 1995.
(10) L.R Nackman, S.M. Pizer "Three-Dimensional Shape Description using The Symmetric Axis Transform 1 : Theory", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol:PAMI-7 No. 2, March 1985.
(11) C.M. Hoffmann "How to Construct the Skeleton of CSG Objects', Proc. 4th IMA Conference on the Mathematics of Surfaces, Bath, England, 1990.
(12) C.G. Armstrong, D.J. Robinson, R.M. McKeag, T.S. Li, S.J. Bridgett, R.J. Donaghy "Applications of the Medial Axis Transform in Analysis Modelling", Proceedings 5th International Conference on Reliability of Finite Element Methods for Engineering Applications, pp 415-426, Amsterdam, 10-12 May, 1995.
(13) M.A. Price, M.A. Sabin, C.G. Armstrong "Fully Automatic Quad and Hex Meshing", Proceedings 5th International Conference on Reliability of Finite Element Methods for Engineering Applications, pp 356-367, Amsterdam, 10-12 May, 1995.
Contents . . .