+#ifndef MSP_GEOMETRY_COMPOSITESHAPE_H_
+#define MSP_GEOMETRY_COMPOSITESHAPE_H_
+
+#include <vector>
+#include "shape.h"
+
+namespace Msp {
+namespace Geometry {
+
+/**
+Common operations for shapes composed of other shapes.
+*/
+template<typename T, unsigned D, typename O>
+class CompositeShape: public Shape<T, D>
+{
+protected:
+ typedef O Ops;
+ typedef std::vector<Shape<T, D> *> ShapeArray;
+
+ ShapeArray shapes;
+
+ CompositeShape(const Shape<T, D> &, const Shape<T, D> &);
+ CompositeShape(const ShapeArray &);
+ CompositeShape(const CompositeShape &);
+ CompositeShape &operator=(const CompositeShape &);
+public:
+ virtual ~CompositeShape();
+
+ virtual HyperBox<T, D> get_axis_aligned_bounding_box() const;
+ virtual bool contains(const LinAl::Vector<T, D> &) const;
+ virtual bool check_intersection(const Ray<T, D> &) const;
+ virtual unsigned get_max_ray_intersections() const;
+ virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
+};
+
+template<typename T, unsigned D, typename O>
+inline CompositeShape<T, D, O>::CompositeShape(const Shape<T, D> &s1, const Shape<T, D> &s2)
+{
+ shapes.reserve(2);
+ shapes.push_back(s1.clone());
+ shapes.push_back(s2.clone());
+}
+
+template<typename T, unsigned D, typename O>
+inline CompositeShape<T, D, O>::CompositeShape(const ShapeArray &s)
+{
+ if(s.empty())
+ throw std::invalid_argument("CompositeShape::CompositeShape");
+
+ shapes.reserve(s.size());
+ for(typename ShapeArray::const_iterator i=s.begin(); i!=s.end(); ++i)
+ shapes.push_back((*i)->clone());
+}
+
+template<typename T, unsigned D, typename O>
+inline CompositeShape<T, D, O>::~CompositeShape()
+{
+ for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
+ delete *i;
+}
+
+template<typename T, unsigned D, typename O>
+inline HyperBox<T, D> CompositeShape<T, D, O>::get_axis_aligned_bounding_box() const
+{
+ HyperBox<T, D> aabb;
+ for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
+ {
+ if(i==shapes.begin())
+ aabb = (*i)->get_axis_aligned_bounding_box();
+ else
+ aabb = Ops::combine_aabb(aabb, (*i)->get_axis_aligned_bounding_box());
+ }
+ return aabb;
+}
+
+template<typename T, unsigned D, typename O>
+inline bool CompositeShape<T, D, O>::contains(const LinAl::Vector<T, D> &point) const
+{
+ bool inside = Ops::init_inside();
+ for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
+ {
+ inside = Ops::combine_inside(inside, (*i)->contains(point));
+ if(Ops::is_inside_decided(inside))
+ break;
+ }
+ return inside;
+}
+
+template<typename T, unsigned D, typename O>
+inline bool CompositeShape<T, D, O>::check_intersection(const Ray<T, D> &ray) const
+{
+ return get_intersections(ray, 0, 1);
+}
+
+template<typename T, unsigned D, typename O>
+inline unsigned CompositeShape<T, D, O>::get_max_ray_intersections() const
+{
+ unsigned max_isect = 0;
+ for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
+ max_isect += (*i)->get_max_ray_intersections();
+ return max_isect;
+}
+
+template<typename T, unsigned D, typename O>
+inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
+{
+ unsigned n = 0;
+ for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
+ {
+ unsigned base = n;
+ unsigned count = (*i)->get_intersections(ray, points+base, size-base);
+ for(unsigned j=0; j<count; ++j)
+ {
+ // XXX Devise a way to reduce copies here
+ SurfacePoint<T, D> pt = points[base+j];
+
+ bool surface = Ops::init_surface();
+ for(typename ShapeArray::const_iterator k=shapes.begin(); k!=shapes.end(); ++k)
+ if(k!=i)
+ surface = Ops::combine_surface(surface, (*k)->contains(pt.position));
+
+ if(surface)
+ {
+ if(points)
+ {
+ unsigned k;
+ for(k=n; (k>0 && points[k-1].distance>pt.distance); --k)
+ points[k] = points[k-1];
+ if(base+j!=k)
+ points[k] = pt;
+ }
+
+ ++n;
+ if(n==size)
+ return n;
+ }
+ }
+ }
+
+ return n;
+}
+
+} // namespace Geometry
+} // namespace Msp
+
+#endif