BoundingBox.hpp

00001 /*------------------------------------------------------------------------*/
00002 /*                 Copyright 2010 Sandia Corporation.                     */
00003 /*  Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive   */
00004 /*  license for use of this work by or on behalf of the U.S. Government.  */
00005 /*  Export of this program may require a license from the                 */
00006 /*  United States Government.                                             */
00007 /*------------------------------------------------------------------------*/
00008 
00009 #ifndef stk_search_BoundingBox_hpp
00010 #define stk_search_BoundingBox_hpp
00011 
00012 #include <iosfwd>
00013 #include <stk_search/BoundingBoxCompare.hpp>
00014 #include <cmath>
00015 #include <stdint.h>
00016 
00017 namespace stk {
00018 namespace search {
00019 namespace box {
00020 
00021 template <class K, class T, int Dim>
00022   struct PointBoundingBox;
00023 
00024 template <class K, class T, int Dim>
00025   struct SphereBoundingBox;
00026 
00027 template <class K, class T, int Dim>
00028   struct AxisAlignedBoundingBox;
00029 
00030 template <class K = uint64_t, class T = float, int Dim = 3>
00031 struct PointBoundingBox
00032 {
00033   typedef K Key;
00034   typedef T Data;
00035 
00036   const static int DIMENSION = Dim;
00037 
00038   inline Data lower(int axis) const { return center[axis]; }
00039   inline Data middle(int axis) const { return center[axis]; }
00040   inline Data upper(int axis) const { return center[axis]; }
00041 
00042   inline Data length(int /* axis */ = 0) const { return 0; }
00043 
00044   PointBoundingBox()
00045     : center(), key()
00046   {}
00047 
00048   PointBoundingBox(const Data center_[], const Key & key_)
00049     : center(), key(key_)
00050   {
00051     set_center(center_);
00052   }
00053 
00054   PointBoundingBox(const PointBoundingBox &point_)
00055     : center(), key(point_.key)
00056   {
00057     set_center(point_.center);
00058   }
00059 
00060   PointBoundingBox & operator = ( const PointBoundingBox &point_) {
00061     if (this != &point_) {
00062       set_center(point_.center);
00063       key = point_.key;
00064     }
00065     return *this;
00066   }
00067 
00068   inline
00069   void set_center(const Data center_[]) {
00070     for (int i = 0; i<DIMENSION; ++i)
00071       center[i] = center_[i];
00072   }
00073 
00074   bool intersect( const PointBoundingBox<K,T,Dim> & point_) const {
00075     Data dist = 0;
00076     for (int i=0; i<DIMENSION; ++i) {
00077       dist += std::abs(middle(i) - point_.middle(i));
00078     }
00079     return dist == 0;
00080   }
00081 
00082   bool intersect( const SphereBoundingBox<K,T,Dim> & sphere_) const {
00083     Data tmp = 0;
00084     Data dist = 0;
00085     for (int i=0; i<DIMENSION; ++i) {
00086       tmp = sphere_.middle(i) - middle(i);
00087       dist += tmp * tmp;
00088     }
00089     return dist < sphere_.radius * sphere_.radius;
00090   }
00091 
00092   bool intersect( const AxisAlignedBoundingBox<K,T,Dim> & box_) const {
00093     for (int i=0; i<DIMENSION; ++i) {
00094       if( middle(i) < box_.lower(i) || middle(i) > box_.upper(i)) {
00095         return false;
00096       }
00097     }
00098     return true;
00099   }
00100 
00101   Data center[DIMENSION];
00102   Key  key;
00103 
00104 };
00105 
00106 template <class K = uint64_t, class T = float, int Dim = 3>
00107 struct SphereBoundingBox
00108 {
00109   typedef K Key;
00110   typedef T Data;
00111 
00112   const static int DIMENSION = Dim;
00113 
00114   inline Data lower(int axis) const { return center[axis] - radius; }
00115   inline Data middle(int axis) const { return center[axis]; }
00116   inline Data upper(int axis) const { return center[axis] + radius; }
00117 
00118   inline Data length(int /* axis */ = 0) const { return 2*radius; }
00119 
00120   inline void expand(const Data delta) { radius += delta; }
00121 
00122 
00123   SphereBoundingBox()
00124     : center(), radius(0), key()
00125   {}
00126 
00127   SphereBoundingBox(const SphereBoundingBox &sphere_)
00128     : center(), radius(sphere_.radius), key(sphere_.key)
00129   {
00130     set_center(sphere_.center);
00131   }
00132 
00133   SphereBoundingBox & operator = ( const SphereBoundingBox &sphere_) {
00134     if (this != &sphere_) {
00135       set_center(sphere_.center);
00136       radius = sphere_.radius;
00137       key = sphere_.key;
00138     }
00139     return *this;
00140   }
00141 
00142   SphereBoundingBox( const PointBoundingBox<K,T,Dim> & point_ )
00143     : center(), radius(0), key(point_.key)
00144   {
00145     set_center(point_.center);
00146   }
00147 
00148   SphereBoundingBox( const AxisAlignedBoundingBox<K,T,Dim> & box_)
00149     : center(), radius(0), key(box_.key)
00150   {
00151     Data dist;
00152     Data radius_squared = 0;
00153     for (int i=0; i<Dim; ++i) {
00154       center[i] = box_.middle(i);
00155       dist = box_.upper(i) - center[i];
00156       radius_squared += dist * dist;
00157     }
00158     radius = std::sqrt(radius_squared);
00159   }
00160 
00161   SphereBoundingBox(const Data center_[], const Data radius_, const Key & key_)
00162     : center(), radius(radius_), key(key_)
00163   {
00164     set_center(center_);
00165   }
00166 
00167   inline
00168   void set_center(const Data center_[]) {
00169     for (int i = 0; i<DIMENSION; ++i)
00170       center[i] = center_[i];
00171   }
00172 
00173   inline
00174   void set_radius(const Data radius_) {
00175     radius = radius_;
00176   }
00177 
00178   inline
00179   bool intersect( const PointBoundingBox<K,T,Dim> & point_) const {
00180     return point_.intersect(*this);
00181   }
00182 
00183   bool intersect( const SphereBoundingBox<K,T,Dim> & sphere_) const {
00184     Data tmp = 0;
00185     Data dist = 0;
00186     for (int i=0; i<DIMENSION; ++i) {
00187       tmp = middle(i) - sphere_.middle(i);
00188       dist += tmp * tmp;
00189     }
00190     Data radius_sum = radius + sphere_.radius;
00191     return dist < radius_sum * radius_sum;
00192   }
00193 
00194   bool intersect( const AxisAlignedBoundingBox<K,T,Dim> & box_) const {
00195     Data tmp = 0;
00196     Data dist = 0;
00197     for (int i=0; i<DIMENSION; ++i) {
00198       if (middle(i) < box_.lower(i)) {
00199         tmp = middle(i) - box_.lower(i);
00200         dist += tmp*tmp;
00201       }
00202       else if (middle(i) > box_.upper(i)) {
00203         tmp = middle(i) - box_.upper(i);
00204         dist += tmp*tmp;
00205       }
00206     }
00207 
00208     return dist <= radius*radius;;
00209   }
00210   Data center[DIMENSION];
00211   Data radius;
00212   Key  key;
00213 
00214 };
00215 
00216 
00217 template <class K = uint64_t, class T = float, int Dim = 3>
00218 struct AxisAlignedBoundingBox
00219 {
00220   typedef K Key;
00221   typedef T Data;
00222 
00223   const static int DIMENSION = Dim;
00224 
00225   inline Data lower(int axis)  const { return box[axis]; }
00226   inline Data middle(int axis) const { return lower(axis) + length(axis)/2; }
00227   inline Data upper(int axis)  const { return box[axis+DIMENSION]; }
00228 
00229   inline Data length(int axis) const { return upper(axis) - lower(axis); }
00230 
00231   inline void expand(const Data delta) {
00232     for (int i=0; i<DIMENSION; ++i) {
00233       box[i] -= delta;
00234       box[i+DIMENSION] += delta;
00235     }
00236   }
00237 
00238   AxisAlignedBoundingBox()
00239     : box(), key()
00240   {}
00241 
00242   AxisAlignedBoundingBox(const Data box_[], const Key & key_)
00243     : box(), key(key_)
00244   {
00245     set_box(box_);
00246   }
00247 
00248   AxisAlignedBoundingBox(const AxisAlignedBoundingBox &box_)
00249     : box(), key(box_.key)
00250   {
00251     set_box(box_.box);
00252   }
00253 
00254   AxisAlignedBoundingBox & operator = ( const AxisAlignedBoundingBox &box_) {
00255     if (this != &box_) {
00256       set_box(box_.box);
00257       key = box_.key;
00258     }
00259     return *this;
00260   }
00261 
00262   AxisAlignedBoundingBox( const PointBoundingBox<K,T,Dim> & point_)
00263     : box(), key(point_.key)
00264   {
00265     for (int i=0; i<Dim; ++i) {
00266       box[i] = point_.lower(i);
00267       box[i+Dim] = point_.upper(i);
00268     }
00269   }
00270 
00271   AxisAlignedBoundingBox( const SphereBoundingBox<K,T,Dim> & sphere_)
00272     : box(), key(sphere_.key)
00273   {
00274     for (int i=0; i<Dim; ++i) {
00275       box[i] = sphere_.lower(i);
00276       box[i+Dim] = sphere_.upper(i);
00277     }
00278   }
00279 
00280   inline
00281   void set_box(const Data box_[]) {
00282     for (int i = 0; i<2*DIMENSION; ++i)
00283       box[i] = box_[i];
00284   }
00285 
00286   inline
00287   bool intersect( const PointBoundingBox<K,T,Dim> & point_) const {
00288     return point_.intersect(*this);
00289   }
00290 
00291   inline
00292   bool intersect( const SphereBoundingBox<K,T,Dim> & sphere_) const {
00293     return sphere_.intersect(*this);
00294   }
00295 
00296   bool intersect( const AxisAlignedBoundingBox<K,T,Dim> & box_) const {
00297     for (int i=0; i<DIMENSION; ++i) {
00298       if( upper(i) < box_.lower(i) || lower(i) > box_.upper(i)) return false;
00299     }
00300     return true;
00301   }
00302 
00303   Data box[2*DIMENSION];
00304   Key  key;
00305 
00306 };
00307 
00308 
00309 
00310 } // namespace box
00311 } // namespace search
00312 } // namespace stk
00313 
00314 #endif // stk_search_BoundingBox_hpp

Generated on Tue Jul 13 09:27:31 2010 for Sierra Toolkit by  doxygen 1.4.7