Graphics Reference
In-Depth Information
Some more references for intersections of quadrics are [OckS84], [GolM87], [Mill87],
[OweR87], [SheJ87], [FaNO89], and [Gold83] (for quadrics of revolution). The special
case of ruled surfaces is considered in [HeKE99]. [HMPY97] describes a robust inter-
val analysis approach. [FaNO89] studies a class of degenerate quadric intersections
that are rather common cases. Because the intersection curves in these cases admit-
ted rational parameterizations, algebraic methods could be applied. Specifically, the
approach described in [FaNO89] made use of both the Segre characteristic of a quad-
ratic form (which is something determined from the multiplicities of roots to an
associated polynomial) and the projecting cone of a space curve (which is the ruled
surface determined by the pencil of lines through the origin and points on the curve)
with multivariate polynomial factorization algorithms. An equivalent approach was
described in [WilM93] that was somewhat simpler and facilitated the display of the
intersection curves.
For cyclide intersections see [MaPS86] and [John93]. For formulas for the
intersection of a ray with various objects see [Hain89] and [Hanr89]. More references
for the general intersection problem can be found in [AbdY97] and [HosL93].
[MarM89] and [LuMM95] address the difficult tangential surface-surface intersection
problem.
Note that nothing has been said about set operations on CSG objects. The reason
is that there is nothing new to say in that regard. The fact is that if we apply set oper-
ations to two CSG objects, then we get another CSG object, so that the problem is
dealt with in the context of the boundary evaluation algorithm for CSG. See Section
5.9.
Methods, such as marching methods, which use Newton-Raphson iteration some-
where along the line, are the most common. [BarK90] has a comparison of some
marching methods. [DoSY89] compares marching and recursive subdivision methods.
Pure marching techniques tend to be faster, because the Newton-Raphson method
has a quadratic rate of convergence, but are liable to failure because they are very
sensitive to local singularities. Pure recursive subdivision techniques need no starting
points and tend to be more robust but are less efficient. They can produce an exces-
sive amount of data for a fixed tolerance when singularities are present. [DoSY89]
describes a method that is a combination of the two where one uses recursion to dis-
cover the geometry and iteration for accuracy. [AzBB90] compares the two methods
for Bézier surfaces and shows that iteration is more accurate. An approach that com-
bines marching and algebraic methods can be found in [KriM97]. It uses a matrix
representation for the intersection curve.
The homotopy method described in Section 13.5.3 has not been used much in
geometric modeling. Marching methods can actually be considered to be a kind of
special case. The papers [LamM95] and [LamM96] compare the two methods, and
the authors argue that the homotopy method has advantages over methods based on
standard Newton-Raphson iteration. It also needs a “starting solution” but often has
better convergence properties. Basically, the problem is that the basins of attraction
for the Newton-Raphson method (the points to which one converges) tend to be
fractal-like whereas the corresponding sets for homotopy methods are smoother. They
are semialgebraic sets when one is solving algebraic systems. It is the chaotic nature
of the Newton-Raphson method that causes its problems. The negative aspect of
homotopy methods is that according to [LamM96] they are roughly 10-20 times
slower than Newton-Raphson methods (
assuming
that the latter converge). The paper
describes how homotopy curves are followed.
