Graphics Reference
In-Depth Information
1. Assign each polygon a sort key equal to the camera-space
z
-value of the
vertex
farthest
from the viewport.
2. Sort all polygons from farthest to nearest according to their keys.
3. Detect cases where two polygons have ambiguous ordering. Subdivide
such polygons until the pieces have an explicit ordering, and place those
in the sort list in the correct priority order.
4. Render all polygons in priority order, from farthest to nearest.
The ordering of two polygons is considered ambiguous under this algorithm
if their
z
-extents and 2D projections (i.e., their homogeneous clip-space, axis-
aligned bounding boxes) overlap and one polygon intersects the plane of the other.
Consider a scene defined by a set of polygons and a viewer using a pinhole pro-
jection model. Schumacker [SBGS69] noted that a plane passing through the
scene that does not intersect any polygons divides them into two sets. Those poly-
gons on the same side of the plane as the viewer must be strictly closer to the
viewer, and thus cannot be occluded by those polygons on the farther side. He
grouped polygons into
clusters,
and recursively subdivided them when suitable
partition planes could not be found. Within each cluster he precomputed a viewer-
independent ordering (see later work by Sander et al. [SNB07] on a related prob-
lem), and employed a special-purpose rasterizer that followed these orderings.
Fuchs, Kedem, and Naylor [FKN80] generalized these ideas into the binary
space partition tree. We have already discussed in this chapter how BSP trees
can solve visible surface determination by accelerating ray-primitive intersection.
They can also be applied in the context of a list-priority algorithm, and that was
their original motivating application. (We will shortly see two more applications
of BSP trees to visibility: portals and mirrors, and precomputed visibility.)
The same logic found in the ray-intersection algorithm applies to the list-
priority rendering with a BSP tree; we are conceptually performing ray intersec-
tion on all possible view rays. Listing 36.2 gives an implementation that sorts all
polygons from farthest to nearest, given a previously computed BSP tree. We can
look at this as a variation on the depth-sort algorithm where we are guaranteed to
never encounter the case requiring subdivision. We never need to subdivide during
traversal because the tree's construction already performed subdivision at partition
planes between nearby polygons.
Listing 36.2: The list-priority algorithm for rendering polygons in a BSP tree
with root
node
as observed by a viewer at
P
.
1
2
3
4
5
6
7
8
9
10
11
12
13
function BSPPriorityRender(P, node):
if node is a leaf:
render the polygon at node
return
closer = node.positiveChild
farther = node.negativeChild
if P is in the negative half-space of node:
swap closer, farther
BSPPriorityRender(P, farther)
BSPPriorityRender(P, closer)
