AN e2 
N el 
FAN Son 
a = = (on) 
os 
e2 e3 
N Sn (below) 
NN el 
general (above) 
(a) lines of sight defining quadric (b) views of edges 
Figure 6. Visual event involving three edges. The lines of sight 
passing through three skew edges define the rulings of a quadric 
surface in (a). The views of the three edges as seen from above, 
on, and below the event surface are shown in (b). 
Yet another method exists, that is applicable under either 
viewing model. This technique uses an intermediate repre- 
sentation known as the asp (Plantinga and Dyer, 1986, 1987, 
1990). This data structure describes the appearance of every 
feature of the object in terms of its image plane location as a 
function of viewpoint. When using a viewing sphere model, 
the resulting space is 4-D in nature, two for the sphere and 
two for the image plane. (It would be a 5-D structure for 
3-D viewpoint space). A vertex on the object corresponds 
to a 2-D surface in this space, such that for any viewpoint, 
its position in the image plane can be calculated. Edges and 
faces are correspondingly represented by 3-D and 4-D struc- 
tures in the space. One property of the asp is that occlusion 
of one feature by another is formed by intersecting the struc- 
tures corresponding to the two entities. In this way stable 
feature configurations will eventually be represented by 4-D 
*volumes" , which can then be projected into viewpoint space 
to define the boundaries in the parcellation. 
The asp also has other uses. Some of these will be alluded 
to in the section on graphics applications. One other is the 
rim appearance model (Seales and Dyer, 1990). In this case, 
the only observed features of the polyhedral model (which is 
considered an approximation of a smooth surface) are those 
edges that project to the occluding contour for a particular 
viewpoint. These features can be easily identified in the 
asp, and only those events relating to changes in the visible 
occluding contour saved (roughly 2596 of all actual events). 
This is a basic approximation to the more exact techniques 
developed in the next section for curved objects. 
4.3 Traversing Viewpoint Space 
  
In general, the resulting viewpoint space will initially be 
*over-partitioned" by the event boundaries after step two. 
There are two reasons for this. One is that an event surface 
may intersect a portion of the object between the observer 
and the features, making a section of it meaningless due to 
this global occlusion. Another is that since edges on the 
object have only finite length, a potential event alignment 
is actually visible only over a subset of the circle/curve (or 
plane/surface) that it defines. Many of these potential event 
surface portions can be discarded entirely, by calculating the 
true “active” subset, using different visibility tests (Gigus, 
Canny and Seidel, 1991). Thus some “extra” processing at 
an early stage of the algorithm can reduce the degree of over- 
partitioning and save processing in later stages. 
    
Once the partition of viewpoint space is determined, the as- 
pect graph structure is created by traversing the partition. 
During this traversal, final merging of over-partitioned cells 
is done. A node is created in the aspect graph for each 
cell in the partition and an arc for each boundary between 
cells. Upper bounds on the number of nodes in the aspect 
graph have been determined to be ©(n°) and O(n?) for a 
general polyhedron of n faces under the viewing sphere and 
3-D space models, respectively (Plantinga and Dyer, 1990). 
Of the algorithms mentioned only a few have been fully im- 
plemented. These include programs for convex polyhedra 
(Stewman and Bowyer, 1990; Watts, 1988), general polyhe- 
dra (Stewman, 1991), and the rim appearance of polyhedra 
for 1-D viewing sphere paths (Seales and Dyer, 1990). 
5. ASPECT GRAPHS OF CURVED OBJECTS 
Research into algorithms for computing exact aspect graphs 
of curved objects has really occurred only in the past few 
years. The notion of partitioning the viewing sphere based 
on visual events for curved objects was first proposed by 
Callahan and Weiss (Callahan and Weiss, 1985), but no al- 
gorithm was given. Original algorithms were developed for 
solids of revolution (Eggert, 1991; Eggert and Bowyer, 1990, 
1992; Kriegman and Ponce, 1990), due to their rotational 
simplicity. Since then several researchers have analyzed ob- 
jects bounded by surface patches of different characteristics. 
These include quadric patches (Chen and Freeman, 1991), 
C? smooth surfaces (Sripradisvarakul and Jain, 1989) and 
parametric or algebraic surfaces (Ponce and Kriegman, 1990; 
Petitjean, Ponce and Kriegman, 1992; Rieger, 1990, 1992). 
All but some of the work on solids of revolution (Eggert and 
Bowyer, 1992; Eggert, 1991) has been limited to an analy- 
sis using the viewing sphere model. The basic approach to 
computing the aspect graph of curved objects is the same as 
that for polyhedra, but the details are more complex. 
5.1 Visual Events 
To begin with, the set of visual events is much more exten- 
sive. Most catalogs are based on the results of singularity 
theory (Whitney, 1955; Arnold, 1983; Koenderink and van 
Doorn, 1976), which involve the study of projections of sur- 
faces. The two major catalogs currently in use are those 
of Kergosien for generic smooth surfaces (Kergosien, 1981), 
and its extension to piece-wise smooth surfaces created by 
Rieger (Rieger, 1987). Both of these were generated under 
the assumption of orthographic projection. 
Though there are several different events, they can usually 
be categorized as to whether or not they involve occlusion. 
Those that don't, correspond to occurrences when either two 
contour generators meet upon the object surface (beak-to— 
beak and lip events), a contour generator makes contact with 
an edge of the object (forming curvature-L and three-tangent 
junctions as shown in Figure 2), or a projected contour forms 
a cusp (a swallowtail event). When occlusion occurs, two 
contours may make contact at a point other than a junction 
(a tangent crossing event), any of the junctions in Figure 2 
may be occluded by a contour, or three contours may inter- 
sect at a triple point as for polyhedra. 
5.2 Parcellating Viewpoint Space 
  
Determining the particular event surfaces of a given object 
becomes a matter of solving systems of polynomial equations