Examples of Degenerate Geometry

(and what intersect does with them...)

Degeneracies arise in geometric data due to the special position of two or more objects. Well-known examples in three-dimensions include co-planar, co-linear, or co-located points, and its even possible for two line segments to intersect exactly in three dimensions. More diabolical cases include those where two line segments in special position overlap without sharing an end point, or even having the decency to be co-linear. While seemingly unlikely (mathematically) degenerate data is common in the real world, and especially the somewhat quantized world of computational geometry.

 In Application Challenges to Computational Geometry the CG Task force writes:

The effect of degeneracy is to vastly increase the number of special cases. While a sorting algorithm must deal only with the possibility of two keys being equal, a typical geometric algorithm faces the possibility of dozens or hundreds of different special cases[..]. The presence of numerical data, added to the inherent completxity of geometric data types, makes geometric algorithms much harder to [robustly] implement correctly than combinatorial (say, graph-theoretical) ones. They are also much harder than just purely numerical algorithms (such as those addressed by numerical analysis) many of which consist of large chunks of straight-line code. Since the overall utility of an implementation may depend upon the correct treatment of special cases, the handling of specail cases can permeate the implementation. (http://www.cs.princeton.edu/~chazelle/taskforce/CGreport.ps.Z) )[emphasis mine]

Here are a few examples of intersecting polyhedra and what intersect does with them while computing the triangulation of the exposed surface.

Single point co-planar with a face

 (resulting polyhedra)

Co-planar faces with no common points

 (resulting polyhedra)

Four coplanar faces with no common points

 (resulting polyhedra)

For more information mail to: aftosmis@nas.nasa.gov
Return to Cart3d or Michael Aftosmis's homepage 
last update 1 Apr 96