


Interactive Geometric
Computations Using Graphics
Introduction
As the performance and programmability of graphics processing units
(or GPUs) increases, the GPU begins to appear more like a general
processing unit or a coprocessor to the CPU, running in parallel
with it. Future generations of graphics hardware will likely make
the graphics pipeline—once a fixedfunction series of steps
designed with the sole purpose of rendering triangles to the display—resemble
even more a general programmable stream processor. Consider all
the computational power a GPU provides. Rich in highly pipelined
computational units, the GPU provides an efficient streaming model
of computation. Furthermore, GPUs have very high memory bandwidth,
able to access multiple gigabytes of memory per second. Yet on the
other hand, the nature of the graphics rendering pipeline means
that GPUs process data in relative isolation: typically a single
vertex enters the pipeline with its associated data and is processed
independently, for the most part, from the vertices that follows.
In addition, GPUs are largely hardwired to run a single highly specialized
pipeline as fast as possible; though parts of the pipeline can be
programmed, there is no sense of control flow as there is in a CPU.
The only way to simulate control flow, or decisionmaking, is to
make multiple rendering passes, where the current pass uses buffer
data (typically stencil buffer) generated in a previous pass.
Course Highlights
In their course entitled “Interactive Geometric Computations
Using Graphics Hardware”, Dinesh Manocha of the University
of North Carolina at Chapel Hill, Michael Doggett of ATI Technologies
Inc., Ned Greene and Mark Kilgard of NVIDIA Corporation, Ming C.
Lin and Dinesh Manocha of University of North Carolina at Chapel
Hill, and Shankar Krishnan of AT&T Labs presented their ideas
and contributions on the use of graphics hardware to perform interactive
geometric computations. The course aimed to demonstrate applications
in such areas as visibility, collision detection, shadow volumes,
and problems involving the use of generalized voronoi diagrams.
Dinesh Manocha explained how graphics hardware could be used in
a conceptually simple way (that is also easy to implement) to calculate
an approximation of a generalized voronoi diagram.
In brief, a voronoi diagram consists of primitives and cell regions.
Primitives may be line segments, curve segments, or points (for
simplicity, only points will be considered here). Consider a set
of five point primitives, labeled A through E, on a plane. Now consider
a region around primitive A such that every point within that region
is closer to
primitive A than any of the other four primitives. This region forms
a voronoi cell around primitive A. Now consider the region around
primitive B such that every point in that region is closer to primitive
B than any other primitive—and so on. Note that there will
be points on the plane that are as close to one primitive as to
another primitive (or more than one other primitive). These points
form the border between the voronoi cells. Voronoi diagrams have
a variety of applications including motion planning, medial axis
computation, and nonphotorealistic rendering.
Note that because graphics hardware is involved—with its
inherent limitations on the accuracy of computations due to the
precision of the values supported in the graphics pipeline—,
only approximations of the solutions to any problem can be found.
In the problem of generating a voronoi diagram for a set of primitives,
the approximation comes from the fact that any image generated in
a GPU’s framebuffer is, by the very nature of rasterized graphics,
pixilated. The bruteforce algorithm to find the voronoi diagram
based on a set of primitives is simple but ineffective: for each
point (or pixel, in the graphics hardware approximation) in the
plane, determine the distance to each primitive and identify the
closest one. Then, color that pixel with a color that is unique
to its closest primitive, thereby forming voronoi cells. Pixels
that are equidistant to two or more primitives may be colored black
to represent the boundary of the voronoi cells.
Dinesh Manocha and Ming Lin described an old yet efficient method
for approximating voronoi diagrams that ports well to graphics hardware.
Notice that if the apex of a right circular cone is aligned with
every point primitive in the plane, the projection of the orthographic
projections (or a “birds eye view”) of the cone intersections
onto the plane form the boundaries of the voronoi cells, and the
projected cones themselves form the interior of the cells. Furthermore,
if preserved, the depth value (the distance from the primitive point
to the cone) at each pixel in the plane is proportional to the distance
from that pixel to its closest primitive. The University of North
Carolina group’s new approach to the same problem involves
distance functions. Unlike the bruteforce method, this approach
avoids perpixel distance evaluation by coarsely pointsampling
the distance function in a region near the primitive, in order to
generate a polygonal mesh approximation that will render much faster
on the graphics hardware. Among the group’s most important
contributions are the specialized algorithms to efficiently construct
such distance meshes for various 2D primitives (recall that these
can include not only points, but line segments and curves also).
Other problems and their graphics hardware solutions presented
in the course included shadow volumes, digital geometry processing,
and visibility culling.




