The scene hierarchy supplies definitions of how items in the database relate to one another. It contains information about the logical and spatial organization of the database. The scene hierarchy is processed by visiting the nodes in depth-first order and operating on them. The process of visiting, or touching, the nodes is called traversing the hierarchy. The tree is traversed from top to bottom and from left to right. OpenGL Performer implements several types of database traversals, including application, clone, cull, delete, draw, flatten, and intersect. These traversals are described in more detail later in this chapter.

The principal traversals (application, cull, draw and intersect) all use a similar traversal mechanism that employs traversal masks and callbacks to control the traversal. When a node is visited during the traversal, processing is performed in the following order:

In addition to imposing a logical and spatial ordering of the database, the hierarchy also defines how state is inherited between parent and child nodes during scene graph traversals. For example, a parent node that represents a transformation causes the subsequent transformation of each of its children when it and they are traversed. In other words, the children inherit state, which includes the current coordinate transformation, from their parent node during database traversal.

A transformation is a 4x4 homogeneous matrix that defines a 3D transformation of geometry, which typically consist of scaling, rotation, and translation. The node types pfSCS and pfDCS both represent transformations. Transformations are inherited through the scene graph with each new transformation being concatenated onto the ones above it in the scene graph. This allows chained articulations and complex modeling hierarchies.

The effects of state are propagated downward only, not from left to right nor upward. This means that only parents can affect their children—siblings have no effect on each other nor on their parents. This behavior results in an easy-to-understand hierarchy that is well suited for high-performance traversals.

Graphics states such as textures and materials are not inherited by way of the scene graph but are encapsulated in leaf geometry nodes called pfGeode nodes, which are described in the section “Node Types” in Chapter 3.

OpenGL Performer uses the spatial organization of the database to increase the performance of certain operations such as drawing and intersections. It is therefore recommended that you consider the spatial arrangement of your database. What you might think of as a logical arrangement of items in the database may not match the spatial arrangement of those items in the visual environment, which can reduce OpenGL Performer's ability to optimize operations on the database. See “Organizing a Database for Efficient Culling” for more information about spatial organization in a visual database and the efficiency of database operations.

The cull is a depth-first, left-to-right traversal of the database hierarchy beginning at a pfScene, which is the hierarchy's root node. For each node, a series of tests is made to determine whether the traversal should prune the node—that is, eliminate it from further consideration—or continue on to that node's children. The cull traversal processing is much as described earlier; in particular, the draw traversal masks are compared and the node is checked for visibility before the traversal continues on to the nodes children. Processing proceeds in the following order:

The following sections discuss these steps in more detail.

Culling determines whether a node is within a pfChannel's viewing frustum for the current frame. Nodes that are not visible are pruned—omitted from the list of objects to be drawn—so that the Geometry Pipeline does not waste time processing primitives that couldn't possibly appear in the final image.

Hierarchical Bounding Volumes

Testing a node for visibility compares the bounding volume of each object in the scene against a viewing frustum that is bounded by the near and far clip planes and the four sides of the viewing pyramid. Both nodes (see Chapter 3, “Nodes and Node Types”) and pfGeoSets (see Chapter 8, “Geometry”) have bounding volumes that surround the geometry that they contain. Bounding volumes are simple geometric shapes whose centers and edges are easy to locate. Bounding volumes are organized hierarchically so that the bounding volume of a parent encloses the bounding volumes of all its children. You can specify bounding volumes or let OpenGL Performer generate them for you (see “Bounding Volumes” in Chapter 3).

Figure 4-1 shows a frustum and three objects surrounded by bounding boxes. Two of the objects are outside the frustum; one is within it. One of the objects outside the frustum has a bounding box whose edges intersect the frustum, as shown by the shaded area. The visibility test for this object returns TRUE, because its bounding box does intersect the view frustum even though the object itself does not.

Figure 4-1. Culling to the Frustum

Visibility Culling Example

Figure 4-2 portrays a simple database that contains a toy block, train, and car. The block is outside the frustum, the bounding volume of the car is partially inside the frustum, and the train is completely inside the frustum.

Figure 4-2. Sample Database Objects and Bounding Volumes

Efficient culling depends on having a database whose hierarchy is organized spatially. A good technique is to partition the database into regions, called tiles. Tiling is also required for database paging. Instead of culling the entire database, only the tiles that are within the view frustum need to be traversed.

The worst case for the cull traversal performance is to have a very flat hierarchy—that is, a pfScene with all the pfGeodes directly under it and many pfGeoSets in each pfGeode—or a hierarchy that is organized by object type (for example, having all trees in the database grouped under one pine tree node, rather than arranged spatially).

Figure 4-3 shows a sample database represented by cubes, cones, pyramids, and spheres. Organizing this database spatially, rather than by object type, promotes efficient culling. This type of spatial organization is the most effective control you have over efficient traversal.

Figure 4-3. How to Partition a Database for Maximum Efficiency

When modeling a database, you should consider other trade-offs as well. Small amounts of geometry in each culling unit, whether pfGeode or pfGeoSet, provide better culling resolution and result in sending less nonvisible geometry to the pipeline. Small pieces also improve the performance of line-segment intersection inquiries (see “Database Concerns” in Chapter 21). However, using many small pieces of geometry can increase the traversal time and can also reduce drawing performance. The optimal amount of geometry to place in each pfGeoSet depends on the application, database, system CPU, and graphics hardware.

During the cull traversal, a pfChannel can rearrange the order in which pfGeoSets are rendered for improved performance and image quality. It does this by binning and sorting. Binning is the act of placing pfGeoSets into specific bins which are rendered in a specific order. OpenGL Performer provides two default bins: one for opaque geometry and one for blended, transparent geometry. The opaque bin is drawn before the transparent bin so transparent surfaces are properly blended with the background scene. Applications are free to add new bins and specify arbitrary bin orderings.

Sorting is done on a per-bin basis. pfGeoSets within a given bin are sorted by a specific criterion. Two useful criteria provided by OpenGL Performer are sorting by graphics state and sorting by range. When sorting by state, pfGeoSets are sorted first by their pfGeoState, then by an application-specified hierarchy of state modes, values, and attributes which are identified by PFSTATE_* tokens and are described in Chapter 9, “Graphics State”. State sorting can offer a huge performance advantage since it greatly reduces the number of mode changes carried out by the Geometry Pipeline. State sorting is the default sorting configuration for the opaque bin.

Range sorting is required for proper rendering of blended, transparent surfaces which must be rendered in back-to-front order so that each surface is properly blended with the current background color. Front-to-back sorting is also supported. The default sorting for the transparent bin is back-to-front sorting. Note that the sorting granularity is per-pfGeoSet, not per-triangle so transparency sorting is not perfect.

The pfChannel bins are given a rendering order and a sorting configuration with pfChanBinOrder() and pfChanBinSort(), respectively. A bin's order is simply an integer identifying its place in the list of bins. An order less than 0 or PFSORT_NO_ORDER means that pfGeoSets which fall into the bin are drawn immediately without any ordering or sorting. Multiple bins may have the same order but the rendering precedence among these bins is undefined.

A bin's sorting configuration is given as a token identifying the major sorting criterion and then an optional list of tokens, terminated with the PFSORT_END token, that defines a state sorting hierarchy. The following tokens control the sort:

For example, the following specification will sort the opaque bin by pfGeoState, then by pfTexture, then by pfMaterial:

  static int sort[] = {PFSORT_STATE_BGN,
                       PFSTATE_TEXTURE, PFSTATE_FRONTMTL,
                       PFSORT_STATE_END, PFSORT_END};
  pfChanBinSort(chan, PFSORT_OPAQUE_BIN, PFSORT_BY_STATE,                 sort);

A pfGeoSet's draw bin may be set directly by the application with pfGSetDrawBin(). Otherwise, OpenGL Performer automatically determines if the pfGeoSet belongs in the default opaque or transparent bins.

You can define a chain, or path, of nodes in a scene graph using the pfPath data structure. (Note that a pfPath has nothing to do with filesystem paths as specified with the PFPATH environment variable or with specifying a path for a user to travel through a scene.) Once you have specified a pfPath with a call to pfNewPath(), you can traverse and cull that path as a subset of the entire scene graph using pfCullPath(). The function pfCullPath() must only be called from the cull callback function set by pfChanTravFunc()—see “Process Callbacks” for details. For more information about the pfPath structure, see the pfPath(3pf) and pfList(3pf) man pages.

When OpenGL Performer looks for intersections, it can return a pfPath to the node containing the intersection. This feature is particularly useful when you are using instancing, in which case you cannot use pfGetParent() to find out where in the scene graph the given node is. Finding out the pfPath to a given node is also useful in implementing picking.

The PFTRAV_CULL argument to pfChanTravMode() modifies the culling traversal. The cull mode is a bitmask that specifies the modes to enable, it is formed by the logical OR of one or more of these tokens:

Culling to the view frustum is enabled by PFCULL_VIEW. Culling to the pfGeoSet-level is enabled by PFCULL_GSET and can produce a tighter cull that improves rendering performance at the expense of culling time.

PFCULL_SORT causes the cull to sort geometry by state—for example, by texture or by material, in order to optimize rendering performance. It also causes transparent geometry to be drawn after opaque geometry for proper transparency effects.

By default, the enabled culling modes are PFCULL_VIEW | PFCULL_GSET | PFCULL_SORT. It is recommended that these modes be enabled unless the cull traversal becomes a significant bottleneck in the processing pipeline. In this case, try disabling PFCULL_GSET first, then PFCULL_SORT.

Normally, a pfChannel's cull traversal pre-traverses the scene, following all paths from the scene to all pfLightSources in the scene so that light sources can be set up before the normal scene traversal. If you want to disable this pre-traversal, set the PFCULL_IGNORE_LSOURCES cull-enable bit but your pfLightSources will not illuminate the scene.

The PFTRAV_DRAW argument to pfChanTravMode() modifies the draw traversal. A mode of PFDRAW_ON is the default and will cause the pfChannel to be rendered. A mode of PFDRAW_OFF indicates that the pfChannel should not be drawn and essentially turns off the pfChannel.

Each node in the database hierarchy can be assigned a mask that dictates whether the node is added to the display list and thereby whether it is drawn. This mask is called the draw mask (even though it is evaluated in the cull traversal) because it tells the cull process whether the node is drawable or not.

The draw mask of a node is set with pfNodeTravMask(). The channel also has a draw mask, which you set with pfChanTravMask(). By default, the masks are all 1's or 0xffffffff.

Before testing a node for visibility, the cull traversal ANDs the two masks together. If the result is zero, the cull prunes the node. If the result is nonzero, the cull proceeds normally. Mask testing occurs before all visibility testing and function callbacks.

Masks allow you to draw different subgraphs of the scene on different channels, to turn portions of the scene graph on and off, or to ignore hidden portions of the scene graph while drawing but make them active during intersection testing.

One of the primary mechanisms for extending OpenGL Performer is through the use of function callbacks, which can be specified on a per-node basis. OpenGL Performer allows separate cull and draw callbacks, which are invoked both before and after node processing. Node callbacks are set with pfNodeTravFuncs().

Cull callbacks can direct the cull traversal, while draw callbacks are added to the display list and later executed in the draw traversal for custom rendering. There are pre-cull and pre-draw callbacks, invoked before a node is processed, and post-cull and post-draw callbacks, invoked after the node is processed.

The cull callbacks return a value indicating how the cull traversal should proceed, as shown in Table 4-2.

Callbacks are processed by the cull traversal in the following order:

Draw callbacks are commonly used to place tags or change state while a subgraph is rendered. Note that if the pre-draw callback is called, the post-draw callback is guaranteed to be invoked. This way the callback can restore any state modified by the pre-draw callback. This is useful for state changes such as pfPushMatrix() and pfPopMatrix(), as shown in the environment-mapping code that is part of Example 4-2.

For doing customized culling, the pre-cull callback can determine whether a PFIS_ALL_IN has already turned off view-frustum culling using pfGetParentCullResult(), in which case it may not wish to do its own cull testing. It can also find out the result of the standard cull test by calling pfGetCullResult().

Cull callbacks can also be used to render geometry (pfGeoSets) or change graphics state. Any libpr drawing commands are captured in a display list and are later executed during the draw traversal (see “Display Lists” in Chapter 9). However, direct graphics library calls can be made safely only in draw function callbacks, because only the draw process of multiprocess OpenGL Performer configurations is known to be associated with a window.

Example 4-2 shows some sample node callbacks.

void
LoadScene(char *filename)
{
    pfScene *scene = pfNewScene();
    pfGroup *root = pfNewGroup();
    pfGroup *reflectiveGeodes = NULL;
 
    root = pfdLoadFile(filename);
    ...
    reflectiveGeodes =
           ReturnListofGeodesWithReflectiveMaterials(root);
 
    /* Use a node callback in the Draw process to turn on
     * and off graphics library environment mapping before
     * and after drawing all of the pfGeodes that have
     * pfGeoStates with reflective materials.
     */
    pfNodeTravFuncs(reflectiveGeodes, PFTRAV_DRAW,
                    pfdPreDrawReflMap, pfdPostDrawReflMap);
}
 
/* This callback turns on graphics library environment
 * mapping.  Because it changes graphics state it must be a
 * Draw process node callback. */
/*ARGSUSED*/
int
pfdPreDrawReflMap(pfTraverser *trav, void *data)
{
    glTexGenf(GL_S, GL_TEXTURE_GEN_MODE, GL_SPHERE_MAP);
    glTexGenf(GL_T, GL_TEXTURE_GEN_MODE, GL_SPHERE_MAP);
    glEnable(GL_TEXTURE_GEN_S);
    glEnable(GL_TEXTURE_GEN_T);
    return NULL;
}
/* This callback turns off graphics library environment
 * mapping.  Because it also changes graphics state it also
 * must be a Draw process node callback.  Also notice that
 * it is important to return the graphics library's state to
 * the state at which it was in before the preNode callback
 * was even made.
 */
/*ARGSUSED*/
int
pfdPostDrawReflMap(pfTraverser *trav, void *data)
{
    glDisable(GL_TEXTURE_GEN_S);
    glDisable(GL_TEXTURE_GEN_T);
    return NULL;
}

Cull and draw callbacks are specified on a per-pfChannel basis using the functions pfChanTravFunc() with PFTRAV_CULL and PFTRAV_DRAW, respectively. pfAllocChanData() allocates passthrough data, data which is passed down the rendering pipeline to the callbacks.

In the cull phase of the rendering pipeline, OpenGL Performer invokes the cull callback with a pointer to the pfChannel that is being culled and a pointer to the pfChannel's passthrough data buffer. The cull callback may modify data in the buffer. The potentially modified buffer is then copied and passed to the user's draw callback.

Default OpenGL Performer processing is triggered by pfCull() and pfDraw(). By default, pfFrame() calls pfCull() first, then calls pfDraw(). If process callbacks are defined, however, pfCull() and pfDraw() are not invoked automatically and must be called by the callbacks to use OpenGL Performer's default processing. pfCull() should be called only in the cull callback; it causes OpenGL Performer to cull the current channel and to generate a display list suitable for rendering.

Channels culled by pfCull() may be drawn in the draw callback by pfDraw(). It is valid for the draw callback to call pfDraw() more than once. Multipass renderings performed with multiple calls to pfDraw() are typical when you use accumulation buffer techniques.

When the draw callback is invoked, the window will have already been properly configured for drawing the pfChannel. Specifically, the viewport, perspective, and viewing matrices are set to their correct values. User modifications of these values are not reset by pfDraw(). If a draw callback is specified, OpenGL Performer does not automatically clear the viewport; it leaves that responsibility to the application. pfClearChan() can be called from the draw callback to clear the channel viewport. If chan has a pfEarthSky(), then the pfEarthSky() is drawn. Otherwise, the viewport is cleared to black and the z-buffer is cleared to its maximum value.

You should call pfPassChanData() to indicate that user data should be passed through the rendering pipeline, which propagates the data downstream to cull and draw callbacks. The next call to pfFrame() copies the channel buffer into internal buffers, so that the application is then free to modify data in the buffer without fear of corruption. The pfPassChanData() function should be called only when necessary, since calling it imposes some buffer-copying overhead. In addition, passthrough data should be as small as possible to reduce the time spent copying data.

The code fragment in Example 4-4 is an example of cull and draw callbacks and the passthrough data that is used to communicate with them.

typedef struct
{
    long val;
}   PassData;
 
void cullFunc(pfChannel *chan, void *data);
void drawFunc(pfChannel *chan, void *data);
 
int main()
{
    PassData   *pd;
 
    /* allocate passthrough data */
    pd = (PassData*)pfAllocChanData(chan,sizeof(PassData));
 
    /* initialize channel callbacks */
    pfChanTravFunc(chan, PFTRAV_CULL, cullFunc);
    pfChanTravFunc(chan, PFTRAV_DRAW, drawFunc);
 
    /* main simulation loop */
    while (1)
    {
        pfSync();
        pd->val = 0;
        pfPassChanData(chan);
        pfFrame();
    }
}
 
void
cullFunc(pfChannel *chan, void *data)
{
    PassData   *pd = (PassData*)data;
 
    pd->val++;
    pfCull();
}
 
void
drawFunc(pfChannel *chan, void *data)
{
    PassData   *pd = (PassData*)data;
    fprintf(stderr, "%ld\n", pd->val);
    pfClearChan(chan);
    pfDraw();
}

This example would, regardless of the multiprocessing mode, have the values 0, 1, and 1 for pd->val at the points where pfFrame(), pfCull(), and pfDraw() are called. In this way, control data can be sent down the pipeline from the application, through the cull, and on to the draw process with frame synchronization without regard to the active multiprocessing mode.

When configured as a process separate from the draw, the cull callback should not attempt to send graphics commands to an OpenGL Performer window because only the draw process is attached to the window. Callbacks should not modify the OpenGL Performer database, but they can use pfGet() routines to inquire about database information. The draw callback should not call glXSwapBuffers() because OpenGL Performer must control buffer swapping in order to manage the necessary frame and channel synchronization. However, if you need special control over buffer swapping, use pfPipeSwapFunc() to register a function as the given pipe's buffer-swapping function. Once your function is registered, it will be called instead of glXSwapBuffers().

The testing of each line segment or group of spatially grouped segments requires a traversal of part or all of a scene graph. You make these inquiries using pfNodeIsectSegs(), which intersects the specified group of segments with the subgraph rooted at the specified node. pfChanNodeIsectSegs() functions similarly, but includes a channel so that the traversal can make decisions based on the level-of-detail specified by pfLOD nodes.

A pfSegSet is a structure that embodies an intersection request.

typedef struct _pfSegSet
{
    long   mode;
    void*  userData;
    pfSeg  segs[PFIS_MAX_SEGS];
    ulong  activeMask;
    ulong  isectMask;
    void*  bound;
    long   (*discFunc)(pfHit*);
} pfSegSet;

The segs field is an array of line segments making up the query. You tell pfNodeIsectSegs() which segments to test with by setting the corresponding bit in the activeMask field. If your pfSegSet contains many closely-grouped line segments, you can specify a bounding volume using the data structure's bound field. pfNodeIsectSegs() can use that bounding volume to more quickly test the request against bounding volumes in the scene graph. The userData field is a pointer with which you can point to other information about the request that you might access in a callback. The other fields are described in the following sections. The pfSegSet is not modified during the traversal.

Intersection information is returned in pfHit objects. These can be queried using pfQueryHit() and pfMQueryHit(). Table 4-3 lists the items that can be queried from a pfHit object.

The PFQHIT_FLAGS field is bit vector with bits that indicate whether an intersection occurred and whether the point, normal, primitive and transformation information is valid. For some types of intersections only some of the information has meaning; for instance, for a pfSegSet bounding volume intersecting a pfNode bounding sphere, the point information may not be valid.

Queries can be performed singly by calling pfQueryHit() with a single query token, or several at a time by using pfMQueryHit() with an array of tokens. In the latter case, the return information is placed in the specified order into a return array.

Before using pfNodeIsectSegs() to intersect the geometry in the scene graph, you must set intersection masks for the nodes in the scene graph and correspondingly in your search request.

pfNodeTravMask(root, PFTRAV_ISECT, 0x01,
               PFTRAV_SELF | PFTRAV_DESCEND, PF_SET)

pfNodeTravMask(root, PFSET_OR, PFTRAV_SET_FROM_CHILD, 0x0);

If you need to make a more sophisticated discrimination than node masks allow about when an intersection is valid, OpenGL Performer can issue a callback on each successful intersection and let you decide whether the intersection is valid in the current context.

If a callback is specified in pfNodeIsectSegs(), then at each level where an intersection occurs—for example, with bounding volumes of libpf pfGeodes (mode PFTRAV_IS_GEODE), libpr GeoSets (mode PFTRAV_IS_GSET), or individual geometric primitives (mode PFTRAV_IS_PRIM)—OpenGL Performer invokes the callback, giving it information about the candidate intersection. The value you return from the callback determines whether the intersection should be ignored and how the intersection traversal should proceed.

If the return value includes the bit PFTRAV_IS_IGNORE, the intersection is ignored. The intersection traversal itself can also be influenced by the callback. The traversal is subject to three possible fates, as detailed in Table 4-6.

Usually, the intersection point of most interest is the one that is nearest to the beginning of the segment. By default, after each successful intersection, the end of the segment is clipped so that the segment now ends at the intersection point. Upon the final return from the traversal, it contains the closest intersection point.

However, if you want to examine all intersections along a segment you can use a discriminator callback to tell OpenGL Performer not to clip segments—simply leave out the PFTRAV_IS_CLIP_END bit in the return value. If you want the farthest intersection point, you can use PFTRAV_IS_CLIP_START so that after each intersection the new segment starts at the intersection point and extends outward.

Level-of-detail nodes are intersected against the model for range zero, which is typically the highest level-of-detail (LOD). If you want to select a different model, you can turn off the intersection mask for the LOD node and place a switch node in parallel (having the same parent and children as the LOD) and set it to the desired model.

Sequences and switches intersect using the currently active child or children. Billboards are not intersected, since no eyepoint is defined for intersection traversals.

The pfChanPick() function provides a simple interface for intersection testing by enabling the user to move a mouse to select one or more geometries. The method uses pfNodeIsectSegs() and uses the high bit, PFIS_PICK_MASK, of the intersection mask in the scene graph. Setting up picking with pfNodePickSetup() sets this bit in the intersection mask throughout the specified subgraph, but does not enable caching inside pfGeoSets. See “Performance”.

The  pfChanPick() function has an extra feature: it can either return the closest intersection ( PFPK_M_NEAREST) or return all pfHits along the picking ray ( PFPK_M_ALL).

The intersection traversal uses the hierarchical bounding volumes in the scene graph to allow culling of the database and then processes candidate GeoSets by testing against their internal geometry. For this reason, the hierarchy should reflect the spatial organization of the database. High-performance culling has similar requirements (see Chapter 21, “Performance Tuning and Debugging”).

Normally, when intersecting down to the primitive level each line segment is separately tested against each bounding volume in the scene graph, and after passing those tests is intersected against the pfGeoSet bounding box. Segments that intersect the bounding box are eventually tested against actual geometry.

When a pfSegSet has a spatially localized group of at least several line segments, you can speed up the traversal by providing a bounding volume. You can use pfCylAroundSegs() to create a bounding cylinder for the segments, place a pointer to the resulting cylinder in the pfSegSet's bound field, then OR the PFTRAV_IS_BCYL bit into the pfSegSet's mode field.

If only a rough volume-volume intersection is required, you can specify a bounding cylinder in the pfSegSet without any line segments at all and request discriminator callbacks at the PFTRAV_IS_NODE or PFTRAV_IS_GSET level.

Figure 4-4 illustrates some aspects of this process. The portion of the figure labeled A represents a single segment; B is a collection of nonparallel segments, not suitable for tightly bounding with a cylinder; and C shows parallel segments surrounded by a bounding cylinder. In the bottom portion of the figure, the bounding cylinder around the segments intersects the bounding box around the object; each segment in the cylinder, thus, must be tested individually to see if any of them intersect.

Figure 4-4. Intersection Methods