Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
BVAlgorithms.h
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// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_BVALGORITHMS_H
12#define EIGEN_BVALGORITHMS_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
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;
27
28 VolIter vBegin = VolIter(), vEnd = VolIter();
29 ObjIter oBegin = ObjIter(), oEnd = ObjIter();
30
31 std::vector<Index> todo(1, root);
32
33 while (!todo.empty()) {
34 tree.getChildren(todo.back(), vBegin, vEnd, oBegin, oEnd);
35 todo.pop_back();
36
37 for (; vBegin != vEnd; ++vBegin) // go through child volumes
38 if (intersector.intersectVolume(tree.getVolume(*vBegin))) todo.push_back(*vBegin);
39
40 for (; oBegin != oEnd; ++oBegin) // go through child objects
41 if (intersector.intersectObject(*oBegin)) return true; // intersector said to stop query
42 }
43 return false;
44}
45#endif // not EIGEN_PARSED_BY_DOXYGEN
46
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); }
52 Object2 stored;
53 Intersector &intersector;
54
55 private:
56 intersector_helper1 &operator=(const intersector_helper1 &) = delete;
57};
58
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); }
64 Object1 stored;
65 Intersector &intersector;
66
67 private:
68 intersector_helper2 &operator=(const intersector_helper2 &) = delete;
69};
70
71} // end namespace internal
72
79template <typename BVH, typename Intersector>
80void BVIntersect(const BVH &tree, Intersector &intersector) {
81 internal::intersect_helper(tree, intersector, tree.getRootIndex());
82}
83
92template <typename BVH1, typename BVH2, typename Intersector>
93void BVIntersect(const BVH1 &tree1, const BVH2 &tree2,
94 Intersector &intersector) // TODO: tandem descent when it makes sense
95{
96 using Index1 = typename BVH1::Index;
97 using Index2 = typename BVH2::Index;
98 using Helper1 =
99 internal::intersector_helper1<typename BVH1::Volume, typename BVH1::Object, typename BVH2::Object, Intersector>;
100 using Helper2 =
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;
106
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();
111
112 std::vector<std::pair<Index1, Index2> > todo(1, std::make_pair(tree1.getRootIndex(), tree2.getRootIndex()));
113
114 while (!todo.empty()) {
115 tree1.getChildren(todo.back().first, vBegin1, vEnd1, oBegin1, oEnd1);
116 tree2.getChildren(todo.back().second, vBegin2, vEnd2, oBegin2, oEnd2);
117 todo.pop_back();
118
119 for (; vBegin1 != vEnd1; ++vBegin1) { // go through child volumes of first tree
120 const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
121 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) { // go through child volumes of second tree
122 if (intersector.intersectVolumeVolume(vol1, tree2.getVolume(*vCur2)))
123 todo.push_back(std::make_pair(*vBegin1, *vCur2));
124 }
125
126 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) { // go through child objects of second tree
127 Helper1 helper(*oCur2, intersector);
128 if (internal::intersect_helper(tree1, helper, *vBegin1)) return; // intersector said to stop query
129 }
130 }
131
132 for (; oBegin1 != oEnd1; ++oBegin1) { // go through child objects of first tree
133 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) { // go through child volumes of second tree
134 Helper2 helper(*oBegin1, intersector);
135 if (internal::intersect_helper(tree2, helper, *vCur2)) return; // intersector said to stop query
136 }
137
138 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) { // go through child objects of second tree
139 if (intersector.intersectObjectObject(*oBegin1, *oCur2)) return; // intersector said to stop query
140 }
141 }
142 }
143}
144
145namespace internal {
146
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>; // first element is priority
154 using VolIter = typename BVH::VolumeIterator;
155 using ObjIter = typename BVH::ObjectIterator;
156
157 VolIter vBegin = VolIter(), vEnd = VolIter();
158 ObjIter oBegin = ObjIter(), oEnd = ObjIter();
159 std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> >
160 todo; // smallest is at the top
161
162 todo.push(std::make_pair(Scalar(), root));
163
164 while (!todo.empty()) {
165 tree.getChildren(todo.top().second, vBegin, vEnd, oBegin, oEnd);
166 todo.pop();
167
168 for (; oBegin != oEnd; ++oBegin) // go through child objects
169 minimum = (std::min)(minimum, minimizer.minimumOnObject(*oBegin));
170
171 for (; vBegin != vEnd; ++vBegin) { // go through child volumes
172 Scalar val = minimizer.minimumOnVolume(tree.getVolume(*vBegin));
173 if (val < minimum) todo.push(std::make_pair(val, *vBegin));
174 }
175 }
176
177 return minimum;
178}
179#endif // not EIGEN_PARSED_BY_DOXYGEN
180
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); }
187 Object2 stored;
188 Minimizer &minimizer;
189
190 private:
191 minimizer_helper1 &operator=(const minimizer_helper1 &) = delete;
192};
193
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); }
200 Object1 stored;
201 Minimizer &minimizer;
202
203 private:
204 minimizer_helper2 &operator=(const minimizer_helper2 &) = delete;
205};
206
207} // end namespace internal
208
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)());
219}
220
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;
235 using Helper1 =
236 internal::minimizer_helper1<typename BVH1::Volume, typename BVH1::Object, typename BVH2::Object, Minimizer>;
237 using Helper2 =
238 internal::minimizer_helper2<typename BVH2::Volume, typename BVH2::Object, typename BVH1::Object, Minimizer>;
239 using QueueElement = std::pair<Scalar, std::pair<Index1, Index2> >; // first element is priority
240 using VolIter1 = typename BVH1::VolumeIterator;
241 using ObjIter1 = typename BVH1::ObjectIterator;
242 using VolIter2 = typename BVH2::VolumeIterator;
243 using ObjIter2 = typename BVH2::ObjectIterator;
244
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> >
250 todo; // smallest is at the top
251
252 Scalar minimum = (std::numeric_limits<Scalar>::max)();
253 todo.push(std::make_pair(Scalar(), std::make_pair(tree1.getRootIndex(), tree2.getRootIndex())));
254
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);
258 todo.pop();
259
260 for (; oBegin1 != oEnd1; ++oBegin1) { // go through child objects of first tree
261 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) { // go through child objects of second tree
262 minimum = (std::min)(minimum, minimizer.minimumOnObjectObject(*oBegin1, *oCur2));
263 }
264
265 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) { // go through child volumes of second tree
266 Helper2 helper(*oBegin1, minimizer);
267 minimum = (std::min)(minimum, internal::minimize_helper(tree2, helper, *vCur2, minimum));
268 }
269 }
270
271 for (; vBegin1 != vEnd1; ++vBegin1) { // go through child volumes of first tree
272 const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
273
274 for (oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) { // go through child objects of second tree
275 Helper1 helper(*oCur2, minimizer);
276 minimum = (std::min)(minimum, internal::minimize_helper(tree1, helper, *vBegin1, minimum));
277 }
278
279 for (vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) { // go through child volumes of second tree
280 Scalar val = minimizer.minimumOnVolumeVolume(vol1, tree2.getVolume(*vCur2));
281 if (val < minimum) todo.push(std::make_pair(val, std::make_pair(*vBegin1, *vCur2)));
282 }
283 }
284 }
285 return minimum;
286}
287
288} // end namespace Eigen
289
290#endif // EIGEN_BVALGORITHMS_H
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