[Computer Graphics Logo]

Surface-to-Surface Intersection Algorithms




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

Surface-to-surface intersection

(Barth, Huber)

This page surveys our work on algorithms for finding an approximative solution for the surface-to-surface intersection (SSI) problem. You can find detailed descriptions of the introduced methods in several publications done by our group.

SSI is a basic problem in CAGD, it is stated very simply: Given are two surfaces in R3, 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:

Eqution: Surface definition

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.

linear approximation bounding volumes

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.

3d curve 2d subdivision and 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.

Bounding volumes for surface-parts

Evaluating the formulas of the coordinate functions of a surface by interval arithmetic provides an axis aligned bounding box (AABB) for the surface. AABBs generally overestimate the enclosed patches, thus leading to unnecessary subdivisions and intersection tests. Therefore, we use tight parallelepipeds as bounding volumes. A parallelepipeds is a better enclosure, taking the shape and orientation of the patch into account (next figure shows the 2d-case).

AABB vs. parallelogram

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].

Bounding volume intersections

The second major operation we need is the test whether two bounding volumes intersect. While this test is trivial for AABBs, it is not for parallelepipeds. Since parallelepipeds are convex polyhedra, we may apply the separating axis theorem:

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].

Fast Subdivision

The algorithm relies on enclosing the patches of the surfaces and splitting them by dividing the parameter domain of one patch. Considering a pair of intersecting patches, the subdivision process can be accelerated by an early detection of parts of a patch which definitely do not intersect with the other one. Parts of the parameter domain where one patch cannot reach the enclosure of the other one can be determined from the intervals of the partial derivatives (similar to the interval Newton method). By applying the mean value theorem of differential calculus we determine for each corner point those parts of the patch and the corresponding region in parameter space, which definitely lie outside of a parallelepiped enclosing the other surface (shown in the following figure for a corner point of a patch and only one pair of planes (slab)).

3d: computing dispensable parts

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:

  1. One region definining all points of the patch which definitely lie on the same side as the corner point,
  2. one region defining all points which possibly lie inside the slab, and
  3. one region defining all points of the patch which definitely lie on the other side of the slab.
Considering only case (1) we get for each corner point a triangular region which is dispensable (see next figure). By cutting off such parts, we reduce the number of surface splits, thus the number of bounding volume computations and intersection tests is reduced.

2d: computing dispensable parts

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.

procedure intersect(Surface fi, gj) // Improved divide-and-conquer SSI-algorithm fi*=cutDomain(fi,boundingVolume(gj)) // reduce the domain of fi if boundingVolumesIntersect (fi*, gj) then if termCondition (fi*, gj) then // e.g. parameter domain small enough intersectBoundingVolumes(fi*, gj) else splitSurface(fi*,f2i+1,f2i+2) // split fi by splitting its domain intersect(gj,f2i+1) // swapping parameters causes an intersect(gj,f2i+2) // alternating subdivision of fi and gj

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

Patches with triangular domains

We currently investigate patches with triangular domains. Triangular domains offer more freedom than axis aligned domains, because they allow us to subdivide a patch in an arbitrary manner by triangulating its domain. In object space we get patches with three corner points which can be approximated by triangles and enclosed by a bounding volume we call ``Tripiped''. This allows to take full advantage of the above introduced optimization step.

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

Results

We constructed several versions of this algorithm. An algorithm using AABBs only, a pure epiped algorithm, and a hybrid algorithm. The latter two can be executed with and without cut-offs as explained. The hybrid algorithm first tests if the AABBs intersect and if they do, then epipeds are computed and tested.

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!).

Publications

Several papers (conference talks), theses (PhD and diploma), and technical reports emerged during the last years from this work. See publications for a detailed list, some of them (or abstracts of them) are available as gzipped ps-file.

Implementation

We integrated all algorithms in an experimental system called asia. We used C++ (gcc) for the algorithmic part and TCL/TK for the user-interface under the Linux operating system. For true interval arithmetic we used the BIAS-Library from TU-Hamburg/Harburg. For visualizing surfaces we used our flirt-ray tracer.

[SSI Logo]

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