Graphics Reference
In-Depth Information
13.5.5.2
Example.
We redo Example 13.5.5.1 using the projection approach.
Solution.
We can skip Steps 1 and 3 this time because there are no singularities
when resolving on x. Using the resultant which eliminates x from f and g, we get
22
Ê
40
yz
+-
1
0
ˆ
Á
Á
Á
˜
˜
˜
22
04
0
yz
+-
1
()
=
Rfg
,
det
x
22
12
-
yz
+
-
0
Ë
¯
22
01
2
yz
+
22
2
(
)
+
(
)
-
22
=
9
yz
+
22
yz
+
11
.
This again defines a circle in the y-z plane. If we had tried to eliminate the y variable
we would have a problem because
22
10 4
xz
+-
1
0
Ê
ˆ
Á
Á
Á
˜
˜
˜
22
01
0
4
xz
+-
1
()
=
Rfg
,
det
y
2
2
10
xxz
-+
2
0
Ë
¯
2
2
01
0
xxz
-+
2
2
(
)
2
=-
321
xx
-
+
.
We need Step 1 and 3 in general to make sure that there are no singularities in the
projection. We were lucky when we chose x originally.
A major problem with algebraic approaches is that algorithms for finding solu-
tions to high-degree polynomial equations are numerically unstable. It is also com-
putationally expensive to compute resultants. By combining elimination theory with
matrix computations the authors of [ManD94] tried to avoid these problems. Rather
than finding roots of polynomials they had to find eigenvalues of matrices. Algorithms
for finding eigenvalues are known to be stable. The algorithm in [ManK97] builds on
this approach. Because one only needs the eigenvalues in a certain range, the new
algorithm saves time by not computing those that are not needed.
13.6
Summary
In this chapter we have seen some of the difficulties involved in finding the intersec-
tion of objects. For that reason, many special cases have been studied extensively to
get the best possible results. We have looked at some of these. Intersections of lines,
conics, and quadrics are other special cases about which much is known. Here are a
few of those and references to optimized algorithms for them:
Rectangular solids and convex polyhedra:
[Gree94]
Line and cylinder:
[Shen94]
Ray and cylinder:
[CycW94]
Line and cone:
[Shen95]
Ray and quadric surface:
[CycW92]
Parametric cubics:
[Klas94]
