Hierarchical Modeling - Essentials of Interactive Computer Graphics - page 308

the point primitive is sufficiently close to other primitives. In this way, the issues
involved here are similar to those of collisions between primitives (as discussed
in Section 7.5). The only difference here is that sufficiently close does not nec-
essarily mean that two primitives have collided. For example, an application can
define that to select an object, the mouse click must be within at least x pixels of
the edges of the object. The more refined the criteria of “sufficiently close,” the
more difficult it is to implement the computations involved. For example, the dot-
ted lines around the rectangle of Figure 11.20 show that the “within x pixels from
the edges” criteria results in circular boundaries around the rectangle vertices. In
this case, a mouse click at position p 1 should be considered hitting the rectangle;
however, the computation involved is expensive.
In general, in the absence of a data structure dedicated to support searching,
selection is an O operation where n is the number of primitives in the scene

hierarchy. This is to say that we must process every primitive to determine the
results of each selection operation. When there is more than one graphical object
under the mouse-click position, there will be more than one successful result from
the proximity tests. In this case, it is the responsibility of the application to deter-
mine the most logical object to be selected by the user. For example, when there
are overlapping objects, our program can decide to select the top-most visible
object.

( n )

UWBGL_D3D_Lib12

Change summary. See p. 524
for a summary of changes to
the library.

This library extends Lib11 to support selection (and collision) functionality in
the SceneNode class. We have chosen the world coordinate (WC) space to per-
form proximity tests. The implementation is based on the BoundingBox class. As
discussed in Section 7.5, although it is simple and efficient to implement, bound-
ing primitives with axis-aligned boxes may result in large void spaces. For this
reason, BoundingBox based selection/collision computation limits our results to
rough approximations. This is especially the case for non-axis aligned rectangles
and lines. The choice of WC space for proximity tests means that we must trans-
form mouse-click positions and primitive bounding boxes to the WC space. List-
ing 11.12 shows that the SceneNode class has been extended to include two new
functions for computing WC space bounding boxes. The GetBounds() function
at label A computes a WC space bounding box that bounds all the primitives,
including those from the child nodes. The GetNodeBounds() function at la-
bel B returns the WC bounding box of pSearchNode , a descendent of the current
node. Listing 11.13 shows the implementation of the SceneNode::GetBounds()
function. Figure 11.21 uses the body and left arm node from the human model
hierarchy of Figure 11.14 to help explain the GetBounds() function.