From 09cc3a8648dd20e9a07d669b353c4a120b67c1c4 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Wed, 22 May 2013 20:34:01 +0300
Subject: [PATCH] Implement bounding boxes with a separate class

This solves several problems with them, including positioning off the
origin and bounding boxes of negated shapes.
---
 source/geometry/boundingbox.h      | 146 +++++++++++++++++++++++++++++
 source/geometry/compositeshape.h   |   7 +-
 source/geometry/extrudedshape.h    |  10 +-
 source/geometry/halfspace.h        |   9 +-
 source/geometry/hyperbox.h         |  10 +-
 source/geometry/hypersphere.h      |  12 +--
 source/geometry/intersection.h     |  12 +--
 source/geometry/negation.h         |   8 +-
 source/geometry/shape.h            |   4 +-
 source/geometry/transformedshape.h |  27 +++++-
 source/geometry/union.h            |  12 +--
 11 files changed, 207 insertions(+), 50 deletions(-)
 create mode 100644 source/geometry/boundingbox.h

diff --git a/source/geometry/boundingbox.h b/source/geometry/boundingbox.h
new file mode 100644
index 0000000..120eedb
--- /dev/null
+++ b/source/geometry/boundingbox.h
@@ -0,0 +1,146 @@
+#ifndef MSP_GEOMETRY_BOUNDINGBOX_H_
+#define MSP_GEOMETRY_BOUNDINGBOX_H_
+
+#include <algorithm>
+#include <stdexcept>
+#include <msp/linal/vector.h>
+
+namespace Msp {
+namespace Geometry {
+
+template<typename T, unsigned D>
+class BoundingBox
+{
+private:
+	LinAl::Vector<T, D> min_pt;
+	LinAl::Vector<T, D> max_pt;
+	bool empty;
+	bool negated;
+
+public:
+	BoundingBox();
+	BoundingBox(const LinAl::Vector<T, D> &, const LinAl::Vector<T, D> &);
+
+	static BoundingBox negate(const BoundingBox &);
+
+	const LinAl::Vector<T, D> &get_minimum_point() const { return min_pt; }
+	T get_minimum_coordinate(unsigned i) const { return min_pt[i]; }
+	const LinAl::Vector<T, D> &get_maximum_point() const { return max_pt; }
+	T get_maximum_coordinate(unsigned i) const { return max_pt[i]; }
+	bool is_empty() const { return empty; }
+	bool is_negated() const { return negated; }
+};
+
+template<typename T, unsigned D>
+inline BoundingBox<T, D>::BoundingBox():
+	empty(true),
+	negated(false)
+{ }
+
+template<typename T, unsigned D>
+inline BoundingBox<T, D>::BoundingBox(const LinAl::Vector<T, D> &n, const LinAl::Vector<T, D> &x):
+	min_pt(n),
+	max_pt(x),
+	empty(false),
+	negated(false)
+{
+	for(unsigned i=0; i<D; ++i)
+		if(min_pt[i]>max_pt[i])
+			throw std::invalid_argument("BoundingBox::BoundingBox");
+}
+
+template<typename T, unsigned D>
+inline BoundingBox<T, D> BoundingBox<T, D>::negate(const BoundingBox<T, D> &bb)
+{
+	BoundingBox<T, D> result = bb;
+	result.negated = !bb.negated;
+	return result;
+}
+
+template<typename T, unsigned D>
+inline BoundingBox<T, D> operator&(const BoundingBox<T, D> &bb1, const BoundingBox<T, D> &bb2)
+{
+	if(bb1.is_empty() || bb2.is_empty())
+		return BoundingBox<T, D>();
+
+	if(bb1.is_negated())
+	{
+		if(bb2.is_negated())
+			return ~((~bb1)|(~bb2));
+		else
+			return bb2&bb1;
+	}
+
+	LinAl::Vector<T, D> result_min;
+	LinAl::Vector<T, D> result_max;
+
+	if(bb2.is_negated())
+	{
+		// This is effectively subtraction of (non-negated) bb2 from bb1
+		int uncovered_axis = -1;
+		for(unsigned i=0; i<D; ++i)
+			if(bb1.get_minimum_coordinate(i)<bb2.get_minimum_coordinate(i) || bb1.get_maximum_coordinate(i)>bb2.get_maximum_coordinate(i))
+			{
+				if(uncovered_axis!=-1)
+					return bb1;
+				uncovered_axis = i;
+			}
+
+		if(uncovered_axis==-1)
+			return BoundingBox<T, D>();
+
+		result_min = bb1.get_minimum_point();
+		result_max = bb1.get_maximum_point();
+		if(bb2.get_minimum_coordinate(uncovered_axis)<bb1.get_minimum_coordinate(uncovered_axis))
+			result_min[uncovered_axis] = bb2.get_maximum_coordinate(uncovered_axis);
+		else
+			result_max[uncovered_axis] = bb2.get_minimum_coordinate(uncovered_axis);
+	}
+	else
+	{
+		for(unsigned i=0; i<D; ++i)
+		{
+			result_min[i] = std::max(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
+			result_max[i] = std::min(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
+			if(result_min[i]>result_max[i])
+				return BoundingBox<T, D>();
+		}
+	}
+
+	return BoundingBox<T, D>(result_min, result_max);
+}
+
+template<typename T, unsigned D>
+inline BoundingBox<T, D> operator|(const BoundingBox<T, D> &bb1, const BoundingBox<T, D> &bb2)
+{
+	if(bb1.is_empty())
+		return bb2;
+	if(bb2.is_empty())
+		return bb1;
+
+	if(bb1.is_negated())
+		return ~((~bb1)&(~bb2));
+	else if(bb2.is_negated())
+		return ~((~bb2)&(~bb1));
+
+	LinAl::Vector<T, D> result_min;
+	LinAl::Vector<T, D> result_max;
+	for(unsigned i=0; i<D; ++i)
+	{
+		result_min[i] = std::min(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
+		result_max[i] = std::max(bb1.get_minimum_coordinate(i), bb1.get_minimum_coordinate(i));
+	}
+
+	return BoundingBox<T, D>(result_min, result_max);
+}
+
+template<typename T, unsigned D>
+inline BoundingBox<T, D> operator~(const BoundingBox<T, D> &bb)
+{
+	return BoundingBox<T, D>::negate(bb);
+}
+
+} // namespace Geometry
+} // namespace Msp
+
+#endif
diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
index 50075d9..4c640be 100644
--- a/source/geometry/compositeshape.h
+++ b/source/geometry/compositeshape.h
@@ -3,6 +3,7 @@
 
 #include <stdexcept>
 #include <vector>
+#include "boundingbox.h"
 #include "shape.h"
 
 namespace Msp {
@@ -29,7 +30,7 @@ protected:
 public:
 	virtual ~CompositeShape();
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const;
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const;
 	virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
@@ -70,9 +71,9 @@ inline CompositeShape<T, D, O>::~CompositeShape()
 }
 
 template<typename T, unsigned D, typename O>
-inline HyperBox<T, D> CompositeShape<T, D, O>::get_axis_aligned_bounding_box() const
+inline BoundingBox<T, D> CompositeShape<T, D, O>::get_axis_aligned_bounding_box() const
 {
-	HyperBox<T, D> aabb;
+	BoundingBox<T, D> aabb;
 	for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
 	{
 		if(i==shapes.begin())
diff --git a/source/geometry/extrudedshape.h b/source/geometry/extrudedshape.h
index 83933b0..de582e3 100644
--- a/source/geometry/extrudedshape.h
+++ b/source/geometry/extrudedshape.h
@@ -31,7 +31,7 @@ public:
 	const Shape<T, D-1> &get_base() const { return *base; }
 	T get_length() const { return length; }
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const;
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const;
 	virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
@@ -74,10 +74,12 @@ inline ExtrudedShape<T, D> *ExtrudedShape<T, D>::clone() const
 }
 
 template<typename T, unsigned D>
-inline HyperBox<T, D> ExtrudedShape<T, D>::get_axis_aligned_bounding_box() const
+inline BoundingBox<T, D> ExtrudedShape<T, D>::get_axis_aligned_bounding_box() const
 {
-	HyperBox<T, D-1> base_bbox = base->get_axis_aligned_bounding_box();
-	return HyperBox<T, D>(LinAl::Vector<T, D>(base_bbox.get_dimensions(), length));
+	BoundingBox<T, D-1> base_bbox = base->get_axis_aligned_bounding_box();
+	T half_length = length/T(2);
+	return BoundingBox<T, D>(LinAl::Vector<T, D>(base_bbox.get_minimum_point(), -half_length),
+		LinAl::Vector<T, D>(base_bbox.get_maximum_point(), half_length));
 }
 
 template<typename T, unsigned D>
diff --git a/source/geometry/halfspace.h b/source/geometry/halfspace.h
index 9ed80ff..60f0403 100644
--- a/source/geometry/halfspace.h
+++ b/source/geometry/halfspace.h
@@ -1,6 +1,7 @@
 #ifndef MSP_GEOMETRY_HALFSPACE_H_
 #define MSP_GEOMETRY_HALFSPACE_H_
 
+#include "boundingbox.h"
 #include "shape.h"
 
 namespace Msp {
@@ -24,7 +25,7 @@ public:
 
 	const LinAl::Vector<T, D> &get_normal() const { return normal; }
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const;
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const { return 1; }
 	virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
@@ -48,10 +49,10 @@ inline HalfSpace<T, D> *HalfSpace<T, D>::clone() const
 }
 
 template<typename T, unsigned D>
-inline HyperBox<T, D> HalfSpace<T, D>::get_axis_aligned_bounding_box() const
+inline BoundingBox<T, D> HalfSpace<T, D>::get_axis_aligned_bounding_box() const
 {
-	// XXX Implement this properly
-	return HyperBox<T, D>();
+	// XXX If the normal is aligned to an axis, should the bounding box reflect that?
+	return ~BoundingBox<T, D>();
 }
 
 template<typename T, unsigned D>
diff --git a/source/geometry/hyperbox.h b/source/geometry/hyperbox.h
index 11c197e..da50091 100644
--- a/source/geometry/hyperbox.h
+++ b/source/geometry/hyperbox.h
@@ -5,6 +5,7 @@
 #include <cmath>
 #include <stdexcept>
 #include <msp/linal/vector.h>
+#include "boundingbox.h"
 #include "ray.h"
 #include "shape.h"
 #include "surfacepoint.h"
@@ -31,7 +32,7 @@ public:
 	const LinAl::Vector<T, D> &get_dimensions() const { return dimensions; }
 	T get_dimension(unsigned) const;
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const { return *this; }
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const { return 2; }
 	virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
@@ -65,6 +66,13 @@ inline T HyperBox<T, D>::get_dimension(unsigned i) const
 	return dimensions[i];
 }
 
+template<typename T, unsigned D>
+inline BoundingBox<T, D> HyperBox<T, D>::get_axis_aligned_bounding_box() const
+{
+	LinAl::Vector<T, D> half_dim = dimensions/T(2);
+	return BoundingBox<T, D>(-half_dim, half_dim);
+}
+
 template<typename T, unsigned D>
 inline bool HyperBox<T, D>::contains(const LinAl::Vector<T, D> &point) const
 {
diff --git a/source/geometry/hypersphere.h b/source/geometry/hypersphere.h
index abdd193..3c04125 100644
--- a/source/geometry/hypersphere.h
+++ b/source/geometry/hypersphere.h
@@ -4,7 +4,7 @@
 #include <cmath>
 #include <stdexcept>
 #include <msp/linal/vector.h>
-#include "hyperbox.h"
+#include "boundingbox.h"
 #include "ray.h"
 #include "shape.h"
 #include "surfacepoint.h"
@@ -30,7 +30,7 @@ public:
 
 	T get_radius() const { return radius; }
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const;
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const { return 2; }
 	virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
@@ -51,12 +51,12 @@ inline HyperSphere<T, D> *HyperSphere<T, D>::clone() const
 }
 
 template<typename T, unsigned D>
-inline HyperBox<T, D> HyperSphere<T, D>::get_axis_aligned_bounding_box() const
+inline BoundingBox<T, D> HyperSphere<T, D>::get_axis_aligned_bounding_box() const
 {
-	LinAl::Vector<T, D> dimensions;
+	LinAl::Vector<T, D> extent;
 	for(unsigned i=0; i<D; ++i)
-		dimensions[i] = radius;
-	return HyperBox<T, D>(dimensions);
+		extent[i] = radius;
+	return BoundingBox<T, D>(-extent, extent);
 }
 
 template<typename T, unsigned D>
diff --git a/source/geometry/intersection.h b/source/geometry/intersection.h
index c20aae1..01707cd 100644
--- a/source/geometry/intersection.h
+++ b/source/geometry/intersection.h
@@ -12,7 +12,7 @@ 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 BoundingBox<T, D> combine_aabb(const BoundingBox<T, D> &a, const BoundingBox<T, D> &b) { return a&b; }
 	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; }
@@ -54,16 +54,6 @@ inline Intersection<T, D> *Intersection<T, D>::clone() const
 	return new Intersection<T, D>(*this);
 }
 
-
-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
 
diff --git a/source/geometry/negation.h b/source/geometry/negation.h
index 6746aed..beb3e4e 100644
--- a/source/geometry/negation.h
+++ b/source/geometry/negation.h
@@ -1,6 +1,7 @@
 #ifndef MSP_GEOMETRY_NEGATION_H_
 #define MSP_GEOMETRY_NEGATION_H_
 
+#include "boundingbox.h"
 #include "shape.h"
 
 namespace Msp {
@@ -23,7 +24,7 @@ public:
 
 	const Shape<T, D> &get_shape() const { return *shape; }
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const;
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
 	virtual bool contains(const LinAl::Vector<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;
@@ -41,10 +42,9 @@ inline Negation<T, D> *Negation<T, D>::clone() const
 }
 
 template<typename T, unsigned D>
-inline HyperBox<T, D> Negation<T, D>::get_axis_aligned_bounding_box() const
+inline BoundingBox<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>();
+	return ~shape->get_axis_aligned_bounding_box();
 }
 
 template<typename T, unsigned D>
diff --git a/source/geometry/shape.h b/source/geometry/shape.h
index 7b1d190..bbe255f 100644
--- a/source/geometry/shape.h
+++ b/source/geometry/shape.h
@@ -8,7 +8,7 @@ namespace Msp {
 namespace Geometry {
 
 template<typename T, unsigned D>
-class HyperBox;
+class BoundingBox;
 
 template<typename T, unsigned D>
 class Ray;
@@ -31,7 +31,7 @@ public:
 
 	virtual Shape *clone() const = 0;
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const = 0;
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const = 0;
 	virtual bool contains(const LinAl::Vector<T, D> &) const = 0;
 	bool check_intersection(const Ray<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const = 0;
diff --git a/source/geometry/transformedshape.h b/source/geometry/transformedshape.h
index 02587bf..58e571a 100644
--- a/source/geometry/transformedshape.h
+++ b/source/geometry/transformedshape.h
@@ -2,6 +2,7 @@
 #define MSP_GEOMETRY_TRANSFORMEDSHAPE_H_
 
 #include "affinetransformation.h"
+#include "boundingbox.h"
 #include "ray.h"
 #include "shape.h"
 
@@ -30,7 +31,7 @@ public:
 	const Shape<T, D> &get_shape() const { return *shape; }
 	const AffineTransformation<T, D> &get_transformation() const { return transformation; }
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const;
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 private:
 	Ray<T, D> make_local_ray(const Ray<T, D> &) const;
@@ -75,10 +76,28 @@ inline TransformedShape<T, D> *TransformedShape<T, D>::clone() const
 }
 
 template<typename T, unsigned D>
-inline HyperBox<T, D> TransformedShape<T, D>::get_axis_aligned_bounding_box() const
+inline BoundingBox<T, D> TransformedShape<T, D>::get_axis_aligned_bounding_box() const
 {
-	// XXX This is not correct for most shapes
-	return shape->get_axis_aligned_bounding_box();
+	BoundingBox<T, D> inner_bbox = shape->get_axis_aligned_bounding_box();
+
+	LinAl::Vector<T, D> min_pt;
+	LinAl::Vector<T, D> max_pt;
+	for(unsigned i=0; i<(1<<D); ++i)
+	{
+		LinAl::Vector<T, D> point;
+		for(unsigned j=0; j<D; ++j)
+			point[j] = ((i>>j)&1 ? inner_bbox.get_maximum_coordinate(j) : inner_bbox.get_minimum_coordinate(j));
+
+		point = transformation.transform(point);
+
+		for(unsigned j=0; j<D; ++j)
+		{
+			min_pt[j] = std::min(min_pt[j], point[j]);
+			max_pt[j] = std::max(min_pt[j], point[j]);
+		}
+	}
+
+	return BoundingBox<T, D>(min_pt, max_pt);
 }
 
 template<typename T, unsigned D>
diff --git a/source/geometry/union.h b/source/geometry/union.h
index 13eb708..8461f84 100644
--- a/source/geometry/union.h
+++ b/source/geometry/union.h
@@ -12,7 +12,7 @@ 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 BoundingBox<T, D> combine_aabb(const BoundingBox<T, D> &a, const BoundingBox<T, D> &b) { return a|b; }
 	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; }
@@ -54,16 +54,6 @@ inline Union<T, D> *Union<T, D>::clone() const
 	return new Union<T, D>(*this);
 }
 
-
-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
 
-- 
2.43.0