Graphics Reference
In-Depth Information
Numerical analysis is clearly the first place to look for answers about accuracy in
a world of approximations. A lot is known about the accuracy of the output of a com-
putation given the accuracy of the input. For example, to get precise answers with
linear problems one would have to perform computations using four to five times the
precision of the initial data. In the case of quadratic problems, one would need forty
to fifty times the precision. Sometimes there may be guidelines that help one improve
the accuracy of results. Given the problems with floating point arithmetic, one could
try other types of arithmetic.
Bounded Rational Arithmetic.
This is suggested in [Hoff89] and refers to restrict-
ing numbers to being rational numbers with denominators that are bounded by a
given fixed integer. One can use the method of continued fractions to find the best
approximation to a real by such rationals.
Infinite Precision Arithmetic.
Of course, there are substantial costs involved in
this.
“Exact” Arithmetic.
This does not mean the same thing as infinite precision
arithmetic. The approach is described in [Fort95]. The idea is to have a fixed but rel-
atively small upper bound on the bit-length of arithmetic operations needed to
compute geometric predicates. This means that one can do integer arithmetic.
Although one does not get “exact” answers, they are reliable. It is claimed that bound-
ary-based
faceted
modelers supporting regularized set operators can be implemented
with minimal overhead (compared with floating point arithmetic). Exact arithmetic
works well for linear objects but has problems with smooth ones. See also [Yu92] and
[CuKM99].
Interval Analysis.
See Chapter 18 for a discussion of this and also [HuPY96a] and
[HuPY96b].
Just knowing the accuracy is not always enough if it is worse than one would
like. Geometric computations often involve many steps. Rather than worrying about
accuracy only after data structures and algorithms have been chosen, one should
perhaps also use accuracy as one criterion for choosing the data structures and
algorithms.
One cause for the problem indicated in Figure 5.48 is that one often uses differ-
ent computations to establish a common fact. The question of whether the line
segment intersected the edge of the cube was answered twice - first by using the face
f
and second by using the face
g
. The problem is in the redundancy in the represen-
tation of the edge and the fact that the intersection is determined from a collection
of isolated computations. If one could represent geometry in a nonredundant way,
then one would be able to eliminate quite a few inconsistency problems. Furthermore,
the problem shown in Figure 5.48 would be resolved if, after one found the intersec-
tion with face
f
, one would check for intersections with all the faces adjacent to
f
and
then resolve any inconsistencies.
We give a brief overview of an approach to achieving robust set operations on
linear polyhedra described in [HoHK89] and [Hoff89]. It involves both data structures
