![]() |
Eigen-unsupported
3.2.0
|
This module provides generic bounding volume hierarchy algorithms and reference tree implementations.
A bounding volume hierarchy (BVH) can accelerate many geometric queries. This module provides a generic implementation of the two basic algorithms over a BVH: intersection of a query object against all objects in the hierarchy and minimization of a function over the objects in the hierarchy. It also provides intersection and minimization over a cartesian product of two BVH's. A BVH accelerates intersection by using the fact that if a query object does not intersect a volume, then it cannot intersect any object contained in that volume. Similarly, a BVH accelerates minimization because the minimum of a function over a volume is no greater than the minimum of a function over any object contained in it.
Some sample queries that can be written in terms of intersection are:
Some sample queries that can be written in terms of function minimization over a set of objects are:
This implementation decouples the basic algorithms both from the type of hierarchy (and the types of the bounding volumes) and from the particulars of the query. To enable abstraction from the BVH, the BVH is required to implement a generic mechanism for traversal. To abstract from the query, the query is responsible for keeping track of results.
To be used in the algorithms, a hierarchy must implement the following traversal mechanism (see KdBVH for a sample implementation):
To use the hierarchy, call BVIntersect or BVMinimize, passing it a BVH (or two, for cartesian product) and a minimizer or intersector. For an intersection query on a single BVH, the intersector encapsulates the query and must provide two functions:
The guarantee that BVIntersect provides is that intersectObject will be called on every object whose bounding volume intersects the query (but possibly on other objects too) unless the search is terminated prematurely. It is the responsibility of the intersectObject function to keep track of the results in whatever manner is appropriate. The cartesian product intersection and the BVMinimize queries are similar–see their individual documentation.
The following is a simple but complete example for how to use the BVH to accelerate the search for a closest red-blue point pair:
Output: