source/geometry/compositeshape.h

   1 #ifndef MSP_GEOMETRY_COMPOSITESHAPE_H_
   2 #define MSP_GEOMETRY_COMPOSITESHAPE_H_
   3
   4 #include <algorithm>
   5 #include <stdexcept>
   6 #include <vector>
   7 #include "shape.h"
   8
   9 namespace Msp {
  10 namespace Geometry {
  11
  12 /**
  13 Common operations for shapes composed of other shapes.
  14 */
  15 template<typename T, unsigned D, typename O>
  16 class CompositeShape: public Shape<T, D>
  17 {
  18 protected:
  19         typedef O Ops;
  20         typedef std::vector<Shape<T, D> *> ShapeArray;
  21
  22         ShapeArray shapes;
  23         unsigned max_isect;
  24
  25         CompositeShape() { }
  26         CompositeShape(const Shape<T, D> &, const Shape<T, D> &);
  27         template<typename Iter>
  28         void init_from_iter_range(const Iter &, const Iter &);
  29 private:
  30         void init();
  31 protected:
  32         CompositeShape(const CompositeShape &);
  33         CompositeShape &operator=(const CompositeShape &);
  34 public:
  35         virtual ~CompositeShape();
  36
  37         virtual BoundingBox<T, D> get_axis_aligned_bounding_box(unsigned = 0) const;
  38         virtual bool contains(const LinAl::Vector<T, D> &) const;
  39         virtual unsigned get_max_ray_intersections() const { return max_isect; }
  40         virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
  41         virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
  42 };
  43
  44 template<typename T, unsigned D, typename O>
  45 inline CompositeShape<T, D, O>::CompositeShape(const Shape<T, D> &s1, const Shape<T, D> &s2)
  46 {
  47         shapes.reserve(2);
  48         shapes.push_back(s1.clone());
  49         shapes.push_back(s2.clone());
  50         init();
  51 }
  52
  53 template<typename T, unsigned D, typename O>
  54 template<typename Iter>
  55 inline void CompositeShape<T, D, O>::init_from_iter_range(const Iter &begin, const Iter &end)
  56 {
  57         if(begin==end)
  58                 throw std::invalid_argument("CompositeShape::init_from_iter_range");
  59
  60         for(Iter i=begin; i!=end; ++i)
  61                 shapes.push_back((*i)->clone());
  62         init();
  63 }
  64
  65 template<typename T, unsigned D, typename O>
  66 inline void CompositeShape<T, D, O>::init()
  67 {
  68         max_isect = 0;
  69         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
  70                 max_isect += (*i)->get_max_ray_intersections();
  71 }
  72
  73 template<typename T, unsigned D, typename O>
  74 inline CompositeShape<T, D, O>::CompositeShape(const CompositeShape<T, D, O> &other):
  75         shapes(other.shapes),
  76         max_isect(other.max_isect)
  77 {
  78         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  79                 *i = (*i)->clone();
  80 }
  81
  82 template<typename T, unsigned D, typename O>
  83 inline CompositeShape<T, D, O> &CompositeShape<T, D, O>::operator=(const CompositeShape<T, D, O> &other)
  84 {
  85         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  86                 delete *i;
  87
  88         shapes = other.shapes;
  89         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  90                 *i = (*i)->clone();
  91
  92         max_isect = other.max_isect;
  93 }
  94
  95 template<typename T, unsigned D, typename O>
  96 inline CompositeShape<T, D, O>::~CompositeShape()
  97 {
  98         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  99                 delete *i;
 100 }
 101
 102 template<typename T, unsigned D, typename O>
 103 inline BoundingBox<T, D> CompositeShape<T, D, O>::get_axis_aligned_bounding_box(unsigned detail) const
 104 {
 105         if(detail)
 106                 return this->bisect_axis_aligned_bounding_box(detail);
 107
 108         BoundingBox<T, D> aabb;
 109         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 110         {
 111                 if(i==shapes.begin())
 112                         aabb = (*i)->get_axis_aligned_bounding_box();
 113                 else
 114                         aabb = Ops::combine_aabb(aabb, (*i)->get_axis_aligned_bounding_box());
 115         }
 116         return aabb;
 117 }
 118
 119 template<typename T, unsigned D, typename O>
 120 inline bool CompositeShape<T, D, O>::contains(const LinAl::Vector<T, D> &point) const
 121 {
 122         bool inside = false;
 123         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 124         {
 125                 inside = (*i)->contains(point);
 126                 if(Ops::shortcircuit(inside))
 127                         return inside;
 128         }
 129         return inside;
 130 }
 131
 132 template<typename T, unsigned D, typename O>
 133 inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
 134 {
 135         SurfacePoint<T, D> *buffer = points;
 136         unsigned buf_size = size;
 137         if(!points && !Ops::shortcircuit(true))
 138         {
 139                 buffer = new SurfacePoint<T, D>[max_isect];
 140                 buf_size = max_isect;
 141         }
 142
 143         int start_nesting = 0;
 144         unsigned n = 0;
 145         for(typename ShapeArray::const_iterator i=shapes.begin(); (n<buf_size && i!=shapes.end()); ++i)
 146         {
 147                 unsigned base = n;
 148                 unsigned count = (*i)->get_intersections(ray, buffer+base, buf_size-base);
 149                 bool start_inside = (*i)->contains(ray.get_start());
 150
 151                 if(!count && !start_inside)
 152                 {
 153                         if(Ops::shortcircuit(false))
 154                                 return 0;
 155                         continue;
 156                 }
 157
 158                 start_nesting += start_inside;
 159
 160                 if(!base)
 161                 {
 162                         n = count;
 163                         continue;
 164                 }
 165
 166                 sort_points(buffer, base+count);
 167
 168                 int nesting = start_nesting;
 169                 unsigned k = 0;
 170                 for(unsigned j=0; j<base+count; ++j)
 171                 {
 172                         if(Ops::shortcircuit(nesting+buffer[j].entry<2))
 173                         {
 174                                 if(j!=k)
 175                                         buffer[k] = buffer[j];
 176                                 ++k;
 177                         }
 178
 179                         nesting += buffer[j].entry*2-1;
 180                 }
 181
 182                 if(!k && Ops::shortcircuit(false))
 183                         return 0;
 184
 185                 n = k;
 186
 187                 if(i!=shapes.begin())
 188                         start_nesting = (start_nesting>!Ops::shortcircuit(true));
 189         }
 190
 191         if(buffer!=points)
 192                 delete[] buffer;
 193
 194         return n;
 195 }
 196
 197 template<typename T, unsigned D, typename O>
 198 inline Coverage CompositeShape<T, D, O>::get_coverage(const BoundingBox<T, D> &bbox) const
 199 {
 200         Coverage coverage = NO_COVERAGE;
 201         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 202         {
 203                 Coverage c = (*i)->get_coverage(bbox);
 204                 if(i==shapes.begin() || Ops::shortcircuit(c>coverage))
 205                         coverage = c;
 206
 207                 if(coverage!=PARTIAL_COVERAGE && Ops::shortcircuit(coverage==FULL_COVERAGE))
 208                         break;
 209         }
 210
 211         return coverage;
 212 }
 213
 214 } // namespace Geometry
 215 } // namespace Msp
 216
 217 #endif