TU Vienna > Computer Graphics > Algorithms and Programming Methodology > Research

SSI is a basic problem in CAGD, it is stated very simply: *Given are two
surfaces in R ^{3}, compute all parts of the intersection curve.*
If two surfaces intersect, the result will be either a set of isolated
points, a set of curves, a set of overlapping surfaces or any combination
of these cases. Because exact solutions can be found only for some special
surface classes, approximation methods are used for the general case. We
introduce a fast algorithm for computing an inclusion of the intersection
curve of two general parametric surfaces.

Each surface is defined as:

*Equation: Surface definition.*

where U, V are intervals in R. The coordinate functions map a rectangular parameter domain to object space. It is only assumed that these functions are continuous in the whole domain and that the partial derivatives exist and are continuous, too.

The subdivision algorithm we introduce follows a divide-and-conquer-approach. It avoids loss of any parts of the intersection curve by using safe bounding volumes for all parts (patches) of the surfaces. For each pair of patches, it first checks for intersection of bounding volumes. If two bounding volumes intersect, it splits one patch, and treats all new pairs recursively until a predefined termination condition is satisfied (patches are divided alternately). Interval Arithmetic is used for all critical operations to achieve a robust algorithm.

Using bounding volumes instead of simple approximations guarantees, that all intersection points are detected. The following figures show this for the 2d-case: The (linear) approximations for the curves do not intersect while the bounding boxes enclose all intersection points.

*Figure: Comparison of linear approximations and bounding volumes.*

The algorithm provides two kinds of results. First, it returns in object space a set of intersections of bounding volumes. Secondly it provides for both parameter domains a collection of rectangular pieces supporting the curve.

*Figure: Inclusions for the intersection curves in object space (left) and in both parameter domains (middle and right).*

The major operations are computing bounding volumes for surface-parts, testing whether two bounding volumes intersect and computing the intersection of two bounding volumes.

*Figure: Comparison of an AABB and a parallelogram.*

We construct with the help of intervals of the partial derivatives and the mean value theorem of differential calculus a tight enclosure for the patch. Each parallelepiped containing this enclosure is a bounding volume for the patch.

A detailed description of this method can be found in [98:1], [99:1], and [99:4].

Two convex polyhedra do not intersect if and only if there exists a separating plane which is either parallel to a face of one polyhedron or which is parallel to at least one edge of each polyhedron.

For a detailed description see [98:1] and [99:1]. A second (slower) method for the intersection test, which relies on edge-face intersection tests, can be found in [99:1] and [99:2].

The algorithm stops if a predefined termination condition is satisfied. We get pairs of intersecting bounding volumes containing patches which (possibly) intersect. For each pair we compute the intersection volume, which is an inclusion for the intersection curve of this two patches. The set of bounding volume intersections is an inclusion for the intersection curve of the original surfaces.

We can avoid finding an exact solution for the intersection of two parallelepipeds by computing just an inclusion for the intersection volume, too. A solution bounded to parallelepipeds can be found in [99:1] and [99:2].

*Figure: Calculating parts of a surface which definitely do not intersect with a parallelepiped enclosing a second patch.*

For each corner point we get a linear interval equation and as solution a line in parameter space, which separates the parameter domain of the patch into three regions:

- One region definining all points of the patch which definitely lie on the same side as the corner point,
- one region defining all points which possibly lie inside the slab, and
- one region defining all points of the patch which definitely lie on the other side of the slab.

*Figure: Original domain, triangular cut-offs, and reduced domain.*

The basic algorithm needs only to be modified slightly: We add the
`cutDomain`-operation, which reduces one surface (and the corresponding
domain) against the bounding volume of the other surface.

These improvements are introduced in [99:1] and [99:4].

The computation of Tripipeds and the modified intersection algorithm can be found in [99:3].

The best performance shows the hybrid algorithm with `cutDomain`-
operation. A factor of up to ten and even more can be achieved, depending
on the surfaces and termination condition.
For some examples see results
(warning: this page contains a couple of pictures!).

`asia`-Source code (under GNU Public License) will be available by ftp on this
page as soon as possible.
If you are interested in a **very preliminary version** (German
comments, lots of debug-code), please contact
huber @ads.tuwien.ac.at.

If you have any suggestions, corrections or additions with regard to our web pages, please send an e-mail to webmaster @ads.tuwien.ac.at. Last modification: E. Huber, 1999-Jun-15