3D Voronoi Diagrams and Medial Axis

Voronoi Diagram of Point sites

• Set S of point sites
• Distance function: d(p,s) = Euclidean distance

Def: Voronoi Diagram

partition of space into regions VR(s) s.t.
For all p in VR(s),    d(p,s) < d(p,t) for all t not = s.

2D:

• Voronoi polygons = Voronoi regions
• Voronoi edges (equidistant to 2 sites)
• Voronoi vertices (equidistant to 3 sites)

Alternative Def:

Given 2 sites s,t,
the bisector B(s,t) of s and t is the set of points p equidistant to s and t (generators)

Example: bisector of 2 points is a line.

Def: The dominance region of s over t is the set of points closer to s than t.

Example: dominance region of a point in a 2 point set is a half-space.

Def: Voronoi region VR(s):

Question: How to find a vertex of VR(s) ?

In 3D:

• Voronoi regions = polytopes (convex polyhedron)
• Voronoi faces (bisectors, bound polytopes)
• Voronoi edges (intersections of faces)
• Voronoi vertices

Voronoi region of point in the center: (cross-eyed stereo pair)

---

Construction:

Convex Hull in 4D + duality (similar to 2D case)

• Map (x,y,z) --> (x,y,z, x² + y² + z²)
• Compute CONVEX - HULL  in R⁴.      Takes O(n²) time.
• Map to Delaunay triangulation in R³
• Tetrahedron circumsphere centers --> Voronoi vertices
• Tetrahedron faces --> Voronoi edges

Alternate point of view (2D):

Front propagation / prairie fire analogy.

At time t the front (fire) is a set of circles of radius t.
Circles intersect at Voronoi edges.

What is the relation to the distance function?

Voronoi edges = ridges of distance function.
Take min of all distance cones --> graph of distance function from all sites.

Generalizes to 3D (spheres growing from point sites).

General Definition: Medial Axis of a surface

Def: Set of points in space equidistant to 2 or more points on the surface.

Def: Locus of the centre of an inscribed sphere of maximal diameter as it rolls along inside the interior of a solid.

Examples:

See also the Geometry in action page (Eppstein)

Voronoi Diagram of polygon sites

• Set S of polygons
• Distance function: d(p,s) = Euclidean distance

2D:

Set of edges.

Bisectors:

Voronoi diagram:

Note: Voronoi diagram of convex polygon is linear.

Problem: Voronoi edges not well defined by distance function

Solution 1: Use bisector of edges as above.

Problem: How to do this in 3D?

Solution 2: Add vertices as sites:

Advantage: a bisector now has only ONE mathematical definition (formula).

Corresponding Voronoi diagram:

Application: determine which feature (vertex/edge) is closest to a query point.

Algorithm: incremental construction [Michael Seal, using LEDA]

HARD: why?

Intersection of quadratic curves,    exact arithmetic...

Wavefront point of view

• Wavefront meets at Voronoi edges
• Voronoi edges appear where wavefront changes from flat to circular (not in Medial Axis).

---

Difference between Voronoi Diagram and Medial Axis

The medial axis is a subset of the Voronoi diagram of the edges and vertices of the polygon.
Voronoi edges that meet the reflex vertices are not part of the medial axis.

---

3D Voronoi Diagrams of polygons:

Bisectors:

Edges:

Curves of algebraic degree <= 4.

Question: How to compute suface equidistant surface between 2 objects?

No general exact algorithms for VD of triangles currently. Why?

--> use approximation algorithm!

0. Exact algorithm for convex case

Property: For convex polygonal objects, bisectors are linear.

Algorithm (based on wavefront idea):

• Input: set of planes: P₁, ... P_n forming polyhedron
  Equations: P_i:   a_i x = b_i   with a_i unit.
• Build planes Q_i at a distance t from P_i:    a_i x + t = b_i
• Consider Q_i as planes in 4 dimensions.
• Take intersection of half-spaces  a_i x + t <= b_i
  ---> get graph of distance function (distance to all bounding planes P_i)
• Project back to R³ by eliminating t.

Running time O(n²). Why?

---

Approximation idea: definitions of VD and MA are essentially the same.

1. Surface sampling + Voronoi diagram

• Sample surface of object uniformly
• Compute Voronoi diagram of samples
• Extract Medial Axis approximation

2. Following ridges of distance function

Use numerical technique to follow curve where fronts meet.
Computes skeleton of medial axis (edges, vertices).

[E. Sherbrooke, N. Patrikalakis, Solid Modeling 1995]

Drawback?

3. Hierarchical voxel approximation

[Overmars et al.]

Idea:

• Divide space into cells (ex. voxels)
• Label cell corners by closest object (triangle)
• Identify cells containing Voronoi diagram

Property: Cell C intersects Voronoi diagram if number of labels L(C) > 1

Question: Is this an iff?

Examples.

3d Voronoi diagram skeleton of a set of tetrahedra (stereo pair):

2d example showing hierarchical subdivision:

Cell Approximation with surface extraction

Use marching cubes-like algorithm for approximating Voronoi surfaces.

Use labels on corners:

3D: Different cases for cell labels:

Dealing with cell labels.

Determine which Voronoi regions intersect cell.

Fact [Teichmann & Teller]: Voronoi region of t intersects cell C iff point closest to t on C is closer to t than any other site.

Bounds

Worst-case complexity of the medial surface of a polyhedron?

Upper bound is O(n^3+e).

Lower bound example with Omega(n²) faces:

See Jeff Ericson's comments.

1. Voronoi Diagrams.

Motion Planning

Find path with large clearance to obstacles: [Overmars et al.]

How to deal with non-point or non-circular objects?

---

Collision Detection

[SIMpact robot simulation system, Stanford]

Idea: For a pair of convex objects, keep track of pair of closest features. HOW?

See [Lin, Canny]

Animation:

Works only for convex objects. Generalization to non-convex objects.

---

Nearest neighbor precomputation

Use with point location in Voronoi cells.

---

Ray casting

1. Use Voronoi subdivision of space. To each region attach list of objects intersecting the region.
    [ See Graphic Gems IV]
2. Use Voronoi-based octree decomposition (as in Overmars' work).

2. Medial Axis

Mesh generation.

Steve Owen's Survey

---

Skeletons for Animation

<demo anim1, anim2>