Object Hierarchy and Simple PHIGS (SPHIGS) computer graphics unit 4 material

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 2_NPC = 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.