##
Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Space

Michal Meyerovitch

### Abstract

Lower envelopes are fundamental structures in computational
geometry that have many applications, such as computing general
Voronoi diagrams and performing hidden surface removal in computer
graphics. We present a generic, robust and efficient
implementation for computing the envelopes of surfaces in
$\reals^3$. To the best of our knowledge, this is the first exact
implementation that computes envelopes in three-dimensional space.
Our implementation is based on \cgal\ and is designated as a
\cgal\ package. The separation of topology and geometry in our
solution allows the reuse of the algorithm with different families
of surfaces, provided that a small set of geometric objects and
operations on them is supplied. We used our algorithm to compute
the lower and upper envelope for several types of surfaces. Our
implementation follows the exact geometric computation paradigm.
Since exact arithmetic is typically slower than floating-point
arithmetic, especially when higher order surfaces are involved, we
minimize the number of such operations, to gain better performance
in practice. Our experiments show interesting phenomena in the
behavior of the divide-and-conquer algorithm and the combinatorics
of lower envelopes of random surfaces.

Code for computing 3D envelopes

Extended experimental results

Some input sets (for triangles and spheres)

### Examples of envelopes computed by our program

Envelope of approximately 16000 triangles:

Envelope of 50 spheres: