Graphics Reference
In-Depth Information
Therefore, before continuing, we need to answer the question: When can a space
be described in terms of unions, intersections, and complements of halfspaces?
Assume that we have a finite collection of halfspaces H = {
H
+
(f
1
),
H
+
(f
2
),...,
H
+
(f
k
)}.
Although there is an infinite number of ways that these spaces can be combined with
the regular operators »*, «*, or -*, the following is true:
5.9.1 Theorem.
All possible combinations of the halfspaces in H using the opera-
tors »*, «*, or -* will generate only a finite number of regular spaces
X
and each of
these can be represented by a unique expression in the form
X
=
U
*,
P
where
P
=
h
«
*
h
«
*
K
«
*
h
(5.6)
i
i
1
2
k
i
and each
h
j
is either
H
+
(f
j
) or
H
-
(f
j
).
Proof.
See [ShaV93].
As an example of this theorem, consider the space
X
in Figure 5.46(b) again. The
unique decomposition of
X
guaranteed by the theorem is the one below:
(
)
»««
(
(
)
)
»
XH
=««
*
H
*
H
*
H
*
H
*
c
*
H
*
3
1
2
3
1
2
(
««
()
)
»««
(
(
)
)
HH
*
*
c
*
H
*
HH
*
*
c
*
H
.
(5.7)
3
2
1
1
2
2
(The decomposition in equation (5.5) does not have the right structure.)
In general, let us call any space like P
i
in equations (5.6) a
canonical intersection
term
for the collection of halfspaces H. Note that the interior of every canonical inter-
section term is the intersection of the interior of the halfspaces that defined that
canonical intersection. This leads to the main theorem about when a space admits a
CSG representation based on a given set of halfspaces.
5.9.2 Theorem.
Let H = {
H
1
,
H
2
,...,
H
k
} be a collection of halfspaces. A solid
X
with the property that ∂
X
à (∂
H
1
»∂
H
2
» ...»∂
H
k
) admits a CSG representation
based on H if and only if the interior of every canonical intersection term based on
H is either entirely contained in
X
or entirely outside of
X
.
Proof.
See [ShaV91a].
Theorem 5.9.2 explains why the two halfspaces in Figure 5.46(a) were inadequate
to describe the space
X
: the canonical intersection
H
1
«* c*(
H
2
) is half in
X
and half
outside of
X
.
We clarify our discussion with another example. We desire a b-rep-to-CSG
conversion for the solid
X
in Figure 5.47(a) ([GHSV93]). The b-rep of our solid
X
specifies five halfspaces associated to each face in the boundary: four halfplanes and
one disk. Figure 5.47(b) shows the
in
/
out
classification of the canonical intersections
for our halfspaces. We see that the regions
A
and
B
in the figure that belong to the
same canonical intersection have a different
in
/
out
classification. They are both in the
square and outside the disk, but one is inside our solid and the other is outside it. By
Theorem 5.9.2 this means that
X
cannot be obtained from the given halfplanes and
