Graphics Reference
In-Depth Information
Corollary 5.11.4 indicates why it is reasonable to stay with semialgebraic sets in
traditional geometric modeling. Corollary 5.11.5, on the other hand, shows that we
do not get fractals in this way. The next result tells us something about the sets one
encounters when trying to define fractals.
5.11.6 Theorem.
The basis of attraction of a complex rational function g :
C
Æ
C
(which means the union of the basin of attraction of all attractive periodic points) is
a recursively enumerable set over
R
. In particular, it is the countable union of semi-
algebraic sets.
Proof.
See [BlSS89]. It can be shown that g has only a finite number of attractive
periodic points and that there is a polynomial h so that a point is in the basin of g if
and only if h(
z
) < 0 for some
z
in its orbit. The theorem is proved using this h and a
machine very similar to the one in Example 5.11.1.
Not all basins of attraction are decidable. In fact, it is shown in [BlSS89] that the
Julia set and most of its analogs are not recursively enumerable. On the other hand,
one can compute semialgebraic set approximations to Julia sets.
5.12
Conclusions
In the 1970s and 1980s most modelers were based on either the boundary or CSG
representations or both. Here is a summary of the differences between these two rep-
resentations. Roughly speaking, the advantages of the boundary representation are
disadvantages for the CSG representation and vice versa.
Advantages of b-reps:
(1) It is good for efficient rendering algorithms.
(2) It can handle general “free-form” or “sculptured” sur-
faces, that is, “curved” surfaces that typically are
defined implicitly or via parameterizations.
(3) It is good for local modification of models.
Disadvantages of b-reps:
(1) It takes a lot of data structures and space to define
objects.
(2) Object definitions tend to be complicated.
(3) Verification of validity is difficult.
Advantages of CSG:
(1) It is very compact.
(2) It is a natural way to define many objects and
“perfect” for most mechanical engineering parts.
(3) Validity checking is “built in.”
Disadvantages of CSG:
(1) It is not good for rendering because one needs a sep-
arate boundary evaluation algorithm.
(2) It may not be easy to define the motions that place
objects in position for the Boolean set operations.
(3) It is impractical to use for sculptured surfaces or
solids bounded by such surfaces except in the most
