Use the coverage function to calculate tighter bounding boxes

[libs/math.git] / source / geometry / shape.h

diff --git a/source/geometry/shape.h b/source/geometry/shape.h
index 1f8176418a4e9a948b460701e6e682d56ae31771..074c11b7289665fa88786aa43b5a4343c06e0741 100644 (file)
--- a/source/geometry/shape.h
+++ b/source/geometry/shape.h
@@ -1,41 +1,129 @@
 #ifndef MSP_GEOMETRY_SHAPE_H_
 #define MSP_GEOMETRY_SHAPE_H_
 
+#include <list>
 #include <vector>
 #include <msp/linal/vector.h>
+#include "boundingbox.h"
+#include "ray.h"
+#include "surfacepoint.h"
 
 namespace Msp {
 namespace Geometry {
 
-template<typename T, unsigned D>
-class HyperBox;
-
-template<typename T, unsigned D>
-class Ray;
-
-template<typename T, unsigned D>
-class SurfacePoint;
+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
+and an outside.
+*/
 template<typename T, unsigned D>
 class Shape
 {
 protected:
+       struct CoverageCell
+       {
+               unsigned level;
+               BoundingBox<T, D> bounding_box;
+               Coverage coverage;
+       };
+
        Shape() { }
 public:
        virtual ~Shape() { }
 
        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(unsigned detail = 0) const = 0;
+protected:
+       BoundingBox<T, D> bisect_axis_aligned_bounding_box(unsigned) const;
+public:
        virtual bool contains(const LinAl::Vector<T, D> &) const = 0;
-       virtual bool check_intersection(const Ray<T, D> &) const = 0;
+       bool check_intersection(const Ray<T, D> &) const;
        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>
-std::vector<SurfacePoint<T, D> > Shape<T, D>::get_intersections(const Ray<T, D> &ray) const
+inline BoundingBox<T, D> Shape<T, D>::bisect_axis_aligned_bounding_box(unsigned detail) const
+{
+       if(!detail)
+               throw std::invalid_argument("Shape::bisect_axis_aligned_bounding_box");
+
+       std::list<CoverageCell> queue;
+       queue.push_back(CoverageCell());
+       CoverageCell &root = queue.front();
+       root.level = 0;
+       root.bounding_box = get_axis_aligned_bounding_box();
+       if(root.bounding_box.is_space())
+               return root.bounding_box;
+
+       root.coverage = get_coverage(root.bounding_box);
+       if(root.coverage==FULL_COVERAGE)
+               return root.bounding_box;
+
+       LinAl::Vector<T, D> tight_min_pt = root.bounding_box.get_maximum_point();
+       LinAl::Vector<T, D> tight_max_pt = root.bounding_box.get_minimum_point();
+
+       while(!queue.empty())
+       {
+               CoverageCell &cell = queue.front();
+
+               const LinAl::Vector<T, D> &min_pt = cell.bounding_box.get_minimum_point();
+               const LinAl::Vector<T, D> &max_pt = cell.bounding_box.get_maximum_point();
+               LinAl::Vector<T, D> center = (min_pt+max_pt)/T(2);
+
+               for(unsigned i=0; i<(1<<D); ++i)
+               {
+                       CoverageCell child;
+                       child.level = cell.level+1;
+
+                       LinAl::Vector<T, D> child_min_pt = min_pt;
+                       LinAl::Vector<T, D> child_max_pt = max_pt;
+                       for(unsigned j=0; j<D; ++j)
+                       {
+                               if((i>>j)&1)
+                                       child_min_pt[j] = center[j];
+                               else
+                                       child_max_pt[j] = center[j];
+                       }
+                       child.bounding_box = BoundingBox<T, D>(child_min_pt, child_max_pt);
+
+                       child.coverage = get_coverage(child.bounding_box);
+                       if(child.coverage==FULL_COVERAGE || (child.level==detail && child.coverage!=NO_COVERAGE))
+                       {
+                               for(unsigned j=0; j<D; ++j)
+                               {
+                                       tight_min_pt[j] = std::min(tight_min_pt[j], child_min_pt[j]);
+                                       tight_max_pt[j] = std::max(tight_max_pt[j], child_max_pt[j]);
+                               }
+                       }
+                       else if(child.coverage==PARTIAL_COVERAGE)
+                               queue.push_back(child);
+               }
+
+               queue.pop_front();
+       }
+
+       return BoundingBox<T, D>(tight_min_pt, tight_max_pt);
+}
+
+template<typename T, unsigned D>
+inline bool Shape<T, D>::check_intersection(const Ray<T, D> &ray) const
+{
+       return get_intersections(ray, 0, 1);
+}
+
+template<typename T, unsigned D>
+inline std::vector<SurfacePoint<T, D> > Shape<T, D>::get_intersections(const Ray<T, D> &ray) const
 {
        unsigned max_isect = get_max_ray_intersections();
        std::vector<SurfacePoint<T, D> > points(max_isect);