3.4. Construction Heuristics

3.4. Construction Heuristics

One can prove that in general, auto-partitions have the same complexity as other partitionings [Paterson and Yao 90, de Berg et al. 00]. In addition, it has been proven that fat objects (i. e., objects with bounded aspect ratios) and uncluttered scenes allow a BSP with linear size [de Berg 95, de Berg 00].

However, for practical applications, the hidden constants do matter. So, the construction strategy should produce good BSPs. Depending on the application itself, however, the definition of exactly what a good BSP tree is can be quite different. Basically, there are two kinds of applications:

  • Classification: these are applications where the BSP is used to determine the inside/outside status of a point, or whether or not a line intersects with an object. In this case, we try to optimize the balance of the BSP.

  • Visibility: these are applications where the BSP is used to sort the polygons in visibility order such as rendering without a Z-buffer. Consequently, we try to minimize the number of splits , i. e., the size of the BSP.

3.4.1. Convex Objects

As an example, consider a convex object. In that case, an auto-partition has size O ( n ), takes time O ( n 2 ) to construct, and is a linear tree. This does not seem to be a very smart BSP (although it is perfectly suitable for visibility ordering).

If we allow arbitrary splitting planes, then we can balance the BSP much better. The construction time will be

image from book

where is the fraction of polygons that are split at each node. The following table shows the actual complexities for some values of :

0.05

0.2

0.4

 

n 1 . 15

n 2

n 7

As we mentioned, the question now is how to choose the splitting planes. We propose the following simple heuristic: [2] compute a representative vertex for each polygon (barycenter, bounding box center, etc.). Determine a plane, such that about the same number of points are on both sides, and such that all points are far away from the plane (obviously, this is an optimization, which can, for instance, be solved by principal component analysis).

3.4.2. Cost-Driven Heuristic

In order to derive construction criteria, one needs to define the quality of a BSP. An abstract measure is the cost of a BSP tree T :

(3.1)  image from book

where P ( T ˆ ) is the probability that the left subtree T ˆ will be visited under the condition that the tree T has been visited (ditto for P ( T + )). This probability depends on the application the BSP is going to be used for. For instance, in the case of inside/outside queries,

image from book

Obviously, trying to optimize Equation (3.1) globally is prohibitively expensive. Therefore, a local heuristic must be employed to guide the splitting process. A simple heuristic is the following [Naylor 96]: estimate the cost of the subtrees by the number of polygons, and add a penalty for polygons that are split by the current node, so that

(3.2)  image from book

where S is the set of polygons associated with a node, s is the set of polygons split by a node, and and are two parameters that can be used to make the BSP more balanced or smaller. ([Naylor 96] reports that = 0 . 8 , , . 95 and = 1/4 , , 3/4 are usually good values to start from.) Again, this is an optimization process, but now only a local one.

If the BSP is to be an auto-partition, then a very quick approximization of the local optimum yields very good results: just sort the polygons according to their size and evaluate Equation (3.2) for the first k polygons. Then choose the one that produces the least costly BSP (subtree). The rationale is that the probability that a polygon will be split is proportional to its size, so we try to get rid of the polygons as early as possible.

An even simpler heuristic was proposed in [Fuchs et al. 80]: randomly choose k polygons from S and select the one that produces the least number of splits. They report that k = 5 yielded near-optimal BSPs (for visibility ordering).

3.4.3. Non-Uniform Queries

In the previous section, we assumed that all queries are uniformly distributed over a certain domain. This is a valid assumption if nothing is known about the distribution. On the other hand, if we know more about it, then we should make use of this and construct the BSP such that frequent queries can be answered most quickly. [3]

Indeed, quite often, we know more about the queries. For instance, in ray tracing, the starting points are usually not uniformly distributed in space; for instance, they usually do not emanate from the interior of objects. Also, the prominent polygons of an object are hit more frequently than those that are within cavities or completely inside.

According to [Ar et al. 00], we can estimate the costs of a query by

image from book

So, according to this, we should minimize the number of stabbed leaf cells before a polygon hit occurs. At least two factors influencing the probability that a ray hits a polygon are:

  • if the angle between a ray and a polygon is large, then the probability is large;

  • if the polygon is large (relative to the total size of the object/universe), then the probability is large.

Let ( l ) denote the density of all rays l over some domain D ; this could be measured, or it could be derived from the geometry. Let S be the set of polygons over which the BSP is to be built. Assign a score p to each polygon

image from book

where the weight w is defined as

image from book

where n p is the normal of p , and r l is the direction of l .

So the algorithm for constructing a BSP adapted to a given distribution is the following randomized greedy strategy: sort all polygons according to score( p ); choose randomly one out of the top k , and split the set S . Thus, polygons with a higher probability of getting hit by the ray tend to end up higher in the tree.

The BSP thus constructed has been named the customized BSP by [Ar et al. 00]. The authors report that it usually has about two times as many polygons as its oblivious version, but the queries have to visit only one-half to one-tenth as many polygons.

3.4.4. Deferred, Self-Organizing BSPs

Now, what should we do if we just dont know the query distribution, or if it is too expensive to measure it by experiments? The answer is to defer the complete construction of the BSP. In other words, we build only as much of the BSP as is absolutely necessary. In addition, we keep a history (in some form) of all the queries we have seen so far, so whenever we need to build a new part of the BSP, we base the construction on that history (as a best guess of the probability distribution of all queries to come) [Ar et al. 02].

As an example, let us consider the problem of detecting intersections between a 3D line segment and a set of polygons. [4]

Since a BSP is now no longer completely constructed before we use it, the nodes must store additional information:

  • the polygon P defining the splitting plane; or, if it is a preliminary leaf,

  • a list image from book S of polygons associated with it, for which the subtree has not been built yet.

Algorithm 3.3: Testing for ray-scene intersections with a deferred BSP.
image from book
   testray(R,           )    if      is a leaf  then   for all   P     image from book         do   if   R  intersects  P   then   return  hit  end if   end for   else       1    child of     that contains startpoint of  R       2    other child           testray(R,      1  )  if  no hit in      1   then  testray(R,      2  )  end if   end if  
image from book
 

Now, the algorithm for answering queries with a ray R also triggers the construction of the BSP (see Algorithm 3.3). The initial BSP tree is just one node (the root) with image from book = S , i. e., all polygons of the object or scene. Since the line segment is finite (in particular, if it is short), this algorithm can usually stop much earlier, but the details have been omitted here.

In the following, we will fill in the open issues, namely:

  • when do we split a preliminary leaf? (and which one?)

  • how do we split?

For the when question: we keep an access counter per node, which is incremented every time that node is traversed during a query. Whenever one of the counters is over a certain threshold, we split that node (leaf). The threshold can be an absolute value or relative to the sum of all counters.

For the how question: we keep a counter per polygon P ˆˆ image from book , which is incremented every time an intersection with P is found. We sort image from book according to this counter; this can be done incrementally whenever one of the counters changes. If a split is to be performed for , then we use the first polygon from image from book as the splitting plane.

It turns out that many polygons are never hit by a line segment. Therefore, with this algorithm, a BSP subtree will never be wasted on these polygons, and they will be stored at the end of the lists at the leaves .

There are other ways to organize the polygon lists at the leaves: move the polygon currently being hit to the front of the list or swap it with the one in front of it. However, according to [Ar et al. 02], the strategy that sorts the list seems to work best.

According to the same authors, the performance gain in their experiments was a factor of about 2 to 20.

[2] For the case of convex objects, a heuristic has already been proposed in [Torres 90]. However, we believe that this heuristic has some flaws.

[3] The same principle underlies the Huffman encoding scheme.

[4] Sometimes, this is also called collision detection , in particular in the game programming industry, because we are interested only in a yes/no answer; in ray tracing, we want to determine the earliest intersection.



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net