1d 
cts) 
  
Figure 4. The aspect graph of a tetrahedron. For this object the 
overall structure is the same for either viewpoint space model. 
Bold arcs follow the visual event convention of Koenderink and 
van Doorn (1979), while the additional dotted arcs follow the 
convention of Plantinga and Dyer (1986). 
marked by a T-junction in the image. (It also includes, as a 
special case, the projection of a face of the object to a line 
segment in the image.) The viewpoints from which such an 
accidental alignment can be seen lie on a plane in the 3-D 
model of viewpoint space, or on a great circle of the viewing 
sphere. Several of these events can be seen in Figures 4 
and 5, which show the aspect graphs of a tetrahedron and a 
triangular prism with a hole through it, under both viewing 
models, respectively. 
An edge triplet alignment occurs when points on three differ- 
ent edges of the object project to the same point in the image 
(see Figure 6). In general, this event represents a change in 
the ordering of the visible T-junction relations between the 
  
(a) Example nonconvex polyhedron 
having equilateral triangular faces 
with through hole of same shape. 
TAY 
three edges. The viewpoints from which such an accidental 
alignment can be seen lie on a quadric surface in the 3-D 
model of viewpoint space, or on a quadric curve on the sur- 
face of the viewing sphere (Gigus and Malik, 1987; Stewman 
and Bowyer, 1988). 
4.2 Parcellating Viewpoint Space 
  
The set of visual event boundaries is found by considering all 
pairs of edges and vertices, and all triplets of edges. Many of 
these combinations may be discarded by performing a local 
visibility test to see if a portion of the object lies between 
the interacting features, therefore blocking the alignment. 
For the surviving events, the corresponding surfaces must be 
used to subdivide viewpoint space. 
Under the assumption of orthographic projection, the great 
circles and quadric curves on the sphere surface can be de- 
composed into portions which are single-valued with respect 
to a particular 2-D parameterization of the sphere. This set 
of curves is then qualitatively equivalent to a set of lines in 
a plane, and the well known plane sweep algorithm can be 
used to determine curve intersections and subdivide view- 
point space (Gigus and Malik, 1990; Gigus, Canny and Sei- 
del, 1991; Watts, 1988). 
Assuming perspective projection, another method is to con- 
struct what is known as a geometric incidence lattice to rep- 
resent the parcellation of 3-D space. This lattice structure 
defines the various volumes of space, their bounding surface 
patches, the curves of intersection between the patches and 
finally the points of intersection between the curves. The 
calculation of the curves of intersection between the planes 
and quadrics in 3-D space is sufficiently well known that 
this structure is constructible for polyhedra (Stewman, 1991; 
Stewman and Bowyer, 1988). 
  
SAY YY 
(c) Representative views of regions on viewing sphere in (b). Note, only four 
different views exist even though there are 24 total regions on the sphere. 
A AD [8 
V NAY 
(b) Partition of upper quadrant of the Inside 
viewing sphere. Partition is rotationally 
symmetric about upper hemisphere and 
mirror symmetric about the equator. 
Ld uod ks L dsl 
(d) Additional views of object when the 3-D viewing space model is used that are not 
seen from viewing sphere. There are 81 total regions for the subdivision of 3-D space. 
Figure 5. Components of aspect graph of nonconvex polyhedron in (a) include viewing sphere partition in (b), along with 
the representative views of its regions, and also in (d) are additional views seen using the 3-D viewing space model.