[136] | 1 | // This file is part of Eigen, a lightweight C++ template library
|
---|
| 2 | // for linear algebra.
|
---|
| 3 | //
|
---|
| 4 | // Copyright (C) 2009 Ilya Baran <ibaran@mit.edu>
|
---|
| 5 | //
|
---|
| 6 | // This Source Code Form is subject to the terms of the Mozilla
|
---|
| 7 | // Public License v. 2.0. If a copy of the MPL was not distributed
|
---|
| 8 | // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
|
---|
| 9 |
|
---|
| 10 | #ifndef EIGEN_BVH_MODULE_H
|
---|
| 11 | #define EIGEN_BVH_MODULE_H
|
---|
| 12 |
|
---|
| 13 | #include <Eigen/Core>
|
---|
| 14 | #include <Eigen/Geometry>
|
---|
| 15 | #include <Eigen/StdVector>
|
---|
| 16 | #include <algorithm>
|
---|
| 17 | #include <queue>
|
---|
| 18 |
|
---|
| 19 | namespace Eigen {
|
---|
| 20 |
|
---|
| 21 | /**
|
---|
| 22 | * \defgroup BVH_Module BVH module
|
---|
| 23 | * \brief This module provides generic bounding volume hierarchy algorithms
|
---|
| 24 | * and reference tree implementations.
|
---|
| 25 | *
|
---|
| 26 | *
|
---|
| 27 | * \code
|
---|
| 28 | * #include <unsupported/Eigen/BVH>
|
---|
| 29 | * \endcode
|
---|
| 30 | *
|
---|
| 31 | * A bounding volume hierarchy (BVH) can accelerate many geometric queries. This module provides a generic implementation
|
---|
| 32 | * of the two basic algorithms over a BVH: intersection of a query object against all objects in the hierarchy and minimization
|
---|
| 33 | * of a function over the objects in the hierarchy. It also provides intersection and minimization over a cartesian product of
|
---|
| 34 | * two BVH's. A BVH accelerates intersection by using the fact that if a query object does not intersect a volume, then it cannot
|
---|
| 35 | * intersect any object contained in that volume. Similarly, a BVH accelerates minimization because the minimum of a function
|
---|
| 36 | * over a volume is no greater than the minimum of a function over any object contained in it.
|
---|
| 37 | *
|
---|
| 38 | * Some sample queries that can be written in terms of intersection are:
|
---|
| 39 | * - Determine all points where a ray intersects a triangle mesh
|
---|
| 40 | * - Given a set of points, determine which are contained in a query sphere
|
---|
| 41 | * - Given a set of spheres, determine which contain the query point
|
---|
| 42 | * - Given a set of disks, determine if any is completely contained in a query rectangle (represent each 2D disk as a point \f$(x,y,r)\f$
|
---|
| 43 | * in 3D and represent the rectangle as a pyramid based on the original rectangle and shrinking in the \f$r\f$ direction)
|
---|
| 44 | * - Given a set of points, count how many pairs are \f$d\pm\epsilon\f$ apart (done by looking at the cartesian product of the set
|
---|
| 45 | * of points with itself)
|
---|
| 46 | *
|
---|
| 47 | * Some sample queries that can be written in terms of function minimization over a set of objects are:
|
---|
| 48 | * - Find the intersection between a ray and a triangle mesh closest to the ray origin (function is infinite off the ray)
|
---|
| 49 | * - Given a polyline and a query point, determine the closest point on the polyline to the query
|
---|
| 50 | * - Find the diameter of a point cloud (done by looking at the cartesian product and using negative distance as the function)
|
---|
| 51 | * - Determine how far two meshes are from colliding (this is also a cartesian product query)
|
---|
| 52 | *
|
---|
| 53 | * This implementation decouples the basic algorithms both from the type of hierarchy (and the types of the bounding volumes) and
|
---|
| 54 | * from the particulars of the query. To enable abstraction from the BVH, the BVH is required to implement a generic mechanism
|
---|
| 55 | * for traversal. To abstract from the query, the query is responsible for keeping track of results.
|
---|
| 56 | *
|
---|
| 57 | * To be used in the algorithms, a hierarchy must implement the following traversal mechanism (see KdBVH for a sample implementation): \code
|
---|
| 58 | typedef Volume //the type of bounding volume
|
---|
| 59 | typedef Object //the type of object in the hierarchy
|
---|
| 60 | typedef Index //a reference to a node in the hierarchy--typically an int or a pointer
|
---|
| 61 | typedef VolumeIterator //an iterator type over node children--returns Index
|
---|
| 62 | typedef ObjectIterator //an iterator over object (leaf) children--returns const Object &
|
---|
| 63 | Index getRootIndex() const //returns the index of the hierarchy root
|
---|
| 64 | const Volume &getVolume(Index index) const //returns the bounding volume of the node at given index
|
---|
| 65 | void getChildren(Index index, VolumeIterator &outVBegin, VolumeIterator &outVEnd,
|
---|
| 66 | ObjectIterator &outOBegin, ObjectIterator &outOEnd) const
|
---|
| 67 | //getChildren takes a node index and makes [outVBegin, outVEnd) range over its node children
|
---|
| 68 | //and [outOBegin, outOEnd) range over its object children
|
---|
| 69 | \endcode
|
---|
| 70 | *
|
---|
| 71 | * To use the hierarchy, call BVIntersect or BVMinimize, passing it a BVH (or two, for cartesian product) and a minimizer or intersector.
|
---|
| 72 | * For an intersection query on a single BVH, the intersector encapsulates the query and must provide two functions:
|
---|
| 73 | * \code
|
---|
| 74 | bool intersectVolume(const Volume &volume) //returns true if the query intersects the volume
|
---|
| 75 | bool intersectObject(const Object &object) //returns true if the intersection search should terminate immediately
|
---|
| 76 | \endcode
|
---|
| 77 | * The guarantee that BVIntersect provides is that intersectObject will be called on every object whose bounding volume
|
---|
| 78 | * intersects the query (but possibly on other objects too) unless the search is terminated prematurely. It is the
|
---|
| 79 | * responsibility of the intersectObject function to keep track of the results in whatever manner is appropriate.
|
---|
| 80 | * The cartesian product intersection and the BVMinimize queries are similar--see their individual documentation.
|
---|
| 81 | *
|
---|
| 82 | * 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:
|
---|
| 83 | * \include BVH_Example.cpp
|
---|
| 84 | * Output: \verbinclude BVH_Example.out
|
---|
| 85 | */
|
---|
| 86 | }
|
---|
| 87 |
|
---|
| 88 | //@{
|
---|
| 89 |
|
---|
| 90 | #include "src/BVH/BVAlgorithms.h"
|
---|
| 91 | #include "src/BVH/KdBVH.h"
|
---|
| 92 |
|
---|
| 93 | //@}
|
---|
| 94 |
|
---|
| 95 | #endif // EIGEN_BVH_MODULE_H
|
---|