<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.5"/>
<title>Eigen-unsupported: BVH module</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
$(window).load(resizeHeight);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
$(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="eigendoxy.css" rel="stylesheet" type="text/css">
<!-- -->
<script type="text/javascript" src="eigen_navtree_hacks.js"></script>
<!-- <script type="text/javascript"> -->
<!-- </script> -->
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<!-- <a name="top"></a> -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td id="projectlogo"><img alt="Logo" src="Eigen_Silly_Professor_64x64.png"/></td>
<td style="padding-left: 0.5em;">
<div id="projectname"><a href="http://eigen.tuxfamily.org">Eigen-unsupported</a>
 <span id="projectnumber">3.2.0</span>
</div>
</td>
<td> <div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</span>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.5 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('group__BVH__Module.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark"> </span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark"> </span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark"> </span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark"> </span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark"> </span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark"> </span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark"> </span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark"> </span>Groups</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark"> </span>Pages</a></div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<div class="header">
<div class="headertitle">
<div class="title">BVH module</div> </div>
</div><!--header-->
<div class="contents">
<p>This module provides generic bounding volume hierarchy algorithms and reference tree implementations. </p>
<div class="fragment"><div class="line">* #include <unsupported/Eigen/BVH></div>
<div class="line">* </div>
</div><!-- fragment --><p>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.</p>
<p>Some sample queries that can be written in terms of intersection are:</p>
<ul>
<li>Determine all points where a ray intersects a triangle mesh</li>
<li>Given a set of points, determine which are contained in a query sphere</li>
<li>Given a set of spheres, determine which contain the query point</li>
<li>Given a set of disks, determine if any is completely contained in a query rectangle (represent each 2D disk as a point <img class="formulaInl" alt="$(x,y,r)$" src="form_0.png"/> in 3D and represent the rectangle as a pyramid based on the original rectangle and shrinking in the <img class="formulaInl" alt="$r$" src="form_1.png"/> direction)</li>
<li>Given a set of points, count how many pairs are <img class="formulaInl" alt="$d\pm\epsilon$" src="form_2.png"/> apart (done by looking at the cartesian product of the set of points with itself)</li>
</ul>
<p>Some sample queries that can be written in terms of function minimization over a set of objects are:</p>
<ul>
<li>Find the intersection between a ray and a triangle mesh closest to the ray origin (function is infinite off the ray)</li>
<li>Given a polyline and a query point, determine the closest point on the polyline to the query</li>
<li>Find the diameter of a point cloud (done by looking at the cartesian product and using negative distance as the function)</li>
<li>Determine how far two meshes are from colliding (this is also a cartesian product query)</li>
</ul>
<p>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.</p>
<p>To be used in the algorithms, a hierarchy must implement the following traversal mechanism (see <a class="el" href="classEigen_1_1KdBVH.html" title="A simple bounding volume hierarchy based on AlignedBox. ">KdBVH</a> for a sample implementation):</p>
<div class="fragment"><div class="line"><span class="keyword">typedef</span> Volume <span class="comment">//the type of bounding volume</span></div>
<div class="line"><span class="keyword">typedef</span> Object <span class="comment">//the type of object in the hierarchy</span></div>
<div class="line"><span class="keyword">typedef</span> Index <span class="comment">//a reference to a node in the hierarchy--typically an int or a pointer</span></div>
<div class="line"><span class="keyword">typedef</span> VolumeIterator <span class="comment">//an iterator type over node children--returns Index</span></div>
<div class="line"><span class="keyword">typedef</span> ObjectIterator <span class="comment">//an iterator over object (leaf) children--returns const Object &</span></div>
<div class="line">Index getRootIndex() const <span class="comment">//returns the index of the hierarchy root</span></div>
<div class="line">const Volume &getVolume(Index index) const <span class="comment">//returns the bounding volume of the node at given index</span></div>
<div class="line"><span class="keywordtype">void</span> getChildren(Index index, VolumeIterator &outVBegin, VolumeIterator &outVEnd,</div>
<div class="line"> ObjectIterator &outOBegin, ObjectIterator &outOEnd) const</div>
<div class="line"><span class="comment">//getChildren takes a node index and makes [outVBegin, outVEnd) range over its node children</span></div>
<div class="line"><span class="comment">//and [outOBegin, outOEnd) range over its object children</span></div>
</div><!-- fragment --><p>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: </p>
<div class="fragment"><div class="line"><span class="keywordtype">bool</span> intersectVolume(<span class="keyword">const</span> Volume &volume) <span class="comment">//returns true if the query intersects the volume</span></div>
<div class="line"><span class="keywordtype">bool</span> intersectObject(<span class="keyword">const</span> Object &<span class="keywordtype">object</span>) <span class="comment">//returns true if the intersection search should terminate immediately</span></div>
</div><!-- fragment --><p> 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.</p>
<p>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: </p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <Eigen/StdVector></span></div>
<div class="line"><span class="preprocessor">#include <unsupported/Eigen/BVH></span></div>
<div class="line"><span class="preprocessor">#include <iostream></span></div>
<div class="line"></div>
<div class="line"><span class="keyword">using namespace </span>Eigen;</div>
<div class="line"><span class="keyword">typedef</span> AlignedBox<double, 2> Box2d;</div>
<div class="line"></div>
<div class="line"><span class="keyword">namespace </span>Eigen {</div>
<div class="line"> <span class="keyword">namespace </span>internal {</div>
<div class="line"> Box2d bounding_box(<span class="keyword">const</span> Vector2d &v) { <span class="keywordflow">return</span> Box2d(v, v); } <span class="comment">//compute the bounding box of a single point</span></div>
<div class="line"> }</div>
<div class="line">}</div>
<div class="line"></div>
<div class="line"><span class="keyword">struct </span>PointPointMinimizer <span class="comment">//how to compute squared distances between points and rectangles</span></div>
<div class="line">{</div>
<div class="line"> PointPointMinimizer() : calls(0) {}</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keywordtype">double</span> Scalar;</div>
<div class="line"></div>
<div class="line"> <span class="keywordtype">double</span> minimumOnVolumeVolume(<span class="keyword">const</span> Box2d &r1, <span class="keyword">const</span> Box2d &r2) { ++calls; <span class="keywordflow">return</span> r1.squaredExteriorDistance(r2); }</div>
<div class="line"> <span class="keywordtype">double</span> minimumOnVolumeObject(<span class="keyword">const</span> Box2d &r, <span class="keyword">const</span> Vector2d &v) { ++calls; <span class="keywordflow">return</span> r.squaredExteriorDistance(v); }</div>
<div class="line"> <span class="keywordtype">double</span> minimumOnObjectVolume(<span class="keyword">const</span> Vector2d &v, <span class="keyword">const</span> Box2d &r) { ++calls; <span class="keywordflow">return</span> r.squaredExteriorDistance(v); }</div>
<div class="line"> <span class="keywordtype">double</span> minimumOnObjectObject(<span class="keyword">const</span> Vector2d &v1, <span class="keyword">const</span> Vector2d &v2) { ++calls; <span class="keywordflow">return</span> (v1 - v2).squaredNorm(); }</div>
<div class="line"></div>
<div class="line"> <span class="keywordtype">int</span> calls;</div>
<div class="line">};</div>
<div class="line"></div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line"> <span class="keyword">typedef</span> std::vector<Vector2d, aligned_allocator<Vector2d> > StdVectorOfVector2d;</div>
<div class="line"> StdVectorOfVector2d redPoints, bluePoints;</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i = 0; i < 100; ++i) { <span class="comment">//initialize random set of red points and blue points</span></div>
<div class="line"> redPoints.push_back(Vector2d::Random());</div>
<div class="line"> bluePoints.push_back(Vector2d::Random());</div>
<div class="line"> }</div>
<div class="line"></div>
<div class="line"> PointPointMinimizer minimizer;</div>
<div class="line"> <span class="keywordtype">double</span> minDistSq = std::numeric_limits<double>::max();</div>
<div class="line"></div>
<div class="line"> <span class="comment">//brute force to find closest red-blue pair</span></div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i = 0; i < (int)redPoints.size(); ++i)</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> j = 0; j < (int)bluePoints.size(); ++j)</div>
<div class="line"> minDistSq = std::min(minDistSq, minimizer.minimumOnObjectObject(redPoints[i], bluePoints[j]));</div>
<div class="line"> std::cout << <span class="stringliteral">"Brute force distance = "</span> << sqrt(minDistSq) << <span class="stringliteral">", calls = "</span> << minimizer.calls << std::endl;</div>
<div class="line"></div>
<div class="line"> <span class="comment">//using BVH to find closest red-blue pair</span></div>
<div class="line"> minimizer.calls = 0;</div>
<div class="line"> <a class="code" href="classEigen_1_1KdBVH.html">KdBVH<double, 2, Vector2d></a> redTree(redPoints.begin(), redPoints.end()), blueTree(bluePoints.begin(), bluePoints.end()); <span class="comment">//construct the trees</span></div>
<div class="line"> minDistSq = <a class="code" href="namespaceEigen.html#adcbe73ac1482eacab0e18ee32c25508e">BVMinimize</a>(redTree, blueTree, minimizer); <span class="comment">//actual BVH minimization call</span></div>
<div class="line"> std::cout << <span class="stringliteral">"BVH distance = "</span> << sqrt(minDistSq) << <span class="stringliteral">", calls = "</span> << minimizer.calls << std::endl;</div>
<div class="line"></div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
</div><!-- fragment --><p> Output: </p>
<pre class="fragment">Brute force distance = 0.00428018, calls = 10000
BVH distance = 0.00428018, calls = 756
</pre> </div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="footer">Generated on Mon Oct 28 2013 11:05:27 for Eigen-unsupported by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.5 </li>
</ul>
</div>
<!-- Piwik -->
<!--
<script type="text/javascript">
var pkBaseURL = (("https:" == document.location.protocol) ? "https://stats.sylphide-consulting.com/piwik/" : "http://stats.sylphide-consulting.com/piwik/");
document.write(unescape("%3Cscript src='" + pkBaseURL + "piwik.js' type='text/javascript'%3E%3C/script%3E"));
</script><script type="text/javascript">
try {
var piwikTracker = Piwik.getTracker(pkBaseURL + "piwik.php", 20);
piwikTracker.trackPageView();
piwikTracker.enableLinkTracking();
} catch( err ) {}
</script><noscript><p><img src="http://stats.sylphide-consulting.com/piwik/piwik.php?idsite=20" style="border:0" alt="" /></p></noscript>
-->
<!-- End Piwik Tracking Code -->
</body>
</html>
