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
19namespace 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
96