Add shapes representing set operations

diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
new file mode 100644 (file)
index 0000000..fd55c8e
--- /dev/null
+++ b/source/geometry/compositeshape.h
@@ -0,0 +1,146 @@
+#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

diff --git a/source/geometry/dummy.cpp b/source/geometry/dummy.cpp
index cc7e2baf1787d51af94f97c33a67ff73ecd41820..ed9c219180a6c702a226129282337c33243bcc8f 100644 (file)
--- a/source/geometry/dummy.cpp
+++ b/source/geometry/dummy.cpp
@@ -4,7 +4,10 @@
 #include "circle.h"
 #include "hyperbox.h"
 #include "hypersphere.h"
+#include "intersection.h"
+#include "negation.h"
 #include "ray.h"
 #include "rectangle.h"
 #include "shape.h"
 #include "transformedshape.h"
+#include "union.h"

diff --git a/source/geometry/intersection.h b/source/geometry/intersection.h
new file mode 100644 (file)
index 0000000..53c25c2
--- /dev/null
+++ b/source/geometry/intersection.h
@@ -0,0 +1,62 @@
+#ifndef MSP_GEOMETRY_INTERSECTION_H_
+#define MSP_GEOMETRY_INTERSECTION_H_
+
+#include "compositeshape.h"
+
+namespace Msp {
+namespace Geometry {
+
+/**
+Forms a shape from the common parts of component shapes.
+*/
+template<typename T, unsigned D>
+struct IntersectionOps
+{
+       static HyperBox<T, D> combine_aabb(const HyperBox<T, D> &, const HyperBox<T, D> &);
+       static bool init_inside() { return true; }
+       static bool combine_inside(bool a, bool b) { return a && b; }
+       static bool is_inside_decided(bool a) { return !a; }
+       static bool init_surface() { return true; }
+       static bool combine_surface(bool a, bool b) { return a && b; }
+};
+
+template<typename T, unsigned D>
+class Intersection: public CompositeShape<T, D, IntersectionOps<T, D> >
+{
+public:
+       Intersection(const Shape<T, D> &, const Shape<T, D> &);
+       Intersection(const std::vector<Shape<T, D> *> &);
+
+       virtual Intersection *clone() const;
+};
+
+template<typename T, unsigned D>
+Intersection<T, D>::Intersection(const Shape<T, D> &s1, const Shape<T, D> &s2):
+       CompositeShape<T, D, IntersectionOps<T, D> >(s1, s2)
+{ }
+
+template<typename T, unsigned D>
+Intersection<T, D>::Intersection(const std::vector<Shape<T, D> *> &s):
+       CompositeShape<T, D, IntersectionOps<T, D> >(s)
+{ }
+
+template<typename T, unsigned D>
+Intersection<T, D> *Intersection<T, D>::clone() const
+{
+       return new Intersection<T, D>(this->shapes);
+}
+
+
+template<typename T, unsigned D>
+inline HyperBox<T, D> IntersectionOps<T, D>::combine_aabb(const HyperBox<T, D> &box1, const HyperBox<T, D> &box2)
+{
+       LinAl::Vector<T, D> dimensions;
+       for(unsigned i=0; i<D; ++i)
+               dimensions[i] = std::min(box1.get_dimension(i), box2.get_dimension(i));
+       return HyperBox<T, D>(dimensions);
+}
+
+} // namespace Geometry
+} // namespace Msp
+
+#endif

diff --git a/source/geometry/negation.h b/source/geometry/negation.h
new file mode 100644 (file)
index 0000000..0fc0196
--- /dev/null
+++ b/source/geometry/negation.h
@@ -0,0 +1,75 @@
+#ifndef MSP_GEOMETRY_NEGATION_H_
+#define MSP_GEOMETRY_NEGATION_H_
+
+#include "shape.h"
+
+namespace Msp {
+namespace Geometry {
+
+/**
+Negates a shape.  Not particulary useful on its own, but can be used together
+with Intersection to cut holes.
+*/
+template<typename T, unsigned D>
+class Negation: public Shape<T, D>
+{
+private:
+       Shape<T, D> *shape;
+
+public:
+       Negation(const Shape<T, D> &);
+
+       virtual Negation *clone() const;
+
+       const Shape<T, D> &get_shape() const { return *shape; }
+
+       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 { return shape->get_max_ray_intersections(); }
+       virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
+};
+
+template<typename T, unsigned D>
+inline Negation<T, D>::Negation(const Shape<T, D> &s):
+       shape(s.clone())
+{ }
+
+template<typename T, unsigned D>
+inline Negation<T, D> *Negation<T, D>::clone() const
+{
+       return new Negation<T, D>(*shape);
+}
+
+template<typename T, unsigned D>
+inline HyperBox<T, D> Negation<T, D>::get_axis_aligned_bounding_box() const
+{
+       // XXX How do we handle this correctly?  In particular negation of a negation?
+       return HyperBox<T, D>();
+}
+
+template<typename T, unsigned D>
+inline bool Negation<T, D>::contains(const LinAl::Vector<T, D> &point) const
+{
+       return !shape->contains(point);
+}
+
+template<typename T, unsigned D>
+inline bool Negation<T, D>::check_intersection(const Ray<T, D> &ray) const
+{
+       return get_intersections(ray, 0, 1);
+}
+
+template<typename T, unsigned D>
+inline unsigned Negation<T, D>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
+{
+       unsigned count = shape->get_intersections(ray, points, size);
+       for(unsigned i=0; i<count; ++i)
+               points[i].normal = -points[i].normal;
+       return count;
+}
+
+} // namespace Geometry
+} // namespace Msp
+
+#endif

diff --git a/source/geometry/union.h b/source/geometry/union.h
new file mode 100644 (file)
index 0000000..fadeff2
--- /dev/null
+++ b/source/geometry/union.h
@@ -0,0 +1,62 @@
+#ifndef MSP_GEOMETRY_UNION_H_
+#define MSP_GEOMETRY_UNION_H_
+
+#include "compositeshape.h"
+
+namespace Msp {
+namespace Geometry {
+
+/**
+Joins component shapes together into one.
+*/
+template<typename T, unsigned D>
+struct UnionOps
+{
+       static HyperBox<T, D> combine_aabb(const HyperBox<T, D> &, const HyperBox<T, D> &);
+       static bool init_inside() { return false; }
+       static bool combine_inside(bool a, bool b) { return a || b; }
+       static bool is_inside_decided(bool a) { return a; }
+       static bool init_surface() { return true; }
+       static bool combine_surface(bool a, bool b) { return a && !b; }
+};
+
+template<typename T, unsigned D>
+class Union: public CompositeShape<T, D, UnionOps<T, D> >
+{
+public:
+       Union(const Shape<T, D> &, const Shape<T, D> &);
+       Union(const std::vector<Shape<T, D> *> &);
+
+       virtual Union *clone() const;
+};
+
+template<typename T, unsigned D>
+inline Union<T, D>::Union(const Shape<T, D> &s1, const Shape<T, D> &s2):
+       CompositeShape<T, D, UnionOps<T, D> >(s1, s2)
+{ }
+
+template<typename T, unsigned D>
+inline Union<T, D>::Union(const std::vector<Shape<T, D> *> &s):
+       CompositeShape<T, D, UnionOps<T, D> >(s)
+{ }
+
+template<typename T, unsigned D>
+inline Union<T, D> *Union<T, D>::clone() const
+{
+       return new Union<T, D>(this->shapes);
+}
+
+
+template<typename T, unsigned D>
+inline HyperBox<T, D> UnionOps<T, D>::combine_aabb(const HyperBox<T, D> &box1, const HyperBox<T, D> &box2)
+{
+       LinAl::Vector<T, D> dimensions;
+       for(unsigned i=0; i<D; ++i)
+               dimensions[i] = std::max(box1.get_dimension(i), box2.get_dimension(i));
+       return HyperBox<T, D>(dimensions);
+}
+
+} // namespace Geometry
+} // namespace Msp
+
+#endif