\documentclass[12pt]{article}
\newcommand{\vect}[1]{\overline{#1}}
\newcommand{\dist}{\mbox{dist}}
\newcommand{\source}{\mbox{source}}
\newcommand{\grad}{\nabla}
\begin{document}
\section{Introduction}

$\Gamma$ (``the manifold'') will be a collection of points, lines, or (in 3D) polygons.

Definition of distance function to $\Gamma$:
\[ u(\vect{x}) = \dist(\vect{x}, \Gamma) = \min_{p\in\Gamma} |\vect{x}-p| \]

If $\Gamma$ is a collection of polygons (2D) or polyhederons (3D), may
want signed distance (negative inside, positive outside).

Definition of closest point function:
\[ \source(\vect{x}) = \left\{ \vect{y}\in\Gamma |
\ \left|\vect{y}-\vect{x}\right|=u(\vect{x}) \right\} \]

[FIGURE 2]

Goal: compute the value of the distance function or closest point
function on a regular grid.

Alternative formulation of distance function:
``viscosity solution of the Eikonal equation:
$| \grad u | - 1 = 0$ with $u(\vect{x}) = 0$ for $\vect{x} \in \Gamma$.''

Supposedly equivalent to: $u(\vect{x}) = \lim_{\epsilon\to 0}
u^\epsilon(\vect{x})$ where $u^\epsilon$ solves the parabolic equation
$|\grad u^\epsilon| -  \epsilon \Delta u^\epsilon = 1$ ($\epsilon >
0$).  Solution exists and is unique.

Applications: level set methods for moving interfaces, motion
planning, (generalized) Voronoi diagrams.

Definition of Voronoi diagrams: if $\Gamma$ is a discrete set of
points (called ``Voronoi sites''), then a Voronoi diagram partitions
space into regions, where each region consists of all points closer to
one site than any other.  One form of generalized Voronoi diagram, the
sites are allowed to be lines or polygons.  Generalized Voronoi
diagrams are useful for, eg, computing the medial axis.  [COVER PLATE]

Note that since the methods here only compute the closest point
function on a grid, they only give the Voronoi diagram approximately.

All presented solutions scale linearly with grid size, and work in
both 2D and 3D.

\section{Approximate solution}
``Rapid and Accurate Computation of the Distance Function Using
Grids'' by Yen-hsi Richard Tsai, 2000-2001.

Idea (distance function case): Initialize grid to $\dist=\infty$.
Iterate through elements of manifold, compute exact answer for
adjacent grid points, mark those grid points immutable.  Can now
forget about the manifold.  Sweep in a diagonal direction:
given neighbors and $\sqrt{2}$-neighbors from ``before'' determine new
distance.  If smaller than original distance, replace.

To determine new distance, see if the circles/spheres of neighbors
represent a consistent intersection (if two, use the farther).
Inconsistent if, for example, triangle inequality violated, in which
case we discard the largest distances.  This gives an algorithm
(``sphere intersection solver'') that works with a discrete manifold.

To extend this to work with line segments in 2D or polygons in 3D, we
need to detect when a combination of distances represents a plane.
Switch to Godunov computation in those cases, since exact for lines
(only need distances at three points since that determines the plane).
[FIGURE 1] 

Closest point procedure: instead of storing distance, can store
element of manifold.  Uses more memory, gives more accurate results,
avoids computing sphere intersection, but lots of distance
computations.

Typically sweep through grids in each of the $2^d$ diagonal directions
and achieve convergence (though they have no proof).

Can never be fully accurate since assumes that closest point to
$\Gamma$ at a grid location is one of the closest points for
neighboring grid locations.  Refining the grid helps.  Closest point
formulation solves remaining source of error: ambiguity of just using
distances.

Error is $O(h)$ where $h$ is the grid spacing.  [FIGURE 5, TABLE II-IV]

Pros: pretty fast, low memory usage, better than Godunov, can be
within machine precision in many cases, works in 2D and 3D.

Cons: approximate, not obviously parallizable, first have to compute
exact answer near manifold, no signed distance?

\section{Scan conversion solution}

``A Fast Algorithm for Computing the Closest Point and Distance
Transform'' by Sean Mauch, December 2000.

Assume only care about finding distances for grid points at most $d$
from $\Gamma$.

Initialize grid to have $\dist = \infty$ as before.  Josh: probably
want to use a sparse representation, anyway.

Scan conversion: determines a list of grid points inside a polygon.
$O(\mbox{edges} + \mbox{rows} + \mbox{grid points inside})$ for small
polygons (relative to grid size), $O(\mbox{grid points inside})$ for
large polygons.  Can take 2D slices of a polyhedron to scan convert in
3D.

Define ``region of influence'' (ROI) for edges to be rectangle
perpendicular to edge (width $d$), for vertices wedges defined by
normals of adjacent edges (min radius $d$).  [FIGURE 3 and 4].
For each edge and vertex, scan convert ROI, brute force update
distances of each grid point in ROI if vertex/edge closer than its
current distance (with a tight loop).

In 3D, regions of influence for faces is face swept in normal
direction.  ROI of edges is triangular prism.  ROI of vertices is
faceted cone with facets determined by normals of adjacent
faces. [FIGURE 6]  Algorithm otherwise the same.

Claims to handle signed distance, works since compares absolute value
of distance in inner loop in update decision.

Complexity: $O(rN+M)$ where $N$ is number of grid points a distance
$d$ from $\Gamma$, $M$ is number of elements in $\Gamma$, and $r$ is
average overlap.  For small $d$, $r$ will also be small.

Pros: exact answer, parallizable, applicable to level-set methods,
sparse solution.

Cons: inefficient far from $\Gamma$, works only on polygons/polyhedra
(could be generalized to points, but would be pretty inefficient).

Basically, this algorithm probably sucks unless you can can limit $d$.
Coming up with an upper bound for $d$ on a per element basis, would
help this algorithm a lot.


\section{Video hardware solution}
``Fast Computation of Generalized Voronoi Diagrams Using Graphics
Hardware'' by Kenneth Hoff, et al, 1999 (Siggraph).  Idea for discrete
$\Gamma$ around since Siggraph 90 article by P. Haeberli.

2D: use cones for points; two rectangles plus two half-cones for line
segments; two rectangles plus part of a cone for each edge of polygon
[FIGURE 7].  Higher order curves approximated by polygons

Cones approximated by triangle fan.  To get less than a grid point of
error: A $512 \times 512$ grid needs fans with 60 triangles.  A
$1024\times 1024$ grid needs fans with 85 triangles.  Can use more
triangles to get subpixel precision, fill limited anyway.

3D: Compute a whole bunch of 2D slices, for each possible $z$ value.
Have to precompute meshes for $\dist(x,y)=dist(A,(x,y,z_0))$ for
points and lines.  Mesh for distance to a line is an elliptical cone,
eccentricity determined by line's angle with plane.  Influence of a
line is restricted to region between two lines.  Mesh for distance to
a point is one sheet of a hyperboloid of revolution. [FIGURES 8--10,
PLATE 3]

Pros: fast (GeForce4 440 Go: 880million texels/sec, GeForce4 Ti:
trillion ops/sec, 1-5 billion pixels/sec (real-theoretical), ATI
Radeon 9700 pro 1.8 billion pixels/sec, doubling every six months),
nearly exact answer, can trade accuracy for speed, can weight sites
differently, can compute farthest-site Voronoi diagram, can compute
distance and closest point at same time.

Cons: meshing error, limited to depth-buffer precision (16-32 bit
fixed point, contrast with 23 bit standard floating point), 1000x1000
tiles, requires special hardware/libraries (though OpenGL quite
portable, and the hardware is now quite common/cheap), not sparse.

Bounds on max distance improve performance a lot (fill-rate limited).

\end{document}