14. Acceleration Algorithms (2/11)

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

650 14. Acceleration Algorithms

BVHs can be used for dynamic scenes as well [1050]. When an object

contained in a BV has moved, simply check whether it is still contained

in its parent’s BV. If it is, then the BVH is still valid. Otherwise, the

object node is removed and the parent’s BV recomputed. The node is then

recursively inserted back into the tree from the root. Another method is to

grow the parent’s BV to hold the child recursively up the tree as needed.

With either method, the tree can become unbalanced and ineﬃcient as

more and more edits are performed. Another approach is to put a BV

around the limits of movement of the object over some period of time.

This is called a temporal bounding volume [4]. For example, a pendulum

could have a bounding box that enclosed the entire volume swept out by

its motion.

To create a BVH, one must ﬁrst be able to compute a tight BV around

a set of objects. This topic is treated in Section 16.3 on page 732. Then,

the actual hierarchy of BVs must be created. Strategies for this are treated

in Section 17.3.1 on page 802.

14.1.2 BSP Trees

Binary space partitioning trees, or BSP trees for short, exist as two notice-

ably diﬀerent variants in computer graphics, which we call axis-aligned and

polygon-aligned. The trees are created by using a plane to divide the space

in two, and then sorting the geometry into these two spaces. This division

is done recursively. One interesting property that these trees have is that

if the trees are traversed in a certain way, the geometrical contents of the

tree can be sorted front-to-back from any point of view. This sorting is

approximate for axis-aligned and exact for polygon-aligned BSPs. This is

in contrast to BVHs, which usually do not include any type of sorting.

Axis-Aligned BSP Trees

An axis-aligned BSP tree

is created as follows. First, the whole scene

is enclosed in an axis-aligned bounding box (AABB). The idea is then to

recursively subdivide that box into smaller boxes. Now, consider a box at

any recursion level. One axis of the box is chosen, and a perpendicular

plane is generated that divides the space into two boxes. Some schemes

ﬁx this partitioning plane so that it divides the box exactly in half; others

allow the plane to vary in position.

An object intersecting the plane can be treated in any number of ways.

For example, it could be stored at this level of the tree, or made a member

of both child boxes, or truly split by the plane into two separate objects.

A BSP tree that is not polygon-aligned may split the space in any way it wishes.

However, we focus on axis-aligned BSP trees here because this is the most commonly

used variant, and the most practical.

14.1. Spatial Data Structures 651

Storing at the tree level has the advantage that there is only one copy of

the object in the tree, making object deletion straightforward. However,

small objects intersected by the splitting plane become lodged in the upper

levels of the tree, which tends to be ineﬃcient. Placing intersected objects

into both children can give tighter bounds to larger objects, as all objects

percolate down to one or more leaf nodes, but only those they overlap.

A mailboxing scheme (also called timestamping) is then used to mark the

object when it is ﬁrst encountered when rendering a frame, e.g., with the

number of the frame. When the object is encountered again in another

leaf node, its mailbox is checked and the object ignored if it has already

been sent to the screen for this frame. One disadvantage here is that large

objects could be duplicated into many leaf nodes, costing time and memory.

However, a more important, though subtle, problem is that every object’s

timestamp must be both read and written. Doing so can cause the memory

cache to be invalidated and so cause signiﬁcant slowdowns [864].

Each child box contains some number of objects, and this plane-splitting

procedure is repeated, subdividing each AABB recursively until some cri-

terion is fulﬁlled to halt the process. See Figure 14.3 for an example of an

axis-aligned BSP tree.

The axis and placement of the splitting plane is important for maximiz-

ing eﬃciency. One strategy for splitting a node’s box is to cycle through

the axes. That is, at the root, the box is always split along the x-axis, its

children are split along y, the grandchildren along z, then the cycle repeats.

BSP trees using this strategy are sometimes called k-d trees [1099]. An-

Figure 14.3. Axis-aligned BSP tree. In this example, the space partitions are allowed to

be anywhere along the axis, not just at its midpoint. The spatial volumes formed are

labeled A through E. The tree on the right shows the underlying BSP data structure.

Each leaf node represents an area, with that area’s contents shown beneath it. Note

that the triangle is in the object list for two areas, C and E, because it overlaps both.

652 14. Acceleration Algorithms

other strategy is to ﬁnd the largest side of the box and split the box along

this direction. For example, say the box is largest in the y-direction; then

splitting occurs at some plane, y = d,whered is a scalar constant. Geo-

metric probability theory (see Section 16.4) is also useful in determining a

near-optimal axis and split location. The idea is to avoid splitting objects

as much as possible, along with ﬁnding two child nodes that together min-

imize the number of objects in a child multiplied by surface area or mean

width of that child.

Aila and Miettinen [4] present an eﬃcient BSP management scheme

for large scenes. The system performs lazy evaluation, subdividing only

those nodes that are visible. This can save work by avoiding computing

splits for parts of the world that are never viewed. It also spreads out

the cost of subdivision over a number of frames. Only those objects that

are smaller than the current node are pushed further down the hierarchy;

larger objects (judged by their diagonal length) remain as direct children

of the node. If the number of small objects in a BSP node is 10 or greater,

the node is subdivided. Geometric probability theory is used to determine

a near-optimal split axis and location. Mailboxing is used to allow an

object cut by a split plane to be in multiple nodes. This approach avoids

small objects getting lodged in the upper levels of the BSP tree, while also

terminating subdivision when it is unlikely to help further.

Rough front-to-back sorting is an example of how axis-aligned BSP trees

can be used. This is useful for occlusion culling algorithms (see Section 14.6

and 18.3.6), as well as for generally reducing pixel shader costs by mini-

mizing pixel overdraw (see Section 15.4.5). Assume that a node called N

is currently traversed. Here, N istherootatthestartoftraversal. The

splitting plane of N is examined, and tree traversal continues recursively

on the side of the plane where the viewer is located. Thus, it is only when

the entire half of the tree has been traversed that we can start to traverse

the other side. This traversal does not give exact front-to-back sorting,

since the contents of the leaf nodes are not sorted, and because objects

may be in many nodes of the tree. However, it gives a rough sorting, which

often is useful. By starting traversal on the other side of a node’s plane

when compared to the viewer’s position, rough back-to-front sorting can

be obtained. This is useful for transparency sorting (see Section 5.7). This

traversal can also be used to test a ray against the scene geometry. The

ray’s origin is simply exchanged for the viewer’s location. Another use is

in view frustum culling (Section 14.3).

Polygon-Aligned BSP Trees

The other type of BSP tree is the polygon-aligned form [1, 366, 367, 428].

This data structure is particularly useful for rendering static or rigid geom-

etry in an exact sorted order. This algorithm was popular for games like

14.1. Spatial Data Structures 653

Figure 14.4. Polygon-aligned BSP tree. Polygons A through G are shown from above.

Space is ﬁrst split by polygon A, then each half-space is split separately by B and C.

The splitting plane formed by polygon B intersects the polygon in the lower left corner,

splitting it into separate polygons D and E. The BSP tree formed is shown on the right.

Doom, back when there was no hardware Z-buﬀer. It still has occasional

use, such as for collision detection (see Section 17.2).

In this scheme, a polygon is chosen as the divider, splitting space into

two halves. That is, at the root, a polygon is selected. The plane in which

the polygon lies is used to divide the rest of the polygons in the scene into

two sets. Any polygon that is intersected by the dividing plane is broken

into two separate pieces along the intersection line. Now in each half-

space of the dividing plane, another polygon is chosen as a divider, which

divides only the polygons in its half-space. This is done recursively until all

polygons are in the BSP tree. Creating an eﬃcient polygon-aligned BSP

tree is a time-consuming process, andsuchtreesarenormally computed

once and stored for reuse. This type of BSP tree is shown in Figure 14.4.

It is generally best to form a balanced tree, i.e., one where the depth

of each leaf node is the same, or at most oﬀ by one. A totally unbalanced

tree is ineﬃcient. An example would be a tree where each selected split-

ting polygon divides the space into one empty space, and the other space

contains the rest of the polygons. There are many diﬀerent strategies for

ﬁnding a polygon used for splitting that gives a good tree. One simple

strategy is the least-crossed criterion [366]. First, a number of candidate

polygons are randomly selected. The polygon whose plane splits the fewest

other polygons is used. For a test scene of 1,000 polygons, James [597]

provides empirical evidence that only ﬁve polygons need to be tested per

split operation in order to get a good tree. James gives a review of a wide

range of other strategies, as well as providing a new one of his own.

The polygon-aligned BSP tree has some useful properties. One is that,

for a given view, the structure can be traversed strictly from back to front

654 14. Acceleration Algorithms

(or front to back). This is in comparison to the axis-aligned BSP tree,

which normally gives only a rough sorted order. Determine on which side

of the root plane the camera is located. The set of polygons on the far side

of this plane is then beyond the near side’s set. Now with the far side’s set,

take the next level’s dividing plane and determine which side the camera

is on. The subset on the far side is again the subset farthest away from the

camera. By continuing recursively, this process establishes a strict back-

to-front order, and a painter’s algorithm can be used to render the scene.

The painter’s algorithm does not need a Z-buﬀer; if all objects are drawn

in a back-to-front order, each closer object is drawn in front of whatever is

behind it, and so no z-depth comparisons are required.

For example, consider what is seen by a viewer v in Figure 14.4. Re-

gardless of the viewing direction and frustum, v is to the left of the splitting

plane formed by A. So C, F, and G are behind B, D, and E. Comparing

v to the splitting plane of C, we ﬁnd G to be on the opposite side of this

plane, so it is displayed ﬁrst. A test of B’s plane determines that E should

be displayed before D. The back-to-front order is then G, C, F, A, E, B,

D. Note that this order does not guarantee that one object is closer to the

viewer than another; rather it provides a strict occlusion order, a subtle

diﬀerence. For example, polygon F is closer to v than polygon E, even

though it is farther back in occlusion order.

Other uses for polygon-aligned BSP trees are intersection testing (see

Chapter 16), and collision detection (see Section 17.2).

14.1.3 Octrees

The octree is similar to the axis-aligned BSP tree. A box is split simulta-

neously along all three axes, and the split point must be the center of the

box. This creates eight new boxes—hence the name octree.Thismakesthe

structure regular, which can make some queries more eﬃcient.

An octree is constructed by enclosing the entire scene in a minimal

axis-aligned box. The rest of the procedure is recursive in nature and ends

when a stopping criterion is fulﬁlled. As with axis-aligned BSP trees, these

criteria can include reaching a maximum recursion depth, or obtaining a

certain number of primitives in a box [1098, 1099]. If a criterion is met,

the algorithm binds the primitives to the box and terminates the recursion.

Otherwise, it subdivides the box along its main axes using three planes,

thereby forming eight equal-sized boxes. Each new box is tested and pos-

sibly subdivided again into 2 × 2 × 2 smaller boxes. This is illustrated

in two dimensions, where the data structure is called a quadtree,inFig-

ure 14.5. Quadtrees are the two-dimensional equivalent of octrees, with a

third axis being ignored. They can be useful in situations where there is

little advantage to categorizing the data along all three axes.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 14. Acceleration Algorithms (2/11)

Create new playlist

Sign In

Sign Up

Table of Contents for
14. Acceleration Algorithms (2/11)