Implement bounding boxes with a separate class

This solves several problems with them, including positioning off the
origin and bounding boxes of negated shapes.

diff --git a/source/geometry/boundingbox.h b/source/geometry/boundingbox.h
new file mode 100644 (file)
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 50075d923b70c3c38f6671ae6ed585fe75f95ec1..4c640be22f4c5045076b9659ce7734d517f1127c 100644 (file)
--- 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 83933b0808a02f32d8febcce5eee8c8a23ad85d0..de582e3d26bf278139600aca6c3cc1d15609a798 100644 (file)
--- 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 9ed80ff71b85052e6525bb46fb800f775c04fe3f..60f040350b0f63ac3ac48409701db028cece4353 100644 (file)
--- 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 11c197e72ebb059814e0c92f685ac533b72acaa2..da500910e4f100d57f865b644bd719d71a3ee34c 100644 (file)
--- 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 abdd1939508c2a717f5856fed975da0690226a0a..3c0412564fcc1cf055842c9d325943935812746a 100644 (file)
--- 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 c20aae126d1b021552d430df5fc05a5c1a8ad205..01707cdfc64274a79317179fc3faa96348c3c591 100644 (file)
--- 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 6746aed113f487618e0e7f254f088fd8bdc2289e..beb3e4e7b845d91edcaff45555add550a8165cd3 100644 (file)
--- 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 7b1d190b5a762b82c7213a012e58190c7ba8d66c..bbe255f9054f919792ca748a7c25468b62bfabc8 100644 (file)
--- 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 02587bfd87877efac86f365d39e1a68e072a7020..58e571a9db389a058cdb8ab3de1343b4ee87cb3e 100644 (file)
--- 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 13eb7080442c625369f2c565fbb71405df5c9955..8461f8484ee5d085560b6fb70f522447d9a95c6e 100644 (file)
--- 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