From 44bd1d1ab256d397be4e2169c4ca5efdd0569d31 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Tue, 18 Apr 2017 09:10:55 +0300 Subject: [PATCH] Use the coverage function to calculate tighter bounding boxes --- source/geometry/compositeshape.h | 7 ++- source/geometry/extrudedshape.h | 6 +-- source/geometry/halfspace.h | 4 +- source/geometry/hyperbox.h | 4 +- source/geometry/hypersphere.h | 4 +- source/geometry/negation.h | 6 +-- source/geometry/shape.h | 77 +++++++++++++++++++++++++++++- source/geometry/transformedshape.h | 7 ++- 8 files changed, 98 insertions(+), 17 deletions(-) diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h index 00ae55d..5d0cd8c 100644 --- a/source/geometry/compositeshape.h +++ b/source/geometry/compositeshape.h @@ -34,7 +34,7 @@ protected: public: virtual ~CompositeShape(); - virtual BoundingBox get_axis_aligned_bounding_box() const; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned = 0) const; virtual bool contains(const LinAl::Vector &) const; virtual unsigned get_max_ray_intersections() const { return max_isect; } virtual unsigned get_intersections(const Ray &, SurfacePoint *, unsigned) const; @@ -100,8 +100,11 @@ inline CompositeShape::~CompositeShape() } template -inline BoundingBox CompositeShape::get_axis_aligned_bounding_box() const +inline BoundingBox CompositeShape::get_axis_aligned_bounding_box(unsigned detail) const { + if(detail) + return this->bisect_axis_aligned_bounding_box(detail); + BoundingBox aabb; for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i) { diff --git a/source/geometry/extrudedshape.h b/source/geometry/extrudedshape.h index e702f90..fd4597b 100644 --- a/source/geometry/extrudedshape.h +++ b/source/geometry/extrudedshape.h @@ -31,7 +31,7 @@ public: const Shape &get_base() const { return *base; } T get_length() const { return length; } - virtual BoundingBox get_axis_aligned_bounding_box() const; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned = 0) const; virtual bool contains(const LinAl::Vector &) const; virtual unsigned get_max_ray_intersections() const; virtual unsigned get_intersections(const Ray &, SurfacePoint *, unsigned) const; @@ -75,9 +75,9 @@ inline ExtrudedShape *ExtrudedShape::clone() const } template -inline BoundingBox ExtrudedShape::get_axis_aligned_bounding_box() const +inline BoundingBox ExtrudedShape::get_axis_aligned_bounding_box(unsigned detail) const { - BoundingBox base_bbox = base->get_axis_aligned_bounding_box(); + BoundingBox base_bbox = base->get_axis_aligned_bounding_box(detail); T half_length = length/T(2); return BoundingBox(compose(base_bbox.get_minimum_point(), -half_length), compose(base_bbox.get_maximum_point(), half_length)); diff --git a/source/geometry/halfspace.h b/source/geometry/halfspace.h index 09ec62c..9fdcdad 100644 --- a/source/geometry/halfspace.h +++ b/source/geometry/halfspace.h @@ -24,7 +24,7 @@ public: const LinAl::Vector &get_normal() const { return normal; } - virtual BoundingBox get_axis_aligned_bounding_box() const; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned = 0) const; virtual bool contains(const LinAl::Vector &) const; virtual unsigned get_max_ray_intersections() const { return 1; } virtual unsigned get_intersections(const Ray &, SurfacePoint *, unsigned) const; @@ -49,7 +49,7 @@ inline HalfSpace *HalfSpace::clone() const } template -inline BoundingBox HalfSpace::get_axis_aligned_bounding_box() const +inline BoundingBox HalfSpace::get_axis_aligned_bounding_box(unsigned) const { // XXX If the normal is aligned to an axis, should the bounding box reflect that? return ~BoundingBox(); diff --git a/source/geometry/hyperbox.h b/source/geometry/hyperbox.h index c3bac57..e3236e8 100644 --- a/source/geometry/hyperbox.h +++ b/source/geometry/hyperbox.h @@ -29,7 +29,7 @@ public: const LinAl::Vector &get_dimensions() const { return dimensions; } T get_dimension(unsigned) const; - virtual BoundingBox get_axis_aligned_bounding_box() const; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned = 0) const; virtual bool contains(const LinAl::Vector &) const; virtual unsigned get_max_ray_intersections() const { return 2; } virtual unsigned get_intersections(const Ray &, SurfacePoint *, unsigned) const; @@ -65,7 +65,7 @@ inline T HyperBox::get_dimension(unsigned i) const } template -inline BoundingBox HyperBox::get_axis_aligned_bounding_box() const +inline BoundingBox HyperBox::get_axis_aligned_bounding_box(unsigned) const { LinAl::Vector half_dim = dimensions/T(2); return BoundingBox(-half_dim, half_dim); diff --git a/source/geometry/hypersphere.h b/source/geometry/hypersphere.h index 8f21db1..13e4278 100644 --- a/source/geometry/hypersphere.h +++ b/source/geometry/hypersphere.h @@ -27,7 +27,7 @@ public: T get_radius() const { return radius; } - virtual BoundingBox get_axis_aligned_bounding_box() const; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned = 0) const; virtual bool contains(const LinAl::Vector &) const; virtual unsigned get_max_ray_intersections() const { return 2; } virtual unsigned get_intersections(const Ray &, SurfacePoint *, unsigned) const; @@ -49,7 +49,7 @@ inline HyperSphere *HyperSphere::clone() const } template -inline BoundingBox HyperSphere::get_axis_aligned_bounding_box() const +inline BoundingBox HyperSphere::get_axis_aligned_bounding_box(unsigned) const { LinAl::Vector extent; for(unsigned i=0; i &get_shape() const { return *shape; } - virtual BoundingBox get_axis_aligned_bounding_box() const; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned = 0) const; virtual bool contains(const LinAl::Vector &) const; virtual unsigned get_max_ray_intersections() const { return shape->get_max_ray_intersections(); } virtual unsigned get_intersections(const Ray &, SurfacePoint *, unsigned) const; @@ -64,9 +64,9 @@ inline Negation *Negation::clone() const } template -inline BoundingBox Negation::get_axis_aligned_bounding_box() const +inline BoundingBox Negation::get_axis_aligned_bounding_box(unsigned detail) const { - return ~shape->get_axis_aligned_bounding_box(); + return ~shape->get_axis_aligned_bounding_box(detail); } template diff --git a/source/geometry/shape.h b/source/geometry/shape.h index ded8f13..074c11b 100644 --- a/source/geometry/shape.h +++ b/source/geometry/shape.h @@ -1,6 +1,7 @@ #ifndef MSP_GEOMETRY_SHAPE_H_ #define MSP_GEOMETRY_SHAPE_H_ +#include #include #include #include "boundingbox.h" @@ -26,13 +27,23 @@ template class Shape { protected: + struct CoverageCell + { + unsigned level; + BoundingBox bounding_box; + Coverage coverage; + }; + Shape() { } public: virtual ~Shape() { } virtual Shape *clone() const = 0; - virtual BoundingBox get_axis_aligned_bounding_box() const = 0; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned detail = 0) const = 0; +protected: + BoundingBox bisect_axis_aligned_bounding_box(unsigned) const; +public: virtual bool contains(const LinAl::Vector &) const = 0; bool check_intersection(const Ray &) const; virtual unsigned get_max_ray_intersections() const = 0; @@ -41,6 +52,70 @@ public: virtual Coverage get_coverage(const BoundingBox &) const = 0; }; +template +inline BoundingBox Shape::bisect_axis_aligned_bounding_box(unsigned detail) const +{ + if(!detail) + throw std::invalid_argument("Shape::bisect_axis_aligned_bounding_box"); + + std::list 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 tight_min_pt = root.bounding_box.get_maximum_point(); + LinAl::Vector tight_max_pt = root.bounding_box.get_minimum_point(); + + while(!queue.empty()) + { + CoverageCell &cell = queue.front(); + + const LinAl::Vector &min_pt = cell.bounding_box.get_minimum_point(); + const LinAl::Vector &max_pt = cell.bounding_box.get_maximum_point(); + LinAl::Vector center = (min_pt+max_pt)/T(2); + + for(unsigned i=0; i<(1< child_min_pt = min_pt; + LinAl::Vector child_max_pt = max_pt; + for(unsigned j=0; j>j)&1) + child_min_pt[j] = center[j]; + else + child_max_pt[j] = center[j]; + } + child.bounding_box = BoundingBox(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(tight_min_pt, tight_max_pt); +} + template inline bool Shape::check_intersection(const Ray &ray) const { diff --git a/source/geometry/transformedshape.h b/source/geometry/transformedshape.h index 91790fc..002f3c1 100644 --- a/source/geometry/transformedshape.h +++ b/source/geometry/transformedshape.h @@ -29,7 +29,7 @@ public: const Shape &get_shape() const { return *shape; } const AffineTransformation &get_transformation() const { return transformation; } - virtual BoundingBox get_axis_aligned_bounding_box() const; + virtual BoundingBox get_axis_aligned_bounding_box(unsigned = 0) const; virtual bool contains(const LinAl::Vector &) const; virtual unsigned get_max_ray_intersections() const { return shape->get_max_ray_intersections(); } virtual unsigned get_intersections(const Ray &, SurfacePoint *, unsigned) const; @@ -72,8 +72,11 @@ inline TransformedShape *TransformedShape::clone() const } template -inline BoundingBox TransformedShape::get_axis_aligned_bounding_box() const +inline BoundingBox TransformedShape::get_axis_aligned_bounding_box(unsigned detail) const { + if(detail) + return this->bisect_axis_aligned_bounding_box(detail); + return transformation.transform(shape->get_axis_aligned_bounding_box()); } -- 2.45.2