This module provides generic bounding volume hierarchy algorithms and reference tree implementations. More...
Namespaces | |
namespace | Eigen::internal |
Classes | |
class | KdBVH< _Scalar, _Dim, _Object > |
A simple bounding volume hierarchy based on AlignedBox. More... |
Functions | |
template<typename BVH , typename Intersector > | |
void | BVIntersect (const BVH &tree, Intersector &intersector) |
template<typename BVH1 , typename BVH2 , typename Intersector > | |
void | BVIntersect (const BVH1 &tree1, const BVH2 &tree2, Intersector &intersector) |
template<typename BVH , typename Minimizer > | |
Minimizer::Scalar | BVMinimize (const BVH &tree, Minimizer &minimizer) |
template<typename BVH1 , typename BVH2 , typename Minimizer > | |
Minimizer::Scalar | BVMinimize (const BVH1 &tree1, const BVH2 &tree2, Minimizer &minimizer) |
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:
Brute force distance = 0.00428018, calls = 10000 BVH distance = 0.00428018, calls = 756
void Eigen::BVIntersect | ( | const BVH & | tree, |
Intersector & | intersector | ||
) |
Given a BVH, runs the query encapsulated by intersector. The Intersector type must provide the following members:
void Eigen::BVIntersect | ( | const BVH1 & | tree1, |
const BVH2 & | tree2, | ||
Intersector & | intersector | ||
) |
Given two BVH's, runs the query on their Cartesian product encapsulated by intersector. The Intersector type must provide the following members:
Minimizer::Scalar Eigen::BVMinimize | ( | const BVH & | tree, |
Minimizer & | minimizer | ||
) |
Given a BVH, runs the query encapsulated by minimizer.
Minimizer::Scalar Eigen::BVMinimize | ( | const BVH1 & | tree1, |
const BVH2 & | tree2, | ||
Minimizer & | minimizer | ||
) |
Given two BVH's, runs the query on their cartesian product encapsulated by minimizer.