Optimize bounding box bisection with more early culling

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

diff --git a/source/geometry/transformedshape.h b/source/geometry/transformedshape.h
index f214e4bb1aa9c578308088f2475879debc726378..9387123508dcf081341c076f8c4e41970a10ead0 100644 (file)
--- a/source/geometry/transformedshape.h
+++ b/source/geometry/transformedshape.h
@@ -29,13 +29,11 @@ public:
        const Shape<T, D> &get_shape() const { return *shape; }
        const AffineTransformation<T, D> &get_transformation() const { return transformation; }
 
-       virtual BoundingBox<T, D> get_axis_aligned_bounding_box() const;
+       virtual BoundingBox<T, D> get_axis_aligned_bounding_box(unsigned = 0) const;
        virtual bool contains(const LinAl::Vector<T, D> &) const;
-private:
-       Ray<T, D> make_local_ray(const Ray<T, D> &) const;
-public:
        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>
@@ -74,36 +72,12 @@ inline TransformedShape<T, D> *TransformedShape<T, D>::clone() const
 }
 
 template<typename T, unsigned D>
-inline BoundingBox<T, D> TransformedShape<T, D>::get_axis_aligned_bounding_box() const
+inline BoundingBox<T, D> TransformedShape<T, D>::get_axis_aligned_bounding_box(unsigned detail) const
 {
-       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));
+       if(detail)
+               return this->bisect_axis_aligned_bounding_box(detail);
 
-               point = transformation.transform(point);
-
-               if(i==0)
-               {
-                       min_pt = point;
-                       max_pt = point;
-               }
-               else
-               {
-                       for(unsigned j=0; j<D; ++j)
-                       {
-                               min_pt[j] = std::min(min_pt[j], point[j]);
-                               max_pt[j] = std::max(max_pt[j], point[j]);
-                       }
-               }
-       }
-
-       return BoundingBox<T, D>(min_pt, max_pt);
+       return transformation.transform(shape->get_axis_aligned_bounding_box());
 }
 
 template<typename T, unsigned D>
@@ -112,18 +86,10 @@ inline bool TransformedShape<T, D>::contains(const LinAl::Vector<T, D> &point) c
        return shape->contains(inverse_trans.transform(point));
 }
 
-template<typename T, unsigned D>
-inline Ray<T, D> TransformedShape<T, D>::make_local_ray(const Ray<T, D> &ray) const
-{
-       LinAl::Vector<T, D> local_dir = inverse_trans.transform_linear(ray.get_direction());
-       float distortion = local_dir.norm();
-       return Ray<T, D>(inverse_trans.transform(ray.get_start()), local_dir, ray.get_limit()*distortion);
-}
-
 template<typename T, unsigned D>
 inline unsigned TransformedShape<T, D>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
 {
-       Ray<T, D> local_ray = make_local_ray(ray);
+       Ray<T, D> local_ray = inverse_trans.transform(ray);
 
        unsigned count = shape->get_intersections(local_ray, points, size);
        if(points)
@@ -140,6 +106,35 @@ 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
+{
+       BoundingBox<T, D> local_bbox = inverse_trans.transform(bbox);
+       Coverage coverage = shape->get_coverage(local_bbox);
+       if(coverage==PARTIAL_COVERAGE)
+       {
+               BoundingBox<T, D> outer_bbox = transformation.transform(local_bbox);
+               LinAl::Vector<T, D> min_pt = local_bbox.get_minimum_point();
+               LinAl::Vector<T, D> max_pt = local_bbox.get_maximum_point();
+               for(unsigned i=0; i<D; ++i)
+               {
+                       T scale_ratio = (1-bbox.get_dimension(i)/outer_bbox.get_dimension(i))*local_bbox.get_dimension(i);
+                       T low_gap = bbox.get_minimum_coordinate(i)-outer_bbox.get_minimum_coordinate(i);
+                       T high_gap = outer_bbox.get_maximum_coordinate(i)-bbox.get_maximum_coordinate(i);
+                       min_pt[i] += low_gap*scale_ratio;
+                       max_pt[i] -= high_gap-scale_ratio;
+               }
+
+               local_bbox = BoundingBox<T, D>(min_pt, max_pt);
+               if(shape->get_coverage(local_bbox)>=PARTIAL_COVERAGE)
+                       return PARTIAL_COVERAGE;
+               else
+                       return UNCERTAIN_COVERAGE;
+       }
+       else
+               return coverage;
+}
+
 } // namespace Geometry
 } // namespace Msp