Last update: July 15, 2004

BACK

Publications in Comp. Geom. & Graphics on Voronoi Diagrams & related concepts, as well as their applications :

• Armstrong, C.G. et al. :
  • Adaptive Curvature-Sensitive Meshing of the Medial Axis, 2001.
  • Techniques for Interactive and Automatic Idealisation of CAD Models, 1998.
  • Shape Description by Medial Surface Construction, 1996.
  • Hexahedral Mesh Generation by Medial Surface Subdivision: Part II. Solids with Flat & Concave Edges, 1997.
  • Hexahedral Mesh Generation by Medial Surface Subdivision: Part I, Solids With Convex Edges", 1995.
  • Dimensional Reduction of Analysis Models, 1996.
  • Medials for Meshing and More, 1995.
• Aurenhammer, F. et al. :
  • Voronoi Diagrams, 2000.
  • Skew Voronoi Diagrams, 1998+.
  • Straight Skeletons for General Polygonal Figures in the Plane, 1998.
  • A Novel Type of Skeleton for Polygons, 1995.
  • Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure, 1991.
  • Power diagrams: Properties, algorithms, and applications, 1987.
• Dey, T. et al.:
  • Approximating medial axis from the Voronoi diagram with convergence guarantee, 2002.
  • Approximate medial axis as a Voronoi subcomplex, 2002.
• Edelsbrunner, H. et al. :
  • Three-dimensional alpha shapes, 1994.
  • Delaunay and Regular Triangulation in Space, 1993.
  • On the Shape of of a Set of Points in the Plane, 1983.
• Etzion, M. et al. :
  • Hexahedral Meshing of Non-Linear Volumes using Voronoi Faces and Edges, 1999.
  • Computing the Voronoi diagram of a 3-D polyhedron by separate computation of its symbolic and geometric parts, 1999.
  • Computing Voronoi skeletons of a 3-D polyhedron by space subdivision, 1997 & 2002.
• Huttenlocher, D. et al. :
  • The Upper Envelope of Voronoi Surfaces and Its Applications, 1993.
  • On Dynamic Voronoi Diagrams and the Minimum Hausdorff Distance for Point Sets Under Euclidean Motion in the Plane, 1992.
• Manocha, D. et al. :
  • Accurate Computation of the Medial Axis of a Polyhedron, 1998 & 1999.
• Marton, G.:
  • Acceleration of Ray Tracing via Voronoi Diagrams, 1995.
• Okabe, A. et al. :
  • Spatial Tessellations - Concepts and Applications of Voronoi Diagrams, 1992 & 2000.
• Patrikalakis, N.M. et al. :
  • An Algorithm for the Medial Axis Transform of 3D Polyhedral Solids, 1996.
  • 3-D Shape Interrogation by Medial Axis Transform, E.C. Sherbrooke (PhD Thesis), 1995.
• Storti, D. & Turkiyyah, G. et al. :
  • A Skeletal/Metaball Shape Representation to Support Deformable Solid Modeling, 2000.
  • Skeleton-based Three-dimensional Geometric Morphing, 2000.
  • Skeleton-Based Modeling Operations on Solids, 1997.
  • An Accelerated Triangulation Method for Computing Skeletons of Free-form Solid Models, 1997.
  • Computation of 3D Skeletons by a Generalized Delaunay Triangulation Approach, 1995.
• Teichmann, M. et al. :
  • Assisted Articulation of Closed Polygonal Models, 1998.
  • Polygonal Approximation of Voronoi Diagrams of Triangles in Three Dimensions, 1997.
• Watson, Dave et al. :
  • modemap: An implementation of natural neighbor interpolation on the sphere, 1998.
  • nngridr: An implementation of natural neighbor interpolation, 1994.
  • Natural neighbor sorting on the n-dimensional sphere, 1988.

BibTeX references.

Web links :

• Geometry in action on Voronoi Diagrams , Delaunay Triangulations , Medial Axes .
• Alpha Shapes: Definition and Software.
• Voronoi softwares, games:
  • http://www.cs.cornell.edu/Info/People/chew/Delaunay.html
  • http://www.voronoigame.com

The medial axis transform provides an alternative representation of geometric models that has many useful properties for analysis modelling. Applications include decomposition of general solids into sub regions for mapped meshing, identification of slender regions for dimensional reduction and recognition of small features for suppression. In order to serve these purposes effectively, it is important to approximate the medial axis so that the curvature has been respected. This paper describes a general idea, which is based on equal distance criteria, for adaptive, curvature-sensitive mesh refinement on the medial axis, after its topology has been defined. The completed set of theories and examples for 2-D planar objects and 3-D solid objects are presented.

Operations to facilitate the derivation of idealised models from CAD geometry and techniques to identify automatically features suitable for idealisation are presented. Whilst the development of idealisation tools in commercial modellers is proceeding rapidly, techniques to estimate the modelling error introduced by idealisation are also necessary. Future developments in analysis modelling will require interaction with CAD systems in a manner which is independent of the underlying modeller.

Keywords: CAD, defeaturing, detail supression, dimensional reduction, idealisation, medial axis.

* D.J. Sheehy is with Hibbitt, Karlsson and Sorensen Inc., 1080 Main St., Pawtucket, RI 02860-4847. E-mail: sheehy@hks.com. C.G. Armstrong is with the Queen's University of Belfast, Dept. of Mechanical & Manufacturing Engineering, Ashby Building, Stranmillis Road, Belfast BT9 5AH, Northern Ireland. E-mail: c.armstrong@qub.ac.uk. D.J. Robinson is with the Department of Civil Engineering at the Queen's University of Belfast, Stranmillis Road, Belfast BT9 5AH, Northern Ireland. E-mail: des.robinson@qub.ac.uk.

The medial surface is a skeletal abstraction of a solid that provides useful shape information, which compliments existing model representation schemes. The medial surface and its associated topological entities are defined, and an algorithm for computing the medial surface of a large class of B-rep solids is then presented. The algorithm is based on the domain Delaunay triangulation of a relatively sparse distribution of points, which are generated on the boundary of the object. This strategy is adaptive in that the boundary point set is refined to guarantee a correct topological representation of the medial surface.

Index Terms: Voronoi diagram, medial axis, skeleton, collision detection, mesh generation, feature recognition, solid modeling.

A method is presented for the subdivision of a large class of solids into simple subregions suitable for automatic finite element meshing with hexahedral elements. The medial surface subdivision technique described previously in the literature is used as the basis for this work and is extended here to cover solids which have flat and concave edges. Problems where the medial surface is degenerated are also addressed.

This paper describes a set of procedures by which an analyst might be able to approximate a 2D plate or 3D shell structure for a quick, linear static analysis. It uses mostly dimensional reduction with some assistance from detail suppression techniques in order to achieve the desired approximation of the structure. Methods for automating these procedures are described and use the 'Medial Axis Transform'. The paper describes the methods used to compute mass and stiffness properties of the approximated structure including appropriate modifications to boundary conditions. Methods for coupling between ID and 2D interfaces are given for stress and strain variables for beam elements. Error indicators are also computed to monitor the validity of the dimensional reductions.

Keywords: defeaturing, dimensional reduction, medial axis.

web link

The medial axis transform provides an alternative representation of geometric models that has many useful properties for analysis modelling. Applications include decomposition of general solids into subregions for mapped meshing, identification of slender regions for dimensional reduction and recognition of small features for suppression. A set of operations for idealisation of the analysis domain are described. These can be specified either interactively or automatically based on features of the medial axis.

The topic of this chapter - Voronoi diagrams - differs from other areas of computational geometry, in that its origin dates back to the 17th century. In his book on the principles of philosophy, R. Descartes' illustrations show a decomposition of space into convex regions, whose underlying idea seems to be that of a Voronoi diagram. This concept has independently emerged, and proven useful, in various fields of science. Different names particular to the respective field have been used, such as medial axis transform in biology and physiology, Wigner-Seitz zones in chemistry and physics, domains of action in crystallography, and Thiessen polygons in metereology and geography. The mathematicians Dirichlet and Voronoi were the first to formally introduce this concept. The resulting structure has been called Dirichlet tessellation or Voronoi diagram, which has become its standard name today. Voronoi was the first to consider the dual of this structure, where any two point sites are connected whose regions have a boundary in common. Later, Delaunay obtained the same by defining that two point sites are connected if and only if they lie on a circle whose interior contains no other point site. After him, the dual of the Voronoi diagram has been denoted Delaunay tessellation or Delaunay triangulation. Besides its applications in other fields of science, the Voronoi diagram and its dual can be used for solving numerous, and surprisingly different, geometric problems. Moreover, these structures are very appealing, and a lot of research has been devoted to their study (about one out of 16 papers in computational geometry), ever since Shamos and Hoey introduced them to the field. Within one chapter, we cannot review all known results and applications. Instead, we are trying to highlight the intrinsic potential of Voronoi diagrams, that lies in its structural properties, in the existence of efficient algorithms for its construction, and in its adaptability.

Animations and pictures (html page).

On a tilted plane T in three-space, skew distances are defined as the Euclidean distance plus a multiple of the signed difference in height. Skew distances may model realistic environments more closely than the Euclidean distance. Voronoi diagrams and related problems under this kind of distances are investigated.

A relationship to convex distance functions and to Euclidean Voronoi diagrams for planar circles is shown, and is exploited for a geometric analysis and a plane-sweep construction of Voronoi diagrams on T. An output-sensitive algorithm running in time O(n log h) is developed, where n and h is the number of sites and non-empty Voronoi regions, respectively. The all nearest neighbors problem for skew distances, which has certain features different from its Euclidean counterpart, is solved in O(n log n) time.

A novel type of skeleton for general polygonal figures, the straight skeleton S(G) of a planar straight line graph G, is introduced and discussed. Exact bounds on the size of S(G) are derived. The straight line structure of S(G) and its lower combinatorial complexity may make S(G) preferable to the widely used Voronoi diagram (or medial axis) of G in several applications.

We explain why S(G) has no Voronoi diagram based interpretation and why standard construction techniques fail to work. A simple O(n) space algorithm for constructing S(G) is proposed. The worst-case running time is O(n² log n), but the algorithm can be expected to be practically efficient, and it is easy to implement.

We also show that the concept of S(G) is flexible enough to allow an individual weighting of the edges and vertices of G, without changes in the size of S(G), or in the method of construction. Apart from offering an alternative to Voronoi-type skeletons, these generalizations of S(G) have applications to the reconstruction of a geographical terrain from a given river map, and to the construction of a polygonal roof above a given layout of ground walls.

Paper in HTML format.

A new internal structure for simple polygons, the straight skeleton, is introduced and discussed. It is composed of pieces of angular bisectores which partition the interior of a given n-gon P in a tree-like fashion into n monotone polygons. Its straight-line structure and its lower combinatorial complexity may make the straight skeleton preferable to the widely used medial axis of a polygon. As a seemingly unrelated application, the straight skeleton provides a canonical way of constructing a polygonal roof above a general layout of ground walls.

Keywords: Simple polygon, angular bisectors, internal skeleton, roof construction

This paper presents a survey of the Voronoi diagram, one of the most fundamental data structures in computational geometry. It demonstrates the importance and usefulness of the Voronoi diagram in a wide variety of fields inside and outside computer science and surveys the history of its development. The paper puts particular emphasis on the unified exposition of its mathematical and algorithmic properties. Finally, the paper provides the first comprehensive bibliography on Voronoi diagrams and related structures.

The power pow(x,s) of a point x with respect to a sphere s in Euclidean d-space E^d is given by d²(x,z)-r², where d denotes the Euclidean distance function, and z and r are the center and the radius of s. The power diagram of a finite set S of spheres in E^d is a cell complex that associates each s in S each with the convex domain

The close relationship to convex hulls and arrangements of hyperplanes is investigated and exploited. Efficient algorithms that compute the power diagram and its order-k modifications are obtained. Among the applications of these results are algorithms for detecting k-sets, for union and intersection problems for cones and paraboloids, and for constructing weighted Voronoi diagrams and Voronoi diagrams for spheres. Upper space bounds for these geometric problems are derived.

Details: click here.

Notes from a lecture given in July 1993.

Details: click here.

Details: click here.

In our recent work a new approach for automatic hexahedral meshing was presented [2]. The presented algorithm decomposes the object into simple parts based on the Embedded Voronoi Graph (EVG) [1]. The EVG contains the complete symbolic information of the Voronoi diagram (or the medial axis) of the object, and a tolerance based geometric approximation to the real geometry. The EVG is used for decomposing the object, with the guiding principle that resulting sub-volumes are sweepable. Sub-volumes are meshed independently, and the resulting meshes are easily combined and smoothed to yield the final mesh.

This approach possesses several advantages:

1. the algorithm for computing the EVG is provenly correct, stable and easy to implement;
2. the approach is well defined and valid on shapes of any geometry, including shapes whose medial axis is degenerate;
3. the decomposition is order independent and prevents intersections between decomposition surfaces;
4. the number of sub-volumes generated is not large since every sub-volume contains a different Voronoi face;
5. since the directions and entities involved in each decomposition are defined by the medial axis, there are no intersection computations;
6. since a decomposition is used, as opposed to template, there is only a minimal need for medial axis geometry; and
7. mesh quality seems high since the decomposition avoids generation of sharp angles, and sweep and other basic methods are used to mesh the sub- volumes.

The algorithm as presented in [2] is not complete. First, while it is shown that most of the sub-volumes resulting from the decomposition are sweepable or hexahedral, some sub-volumes that result from decomposing along one or more Voronoi edges might be not meshable by the available basic algorithms. Second, though a general explanation is given on handling non-polyhedral volumes, it was not fully defined or implemented.

In this work the algorithm is developed further, to address the issues unresolved in the previous publication. The decomposition algorithm is expanded to further decompose the problematic sub-volumes mentioned above. The purpose of the decomposition is to create sub-volumes sweepable along previously unaddressed medial edges. The EVG computation and analysis are expanded to non-linear objects, enabling the meshing of non-polyhedral volumes. The algorithm is demonstrated on several real life examples.

References

[1] M. Etzion, A. Rappoport, 'Computing Voronoi Skeletons of a 3-D Polyhedron by Space Subdivision', Technical Report TR-8-97, Institute of Computer Science, The Hebrew University of Jerusalem, 1997.

[2] A. Sheffer, M. Ezion, A. Rappoport, M. Bercovier 'Hexahedral Mesh Generation using the Embedded Voronoi Graph', Proc. 7th International Meshing Roundtable, Dearborn, USA, October 26-28, 1998. Accepted to 'Engineering with Computers'.

Symbolic part = Voronoi graph:

• Nodes of the graph are the vertices, edges and faces of the Voronoi diagram.
• Arcs connect these "nodes".
• No geometry (location and trace) is computed/included in this graph.

Iterative computation of the Voronoi graph:

1. Construct a Proximity Structure Subdivision (PSS): space subdivided in cells labelled according to relative proximities to polyhedron entities. This is done via a recusrsive octree construction.
2. Compute Voronoi edge witnesses: intercepts between the Voronoi Diagram edges and the previously lebelled cells; only 2D computations involved.
3. Extract the vertices of the Voronoi Graph.
4. Extract the edges of the Voronoi Graph.
5. Extract the faces of the Voronoi Graph.

Voronoi Diagram Computation

The center of the cells containing VG vertices provide approximate loci of vertices of VD. Piecewise linear curves connecting Voronoi edge witnesses and the previously extracted vertices, approximate the loci of the edges of VD. Then use the symbolic information contained in VG to derive a set of equations defining the precise loci of vertices and edges.

We tackle the problem of computing the Voronoi diagram of a linear 3-D polyhedron. The main difficulty with the computation is that the diagram's edges and vertices are of relatively high algebraic degrees. As a result, previous approaches to the problem have been non-robust, difficult to implement, or not provenly correct.

We introduce three new proximity skeletons related to the Voronoi diagram: (1) the Voronoi Graph (VG), which contains the complete symbolic information of the Voronoi diagram without containing any geometry; (2) the Approximate Voronoi Graph (AVG), which deals with degenerate diagrams by collapsing sub-graphs of the VG into single nodes; and (3) the Proximity Structure Diagram (PSD), which enhances the VG with a geometric approximation of Voronoi elements to any desired accuracy. The new skeletons are important for both theoretical and practical reasons. Many applications that extract the proximity information of the object from its Voronoi diagram can use the Voronoi graphs or the PSD instead. In addition, the skeletons can be used as initial structures for a robust and efficient global or local computation of the Voronoi diagram.

We present a space subdivision algorithm to construct the new skeletons, having three main advantages. First, it solves at most uni-variate quartic polynomials. This stands in sharp contrast to previous approaches, which require the solution of a non-linear tri-variate system of equations. Second, the algorithm enables purely local computation of the skeletons in any limited region of interest. Third, the algorithm is simple to implement.

We present an accurate and efficient algorithm to compute the internal Voronoi region and medial axis of a 3D polyhedron. It uses exact arithmetic and representations for accurate computation of the medial axis. The sheets, seams, and junctions of the medial axis are represented as trimmed quadric surfaces, algebraic space curves, and algebraic numbers, respectively. The algorithm works by recursively finding neighboring junctions along the axis. It utilizes discretization of space and linear programming to speed up the search step.

We also present a new algorithm for analysis of the topology of an algebraic plane curve, which is the core of our medial axis algorithm. To speed up the computation, we have designed specialized algorithms for fast computation on implicit geometric structures. These include lazy evaluation based on multivariate Sturm sequences, fast resultant computation, curve topology analysis, and floating-point filters. The algorithm has been implemented and we highlight its performance on a number of examples.

For a solid polyhedron, the bisectors (making-up the medial axes) consists of planar and quadric patches.

Web link.

Given a pattern of objects in continuous space, Voronoi diagrams provide a means of naturally partitioning the space into subregions. This is a rapidly expanding topic as these diagrams find application in such areas as spatial data manipulation, modelling spatial structures and spatial processes, pattern analysis and locational optimization. These areas can be found within many different scientific fields, and consequently this increases not only the use of Voronoi diagrams but also the demand for knowledge about them. This is the first book which, dealing exclusively with these diagrams, meet this demand. Material within is synthesized, unified and presented in a structured form. Emphasis of a particular perspective is deliberately avoided in order to provide a comprehensive and balanced treatment of all aspects of Volonoi diagrams. A wide range of applications drawn from over a dozen fields is discussed, enabling this book to serve as an important reference volume on this topic. This book should appeal equally to those whose interests in Voronoi diagrams are theoretical, practical or both.

* E.C. Sherbrooke is with New Technologies, Inc., Bedford, MA 01730. E-mail: esher@mit.edu. N.M. Patrikalakis is with the Massachusetts Institute of Technology, Department of Ocean Engineering, Cambridge, MA 02139. E-mail: nmp@deslab.mit.edu. E. Brisson is with Boston University, Office of Information Technology, Boston, MA 02215. E-mail: ebrisson@bu.edu.

Prof. Patrikalakis heads the CAD/CAM/CAE group of the Design Lab @ MIT:

• http://deslab.mit.edu/DesignLab/new_deslab/

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 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.

Index Terms: CAD, CAGD, CAM, geometric modeling, solid modeling, skeleton, symmetry, Voronoi diagram, polyhedra.

MAT of Polyhedral solids.

Details here.

Details here.

Details here.

Details here.

Details here.

Summary:

• A wavefront propagation technique is combined with techniques for polygonal approximation of non-manifold implicit surface to give a simple and efficient algorithm.

Details: click here.

Details: click here.

Web link

Demo link

Web link.

BACK

Page created & maintained by Frederic Leymarie, 1998-2004.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu