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 };
  42
  43 template<typename T, unsigned D, typename O>
  44 inline CompositeShape<T, D, O>::CompositeShape(const Shape<T, D> &s1, const Shape<T, D> &s2)
  45 {
  46         shapes.reserve(2);
  47         shapes.push_back(s1.clone());
  48         shapes.push_back(s2.clone());
  49         init();
  50 }
  51
  52 template<typename T, unsigned D, typename O>
  53 template<typename Iter>
  54 inline void CompositeShape<T, D, O>::init_from_iter_range(const Iter &begin, const Iter &end)
  55 {
  56         if(begin==end)
  57                 throw std::invalid_argument("CompositeShape::init_from_iter_range");
  58
  59         for(Iter i=begin; i!=end; ++i)
  60                 shapes.push_back((*i)->clone());
  61         init();
  62 }
  63
  64 template<typename T, unsigned D, typename O>
  65 inline void CompositeShape<T, D, O>::init()
  66 {
  67         max_isect = 0;
  68         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
  69                 max_isect += (*i)->get_max_ray_intersections();
  70 }
  71
  72 template<typename T, unsigned D, typename O>
  73 inline CompositeShape<T, D, O>::CompositeShape(const CompositeShape<T, D, O> &other):
  74         shapes(other.shapes),
  75         max_isect(other.max_isect)
  76 {
  77         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  78                 *i = (*i)->clone();
  79 }
  80
  81 template<typename T, unsigned D, typename O>
  82 inline CompositeShape<T, D, O> &CompositeShape<T, D, O>::operator=(const CompositeShape<T, D, O> &other)
  83 {
  84         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  85                 delete *i;
  86
  87         shapes = other.shapes;
  88         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  89                 *i = (*i)->clone();
  90
  91         max_isect = other.max_isect;
  92 }
  93
  94 template<typename T, unsigned D, typename O>
  95 inline CompositeShape<T, D, O>::~CompositeShape()
  96 {
  97         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  98                 delete *i;
  99 }
 100
 101 template<typename T, unsigned D, typename O>
 102 inline BoundingBox<T, D> CompositeShape<T, D, O>::get_axis_aligned_bounding_box() const
 103 {
 104         BoundingBox<T, D> aabb;
 105         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 106         {
 107                 if(i==shapes.begin())
 108                         aabb = (*i)->get_axis_aligned_bounding_box();
 109                 else
 110                         aabb = Ops::combine_aabb(aabb, (*i)->get_axis_aligned_bounding_box());
 111         }
 112         return aabb;
 113 }
 114
 115 template<typename T, unsigned D, typename O>
 116 inline bool CompositeShape<T, D, O>::contains(const LinAl::Vector<T, D> &point) const
 117 {
 118         bool inside = false;
 119         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 120         {
 121                 inside = (*i)->contains(point);
 122                 if(Ops::shortcircuit(inside))
 123                         return inside;
 124         }
 125         return inside;
 126 }
 127
 128 template<typename T, unsigned D, typename O>
 129 inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
 130 {
 131         SurfacePoint<T, D> *buffer = points;
 132         unsigned buf_size = size;
 133         if(!points && !Ops::shortcircuit(true))
 134         {
 135                 buffer = new SurfacePoint<T, D>[max_isect];
 136                 buf_size = max_isect;
 137         }
 138
 139         int start_nesting = 0;
 140         unsigned n = 0;
 141         for(typename ShapeArray::const_iterator i=shapes.begin(); (n<buf_size && i!=shapes.end()); ++i)
 142         {
 143                 unsigned base = n;
 144                 unsigned count = (*i)->get_intersections(ray, buffer+base, buf_size-base);
 145                 bool start_inside = (*i)->contains(ray.get_start());
 146
 147                 if(!count && !start_inside)
 148                 {
 149                         if(Ops::shortcircuit(false))
 150                                 return 0;
 151                         continue;
 152                 }
 153
 154                 start_nesting += start_inside;
 155
 156                 if(!base)
 157                 {
 158                         n = count;
 159                         continue;
 160                 }
 161
 162                 sort_points(buffer, base+count);
 163
 164                 int nesting = start_nesting;
 165                 unsigned k = 0;
 166                 for(unsigned j=0; j<base+count; ++j)
 167                 {
 168                         if(Ops::shortcircuit(nesting+buffer[j].entry<2))
 169                         {
 170                                 if(j!=k)
 171                                         buffer[k] = buffer[j];
 172                                 ++k;
 173                         }
 174
 175                         nesting += buffer[j].entry*2-1;
 176                 }
 177
 178                 if(!k && Ops::shortcircuit(false))
 179                         return 0;
 180
 181                 n = k;
 182
 183                 if(i!=shapes.begin())
 184                         start_nesting = (start_nesting>!Ops::shortcircuit(false));
 185         }
 186
 187         if(buffer!=points)
 188                 delete[] buffer;
 189
 190         return n;
 191 }
 192
 193 } // namespace Geometry
 194 } // namespace Msp
 195
 196 #endif