Object Hierarchy and Simple PHIGS (SPHIGS)
A graphics package is an
intermediary between an application program and the graphics hardware.
Ø
SRGP Is a
simple and low-level package
Ø
SPHIGS Is a
richer but more complex standard graphics package
Ø
Main purpose
of such standards is to promote portability of application programs and of
programmers.
Ø
SPHIGS (pronounced
“ess-figs”)it is a subset of PHIGS.
Ø
SPHIGS (Includes
PHIGS and PHIGS+ features),But our aim in designing SPHIGS has been to
introduce concepts in the simplest possible way, not to provide package that it
is strictly upward-compatible with PHIGS.
There are
three major differences between SRGP and SPHIGS
1) To suit engineering and
scientific applications, SPHIGS uses3D, floating-point coordinate system, and
implements the 3D viewing pipeline.
2) SPHIGS maintains a database
structure. A structure is a logical grouping of primitives, attributes, and
other information.
3) SPHIGS operates in an
abstract,3D world-coordinate system, not in 2D screen space, and therefore does
not support direct pixel manipulation.
7.1 GEOMETRIC MODELING
7.1.1 What is a model?
Ø
Model is a
representation of some(not necessarily all) features of a concrete or abstract
entity.
Ø The purpose of a model of an entity is to
allow people to visualize and understand the structure or behavior of the
entity, and to provide a convenient vehicle for “experimentation” with and
prediction of the effects of inputs or changes to the model.
Ø Models simplify the actual structure of
behavior of the modeled entity to make the model easier to visualize or, for
those models represented by systems of equations, to make the model
computationally tractable.
Among common
types of models for which computer graphics is used are these:
Ø
Organizational models are hierarchies representing institutional
bureaucracies and taxonomies, such as library classification schemes and
biological taxonomies. These models have various directed-graph representations,
such as the organization chart.
Ø
Quantitative modes are equations describing econometric,
financial, sociological, demographics, climatic, Chemical, physical, and
mathematical systems. These are often depicted by graphs or statistical plots.
Ø
Geometric models are collections of components with well-defined
geometry and, often, interconnections between components, including engineering
and architectural structures, molecules and other chemical structures,
geographic structures, and vehicles. These models are usually depicted by block
diagrams or by pseudo-realistic “synthetic photographs”.
7.1.2 Geometric Models:
Geometric
model may represent are the following:
ü Spatial
layout and shape of components (i.e., the
geometry of the entity), and other attributes affecting the appearance of
components, such as color.
ü Connectivity
of components (i.e., the structure or topology
of the entity);
ü Application
– specific data values and properties associated with components, such as electrical characteristics or
descriptive text.
7.1.3 Hierarchy in Geometric Models
Geometric
models often have a hierarchical structure induced by a bottom-up construction
process: Components are used as building
blocks to create higher-level entities, which in turn serve as building blocks
for yet higher-level entities, and so on.Like large programming systems,
hierarchies are seldom constructed strictly bottom-up or top-down;
What matters is the final hierarchy, not the
exact construction process. Object hierarchies are common because few entities
are monolithic (indivisible); once we decompose an entity into a collection of
parts, we have created at least a two-level hierarchy.In the uncommoCase that
each object is included only once in a higher-level object, the hierarchy can
be symbolized as a tree, with objects as nodes and inclusion relations between
objects as edges. In the more common case of objects included multiple times,
the hierarchy is symbolized by a directed acyclic graph(DAG). As a simple Example
of object hierarchy, fig 7.1 shows a perspective view of a rudimentary
"android" robot;
Fig.7.2(a)
shows the robot's structure as a DAG. As a simple example of object hierarchy,
Fig 7.1 shows a perspective view of a rudimentary “android” robot; Fig.7.2(a)
shows the robot’s structure as a DAG. Note that we can duplicate the multiply
included objects to converttheDAGto a tree(Fig.7.2b).By convention, the arrow
are left off as redundant because the ordering relationship between nodes is
indicated by the nodes’ relative positions in the tree – if node A is above
node B, then A includes B.
A hierarchy, then, is created for
a variety of purposes:
To construct complex objects in a modular
fashion, typically by repetitive invocations of building locks that vary in
geometric and appearance attributes
To increase storage economy, since it suffices
to store only references to objects that are used repeatedly, rather than the
complete object definition each time
To allow easy update propagation, because a
change in the definition of one building-block object is automatically
propagated to all higher-level objects that use that object (since they now refer
to an updated version); the analogy between object and procedure hierarchy is
useful here, in that a change to the body of a procedure is also reflected in
all invocations of that procedure.
Interconnections. In most networks, objects arc placed in specified
locations (either interactively by the user or automatically by the application
program) and then are interconnected. Interconnections may be abstract and thus
of arbitrarily shape {e.g., in hierarchy or network diagrams, such as
organization charts or project-scheduling charts), or they may have significant
geometry of their own (e.g., a VLSI chip).
Parameter passing in object hierarchy. Objects invoked as building blocks must be
positioned in exactly the right place in their parent objects, and, in order to
fit, often must be resized and reoriented as well.
7.1.4 Relationship between Model. Application
Program, and Graphics System
interrelationship
between the model, the application program, and the graphics system. In the
diagram in Fig. 7.3, application programs are divided into five subsystems,
labeled (a) through (e):
a. Build.
modify, and maintain the model by adding, deleting, and replacing information
in it
b. Traverse
(scan) the model to extract information for display
c. Traverse
the model to extract information used in the analysis of the model’s behavior/performance
d. Display
both information (e.g., rendering of a geometric model. output of an analysis)
and user-interface "tools" (e.g., menus, dialog boxes)
e. Perform miscellaneous application tasks
not directly involving the model or display (e.g., housekeeping).
7.2 CHARACTERISTICS OF RETAINED-MODE GRAPHICS PACKAGES
SRGP-
Operates in Immediate mode and keeps
no record of the primitives and attributes passed to it. Thus deletions of and
changes to application objects necessitate he removal of information on the
screen and therefore either selective modification or complete regenerations of
the screen;either of these requires the application to re-specify primitives
from its model.
PHIGS- Operates
in retained mode;It keeps a
record of all primitives and other related information to allow subsequent
editing and automatic updating of the display, thereby offloading the
application program.
7.2.1 CENTRAL STORAGE STRUCTURE STORAGE (CSS)
and IT’S ADVANTAGES
PHIGS stored
information in a special-purpose database called theCentral Structure Storage
A structure
in PHIGS is a sequence of elements – primitives; appearance attributes
transformation matrices, and invocations of subordinate structures – whose
purpose is to define a coherent geometric object. Thus, PHIGS effectively
stores a special-purpose modeling hierarchy, complete with modeling
transformations and other attributes passed as "parameters’ ’ to
subordinate structures.
Advantages of CSS:
The primary advantage of the CSS: is rapid automatic screen regeneration
whenever the application updates the CSS.
A second advantage of the CSS: is automatic pick correlation.
A third advantage of the CSS: is that its editing facilities, in
combination with the features of hierarchical modeling, make it easy to create
various dynamic effects
7.2.2
Limitations of Retained-Mode Packages
Ø It is not necessary because an application
can do its own screen regeneration when the model is changed, can do its own
pick correlation, and can implement its own abject hierarchy via procedures
defining objects and accepting transformations and other parameters.
Ø The CSS is generally not sufficient because,
in most applications, a separately built and updated application data structure
is still necessary to record all appropriate data for each application object.
Ø The rationale for such immediate-mode
packages is that maintaining the CSS is often not worth the overhead, since the
application typically maintains an application model sufficient for
regenerating the screen image.
Ø For applications in which there is
significant structural change between successive images, using a retained—mode
package does not pay.
7.3 Defining and Displaying Structures
The
manipulations permitted on SPHIGS structures include the following:
Ø
Opening (to
initiate editing) and closing (to conclude editing)
Ø
Deleting
Ø
Inserting structure elements
Ø
Deleting structure elements
Ø
Posting for display
7.3.1
Opening and Closing Structures
To create a structure—for example, the
collection of primitives and attributes forming the arm component of the robot
in Fig. 7.2—we bracket calls to the element-generator procedures with calls to
voidSPH_openStructure (IntstructureID);
voidSPH_closeStructure (void];
7.3.2
Specifying Output Primitives and Their Attributes
voidSPH_polyLine (intvertexCount, point *vertices):
voidSPH_poIyMarker(intvertexCount, point *vertices);
voidSPH_fillArea(intvertexCount. point *vertices);
/* Like SRGP_polygon*/
voidSPH_text (point origin, char *str); /*Not fully 3D; see Section 7.7.2 */
Now, consider the definition of a simple
house, shown in Fig. 7.4. We can describe this house to SPHIGS by specifying
each face (also called a facet) as a fill area, at the cost of unnecessary
duplication in the specification and storage (in CSS) of each shared vertex.
This duplication also shows down display generation, since the viewing operation
calculation would be performed on a single vertex more than once. It is far
more efficient in storageand processing time to specify the facets using
indirect references to the shared vertices. We thus think of a polyhedron as a
collection of facets, each facet being a list of vertex indices and each index
being a "pointer" into a list of vertices. We can describe a
polyhedron’s specification using the following notation:
Polyhedron =
{VertexList, FacetList}
VertexList =
{VI, V2, V3, V4, V5. V6, V7, V8, V9,. V10}
V1 = (x1,
y1, z1), V2 = (x2, y2, z2). ..
FacetList =
{front = {I. 2, 3. 4. 5}, right = {2, 7, 8. 3}, . . . bottom = {. . .}}
SPHIGS
offers this efficient form of specification with its polyhedron primitive.
voidSPH_poIyhedron
(intvertexCount, intfacetCount, point *vertices, vertexlndex *facets);
As a simple
example, the following C code creates a structure consisting of a single polyhedron
modeling the house of Fig. 7.4:
SPH_openStructurc
(HOUSE_STRUCT);
SPH_polyhedron(10,
7,houseVertexList,houseFacesDescription);
SPH _closeStructure
();
Attributes:
The procedures listed in Fig. 7.5 generate
attribute elements. During display traversal, the execution of an attribute
element changes the attribute’s value in a modal fashion: The new value stays
in effect until it is changed explicitly.
PolyLine:
Void SPH_setLineStyle(CONTINOUS/DASHED/DOTTED/DOT_DASHED
lineStyle);
Void SPH_setLineWidthScaleFactor(double
scaleFactor);
Void
SPH_setLineColor(intcolorIndex);
Fill area and polyhedron:
Void
SPH_setInteriorColor(intcolorIndex);
Void
SPH_setEdgeFlag(EDGE_VISIBLE/EDGE_INVISIBLE flag);
Void SPH_setEdgeStyle(CONTINOUS/DASHED/DOTTED/DOT_DASHED
lineStyle);
Void
SPH_setEdgeWidthScaleFactor(double scaleFactor);
Void
SPH_setEdgeColor(intcolorIndex);
PolyMarker:
Void
SPH_setMarkerStyle(MARKER.CIRCLE/MARKER.SQUARE/…markerStyle);
Void
SPH_setMarkerSizeScaleFactor(double scaleFactor);
Void
SPH_setMarerColor(intcolorIndex);
Text:
Void
SPH_setTextFont(intfontIndex);
Void
SPH_setTextColor(intcolorIndex);
Fig.7.5 procedures generating attribute
elements.
7.3.3 Posting Structures for Display
Traversal
SPHIGS performs
a display traversal of the structure's elements in the CSS, executing each
element in order from the first to the last.
The following procedure adds a structure to
the list of posted structures maintained internally by SPHIGS:
voidSPH_postRoot (intstructID, intviewlndex);
7.3.4 Viewing
The
synthetic camera, it is helpful to think of a 3D graphics package as a
synthetic camera that takes "snapshots" of a 3D world inhabited by
geometrically defined objects.
The Viewport:
The viewport specifies a parallelpiped in the
NPC system to which the contents of the view volume defined in VRC is mapped.
The View table: SPHIGS
maintains a table of views that has an implementation dependent number of
entries. Each view consists of a specification of the view volume and viewport,
called the view representation, and a list (initially empty) of the roots
posted to it.
Void
SPH_setViewRepresentation(Int vieIndex,matrix_4x4 voMtrix,matrix_4x4 vmMatrix,
doubleNPCviewport_minX,doubleNPCviewport_maxX,
doubleNPCviewport_minYdoubleNPCVIEWPORT_maxY,
doubleNPCviewport_minZ,doubleNPCviewport_maxZ);
Multiple views. The
use of multiple views is powerful in many ways. We can display several
different structures simultaneously in individual areas of the screen by
posting them with different views. In
Fig 7.7 (a) , we present a schematic representation of the view table, showing
only the pointers to the list of structure networks posted to each view.We can
see that there is one view showing a street scene; also , there are three
separate views of robot.
7.5 Hierarchical
Structure Networks
7.5.1 Two-Level Hierarchy:Three types of structure elements:
output primitives,appearance
attributes, and transformation.
We show how the power of SPHIGS derives in
large part from structure hierarchy, implemented via an element that “calls"
a substructure when executed during traversal. Structure hierarchy should not
be confused with the template- procedure hierarchy of the previous section.
Template—procedure hierarchy is resolved at specification time, when the CSS is
being edited, and produces in—line elements, but substructure invocations. By
contrast, structure hierarchy induced by invocation of substructures is
resolved when the CSS is traversed for display—the execution of an invocation
element acts as a subroutine call.
The
structure-execution element that invokes a substructure is created by
void SPH_executeStructure(int
structureID);
Let us
replace the template procedure of the previous section by a procedure that
builds a house structure in the CSS (see Fig. 7.12). This procedure is called
exactly once by the mainline procedure, and the HOUSE_STRUCT is never posted;
rather, its display results from its being invoked as a subobject ofthe Street
structure. Note that the only differences in the-. STREET_STRUCT specification
is the addition of the call to the procedure that builds the house structure
and the replacement of each template procedure call by the generation of an
execute-structure element. Although the displayed image is the same as that of
Fig. 7.9(a), the structure network is different as shown in Fig.7.13, in which
the execute-structure element is depicted as an arrow.
Posting STREET_STRUCT tells SPHIGS to update
the screen by traversing the STREET_STRUCT structure network; the traversal is
in the form of a depth-First tree walk, just as a procedure/subroutine
hierarchy is executed. In the preceding example, the traverser initializes the
street structure's local matrix to the identity matrix, and then performs the
first invocation of the house substructure, applying the street structure’s
local matrix to each of the house’s vertices as though the house polyhedron
were a primitive element in the street structure itself. When it returns from
the first invocation, it sets the local matrix to a desired composite
transformation, and then performs the second invocation, applying thenew
composite matrix to the vertices of the house to create the second
instantiation of the house.
voidBuildStandardizedHouse(void)
{
SPH_openStructure
(HOUSE_STREET);
SPH_polyhedron(…);
SPH_closeStructure();
}
/*Mainline */
BuildStandardizedHouse();
SPH_openStructure
(STREET_STRUCT);
SPH_executeStructure(HOUSE_STRUCT):
/* First house */
Setlocal
transformation matrix;
SPH_executeStructure
(HOUSE_STRUCT); /* Mansion*/
Set local
transformation matrix;
SPH_executeSrructure
(HOUSE_STRUCT); /*Cottage */
SPH_c1oseStructure();
SPH_postRoot
(STREET_STRUCT,0);
Fig. 7.12
Use of a subordinate structure to model the street.
When it returns the local matrix is again
changed; the new composite is applied to the house's vertices to produce the
third house instance. We think of a structure as an independent object, with
its primitives defined in its own floating-point modeling—coordinate system
(MCS); this way of thinking facilitates the building of low-level standardized
building blocks. As we noted in Section 5.8, a transformation maps the vertices
in one coordinate system into another; here, SPHIGS uses the local matrix of
structure S to transform the primitives of substructures into S’s own MCS.
7.5.2 Simple Three-Level Hierarchy
As a simple example of three-level hierarchy,
we extend the house in our street example. The new house is composed of the
original standardized house (renamed SlMPLE_HOUSE_STRUCT) and a chimney
suitably scaled and translated to lie in the right place on top of the house.
We could revise the house structure by adding the chimneys facets directly to
the original polyhedron, or by adding a second polyhedron to the structure, but
we choose here to induce three-level hierarchy by decomposing the house into
two subobjects. An advantage of this modularization is that we can define the
chimney in a standardized manner (at the origin, of unit size) in its own MCS
(as shown in Fig. 7.14a) and then use scaling and translation to place it on
the roof in tl1e house’s MCS. If we had to define the chimney to fit exactly on
the roof and to map into the hot1se’s MCS without scaling.we would have to do
messy calculations to compute the vertices explicitly. With modularity,
however, we simply define the standardized chimney such that its bottom facet
has the same slope as the roof itself; with that condition met, uniform scaling
and arbitrary translation can be applied.
The revised house structure is
built via
SPH_openStructure (HOUSE_STRUCT);
SPH_executeStructure (SIMPLE_HOUSE_STREET);
set local matrix to
scale/translate standardized chimney onto roof of simple house;
SPH_executeStructure (CHIMNEY_STRUCT);
SPH_closeStructure();
What happens when this two—level house object
is instantiated by the street structure with a transformation to yield the
three-level hierarchy shown in Fig. 7.l4(b)C’ Since SPHIGS transforms at parent
by transforming the latter’s Component elements and substructures, we are
assured that the two component primitives (the simple house and the chimney)
are transformed together as a single unified object (Fig. 7.140). The key point
is that the street—structure specification did not need to be changed at all.
Thus, the designer of the strect structure does not need to be concerned with
the internal details of how the house is constructed or subsequently edited——it
is a black box.
7.5.3 Bottom-Up Construction of the Robot
A complex object or System hierarchy is
usually conceptualized and informally described top-down. For example, a
computerscience department building is composed of floors, which are composed
of offices and laboratories, which are composed of furniture and equipment, and
so on. Recall that our simple android robot is composed of an upper body and a
pedestal base; the upper body is composed of a trunk, a head, and two identical
arms, each of which is composed of a fixed hand and a "sliding"
(translating) thumb as gripper.
Even though we design top-down, we often
implement bottom-up, defining building blocks for use in the definitions of higher—level
building blocks, and so on.To create the hierarchy of building blocks. Thus, in
constructing the robot, we define the thumb building block for the robot's arm,
then the arm itself, and then join two instances of the arm building block onto
the upper body, and so on, as shown in the symbolic parts hierarchy of Fig. 7.2
and in the more detailed structure network diagram of the upper body in Fig. 7.
15.
Let us look at the bottom-up construction
process in more detail to see what geometry and transformations are involved.
It makes sense to design the arm and thumb in the same units of measurement, so
that they fit together easily. We define the thumb structure in a standardized
position in its own MCS in which it "hangs" along the y axis
(Fig.7.l6a). The arm structure is defined with the same unit of measurement as
that used for the thumb;
it consists
of the arm+hand polyhedron (standardized, hanging down along the y axis, as
shown in Fig. 7.16b) and a translated invocation of the thumb structure. The
translation element preceding the invocation of the thumb is responsible for
moving the thumb from its standardized position at the origin to its proper
place on the wrist of the arm (c).
The arm-invoking-thumb network is a two—level
hierarchy similar to the street-house example. By editing the translation
element in the arm structure, we can "slide’ ’ the thumb along the wrist
of the arm (Fig. 7.l6 d).
Next, we build the upper body. Since we want
to be able to rotate the head, we first specify the trunk polyhedron, then a
rotation,and next the head polyhedron (Fig. 7. l6e). Our next step is to have
the upper-body structure invoke the arm structure twice. What transformations
should precede these invocations? If our sole concern is positioning (i.e.,
translating) each arm correctly in the upper-body MCS, we may produce a picture
like Fig. 7.160-). Where the arm and upper body were clearly designed at
different scales. This is easy to fix: We can add a scale transformation
preceding the translation (Fig. 7.16g). However, a scale and a translation is
not enough if we want arms that can swing on the axis
connecting the two shoulders (for movement
much like that of the arm of a marchingsoldier); for this. we place a rotation
element in the structure preceding the translation. We have completed our
definition of the upper-body structure; assembling the full robot is Exercise
7.l. Fig. 7. l6(h) shows the upper body as it looks when the left arm`s
rotation element is nonzero.
7.5.4 Interactive Modeling Programs
Interactive 3D construction and modeling
programs facilitate the construction of object hierarchies through the bottom-up
assembly process just described. Most such programs offer a palette of icons
representing the program’s fundamental set of building blocks. If the drawing program
is application-specific, so are the building blocks; otherwise, they are such
common atoms as polylines, polygons, cubes, parallelepipeds, cylinders, and
spheres.
The user can select an icon in order to
instantiate the associated building block, and can then specify transformations
to be applied to the building-block instance. Such specification is typically
done via input devices, such as the mouse or control dials, that let the user
experiment with the instance’s size orientation, and position until it
"looks right." Since it is difficult to judge spatial relationships
in 2D projections of 3D scenes, more sophisticated interaction techniques use
3D grids, often with "gravity fields" surrounding intersection
points, numerical scales, sliders of various types, numerical feedback on the position
of vertices.
7.1O INTERACTION
Both SRGP’s and SPHIGS's interaction modules
are based on the PHIGS specification, and thus they have the same facilities
for setting device modes and attributes, and for obtaining measures.
The SPHIGS keyboard device is identical to
that of SRGP, except that the echo origin is specified in NPC space with the z
coordinate ignored. The SPHIGS locator device’s measure has an additional field
for the z coordinate, but is otherwise unchanged. SPHIGS also adds two new
interaction facilities.
The first is
pick correlation:-augmenting
the locator functionality to provide identification of an object picked by the
user.
The second
is the choice device:- described
in the reference manual, which supports menus.
7.1 0.1 Locator
The SPHIGS locator returns the cursor
position in NPC coordinates, with 2NPC = 0. It also returns the
index of the highest-priority view whose viewport encloses the cursor.
typedefstruct {
point position; /* [x, Y,0]NPCscreen
position */
intviewlndex; /* Index of view whose
viewport encloses the cursor */
intbuttonOfMostRecentTransition;
enum {UP, DOWN}
buttonChord[MAX_BUTTON_COUNT]:
} locatorMeasure;
When two viewports overlap and the cursor
position lies in the intersection of their bounds.
7.10.2 Pick
Correlation
Because the SPHIGS programmer thinks in terms
of modeled objects rather than of the pixels composing their images, it is
useful for the application to be able to determine the identity of an object
whose image a user has picked.
The primary use of the locator, therefore, is
to provide an NPC point for input to the pick—correlation procedure discussed
in this section. As we saw with SRGP, pick correlation in a flat—earth world is
a straightforward matter of detecting hits—primitives whose images lie close
enough to the locator position to be considered chosen by the user. If there is
more than one hit, due to overlapping primitives near the cursor, we
disambiguate by choosing the one most recently drawn. since that is the one
that lies "on top." Thus, a 2D pick correlation examines the
primitives in inverse temporal order, and picks the first hit. Picking objects
in a 3D, hierarchical world is a great deal more complex, for the reasons
described next; fortunately, SPHIGS relieves an application of this task.
Picking in a hierarchy. Consider the complexity introduced by
hierarchy. First, what information should be returned by the pick-correlation
utility to identity the picked object'? A structure ID is not enough because it
does not distinguish between multiple instances of a structure. Only the full
path—a description of the complete ancestry from root to picked primitive-provides
unique identification.
Comparison criterion. How proximity to an object is defined when
the comparison should really be done in 3D? Since the locator device
effectively yields a 2D NPC value, there is no basis for comparing the z
coordinates of primitives to the locator position. Thus, SPHIGS can compare the
cursor position only to the screen images of the primitives, not to the WC
locations of the primitives.
If a primitive is a hit, it is deemed a
candidate for correlation. In wireframe mode, SPH IGS picks the very first
candidate encountered during traversal; the reason for this strategy is that
there is no obvious depth information in a wireframe image. so the user does
not expect pick correlation to take relative depth into account. (A side effect
of the strategy is that it optimizes pick correlation).In shaded rendering modes,
SPHIGS picks the candidate whose hit point (the NPC point, on the primitive’s
normalized (3D NPC) surface. to which the user pointed directly) is closest to the
viewpoint—the one "in front”.
Pick-correlation utility. To perform pick correlation, the application
program calls a SPHIGS pick-correlation utility’s with an NPC point and a view
index, typically returned by a previous interaction with the locator:
voidSPH_pickCorrelate
( point position. IntviewIndex,pickInformation *pickInfo);
The returned
information identifies the primitive picked and its ancestry via a pick path,
as described by Pascal data types in Fig. 7.24.
typedefstruct
{
intstructureID;
intelementlndex;
/* Enumerated type: polyline,polyhedron,
execute-structure, etc. */
ElementTypeCodeelementype;
intpicklD;
}pickPathltem;
typedefpickPathltempickPath[MAX.HIERARCHY_LEVEL];
typedefstruct{
intpickLevel;
pickPath
path;
}picklnformation;
Fig. 7.24 Pick-path storage types.
In that structure, a code presenting the type
of the element, and the pick ID ofthe element. Figure 7-25 uses the structure
network of Fig. 7.15 for the robot’s upper body, and shows the pick information
returned by several picks within the structure’s displayed image.
How does the pick path uniquely identify each
instance of a structure that is invoked arbitrarily many times within the
hierarchy? For example, how do we distinguish a pick on the robot’s left thumb
from a pick on its right thumb'? The pick paths for the two thumbs are
identical except at the root level, as demonstrated by points a and e in Fig.
7.25.
voidSPH_setPickIdentifier(int
id);
7.12.1 Rendering
The
conceptual rendering pipeline that implements display traversal is illustrated
in Fig. 7.26. Its First stage is the actual depth—first traversal of the CSS
itself.
Each primitive encountered during traversal
is passed through the remainder of the pipeline: First, the modeling
transformations are applied to map the primitive from modeling coordinates to
world coordinates. Then, the viewing operation is applied to transform and clip
the primitive to the canonical view volume, and then to map it to the NPC
Parallelepiped. Since these processes are independent of the display device and
deal with vertex geometry in floating—point coordinates, this portion of
The pipeline
immediately following traversal is often referred to as the geometry-processing
subsystem.
The back end
of the pipeline takes transformed, clipped primitives and produces pixels; we
will refer to this pixel processing as rasterization. This process is, of
course, straightforward for wireframe mode: The NPC coordinates are easily
mapped (via scaling and translating, with z ignored) to integer device
coordinates, and then the underlying raster graphics package’s line-drawing
function is invoked to do the actual scan conversion. Shaded rendering,
however, is quite complex, and is composed of three subprocessesvisible-surface
determination (determining which portions of a primitive are actually visible
from the synthetic camera’s point of view), scan conversion (determining the
pixels covered by a primitive’s image), and shading (determining which color to
assign to each covered pixel). The exact order in which these subprocesses are
performed varies as a function of the rendering mode and implementation method.
Traversal.
Since all stages of the rendering pipeline but the first one are covered in
other chapters, we need to discuss only the traversal stage here. In a simple
implementation, SPHIGS regenerates the screen by erasing it and then re-traversing
all posted roots (a list of which is stored with each view). Optimizing
regeneration in order to traverse as little of the CSS as possible is quite
difficult, because the effect of a trivial operation is potentially enormous.
For example, it is difficult to determine how much of the screen must be
regenerated due to the editing of a structure: It is possible that the
structure is never invoked and thus has no effect on the screen, but it is also
possible that it is a commonly invoked
Building
blocks appearing in most of the views. Even when the implementation can
determine that only a single view has been affected by an operation, refreshing
that view may damage the images of objects in overlapping viewports of higher
priority. Doing damage repair efficiently is, in general, a complicated task
requiring considerable bookkeeping.
In implementations on high-performance
workstations, where the image can be traversed and regenerated in a fraction of
a second, the bookkeeping space and time overhead needed to regenerate the
screen selectively is probably not worthwhile, and therefore complete
regeneration is used most frequently. In either the complete or selective regeneration
schemes, the double—buffering technique described later in this section can be
used to prevent annoying visual discontinuities on the screen during display
traversal.
The traversal of a structure cart be done in
hardware or software; here, we show a procedural—language implementation, the pseudo-code
for which is given in Fig. 7.27, The procedure inherits a traversal state,
which it then maintains as its local state for the duration of its activation.
The attribute values (including the name set) and three transformations matrices
(GM, LM, and their product, CMTM) harm the traversal state, and the attributes
and the CMTM are passed down from parent activation to child activation. (The
activation of the procedure for a root structure inherits an identity GM and an
attribute record filled with default values). The procedure visits each element
in the structure and performs an operation based on the elements type, as
indicated in Fig. 7.27.
7.12.2 Pick
Correlation
In pick correlation, SPHIGS traverses those
networks posted to the view port in which the specified NPC point lies. The
traversal is nearly identical to that performed during display; the
modeling-transformation matrices are maintained, and much of the rendering
pipeline is performed. Moreover. the pick ID ignored during display traversal,
is maintained as part of the local traversal state in the recursive traversal
procedure. (The attribute group does not need to be maintained because during
hit detection SPHIGS does not take into account attributes such as line
thickness.) Let us first examine pick correlation for wireframe rendering,
where traversal is halted at the very first hit. Because traversal is
recursive, the pick path is easily determined the moment the first hit is
found: Each activation of the traversal procedure is responsible for one level
of information in the pick path. Each primitive is transformed to NPC before
being compared to the locator position for hit detection. When a hit is
discovered by an activation of the procedure, it returns and the recursion is
unwound. Before returning each activation stores its pick information into one
level of a global pick-information array.
In shaded rendering modes, the order in which
primitives are encountered during traversal has no bearing on whether they
appear in front of or in back of other primitives whose images map to the same
part of the screen. Therefore, the SPHIGS pick-correlation algorithm cannot
simply choose the first hit detected. Rather, it must traverse all posted structure
networks, maintaining a list of candidate hits. When traversal is completed,
the candidates are compared to determine the candidate whose NPC hit point is
closest to the viewpoint—that is, the one whose z coordinate is algebraically
largest. To calculate a candidates z coordinate at the hit point, we can plug
the x and y coordinates of the locator measure into the appropriate equations
for each primitive; the (parametric) line equation for edges, and the plane
equation for facets (see Exercises 7.7 and 7.8). Another approach using a
hardware visible- surface determination algorithm.Pick-correlation traversal
can, of course, be optimized in a variety of ways, including the
extent-checking techniques used to optimize display traversal.
Analytical hit detection. Two fundamental methods. analytical and
clipping, are used for hit detection. For analytical hit detection.algebraic
equations are used to determine whether the NPC primitive lies sufficiently
close to the 2D NPC locator measure. We First convert to 2D by ignoring the z coordinate for an orthographic
projection or use the perspective transform to create an orthographic view
volume. Some examples of analytical techniques follow:
Ø In WIREFRAME mode, a functionPtNearLineSegment
is used to compute the distance in NPC from the cursor position 10 each edge of
a facet or fill area, and to each line segment 0f a polyline. This same
function would be used in shaded rendering modes for polyline primitives.
Ø In
shaded rendering modes, a function PtlnPolygon is used to test for hits cm till
areasand facets. One popular algorithm for determining it` the NPC cursor
position lies inside a polygon, based on the odd-parity rule casts a ray from
the locator position and determines how many times the ray intersects the
polygon. The algorithm traverses the edge list, testing for intersections and
special cases (e.g., intersections at vertices, edge—ray co-linearity). This
algorithm handles the general case of concave and self-intersecting polygons.
Optimized computational geometry algorithms are available ii` it can be
guaranteed that polygons do not self-intersect, 0r that a horizontal ray
intersects only two edges, or that the polygon is convex.
Ø Hit detection for non-geometric text is most
easily performed by comparing the locator position to the text’s rectangular
screen extent.
Ø Packages that support primitives such as
ellipses and curves and surfaces require more complex pick-correlation
algorithms.
Hit
detection via clipping. Some
hardware clipping devices and optimized software clipping utilities return
state information, allowing an application to determine whether anypan of a
primitive’s image lies inside a 2D integer clip rectangle, without having
actually to draw the primitive. An SPHIGS implementation can use this type of
clipping to test for candidacy: The clip rectangle is set to a pick window- a
small square surrounding the cursor position-and then traversal is performed.
Each primitive (transformed to integer device coordinates) is given to the clipper,
which returns a Boolean "hit—detection" result. Alternatively, ifthe
clipper does not return any such state information, we can draw each primitive
into an offscreen bitmap using the pick-window clip rectangle; if any pixels
are changed, the primitive is deemed a candidate.
7.14 LIMITATIONS OF HIERARCHICAL
MODELING IN PHIGS
We
discuss the limitations of hierarchy in general and in PHIGS in particular
Limitations
of Simple Hierarchy: Some
applications have no real structure for their data(e.g., data for scatter
plots), or have at most a (partial) ordering in their data (e. g., a function
represented algebraically). Many other applications are more naturally
expressed as networks, that is, as general (directed) graphs (which may have
hierarchical subnets). Among these are circuit and electrical—wiring diagrams,
transportation and communication networks, and chemical-plant—piping diagrams.
Another example of simple hierarchy’s insufficiency
for certain types of models is Rubik‘s cube, a collection of components in
which the network and any hierarchy (say of layers, rows, and columns) is fundamentally
altered after any transformation.
For
other types of models, a single hierarchy does not suffice. For example, the
pen holder on an (x, y) plotter is moved by, and therefore "belongs"
to, both the horizontal and vertical arms. In short, whether the application
model exhibits pure hierarchy, pure network without hierarchy, and hierarchy in
a network with cross-links. or multiple hierarchies. SPHlGS can be used to
display it, but we may not want, or be able, to use structure hierarchy in its
full generality.
7.14.2
Limitations of SPHIGS "Parameter Passing"
For example, how can we build a robot with
two identical arms and have the robot useits right arm to pick up a cylinder
from a table and move away with that cylinder`? The pick-up operation can be
performed by editing the arm structure to add an invocation of the cylinder
structure, so that as the robot or arm moves subsequently. The cylinder moves
along with it. But if we implement the robot by having a single arm structure invoked
twice by the upper-body structure, the result of that operation would be that
both the left and right arm would be holding a Cylinder! Thus, we have no
Choice but to build two separate arm structures with unique structure ID’s,
each invoked only once. Let US extend this example. If we wish to have an army
of robots with independently controlled arms, wemust build Iwo unique arm
structures for each robot! Obviously, here is a case where structure hierarchy
is not as useful as we first thought.
The reason that structure hierarchy does not support
instances of structures differing in the settings of transformations at various
hierarchical levels is that structure hierarchy has neither the general
parameter- passing mechanism of procedure hierarchy nor general How—of-control
constructs. Rather, it is essentially a data organization with rudimentary
interactions between structures and at most limited conditional execution of
structures (in PHIGS+). We have seen that a parent’s transformations are
inherited by all the children, and there is no provision for a particular child
to be affected selectively.
By contrast, in a procedure hierarchy, a
"root" procedure passes parameters that are either used directly by
procedures the root calls, or passed down by those procedures to lower-level
procedures. Thus, the root can pass down parameters arbitrarily deeply and selectively
via intermediate procedures. Furthermore, with parameters, a procedure can control
not just the data on which a lower-level procedure operates, but even the way
in which the lower-level procedure operates. To change its operation, the
lower—level procedure uses flow-of-control constructs to test parameters and
selectively enables or disables code segments. Because of structure hierarchy’s
lack of general parameter-passing and flow-of-control mechanisms, our analogy
between structure hierarchy and procedure hierarchy in the introduction was a
superficial one.
By augmenting the attribute—binding model of
PHIGS, we could specify attributes for selected object instances at arbitrary
levels in a hierarchy. A system that has such a general mechanism is SCEFO
[STRA88], which allows the programmer to specify an attribute that is to be
applied when the traversal reaches a certain state, the state being represented
by a pathname similar to the pick path returned by the PHIGS pick device. With
this facility, it would be possible to control individually the colors or
positions of the thumb instances in our robot, without having to create two
virtually identical arm masters, by making use of the fact that the two thumb
instances have unique pathnames.
Another limitation in the PHIGS parameter—passing
mechanism is that it handles transformations and appearance attributes for
which inheritance rules are very simple. Itwould not be easy to support
operations more complex than geometric transformations; a more general model is
needed to support set operations on solid primitives and deformation operations
such as bend, taper and twist.
No comments:
Post a Comment