Graphics Reference
In-Depth Information
(1) find and analyze the points and segments in the intersection,
(2) transfer the results to adjacent faces in
X
and
Y
, and
(3) link the various intersection pieces into complete face and edge descriptions.
These steps involve careful analysis of neighborhoods of cells. The six major cases
arise from face/face, face/edge, face/vertex, edge/edge, edge/vertex, and vertex/vertex
intersections.
The authors of [HoHK89] reported that when the algorithm we just described was
implemented, very substantial improvements in robustness were realized compared
with other modelers. Their test cases included such typically difficult cases as finding
the intersection of two cubes, where the second is a slightly rotated version of the
first. We refer the reader to that paper and [Hoff89] for additional ideas about dealing
with accuracy and robustness that we do not have space to get into here. More papers
on robustness can be found in [LinM96]. See also [DeSB92] and [EdaL99]. Often the
problems we have talked about are caused by the fact that they are special cases or
some sort of degeneracy. There is no problem determining whether two lines inter-
sect if they are reasonably skew. Therefore, perhaps one can always arrange it so that
they are or that objects are not almost touching, etc., by perturbing them slightly. This
is the basis for an approach to robustness described in [EdeM90]. Objects are put into
general position by a small perturbation; however, the perturbation is done symboli-
cally. Nothing is actually ever perturbed.
Finally, because conics are such an important class of spaces in modeling, we
finish this section with some facts about the robustness of some of their standard rep-
resentations. Four common ways to define conic curves are:
(1) via the general quadratic equation
(2) in standard form at the origin along with a transformation
(3) via a few points and/or reals (For example, one can define an ellipse in terms
of its center, major axis, and major and minor axes lengths.)
(4) via projective geometry type constructions
Which is best? It is well known that (1) is by far the worst representation. Changing
coefficients even just slightly, can, in certain circumstances, lead to incorrect conclu-
sions as to the type of the conic. According to [Wils87], (2) and (3) are the best with
(3) slightly better.
5.11
Algorithmic Modeling
Sections 5.3.1-5.3.9 discussed various specific approaches to geometric modeling.
This section takes a more global view and tries to identify some unifying principles
behind some of the details. Specifically, the relatively recent generative modeling
scheme and the natural phenomena and physically based modeling schemes are exam-
ples of what is referred to as
algorithmic
or
procedural modeling
in [GHSV93]. Algo-
rithmic modeling refers to that part of geometric modeling where one uses algorithms
to define and manipulate objects or functions rather than nonconstructive definitions.
