BSP efficiency
From CGAFaq
Contents |
Space complexity
For the problem of hidden surface removal, consider a set of n parallel
polygons, and the set of m partitioning planes, all of which are
perpendicular to the polgyons. This has the effect of splitting every
polygon with every partition. The number of polygons resulting from
this partitioning scheme is .
If the partitioning planes are
selected from the candidate polygon set (an autopartition), then
,
and the expression reduces to
.
Thus the worst case spatial
complexity of a BSP tree constructed using an autopartition is
.
It will be extremely difficult to construct a case which satisfies this
formula. The "expected" case, repeatedly expressed by Naylor, is .
Time complexity
The time complexity of rendering from a BSP built using an
autopartition is the same as the spatial complexity, that is a worst
case of , and an "expected" case of
.
Improving Efficiency
Bounding volumes
Bounding spheres are simple to implement, take only a single plane comparison, using the center of the sphere.
Optimal trees
Construction of an optimal tree is an NP-complete problem. The problem is one of splitting versus tree balancing. These are mutually exclusive requirements. You should choose your strategy for building a good tree based on how you intend to use the tree.
Minimizing splitting
An obvious problem with BSP trees is that polygons get split during the construction phase, which results in a larger number of polygons. Larger numbers of polygons translate into larger storage requirements and longer tree traversal times. This is undesirable in all applications of BSP trees, so some scheme for minimizing splitting will improve tree performance.
Bear in mind that minimization of splitting requires pre-existing knowledge about all of the polygons that will be inserted into the tree. This knowledge may not exist for interactive uses such as solid modelling.
Tree balancing
Tree balancing is important for uses which perform spatial classification of points, lines, and surfaces. This includes ray tracing and solid modelling. Tree balancing is important for these applications because the time complexity for classification is based on the depth of the tree. Unbalanced trees have deeper subtrees, and therefore have a worse worst case.
For the hidden surface problem, balancing doesn't significantly affect runtime. This is because the expected time complexity for tree traversal is linear on the number of polygons in the tree, rather than the depth of the tree.
Balancing vs. splitting
If balancing is an important concern for your application, it will be necessary to trade off some balance for reduced splitting. If you are choosing your hyperplanes from the polygon candidates, then one way to optimize these two factors is to randomly select a small number of candidates. These new candidates are tested against the full list for splitting and balancing efficiency. A linear combination of the two efficiencies is used to rank the candidates, and the best one is chosen.
Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.
