Graphics Reference
In-Depth Information
are semantically correct. A sequence of collinear points does not correspond to a
polygon in
O
.
We could modify Example 5.3.1. For example, we could require the polygons to
be convex or we could require that the vertices be listed in counter-clockwise order.
In both instances we would then have an unambiguous representation scheme.
There are reasons for why unambiguousness and uniqueness are important prop-
erties of a representation scheme. It is difficult to compute properties from ambigu-
ous schemes. For example, it would be impossible to compute the area of a polygon
with the ambiguous scheme in Example 5.3.1. An example of why uniqueness is
important is when one wants to determine if two objects are the same. The ability to
test for equality is important because one needs it for
(1) detecting duplication in data base of objects
(2) detecting loops in algorithms, and
(3) verifying results such as in case of numerically controlled (NC) machines
where it is important that the desired object is created
With uniqueness one merely needs to compare items syntactically. Note that the
problem of determining whether two sets are the same can be reduced to a problem
of whether a certain other set is empty, because two sets
X
and
Y
are the same if and
only if the regularized symmetric difference
X
D*
Y
is empty.
Although unambiguousness and uniqueness are highly desirable, such represen-
tations are hardly ever found. Two common types of nonuniqueness are
(1) permutational (as in the example where sequences of points represent a
polygon) and
(2) positional (where different representations exist due to primitives that differ
only by a rigid motion).
Eliminating these types of nonuniqueness would involve a high computational
expense.
The domain of a representation scheme specifies the objects that the scheme is
capable of representing. One clearly wants this to be as large as possible. In particu-
lar, one would want it to include at the very least all linear polyhedral “solids.” One
also wants the domain to be closed under some natural set operations such as union,
intersection, and difference. This raises some technical issues.
One issue that has become very important in the context of representation
schemes is
validity
.
The Basic Validity Problem for a Representation Scheme:
When does a representa-
tion correspond to a “real” object, that is, when is a syntactically correct representation
semantically correct or valid?
Ideally, every syntactically correct representation should be semantically correct
because syntactical correctness is usually much easier to check than semantic
correctness. Certainly, a geometric database should not contain representations of
nonsense objects. The object in Figure 5.7 could easily be described in terms of surface
