Chapter 13. Intersection Testing

Detecting when one shape touches another is useful for determining:

Instead of using a bounding volume for intersection testing, you construct segments that approximate the shape of the object, as shown in Figure 13-1.

Figure 13-1. Approximating a Shape with Segments

Approximating a Shape with Segments

This chapter describes how to check for intersections in the following sections:

For more information on intersections, see Chapter 4, “Database Traversal ,” in the OpenGL Performer Programmer's Guide. Also, there are several source code examples included in the OpenGL Performer source code for intersections:

Creating an ISECT Process

By default, no intersection processing is performed by OpenGL Performer. OpenGL Performer allows you to specify a function that will be called in the intersection stage of the application with pfIsectFunc().

void pfIsectFunc(pfIsectFuncType func);

Intersection testing is often time consuming. For that reason, it is often a good idea to let the task run asynchronously in its own process. If the PFMP_FORK_ISECT bit is specified in the  pfMultiprocess() bitmask, the intersection stage will be run as a separate asynchronous process and therefore can extend beyond the time for a frame without impacting the performance of the main rendering pipeline.

pfInit();
pfMultiprocess(PFMP_FORK_DRAW | PFMP_FORK_ISECT | PFMP_FORK_DBASE);
pfConfig();
 
pfIsectFunc(myIsectFunc);

Because the ISECT process runs asynchronously, two objects could collide without providing immediate notification of the collision. If immediate notification is very important, perform those intersections separately as part of the application process, or do not create a separate intersection process. The function you register with pfIsectFunc is called from the APP process and runs synchronously.

Constructing a Segment Set for pfNodeIsectSegs()

Evaluating every point on the surface of a geometric surface is far too computation- intensive. Instead, a set of segments is used to grossly approximate the shape of an object to test for intersections with that object. pfIsectNodeSegs() traverses a scene graph looking for intersections with the provided segment set.

To create a segment set, you create a pfSegSet, which is a structure defined as follows:

typedef struct {
    int mode;
    void *userData;
    pfSeg segs[PFIS_MAX_SEGS]; /* currently 32 */
    uint activeMask;
    uint isectMask;
    void *bound;
    int (*discFunc)(pfHit *);
} pfSegSet;
 
typedef struct {
    pfVec3 pos;
    pfVec3 dir;
    float length;
} pfSeg;

Setting the Mode

The mode field of pfSegSet specifies the kind of information recorded when there is a hit at an intersection. The mode value is a bitwise OR of one or more of the values in Table 13-1.

Table 13-1. Segment Set Modes

Mode

Description

PFTRAV_IS_PRIM

 Intersect with quads or triangle geometry.

PFTRAV_IS_GSET

 Intersect with pfGeoSet or pfGeoArray bounding boxes.

PFTRAV_IS_GEODE

 Intersect with pfGeode bounding sphere.

PFTRAV_IS_NORM

 Return normals in the pfHit structure.

PFTRAV_IS_CULL_BACK

 Ignore back-facing polygons.

PFTRAV_IS_CULL_FRONT

 Ignore front-facing polygons.

PFTRAV_IS_PATH

 Retain traversal path information.

PFTRAV_IS_NO_PART

 Do not use partitions for intersections.

PFTRAV_IS_PRIM, PFTRAV_IS_GSET, and PFTRAV_IS_GEODE define where the geometry is stored and thereby define the depth of the intersection test.

Intersection Masks

There are several mask fields in the pfSegSet structure to enable you to have conditional intersection traversal. The activeMask field of pfSegSet is a 32-bit mask that allows you to specify which segments are active.

The isectMask is masked with the intersection mask of each node, set on the node by pfNodeTravMask() for PFTRAV_ISECT, in the intersection traversal. The traversal will not intersect with a node or its children if the AND of its isectMask and the pfSegSet isect Mask is zero. This allows you to create intersection classes of objects and intersection types.

pfNodeTravMask() allows you to specify additional things for controlling the intersection traversal of a scene. The function prototype is:

pfNodeTravMask(pfNode *node, int which, uint mask, int setMode, int bitOp);

The setMode enables you to specify intersection caching, and the bitOp enables you to and- or- or set- the specified mask against the previous mask in the node. The following is an example call:

pfNodeTravMask(node, PFTRAV_ISECT, 0xfffffffff,
PFTRAV_SELF|PFTRAV_DESCEND|PFTRAV_IS_CACHE /* turn on caching for entire scene graph below object */, 
PF_OR /* or- with prev bitmask in each node for new bitmask */);

Creating the Segment Array

The segment array defines the origin, direction, and length of the segments in the following structure:

typedef struct {
    pfVec3 pos;
    pfVec3 dir;
    float length;
} pfSeg;

The pfSegSet array can have up to 32 segments. The segment array is then set in the pfSegSet structure in the segs[] field.

The pfSegSet Bound

To further improve intersection performance when you have many segments in a pfSegSet, you can provide a bounding pfCylinder for the segments in the bound field of the pfSegSet. You can create the bounding cylinder can be created with  pfCylAroundSegs(). The array passed to pfCylAroundSegs() needs to be an array of pointers to pfSegs, which is different than the array of pfSegs for the pfSegSet.

Testing for Intersections

After setting up the segment set for the geometry and setting the mask for the nodes in the scene graph, you can check for intersections between the geometry and the segment set using the following pfNode method:

int pfNodeIsectSegs(pfNode *node, pfSegSet *segSet, pfHit **hits[]);

segSet is the segment set for the geometry you are testing.

node is where the intersection testing begins.

hits is an empty array that the traversal will fill with pfHit structures for successful intersections— one per segment.


Note: An alternative to pfNodeIsectSegs() is pfChanNodeIsectSegs().

Figure 13-2. Hits Array

Hits Array

The number of array elements matches the size of the segment set array.

Intersection Information

The hits array is filled by the intersection traversal, with temporary hit structures for each intersection. The first element corresponds to the segment in the segment array, and the second dimension is a list of pointers to hit structures relating to that segment. The data in the hit structures only remains until another ISECT traversal is called, so you do not want to save pointers to the pfHit structures and you do not want to free them.

To return all of the other information contained in a Hit structure, use the following method:

int pfQueryHit(pfHit *hit, uint which, void *dst);

hit is a pfHit structure that the traversal fills with information regarding an intersection.

which is the information to retrieve from the hit structure.

dst is the pfMemory where the query results are placed.

Table 13-2 shows the PFHIT_ tokens, supplied for which, that specify the hit structure information to return.

Table 13-2. Hit Information

Token

Definition

PFQHIT_FLAGS

Indicates the validity of information in the hit structure described in this table.

PFQHIT_POINT

Returns the point of intersection.

PFQHIT_NORM

Returns the normal of the triangle at that point.

PFQHIT_SEG

Returns the current segment as clipped by the intersection process.

PFQHIT_PRIM

Provides the index of the primitive within the pfGeoSet or pfGeoArray.

PFQHIT_TRI

Returns the triangle index within the primitive.

PFQHIT_VERTS

Returns the vertices of the intersected triangle.

PFHIT_XFORM

Returns the non-identity transformation matrix.

PFQHIT_GSET

Returns a pointer to the pfGeoSet or pfGeoArray.

PFQHIT_NODE

Returns a pointer to the parent pfGeode.

PFQHIT_PATH

Returns a pfPath* denoting the traversal path.

PFQHIT_FLAGS is formed by optionally bitwise ORing zero or more of the PFHIT_POINT, PFHIT_NORM, PFHIT_PRIM, PFHIT_TRI, PFHIT_VERTS and PFHIT_XFORM symbols.

Determining If a Segment Was Hit

pfNodeIsectSegs() returns the number of segments that were intersected. To determine which of the segments were intersected, use code similar to the following:

uint flags;
pfHit **hits[32];
 
// Assume segset has four active segs, indicies 0 - 3
 
nhits = pfNodeIsectSegs(scene, &segset, hits);
for (i = 0, i < 4 && nhits > 0, i++){
    pfQueryHit(hits[i][0], PRQHIT_FLAGS, &flags);
    if (flags & PFHIT_ISECT) {
        // valid intersection
        nhits--;
    }
}

Testing for Valid Information

Each element in the hit array contains all of the hit structures recorded for a specific segment. All of the fields in the hit structures may not have data. To see if the fields have data, use the PFQHIT_FLAGS token in pfQueryHit(). Use this function to test the following fields:

  • PFHIT_POINT

  • PFHIT_NORM

  • PFHIT_PRIM

  • PFHIT_TRI

  • PFHIT_VERTS

  • PFHIT_XFORM

Use code similar to the following to test whether or not the fields have values; if not, they contain NULL:

pfQueryHit(hits[i][0], PFQHIT_POINT, &pt);
pfQueryHit(hit, PFQHIT_FORM, xform)'
if ( (flags & PFHIT_XFORM) == 0) {
    // xform contains garbage. so set it to the identity
    // matrix so there is no transformation.
    pfMakeIdentMat(xform);
}
pfXformPt3(xpt, pt, xform);

Retrieving the Intersection Location

You can find out what object in the scene graph was hit, the location of the intersection on that object, the object normal at the point of intersection, a traversal path to that object in the scene graph, and more. All of the geometric data is expressed in local object coordinates. To transform the data into world coordinates, use:

  • pfXformPt3 to transform the point of intersection.

  • pfXformVec3 to transform the normal.

 Use these methods with the PFQHIT_XFORM matrix, as follows:

if (flags & PFHIT_ISECT) {
    pfVec3 pt, xpt;
    pfMatrix xform;
 
    pfQueryHit(hits[i][0], PFQHIT_POINT, &pt);
    pfQueryHit(hit, PFQHIT_XFORM, xform);
    pfXformPt3(xpt, pt, xform);
 
    shared->zpos = xpt[PF_Z] + 0.7;
}

In this example, the eyepoint is 0.7 units above the geometry.