BVAlgorithms.h
Go to the documentation of this file.
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2009 Ilya Baran <ibaran@mit.edu>
00005 //
00006 // Eigen is free software; you can redistribute it and/or
00007 // modify it under the terms of the GNU Lesser General Public
00008 // License as published by the Free Software Foundation; either
00009 // version 3 of the License, or (at your option) any later version.
00010 //
00011 // Alternatively, you can redistribute it and/or
00012 // modify it under the terms of the GNU General Public License as
00013 // published by the Free Software Foundation; either version 2 of
00014 // the License, or (at your option) any later version.
00015 //
00016 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
00017 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00018 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
00019 // GNU General Public License for more details.
00020 //
00021 // You should have received a copy of the GNU Lesser General Public
00022 // License and a copy of the GNU General Public License along with
00023 // Eigen. If not, see <http://www.gnu.org/licenses/>.
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) //go through child volumes
00048       if(intersector.intersectVolume(tree.getVolume(*vBegin)))
00049         todo.push_back(*vBegin);
00050 
00051     for(; oBegin != oEnd; ++oBegin) //go through child objects
00052       if(intersector.intersectObject(*oBegin))
00053         return true; //intersector said to stop query
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 } // end namespace internal
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) //TODO: tandem descent when it makes sense
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) { //go through child volumes of first tree
00130       const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
00131       for(vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) { //go through child volumes of second tree
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) {//go through child objects of second tree
00137         Helper1 helper(*oCur2, intersector);
00138         if(internal::intersect_helper(tree1, helper, *vBegin1))
00139           return; //intersector said to stop query
00140       }
00141     }
00142 
00143     for(; oBegin1 != oEnd1; ++oBegin1) { //go through child objects of first tree
00144       for(vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) { //go through child volumes of second tree
00145         Helper2 helper(*oBegin1, intersector);
00146         if(internal::intersect_helper(tree2, helper, *vCur2))
00147           return; //intersector said to stop query
00148       }
00149 
00150       for(oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {//go through child objects of second tree
00151         if(intersector.intersectObjectObject(*oBegin1, *oCur2))
00152           return; //intersector said to stop query
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; //first element is priority
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; //smallest is at the top
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) //go through child objects
00181       minimum = (std::min)(minimum, minimizer.minimumOnObject(*oBegin));
00182 
00183     for(; vBegin != vEnd; ++vBegin) { //go through child volumes
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 } // end namespace internal
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; //first element is priority
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; //smallest is at the top
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) { //go through child objects of first tree
00276       for(oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {//go through child objects of second tree
00277         minimum = (std::min)(minimum, minimizer.minimumOnObjectObject(*oBegin1, *oCur2));
00278       }
00279 
00280       for(vCur2 = vBegin2; vCur2 != vEnd2; ++vCur2) { //go through child volumes of second tree
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) { //go through child volumes of first tree
00287       const typename BVH1::Volume &vol1 = tree1.getVolume(*vBegin1);
00288 
00289       for(oCur2 = oBegin2; oCur2 != oEnd2; ++oCur2) {//go through child objects of second tree
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) { //go through child volumes of second tree
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


libicr
Author(s): Robert Krug
autogenerated on Mon Jan 6 2014 11:32:31