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() 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() const
 104 {
 105         BoundingBox<T, D> aabb;
 106         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 107         {
 108                 if(i==shapes.begin())
 109                         aabb = (*i)->get_axis_aligned_bounding_box();
 110                 else
 111                         aabb = Ops::combine_aabb(aabb, (*i)->get_axis_aligned_bounding_box());
 112         }
 113         return aabb;
 114 }
 115
 116 template<typename T, unsigned D, typename O>
 117 inline bool CompositeShape<T, D, O>::contains(const LinAl::Vector<T, D> &point) const
 118 {
 119         bool inside = false;
 120         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 121         {
 122                 inside = (*i)->contains(point);
 123                 if(Ops::shortcircuit(inside))
 124                         return inside;
 125         }
 126         return inside;
 127 }
 128
 129 template<typename T, unsigned D, typename O>
 130 inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
 131 {
 132         SurfacePoint<T, D> *buffer = points;
 133         unsigned buf_size = size;
 134         if(!points && !Ops::shortcircuit(true))
 135         {
 136                 buffer = new SurfacePoint<T, D>[max_isect];
 137                 buf_size = max_isect;
 138         }
 139
 140         int start_nesting = 0;
 141         unsigned n = 0;
 142         for(typename ShapeArray::const_iterator i=shapes.begin(); (n<buf_size && i!=shapes.end()); ++i)
 143         {
 144                 unsigned base = n;
 145                 unsigned count = (*i)->get_intersections(ray, buffer+base, buf_size-base);
 146                 bool start_inside = (*i)->contains(ray.get_start());
 147
 148                 if(!count && !start_inside)
 149                 {
 150                         if(Ops::shortcircuit(false))
 151                                 return 0;
 152                         continue;
 153                 }
 154
 155                 start_nesting += start_inside;
 156
 157                 if(!base)
 158                 {
 159                         n = count;
 160                         continue;
 161                 }
 162
 163                 sort_points(buffer, base+count);
 164
 165                 int nesting = start_nesting;
 166                 unsigned k = 0;
 167                 for(unsigned j=0; j<base+count; ++j)
 168                 {
 169                         if(Ops::shortcircuit(nesting+buffer[j].entry<2))
 170                         {
 171                                 if(j!=k)
 172                                         buffer[k] = buffer[j];
 173                                 ++k;
 174                         }
 175
 176                         nesting += buffer[j].entry*2-1;
 177                 }
 178
 179                 if(!k && Ops::shortcircuit(false))
 180                         return 0;
 181
 182                 n = k;
 183
 184                 if(i!=shapes.begin())
 185                         start_nesting = (start_nesting>!Ops::shortcircuit(true));
 186         }
 187
 188         if(buffer!=points)
 189                 delete[] buffer;
 190
 191         return n;
 192 }
 193
 194 template<typename T, unsigned D, typename O>
 195 inline Coverage CompositeShape<T, D, O>::get_coverage(const BoundingBox<T, D> &bbox) const
 196 {
 197         Coverage coverage = NO_COVERAGE;
 198         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 199         {
 200                 Coverage c = (*i)->get_coverage(bbox);
 201                 if(i==shapes.begin() || Ops::shortcircuit(c>coverage))
 202                         coverage = c;
 203
 204                 if(coverage!=PARTIAL_COVERAGE && Ops::shortcircuit(coverage==FULL_COVERAGE))
 205                         break;
 206         }
 207
 208         return coverage;
 209 }
 210
 211 } // namespace Geometry
 212 } // namespace Msp
 213
 214 #endif