Add a function to test whether a shapes covers a bounding box

diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
index e9aeadcfe73df68657fab07473d15a6fba2f25a6..00ae55d0ad7b83e8d67a3f15867d75c6419a6903 100644 (file)
--- a/source/geometry/compositeshape.h
+++ b/source/geometry/compositeshape.h
@@ -38,6 +38,7 @@ public:
        virtual bool contains(const LinAl::Vector<T, D> &) const;
        virtual unsigned get_max_ray_intersections() const { return max_isect; }
        virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
 };
 
 template<typename T, unsigned D, typename O>
@@ -190,6 +191,23 @@ inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray,
        return n;
 }
 
+template<typename T, unsigned D, typename O>
+inline Coverage CompositeShape<T, D, O>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+       Coverage coverage = NO_COVERAGE;
+       for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
+       {
+               Coverage c = (*i)->get_coverage(bbox);
+               if(i==shapes.begin() || Ops::shortcircuit(c>coverage))
+                       coverage = c;
+
+               if(coverage!=PARTIAL_COVERAGE && Ops::shortcircuit(coverage==FULL_COVERAGE))
+                       break;
+       }
+
+       return coverage;
+}
+
 } // namespace Geometry
 } // namespace Msp
 

diff --git a/source/geometry/extrudedshape.h b/source/geometry/extrudedshape.h
index 78dfa4911463e57951eaa0ca4524c223ab9ce9b5..e702f90a7a0f844d93f417b53d38a8c6aea2359a 100644 (file)
--- a/source/geometry/extrudedshape.h
+++ b/source/geometry/extrudedshape.h
@@ -35,6 +35,7 @@ public:
        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;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
 };
 
 template<typename T, unsigned D>
@@ -187,6 +188,24 @@ inline unsigned ExtrudedShape<T, D>::get_intersections(const Ray<T, D> &ray, Sur
        return n;
 }
 
+template<typename T, unsigned D>
+inline Coverage ExtrudedShape<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+       T half_length = length/T(2);
+       if(bbox.get_maximum_coordinate(D-1)<-half_length || bbox.get_minimum_coordinate(D-1)>half_length)
+               return NO_COVERAGE;
+
+       BoundingBox<T, D-1> base_bbox(bbox.get_minimum_point().template slice<D-1>(0), bbox.get_maximum_point().template slice<D-1>(0));
+       Coverage coverage = base->get_coverage(base_bbox);
+       if(coverage==NO_COVERAGE)
+               return NO_COVERAGE;
+
+       if(bbox.get_minimum_coordinate(D-1)<-half_length || bbox.get_maximum_coordinate(D-1)>half_length)
+               return PARTIAL_COVERAGE;
+       else
+               return coverage;
+}
+
 } // namespace Geometry
 } // namespace Msp
 

diff --git a/source/geometry/halfspace.h b/source/geometry/halfspace.h
index b439851bd5adaf3a7067c7f91f5bf8308bb01166..09ec62ce600b9258b1044a0113a61251f5c424aa 100644 (file)
--- a/source/geometry/halfspace.h
+++ b/source/geometry/halfspace.h
@@ -28,6 +28,7 @@ public:
        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;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
 };
 
 template<typename T, unsigned D>
@@ -85,6 +86,25 @@ inline unsigned HalfSpace<T, D>::get_intersections(const Ray<T, D> &ray, Surface
        return 0;
 }
 
+template<typename T, unsigned D>
+inline Coverage HalfSpace<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+       LinAl::Vector<T, D> low_point;
+       LinAl::Vector<T, D> high_point;
+       for(unsigned i=0; i<D; ++i)
+       {
+               low_point[i] = (normal[i]>=T(0) ? bbox.get_minimum_coordinate(i) : bbox.get_maximum_coordinate(i));
+               high_point[i] = (normal[i]>=T(0) ? bbox.get_maximum_coordinate(i) : bbox.get_minimum_coordinate(i));
+       }
+
+       if(contains(high_point))
+               return FULL_COVERAGE;
+       else if(contains(low_point))
+               return PARTIAL_COVERAGE;
+       else
+               return NO_COVERAGE;
+}
+
 } // namespace Geometry
 } // namespace Msp
 

diff --git a/source/geometry/hyperbox.h b/source/geometry/hyperbox.h
index b9fad33d620d205f1a5043e002cb88556cbc6e32..c3bac57d97e3464d20535a66928106079777801a 100644 (file)
--- a/source/geometry/hyperbox.h
+++ b/source/geometry/hyperbox.h
@@ -33,6 +33,7 @@ public:
        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;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
 };
 
 template<typename T, unsigned D>
@@ -139,6 +140,25 @@ inline unsigned HyperBox<T, D>::get_intersections(const Ray<T, D> &ray, SurfaceP
        return n;
 }
 
+template<typename T, unsigned D>
+inline Coverage HyperBox<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+       const LinAl::Vector<T, D> &min_pt = bbox.get_minimum_point();
+       const LinAl::Vector<T, D> &max_pt = bbox.get_maximum_point();
+       LinAl::Vector<T, D> half_dim = dimensions/T(2);
+
+       Coverage coverage = FULL_COVERAGE;
+       for(unsigned i=0; i<D; ++i)
+       {
+               if(max_pt[i]<-half_dim[i] || min_pt[i]>half_dim[i])
+                       return NO_COVERAGE;
+               if(min_pt[i]<-half_dim[i] || max_pt[i]>half_dim[i])
+                       coverage = PARTIAL_COVERAGE;
+       }
+
+       return coverage;
+}
+
 } // namespace Geometry
 } // namespace Msp
 

diff --git a/source/geometry/hypersphere.h b/source/geometry/hypersphere.h
index 6bb4352f4016840ca331ebfd2034f35a7090e7d2..8f21db1d78f40689cda50c40d7ccd18cb3aa93b8 100644 (file)
--- a/source/geometry/hypersphere.h
+++ b/source/geometry/hypersphere.h
@@ -31,6 +31,7 @@ public:
        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;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
 };
 
 template<typename T, unsigned D>
@@ -95,6 +96,41 @@ inline unsigned HyperSphere<T, D>::get_intersections(const Ray<T, D> &ray, Surfa
        return n;
 }
 
+template<typename T, unsigned D>
+inline Coverage HyperSphere<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+       const LinAl::Vector<T, D> &min_pt = bbox.get_minimum_point();
+       const LinAl::Vector<T, D> &max_pt = bbox.get_maximum_point();
+
+       LinAl::Vector<T, D> far_point;
+       for(unsigned i=0; i<D; ++i)
+               far_point[i] = std::max(std::abs(min_pt[i]), std::abs(max_pt[i]));
+
+       if(contains(far_point))
+               return FULL_COVERAGE;
+
+       unsigned spanned_dimensions = 0;
+       for(unsigned i=0; i<D; ++i)
+               if(min_pt[i]<T(0) && max_pt[i]>T(0))
+                       spanned_dimensions |= 1<<i;
+
+       for(unsigned i=0; i<(1<<D); ++i)
+       {
+               if(i&spanned_dimensions)
+                       continue;
+
+               LinAl::Vector<T, D> point;
+               for(unsigned j=0; j<D; ++j)
+                       if(!((spanned_dimensions>>j)&1))
+                               point[j] = ((i>>j)&1 ? max_pt[j] : min_pt[j]);
+
+               if(contains(point))
+                       return PARTIAL_COVERAGE;
+       }
+
+       return NO_COVERAGE;
+}
+
 } // namespace Geometry
 } // namespace Msp
 

diff --git a/source/geometry/negation.h b/source/geometry/negation.h
index 8e2b3f41a6d7c30681026176330d0ed1a04d965e..d90c4deb5a7de767b2f36cb0ed165d53f8a5c851 100644 (file)
--- a/source/geometry/negation.h
+++ b/source/geometry/negation.h
@@ -30,6 +30,7 @@ public:
        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;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
 };
 
 template<typename T, unsigned D>
@@ -86,6 +87,18 @@ inline unsigned Negation<T, D>::get_intersections(const Ray<T, D> &ray, SurfaceP
        return count;
 }
 
+template<typename T, unsigned D>
+inline Coverage Negation<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+       Coverage coverage = shape->get_coverage(bbox);
+       if(coverage==FULL_COVERAGE)
+               return NO_COVERAGE;
+       else if(coverage==NO_COVERAGE)
+               return FULL_COVERAGE;
+       else
+               return PARTIAL_COVERAGE;
+}
+
 } // namespace Geometry
 } // namespace Msp
 

diff --git a/source/geometry/shape.h b/source/geometry/shape.h
index 22b18876620657e9f2858ea568196cc66a2d3f9c..ded8f13d8b7464b896e8d0510fe8146de2e68a85 100644 (file)
--- a/source/geometry/shape.h
+++ b/source/geometry/shape.h
@@ -10,6 +10,13 @@
 namespace Msp {
 namespace Geometry {
 
+enum Coverage
+{
+       NO_COVERAGE,
+       PARTIAL_COVERAGE,
+       FULL_COVERAGE
+};
+
 /**
 Base class and interface for geometric shapes.  Shapes may be bounded or
 unbounded.  They are always considered to be solid, i.e. have a distinct inside
@@ -31,6 +38,7 @@ public:
        virtual unsigned get_max_ray_intersections() const = 0;
        virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const = 0;
        std::vector<SurfacePoint<T, D> > get_intersections(const Ray<T, D> &) const;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const = 0;
 };
 
 template<typename T, unsigned D>

diff --git a/source/geometry/transformedshape.h b/source/geometry/transformedshape.h
index 6a14b0b75a1951f69a72cc9c3034fb56161dfc49..91790fc77276fd8aedbb75f318b856d775334cd2 100644 (file)
--- a/source/geometry/transformedshape.h
+++ b/source/geometry/transformedshape.h
@@ -33,6 +33,7 @@ public:
        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;
+       virtual Coverage get_coverage(const BoundingBox<T, D> &) const;
 };
 
 template<typename T, unsigned D>
@@ -102,6 +103,12 @@ inline unsigned TransformedShape<T, D>::get_intersections(const Ray<T, D> &ray,
        return count;
 }
 
+template<typename T, unsigned D>
+inline Coverage TransformedShape<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+       return shape->get_coverage(inverse_trans.transform(bbox));
+}
+
 } // namespace Geometry
 } // namespace Msp