Graphics Reference
In-Depth Information
Figure 5.35.
Relationship between functions
and algorithms.
In a modeler mathematical functions get replaced by algorithms. We want a
commutative diagram as shown in Figure 5.35. Some issues that arise are:
(1) A “correct” algorithm must perform the “correct” action on all
valid
inputs.
This is a serious issue in the context of computers because of round-off errors.
For example, finding the intersection of two rectangles should work if they
only touch along a face.
(2) If an input to an algorithm is meaningless or invalid the algorithm should
(a) inform the user, and
(b) still return some answer which will not cause the system to crash
(3) An algorithm should be efficient. If objects have several representations it
should be smart enough to pick the best one for its task.
(4) An algorithm should be as general as possible to allow extensions.
We can see from this discussion that modelers must deal with many tasks that
fall into the field of computational geometry, which deals with finding geometric
algorithms and analyzing them. In this regard we should mention the relatively new
but growing area of research into genetic algorithms. These algorithms are a class
of search algorithms that are proving to be very useful in the complex optimization
problems encountered by modelers. An overview of this topic can be found in
[RenE03].
5.8
Data Structures
5.8.1
Data Structures for Boundary Representations
Anyone interested in implementing a geometric modeling program will quickly face
the problem of choosing appropriate data structures for the geometry that is to be
modeled. As usual, one wants data structures that will be efficient in both space and
execution times of algorithms. This section will briefly look at this issue in the case
where we use a boundary representation for linear polyhedra. The next section will
look at what one can do in the case of volume rendering.
Rendering linear polyhedra, or cell complexes in general, involves two parts: the
abstract structure of the complex and the actual data. To describe the structure means
describing various adjacency relations between the cells of the space.
