11#ifndef EIGEN_BVALGORITHMS_H
12#define EIGEN_BVALGORITHMS_H
15#include "./InternalHeaderCheck.h"
21#ifndef EIGEN_PARSED_BY_DOXYGEN
22template <
typename BVH,
typename Intersector>
23bool intersect_helper(
const BVH &tree, Intersector &intersector,
typename BVH::Index root) {
24 using Index =
typename BVH::Index;
25 using VolIter =
typename BVH::VolumeIterator;
26 using ObjIter =
typename BVH::ObjectIterator;
28 VolIter vBegin = VolIter(), vEnd = VolIter();
29 ObjIter oBegin = ObjIter(), oEnd = ObjIter();
31 std::vector<Index> todo(1, root);
33 while (!todo.empty()) {
34 tree.getChildren(todo.back(), vBegin, vEnd, oBegin, oEnd);
37 for (; vBegin != vEnd; ++vBegin)
38 if (intersector.intersectVolume(tree.getVolume(*vBegin))) todo.push_back(*vBegin);
40 for (; oBegin != oEnd; ++oBegin)
41 if (intersector.intersectObject(*oBegin))
return true;
47template <
typename Volume1,
typename Object1,
typename Object2,
typename Intersector>
48struct intersector_helper1 {
49 intersector_helper1(
const Object2 &inStored, Intersector &in) : stored(inStored), intersector(in) {}
50 bool intersectVolume(
const Volume1 &vol) {
return intersector.intersectVolumeObject(vol, stored); }
51 bool intersectObject(
const Object1 &obj) {
return intersector.intersectObjectObject(obj, stored); }
53 Intersector &intersector;
56 intersector_helper1 &operator=(
const intersector_helper1 &) =
delete;
59template <
typename Volume2,
typename Object2,
typename Object1,
typename Intersector>
60struct intersector_helper2 {
61 intersector_helper2(
const Object1 &inStored, Intersector &in) : stored(inStored), intersector(in) {}
62 bool intersectVolume(
const Volume2 &vol) {
return intersector.intersectObjectVolume(stored, vol); }
63 bool intersectObject(
const Object2 &obj) {
return intersector.intersectObjectObject(stored, obj); }
65 Intersector &intersector;
68 intersector_helper2 &operator=(
const intersector_helper2 &) =
delete;
79template <
typename BVH,
typename Intersector>
81 internal::intersect_helper(tree, intersector, tree.getRootIndex());
92template <
typename BVH1,
typename BVH2,
typename Intersector>
94 Intersector &intersector)
96 using Index1 =
typename BVH1::Index;
97 using Index2 =
typename BVH2::Index;
99 internal::intersector_helper1<typename BVH1::Volume, typename BVH1::Object, typename BVH2::Object, Intersector>;
101 internal::intersector_helper2<typename BVH2::Volume, typename BVH2::Object, typename BVH1::Object, Intersector>;
102 using VolIter1 =
typename BVH1::VolumeIterator;
103 using ObjIter1 =
typename BVH1::ObjectIterator;
104 using VolIter2 =
typename BVH2::VolumeIterator;
105 using ObjIter2 =
typename BVH2::ObjectIterator;
107 VolIter1 vBegin1 = VolIter1(), vEnd1 = VolIter1();
108 ObjIter1 oBegin1 = ObjIter1(), oEnd1 = ObjIter1();
109 VolIter2 vBegin2 = VolIter2(), vEnd2 = VolIter2(), vCur2 = VolIter2();
110 ObjIter2 oBegin2 = ObjIter2(), oEnd2 = ObjIter2(), oCur2 = ObjIter2();
112 std::vector<std::pair<Index1, Index2> > todo(1, std::make_pair(tree1.getRootIndex(), tree2.getRootIndex()));
114 while (!todo.empty()) {
115 tree1.getChildren(todo.back().first, vBegin1, vEnd1, oBegin1, oEnd1);
116 tree2.getChildren(todo.back().second, vBegin2, vEnd2, oBegin2, oEnd2);
119 for (; vBegin1 != vEnd1; ++vBegin1) {
120 const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
121 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
122 if (intersector.intersectVolumeVolume(vol1, tree2.getVolume(*vCur2)))
123 todo.push_back(std::make_pair(*vBegin1, *vCur2));
126 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
127 Helper1 helper(*oCur2, intersector);
128 if (internal::intersect_helper(tree1, helper, *vBegin1))
return;
132 for (; oBegin1 != oEnd1; ++oBegin1) {
133 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
134 Helper2 helper(*oBegin1, intersector);
135 if (internal::intersect_helper(tree2, helper, *vCur2))
return;
138 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
139 if (intersector.intersectObjectObject(*oBegin1, *oCur2))
return;
147#ifndef EIGEN_PARSED_BY_DOXYGEN
148template <
typename BVH,
typename Minimizer>
149typename Minimizer::Scalar minimize_helper(
const BVH &tree, Minimizer &minimizer,
typename BVH::Index root,
150 typename Minimizer::Scalar minimum) {
151 using Scalar =
typename Minimizer::Scalar;
152 using Index =
typename BVH::Index;
153 using QueueElement = std::pair<Scalar, Index>;
154 using VolIter =
typename BVH::VolumeIterator;
155 using ObjIter =
typename BVH::ObjectIterator;
157 VolIter vBegin = VolIter(), vEnd = VolIter();
158 ObjIter oBegin = ObjIter(), oEnd = ObjIter();
159 std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> >
162 todo.push(std::make_pair(Scalar(), root));
164 while (!todo.empty()) {
165 tree.getChildren(todo.top().second, vBegin, vEnd, oBegin, oEnd);
168 for (; oBegin != oEnd; ++oBegin)
169 minimum = (std::min)(minimum, minimizer.minimumOnObject(*oBegin));
171 for (; vBegin != vEnd; ++vBegin) {
172 Scalar val = minimizer.minimumOnVolume(tree.getVolume(*vBegin));
173 if (val < minimum) todo.push(std::make_pair(val, *vBegin));
181template <
typename Volume1,
typename Object1,
typename Object2,
typename Minimizer>
182struct minimizer_helper1 {
183 using Scalar =
typename Minimizer::Scalar;
184 minimizer_helper1(
const Object2 &inStored, Minimizer &m) : stored(inStored), minimizer(m) {}
185 Scalar minimumOnVolume(
const Volume1 &vol) {
return minimizer.minimumOnVolumeObject(vol, stored); }
186 Scalar minimumOnObject(
const Object1 &obj) {
return minimizer.minimumOnObjectObject(obj, stored); }
188 Minimizer &minimizer;
191 minimizer_helper1 &operator=(
const minimizer_helper1 &) =
delete;
194template <
typename Volume2,
typename Object2,
typename Object1,
typename Minimizer>
195struct minimizer_helper2 {
196 using Scalar =
typename Minimizer::Scalar;
197 minimizer_helper2(
const Object1 &inStored, Minimizer &m) : stored(inStored), minimizer(m) {}
198 Scalar minimumOnVolume(
const Volume2 &vol) {
return minimizer.minimumOnObjectVolume(stored, vol); }
199 Scalar minimumOnObject(
const Object2 &obj) {
return minimizer.minimumOnObjectObject(stored, obj); }
201 Minimizer &minimizer;
204 minimizer_helper2 &operator=(
const minimizer_helper2 &) =
delete;
215template <
typename BVH,
typename Minimizer>
216typename Minimizer::Scalar
BVMinimize(
const BVH &tree, Minimizer &minimizer) {
217 return internal::minimize_helper(tree, minimizer, tree.getRootIndex(),
218 (std::numeric_limits<typename Minimizer::Scalar>::max)());
230template <
typename BVH1,
typename BVH2,
typename Minimizer>
231typename Minimizer::Scalar
BVMinimize(
const BVH1 &tree1,
const BVH2 &tree2, Minimizer &minimizer) {
232 using Scalar =
typename Minimizer::Scalar;
233 using Index1 =
typename BVH1::Index;
234 using Index2 =
typename BVH2::Index;
236 internal::minimizer_helper1<typename BVH1::Volume, typename BVH1::Object, typename BVH2::Object, Minimizer>;
238 internal::minimizer_helper2<typename BVH2::Volume, typename BVH2::Object, typename BVH1::Object, Minimizer>;
239 using QueueElement = std::pair<Scalar, std::pair<Index1, Index2> >;
240 using VolIter1 =
typename BVH1::VolumeIterator;
241 using ObjIter1 =
typename BVH1::ObjectIterator;
242 using VolIter2 =
typename BVH2::VolumeIterator;
243 using ObjIter2 =
typename BVH2::ObjectIterator;
245 VolIter1 vBegin1 = VolIter1(), vEnd1 = VolIter1();
246 ObjIter1 oBegin1 = ObjIter1(), oEnd1 = ObjIter1();
247 VolIter2 vBegin2 = VolIter2(), vEnd2 = VolIter2(), vCur2 = VolIter2();
248 ObjIter2 oBegin2 = ObjIter2(), oEnd2 = ObjIter2(), oCur2 = ObjIter2();
249 std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> >
252 Scalar minimum = (std::numeric_limits<Scalar>::max)();
253 todo.push(std::make_pair(Scalar(), std::make_pair(tree1.getRootIndex(), tree2.getRootIndex())));
255 while (!todo.empty()) {
256 tree1.getChildren(todo.top().second.first, vBegin1, vEnd1, oBegin1, oEnd1);
257 tree2.getChildren(todo.top().second.second, vBegin2, vEnd2, oBegin2, oEnd2);
260 for (; oBegin1 != oEnd1; ++oBegin1) {
261 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
262 minimum = (std::min)(minimum, minimizer.minimumOnObjectObject(*oBegin1, *oCur2));
265 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
266 Helper2 helper(*oBegin1, minimizer);
267 minimum = (std::min)(minimum, internal::minimize_helper(tree2, helper, *vCur2, minimum));
271 for (; vBegin1 != vEnd1; ++vBegin1) {
272 const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
274 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
275 Helper1 helper(*oCur2, minimizer);
276 minimum = (std::min)(minimum, internal::minimize_helper(tree1, helper, *vBegin1, minimum));
279 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
280 Scalar val = minimizer.minimumOnVolumeVolume(vol1, tree2.getVolume(*vCur2));
281 if (val < minimum) todo.push(std::make_pair(val, std::make_pair(*vBegin1, *vCur2)));
Namespace containing all symbols from the Eigen library.
void BVIntersect(const BVH &tree, Intersector &intersector)
Definition BVAlgorithms.h:80
Minimizer::Scalar BVMinimize(const BVH &tree, Minimizer &minimizer)
Definition BVAlgorithms.h:216