source/geometry/boundingbox.h

   1 #ifndef MSP_GEOMETRY_BOUNDINGBOX_H_
   2 #define MSP_GEOMETRY_BOUNDINGBOX_H_
   3
   4 #include <algorithm>
   5 #include <stdexcept>
   6 #include <msp/linal/vector.h>
   7
   8 namespace Msp {
   9 namespace Geometry {
  10
  11 template<typename T, unsigned D>
  12 class BoundingBox
  13 {
  14 private:
  15         LinAl::Vector<T, D> min_pt;
  16         LinAl::Vector<T, D> max_pt;
  17         bool empty;
  18         bool negated;
  19
  20 public:
  21         BoundingBox();
  22         BoundingBox(const LinAl::Vector<T, D> &, const LinAl::Vector<T, D> &);
  23
  24         static BoundingBox negate(const BoundingBox &);
  25
  26         const LinAl::Vector<T, D> &get_minimum_point() const { return min_pt; }
  27         T get_minimum_coordinate(unsigned i) const { return min_pt[i]; }
  28         const LinAl::Vector<T, D> &get_maximum_point() const { return max_pt; }
  29         T get_maximum_coordinate(unsigned i) const { return max_pt[i]; }
  30         bool is_empty() const { return empty; }
  31         bool is_negated() const { return negated; }
  32 };
  33
  34 template<typename T, unsigned D>
  35 inline BoundingBox<T, D>::BoundingBox():
  36         empty(true),
  37         negated(false)
  38 { }
  39
  40 template<typename T, unsigned D>
  41 inline BoundingBox<T, D>::BoundingBox(const LinAl::Vector<T, D> &n, const LinAl::Vector<T, D> &x):
  42         min_pt(n),
  43         max_pt(x),
  44         empty(false),
  45         negated(false)
  46 {
  47         for(unsigned i=0; i<D; ++i)
  48                 if(min_pt[i]>max_pt[i])
  49                         throw std::invalid_argument("BoundingBox::BoundingBox");
  50 }
  51
  52 template<typename T, unsigned D>
  53 inline BoundingBox<T, D> BoundingBox<T, D>::negate(const BoundingBox<T, D> &bb)
  54 {
  55         BoundingBox<T, D> result = bb;
  56         result.negated = !bb.negated;
  57         return result;
  58 }
  59
  60 template<typename T, unsigned D>
  61 inline BoundingBox<T, D> operator&(const BoundingBox<T, D> &bb1, const BoundingBox<T, D> &bb2)
  62 {
  63         if(bb1.is_empty() || bb2.is_empty())
  64                 return BoundingBox<T, D>();
  65
  66         if(bb1.is_negated())
  67         {
  68                 if(bb2.is_negated())
  69                         return ~((~bb1)|(~bb2));
  70                 else
  71                         return bb2&bb1;
  72         }
  73
  74         LinAl::Vector<T, D> result_min;
  75         LinAl::Vector<T, D> result_max;
  76
  77         if(bb2.is_negated())
  78         {
  79                 // This is effectively subtraction of (non-negated) bb2 from bb1
  80                 int uncovered_axis = -1;
  81                 for(unsigned i=0; i<D; ++i)
  82                         if(bb1.get_minimum_coordinate(i)<bb2.get_minimum_coordinate(i) || bb1.get_maximum_coordinate(i)>bb2.get_maximum_coordinate(i))
  83                         {
  84                                 if(uncovered_axis!=-1)
  85                                         return bb1;
  86                                 uncovered_axis = i;
  87                         }
  88
  89                 if(uncovered_axis==-1)
  90                         return BoundingBox<T, D>();
  91
  92                 result_min = bb1.get_minimum_point();
  93                 result_max = bb1.get_maximum_point();
  94                 if(bb2.get_minimum_coordinate(uncovered_axis)<bb1.get_minimum_coordinate(uncovered_axis))
  95                         result_min[uncovered_axis] = bb2.get_maximum_coordinate(uncovered_axis);
  96                 else
  97                         result_max[uncovered_axis] = bb2.get_minimum_coordinate(uncovered_axis);
  98         }
  99         else
 100         {
 101                 for(unsigned i=0; i<D; ++i)
 102                 {
 103                         result_min[i] = std::max(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
 104                         result_max[i] = std::min(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
 105                         if(result_min[i]>result_max[i])
 106                                 return BoundingBox<T, D>();
 107                 }
 108         }
 109
 110         return BoundingBox<T, D>(result_min, result_max);
 111 }
 112
 113 template<typename T, unsigned D>
 114 inline BoundingBox<T, D> operator|(const BoundingBox<T, D> &bb1, const BoundingBox<T, D> &bb2)
 115 {
 116         if(bb1.is_empty())
 117                 return bb2;
 118         if(bb2.is_empty())
 119                 return bb1;
 120
 121         if(bb1.is_negated())
 122                 return ~((~bb1)&(~bb2));
 123         else if(bb2.is_negated())
 124                 return ~((~bb2)&(~bb1));
 125
 126         LinAl::Vector<T, D> result_min;
 127         LinAl::Vector<T, D> result_max;
 128         for(unsigned i=0; i<D; ++i)
 129         {
 130                 result_min[i] = std::min(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
 131                 result_max[i] = std::max(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
 132         }
 133
 134         return BoundingBox<T, D>(result_min, result_max);
 135 }
 136
 137 template<typename T, unsigned D>
 138 inline BoundingBox<T, D> operator~(const BoundingBox<T, D> &bb)
 139 {
 140         return BoundingBox<T, D>::negate(bb);
 141 }
 142
 143 } // namespace Geometry
 144 } // namespace Msp
 145
 146 #endif