Graphics Reference
In-Depth Information
since the average-case performance depends on the queries and we expect many
queries for a graphics application, we should intentionally unbalance the tree to
favor expected queries. This is directly analogous to the tree used to build a Huff-
man code for data compression. There, one knows the statistics of the input stream
and wants to build a tree that minimizes the average node depth weighted by the
number of occurrences of each node in the input stream. Unfortunately, we don't
know the exact queries that will be made, so we can't apply Huffman's algorithm
exactly to building a spatial data structure. But we can choose some reasonable
heuristics because our values have a spatial interpretation. For example, we might
assume that queries will be equally distributed in space or that the probability of
a random query returning a primitive is proportional to the size of that primitive.
Finally, because wall-clock time is what matters for this kind of analysis, we
have to factor in the tree-build time and the relative costs of memory operations
and comparisons when optimizing.
37.6.2 Building BSP Trees: oct tree, quad tree, BSP
tree, k dtree
It is hard to choose good partition planes. There are theoretically infinitely many
planes to choose from. The choice depends on the types of queries, the distribution
of data, and whether one wants to optimize the worst case, the best case, or the
“average” case. If the tree structure will be precomputed, the build process can
be made expensive—and some algorithms take O( n 2 ) time to build a tree on n
primitives. If the tree will be built or modified frequently inside an interactive
program, it is important to minimize the combination of tree-build and query time,
so one might choose partitions that can be identified quickly rather than ones that
give optimal query behavior.
To address the problem of considering too many choices of partition planes,
it is often easier to introduce constraints so as to consider a smaller number of
options. This has the added advantage of requiring fewer bits to represent the par-
titions, which translates to reduced storage cost and reduced memory bandwidth
during queries.
One such artificial constraint is to consider only axis-aligned parti-
tions [RR78]. The resultant BSP tree is called a k d tree (also written as “ k -d
tree”). The axis to split along may be chosen based on the data, or simply rotated
in round-robin fashion. In the latter case, each partition plane can be represented
(see Listing 37.13) by a single number representing its distance from the origin,
since the plane normal is determined by the depth of a plane's node in the tree.
Listing 37.13: k d tree representation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template < class Value >
class KDTree {
class Node {
public :
float partition;
Node * negativeHalfSpace;
Node * positiveHalfSpace;
List< Value > valueArray;
};
Node * root;
...
};
 
 
 
Search WWH ::




Custom Search