1 // This file is part of Eigen, a lightweight C++ template library 2 // for linear algebra. 3 // 4 // Copyright (C) 2009 Ilya Baran <ibaran (a] 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 /** \ingroup Unsupported_modules 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
