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         unsigned min_scratch;
  25
  26         CompositeShape() { }
  27         CompositeShape(const Shape<T, D> &, const Shape<T, D> &);
  28         template<typename Iter>
  29         void init_from_iter_range(const Iter &, const Iter &);
  30 private:
  31         void init();
  32 protected:
  33         CompositeShape(const CompositeShape &);
  34         CompositeShape &operator=(const CompositeShape &);
  35 public:
  36         virtual ~CompositeShape();
  37
  38         virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
  39         virtual bool contains(const LinAl::Vector<T, D> &) const;
  40         virtual unsigned get_max_ray_intersections() const { return max_isect; }
  41         virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) 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         min_scratch = 0;
  70         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
  71         {
  72                 unsigned mi = (*i)->get_max_ray_intersections();
  73                 max_isect += mi;
  74                 min_scratch = std::max(min_scratch, mi);
  75         }
  76 }
  77
  78 template<typename T, unsigned D, typename O>
  79 inline CompositeShape<T, D, O>::CompositeShape(const CompositeShape<T, D, O> &other):
  80         shapes(other.shapes),
  81         max_isect(other.max_isect),
  82         min_scratch(other.min_scratch)
  83 {
  84         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  85                 *i = (*i)->clone();
  86 }
  87
  88 template<typename T, unsigned D, typename O>
  89 inline CompositeShape<T, D, O> &CompositeShape<T, D, O>::operator=(const CompositeShape<T, D, O> &other)
  90 {
  91         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  92                 delete *i;
  93
  94         shapes = other.shapes;
  95         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
  96                 *i = (*i)->clone();
  97
  98         max_isect = other.max_isect;
  99         min_scratch = other.min_scratch;
 100 }
 101
 102 template<typename T, unsigned D, typename O>
 103 inline CompositeShape<T, D, O>::~CompositeShape()
 104 {
 105         for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
 106                 delete *i;
 107 }
 108
 109 template<typename T, unsigned D, typename O>
 110 inline BoundingBox<T, D> CompositeShape<T, D, O>::get_axis_aligned_bounding_box() const
 111 {
 112         BoundingBox<T, D> aabb;
 113         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 114         {
 115                 if(i==shapes.begin())
 116                         aabb = (*i)->get_axis_aligned_bounding_box();
 117                 else
 118                         aabb = Ops::combine_aabb(aabb, (*i)->get_axis_aligned_bounding_box());
 119         }
 120         return aabb;
 121 }
 122
 123 template<typename T, unsigned D, typename O>
 124 inline bool CompositeShape<T, D, O>::contains(const LinAl::Vector<T, D> &point) const
 125 {
 126         bool inside = Ops::init_inside();
 127         for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 128         {
 129                 inside = Ops::combine_inside(inside, (*i)->contains(point));
 130                 if(Ops::is_inside_decided(inside))
 131                         break;
 132         }
 133         return inside;
 134 }
 135
 136 template<typename T, unsigned D, typename O>
 137 inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
 138 {
 139         SurfacePoint<T, D> *buffer = points;
 140         unsigned buf_size = size;
 141         if(!points)
 142         {
 143                 buffer = new SurfacePoint<T, D>[min_scratch];
 144                 buf_size = min_scratch;
 145         }
 146
 147         unsigned n = 0;
 148         for(typename ShapeArray::const_iterator i=shapes.begin(); (n<size && i!=shapes.end()); ++i)
 149         {
 150                 unsigned base = (points ? n : 0);
 151                 unsigned count = (*i)->get_intersections(ray, buffer+base, buf_size-base);
 152                 for(unsigned j=0; (n<size && j<count); ++j)
 153                 {
 154                         SurfacePoint<T, D> &pt = buffer[base+j];
 155
 156                         bool surface = Ops::init_surface();
 157                         for(typename ShapeArray::const_iterator k=shapes.begin(); k!=shapes.end(); ++k)
 158                                 if(k!=i)
 159                                         surface = Ops::combine_surface(surface, (*k)->contains(pt.position));
 160
 161                         if(surface)
 162                         {
 163                                 if(points && base+j!=n)
 164                                         points[n] = pt;
 165
 166                                 ++n;
 167                         }
 168                 }
 169         }
 170
 171         if(points)
 172                 sort_points(points, n);
 173         else
 174                 delete[] buffer;
 175
 176         return n;
 177 }
 178
 179 } // namespace Geometry
 180 } // namespace Msp
 181
 182 #endif