Graphics Reference
In-Depth Information
CHAPTER 13
Intersection Algorithms
Prerequisites: Basic calculus and vectors, Section 4.7 in [AgoM05] (Newton-Raphson
method), Sections 10.4, 10.9, 10.10, and 10.15 in [AgoM05] for Sections
13.5.2 and 13.5.5
13.1
Overview
Set operations are common types of operations performed in geometric modeling. It
is therefore important to have efficient algorithms for them, but mathematical solu-
tions are only part of the problem. Set operation algorithms very often tend to involve
relatively complex numerical computations and, even if they do not, they invariably
are driven by the outcome of numeric tests, such as whether some quantity is zero or
not. If there is ever a place where the shortcoming of a computer's finite precision
arithmetic is apparent, then this is one of those places. Questions such as whether
two lines or planes intersect, which are simple to answer mathematically, become
complicated to answer in a consistent manner. Therefore, the accuracy and robust-
ness of solutions are major criteria for evaluating algorithms. Speed is also impor-
tant. It is possible to do infinite precision arithmetic on a computer, but the problem
with this approach is speed. Next to infinite precision, interval arithmetic seems to be
the best way to achieve accuracy. There are intersection algorithms for “interval”
curves and surfaces, but they will not be discussed due to space and time limitations.
The interested reader is referred to [HMSP96] and [HMPY97].
This chapter describes various approaches to finding intersections of objects.
Actually, since finding intersections of linear objects reduces mathematically to solving
basic linear algebra problems, we are mainly interested in the more complicated case
of smooth object intersections. The only exception to this is Section 13.2, which
describes a simple test for whether two convex linear polyhedra intersect. Sections
13.3-13.5 make up the bulk of the chapter. They describe algorithms for various types
of intersections. Unfortunately, all we have time for is to describe the steps and the
mathematics behind some of the algorithms and will have little to say on important
implementation details for ensuring accuracy and robustness. The reader will have to
Search WWH ::




Custom Search