Visibility Determination - Computer Graphics: Principles and Practice - page 1032

Listing 36.1: Pseudocode for visibility testing in a BSP tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function V(P, Q):
return not intersects(P, Q, root)

function intersects(P, Q, node):
if node is a leaf:
return (PQ intersects the primitive at the node)

closer = node.positiveChild
farther = node.negativeChild

if P is in the negative half-space of node:
// The negative side of the plane is closer to P
swap closer, farther

if intersects(P, Q, closer):
// Terminate early because an intersection was found
return true

if P and Q are in the same half-space of node:
// Segment PQ does not extend into the farther side
return false

// After searching the closer side, recursively search
// for an intersection on the farther side
return intersects(P, Q, farther)

Inline Exercise 36.1: The visibility testing code assumes that there's a closer
and a farther half-space. What will this code do when the splitting plane con-
tains the camera point P ? Will it still perform correctly? If not, what modifica-
tions are needed?

In the worst case the routine must visit every node of the tree. In practice this
rarely occurs. Typically, PQ is small with respect to the size of the scene and the
planes carve space into convex regions that do not all lie along the same line.
So we expect a relatively tight depth-first search with runtime proportional to the
height of the tree.
There are many ways to improve the performance of this algorithm by a
constant factor. These include clever algorithms for constructing the tree and
extending the binary tree to higher branching factors. For sparse scenes, alter-
native spatial partitions can be advantageous. The convex spaces created by the
splitting planes often have a lot of empty space compared to the volumes bounded
by the geometric primitives within them in a BSP tree. A regular grid or bound-
ing volume hierarchy may increase the primitive density within leaf nodes, thus
reducing the number of primitive intersections performed.
Where BSP tree iteration is limited by memory bandwidth, substantial savings
can be gained by using techniques for compressing the plane and node pointer
representation [SSW + 06].

36.2.2 Parallel Evaluation of Ray Tests
The previous analysis considered serial processing on a single scalar core. Paral-
lel execution architectures change the analysis. Tree search is notoriously hard to
execute concurrently for a single query . Near the root of a tree there isn't enough