00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #ifndef EIGEN_BVALGORITHMS_H
00026 #define EIGEN_BVALGORITHMS_H
00027
00028 namespace internal {
00029
00030 #ifndef EIGEN_PARSED_BY_DOXYGEN
00031 template<typename BVH, typename Intersector>
00032 bool intersect_helper(const BVH &tree, Intersector &intersector, typename BVH::Index root)
00033 {
00034 typedef typename BVH::Index Index;
00035 typedef typename BVH::VolumeIterator VolIter;
00036 typedef typename BVH::ObjectIterator ObjIter;
00037
00038 VolIter vBegin = VolIter(), vEnd = VolIter();
00039 ObjIter oBegin = ObjIter(), oEnd = ObjIter();
00040
00041 std::vector<Index> todo(1, root);
00042
00043 while(!todo.empty()) {
00044 tree.getChildren(todo.back(), vBegin, vEnd, oBegin, oEnd);
00045 todo.pop_back();
00046
00047 for(; vBegin != vEnd; ++vBegin)
00048 if(intersector.intersectVolume(tree.getVolume(*vBegin)))
00049 todo.push_back(*vBegin);
00050
00051 for(; oBegin != oEnd; ++oBegin)
00052 if(intersector.intersectObject(*oBegin))
00053 return true;
00054 }
00055 return false;
00056 }
00057 #endif //not EIGEN_PARSED_BY_DOXYGEN
00058
00059 template<typename Volume1, typename Object1, typename Object2, typename Intersector>
00060 struct intersector_helper1
00061 {
00062 intersector_helper1(const Object2 &inStored, Intersector &in) : stored(inStored), intersector(in) {}
00063 bool intersectVolume(const Volume1 &vol) { return intersector.intersectVolumeObject(vol, stored); }
00064 bool intersectObject(const Object1 &obj) { return intersector.intersectObjectObject(obj, stored); }
00065 Object2 stored;
00066 Intersector &intersector;
00067 private:
00068 intersector_helper1& operator=(const intersector_helper1&);
00069 };
00070
00071 template<typename Volume2, typename Object2, typename Object1, typename Intersector>
00072 struct intersector_helper2
00073 {
00074 intersector_helper2(const Object1 &inStored, Intersector &in) : stored(inStored), intersector(in) {}
00075 bool intersectVolume(const Volume2 &vol) { return intersector.intersectObjectVolume(stored, vol); }
00076 bool intersectObject(const Object2 &obj) { return intersector.intersectObjectObject(stored, obj); }
00077 Object1 stored;
00078 Intersector &intersector;
00079 private:
00080 intersector_helper2& operator=(const intersector_helper2&);
00081 };
00082
00083 }
00084
00091 template<typename BVH, typename Intersector>
00092 void BVIntersect(const BVH &tree, Intersector &intersector)
00093 {
00094 internal::intersect_helper(tree, intersector, tree.getRootIndex());
00095 }
00096
00105 template<typename BVH1, typename BVH2, typename Intersector>
00106 void BVIntersect(const BVH1 &tree1, const BVH2 &tree2, Intersector &intersector)
00107 {
00108 typedef typename BVH1::Index Index1;
00109 typedef typename BVH2::Index Index2;
00110 typedef internal::intersector_helper1<typename BVH1::Volume, typename BVH1::Object, typename BVH2::Object, Intersector> Helper1;
00111 typedef internal::intersector_helper2<typename BVH2::Volume, typename BVH2::Object, typename BVH1::Object, Intersector> Helper2;
00112 typedef typename BVH1::VolumeIterator VolIter1;
00113 typedef typename BVH1::ObjectIterator ObjIter1;
00114 typedef typename BVH2::VolumeIterator VolIter2;
00115 typedef typename BVH2::ObjectIterator ObjIter2;
00116
00117 VolIter1 vBegin1 = VolIter1(), vEnd1 = VolIter1();
00118 ObjIter1 oBegin1 = ObjIter1(), oEnd1 = ObjIter1();
00119 VolIter2 vBegin2 = VolIter2(), vEnd2 = VolIter2(), vCur2 = VolIter2();
00120 ObjIter2 oBegin2 = ObjIter2(), oEnd2 = ObjIter2(), oCur2 = ObjIter2();
00121
00122 std::vector<std::pair<Index1, Index2> > todo(1, std::make_pair(tree1.getRootIndex(), tree2.getRootIndex()));
00123
00124 while(!todo.empty()) {
00125 tree1.getChildren(todo.back().first, vBegin1, vEnd1, oBegin1, oEnd1);
00126 tree2.getChildren(todo.back().second, vBegin2, vEnd2, oBegin2, oEnd2);
00127 todo.pop_back();
00128
00129 for(; vBegin1 != vEnd1; ++vBegin1) {
00130 const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
00131 for(vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
00132 if(intersector.intersectVolumeVolume(vol1, tree2.getVolume(*vCur2)))
00133 todo.push_back(std::make_pair(*vBegin1, *vCur2));
00134 }
00135
00136 for(oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
00137 Helper1 helper(*oCur2, intersector);
00138 if(internal::intersect_helper(tree1, helper, *vBegin1))
00139 return;
00140 }
00141 }
00142
00143 for(; oBegin1 != oEnd1; ++oBegin1) {
00144 for(vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
00145 Helper2 helper(*oBegin1, intersector);
00146 if(internal::intersect_helper(tree2, helper, *vCur2))
00147 return;
00148 }
00149
00150 for(oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
00151 if(intersector.intersectObjectObject(*oBegin1, *oCur2))
00152 return;
00153 }
00154 }
00155 }
00156 }
00157
00158 namespace internal {
00159
00160 #ifndef EIGEN_PARSED_BY_DOXYGEN
00161 template<typename BVH, typename Minimizer>
00162 typename Minimizer::Scalar minimize_helper(const BVH &tree, Minimizer &minimizer, typename BVH::Index root, typename Minimizer::Scalar minimum)
00163 {
00164 typedef typename Minimizer::Scalar Scalar;
00165 typedef typename BVH::Index Index;
00166 typedef std::pair<Scalar, Index> QueueElement;
00167 typedef typename BVH::VolumeIterator VolIter;
00168 typedef typename BVH::ObjectIterator ObjIter;
00169
00170 VolIter vBegin = VolIter(), vEnd = VolIter();
00171 ObjIter oBegin = ObjIter(), oEnd = ObjIter();
00172 std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> > todo;
00173
00174 todo.push(std::make_pair(Scalar(), root));
00175
00176 while(!todo.empty()) {
00177 tree.getChildren(todo.top().second, vBegin, vEnd, oBegin, oEnd);
00178 todo.pop();
00179
00180 for(; oBegin != oEnd; ++oBegin)
00181 minimum = (std::min)(minimum, minimizer.minimumOnObject(*oBegin));
00182
00183 for(; vBegin != vEnd; ++vBegin) {
00184 Scalar val = minimizer.minimumOnVolume(tree.getVolume(*vBegin));
00185 if(val < minimum)
00186 todo.push(std::make_pair(val, *vBegin));
00187 }
00188 }
00189
00190 return minimum;
00191 }
00192 #endif //not EIGEN_PARSED_BY_DOXYGEN
00193
00194
00195 template<typename Volume1, typename Object1, typename Object2, typename Minimizer>
00196 struct minimizer_helper1
00197 {
00198 typedef typename Minimizer::Scalar Scalar;
00199 minimizer_helper1(const Object2 &inStored, Minimizer &m) : stored(inStored), minimizer(m) {}
00200 Scalar minimumOnVolume(const Volume1 &vol) { return minimizer.minimumOnVolumeObject(vol, stored); }
00201 Scalar minimumOnObject(const Object1 &obj) { return minimizer.minimumOnObjectObject(obj, stored); }
00202 Object2 stored;
00203 Minimizer &minimizer;
00204 private:
00205 minimizer_helper1& operator=(const minimizer_helper1&) {}
00206 };
00207
00208 template<typename Volume2, typename Object2, typename Object1, typename Minimizer>
00209 struct minimizer_helper2
00210 {
00211 typedef typename Minimizer::Scalar Scalar;
00212 minimizer_helper2(const Object1 &inStored, Minimizer &m) : stored(inStored), minimizer(m) {}
00213 Scalar minimumOnVolume(const Volume2 &vol) { return minimizer.minimumOnObjectVolume(stored, vol); }
00214 Scalar minimumOnObject(const Object2 &obj) { return minimizer.minimumOnObjectObject(stored, obj); }
00215 Object1 stored;
00216 Minimizer &minimizer;
00217 private:
00218 minimizer_helper2& operator=(const minimizer_helper2&);
00219 };
00220
00221 }
00222
00231 template<typename BVH, typename Minimizer>
00232 typename Minimizer::Scalar BVMinimize(const BVH &tree, Minimizer &minimizer)
00233 {
00234 return internal::minimize_helper(tree, minimizer, tree.getRootIndex(), std::numeric_limits<typename Minimizer::Scalar>::max());
00235 }
00236
00247 template<typename BVH1, typename BVH2, typename Minimizer>
00248 typename Minimizer::Scalar BVMinimize(const BVH1 &tree1, const BVH2 &tree2, Minimizer &minimizer)
00249 {
00250 typedef typename Minimizer::Scalar Scalar;
00251 typedef typename BVH1::Index Index1;
00252 typedef typename BVH2::Index Index2;
00253 typedef internal::minimizer_helper1<typename BVH1::Volume, typename BVH1::Object, typename BVH2::Object, Minimizer> Helper1;
00254 typedef internal::minimizer_helper2<typename BVH2::Volume, typename BVH2::Object, typename BVH1::Object, Minimizer> Helper2;
00255 typedef std::pair<Scalar, std::pair<Index1, Index2> > QueueElement;
00256 typedef typename BVH1::VolumeIterator VolIter1;
00257 typedef typename BVH1::ObjectIterator ObjIter1;
00258 typedef typename BVH2::VolumeIterator VolIter2;
00259 typedef typename BVH2::ObjectIterator ObjIter2;
00260
00261 VolIter1 vBegin1 = VolIter1(), vEnd1 = VolIter1();
00262 ObjIter1 oBegin1 = ObjIter1(), oEnd1 = ObjIter1();
00263 VolIter2 vBegin2 = VolIter2(), vEnd2 = VolIter2(), vCur2 = VolIter2();
00264 ObjIter2 oBegin2 = ObjIter2(), oEnd2 = ObjIter2(), oCur2 = ObjIter2();
00265 std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> > todo;
00266
00267 Scalar minimum = std::numeric_limits<Scalar>::max();
00268 todo.push(std::make_pair(Scalar(), std::make_pair(tree1.getRootIndex(), tree2.getRootIndex())));
00269
00270 while(!todo.empty()) {
00271 tree1.getChildren(todo.top().second.first, vBegin1, vEnd1, oBegin1, oEnd1);
00272 tree2.getChildren(todo.top().second.second, vBegin2, vEnd2, oBegin2, oEnd2);
00273 todo.pop();
00274
00275 for(; oBegin1 != oEnd1; ++oBegin1) {
00276 for(oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
00277 minimum = (std::min)(minimum, minimizer.minimumOnObjectObject(*oBegin1, *oCur2));
00278 }
00279
00280 for(vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
00281 Helper2 helper(*oBegin1, minimizer);
00282 minimum = (std::min)(minimum, internal::minimize_helper(tree2, helper, *vCur2, minimum));
00283 }
00284 }
00285
00286 for(; vBegin1 != vEnd1; ++vBegin1) {
00287 const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
00288
00289 for(oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {
00290 Helper1 helper(*oCur2, minimizer);
00291 minimum = (std::min)(minimum, internal::minimize_helper(tree1, helper, *vBegin1, minimum));
00292 }
00293
00294 for(vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) {
00295 Scalar val = minimizer.minimumOnVolumeVolume(vol1, tree2.getVolume(*vCur2));
00296 if(val < minimum)
00297 todo.push(std::make_pair(val, std::make_pair(*vBegin1, *vCur2)));
00298 }
00299 }
00300 }
00301 return minimum;
00302 }
00303
00304 #endif // EIGEN_BVALGORITHMS_H