From 68389c29cf88d6522dcfa00b5e2a5166e3947210 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Tue, 21 May 2013 18:39:37 +0300
Subject: [PATCH] Add shapes representing set operations

---
 source/geometry/compositeshape.h | 146 +++++++++++++++++++++++++++++++
 source/geometry/dummy.cpp        |   3 +
 source/geometry/intersection.h   |  62 +++++++++++++
 source/geometry/negation.h       |  75 ++++++++++++++++
 source/geometry/union.h          |  62 +++++++++++++
 5 files changed, 348 insertions(+)
 create mode 100644 source/geometry/compositeshape.h
 create mode 100644 source/geometry/intersection.h
 create mode 100644 source/geometry/negation.h
 create mode 100644 source/geometry/union.h

diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
new file mode 100644
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 cc7e2ba..ed9c219 100644
--- 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
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
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
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
-- 
2.43.0