From 2826730b5d68d1ad74dc6363af43ca796f96caa2 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Tue, 18 Apr 2017 14:16:45 +0300 Subject: [PATCH] Optimize bounding box bisection with more early culling --- source/geometry/boundingbox.h | 3 +++ source/geometry/compositeshape.h | 6 ++++-- source/geometry/intersection.h | 1 + source/geometry/negation.h | 2 +- source/geometry/shape.h | 28 +++++++++++++++++++++++++--- source/geometry/transformedshape.h | 25 ++++++++++++++++++++++++- source/geometry/union.h | 1 + 7 files changed, 59 insertions(+), 7 deletions(-) diff --git a/source/geometry/boundingbox.h b/source/geometry/boundingbox.h index ac384ec..4ae2935 100644 --- a/source/geometry/boundingbox.h +++ b/source/geometry/boundingbox.h @@ -27,6 +27,9 @@ public: T get_minimum_coordinate(unsigned i) const { return min_pt[i]; } const LinAl::Vector &get_maximum_point() const { return max_pt; } T get_maximum_coordinate(unsigned i) const { return max_pt[i]; } + LinAl::Vector get_dimensions() const { return max_pt-min_pt; } + T get_dimension(unsigned i) const { return max_pt[i]-min_pt[i]; } + bool is_empty() const { return empty && !negated; } bool is_space() const { return empty && negated; } bool is_negated() const { return negated; } diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h index 5d0cd8c..c472b43 100644 --- a/source/geometry/compositeshape.h +++ b/source/geometry/compositeshape.h @@ -201,10 +201,12 @@ inline Coverage CompositeShape::get_coverage(const BoundingBox &b 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)) + if(i==shapes.begin()) coverage = c; + else + coverage = Ops::combine_coverage(coverage, c); - if(coverage!=PARTIAL_COVERAGE && Ops::shortcircuit(coverage==FULL_COVERAGE)) + if((coverage==NO_COVERAGE && Ops::shortcircuit(false)) || (coverage==FULL_COVERAGE && Ops::shortcircuit(true))) break; } diff --git a/source/geometry/intersection.h b/source/geometry/intersection.h index 0e555b0..24e668d 100644 --- a/source/geometry/intersection.h +++ b/source/geometry/intersection.h @@ -10,6 +10,7 @@ template struct IntersectionOps { static BoundingBox combine_aabb(const BoundingBox &a, const BoundingBox &b) { return a&b; } + static Coverage combine_coverage(Coverage a, Coverage b) { return ((a==PARTIAL_COVERAGE && b==a) ? UNCERTAIN_COVERAGE : std::min(a, b)); } static bool shortcircuit(bool c) { return !c; } }; diff --git a/source/geometry/negation.h b/source/geometry/negation.h index 91802f8..60b92e3 100644 --- a/source/geometry/negation.h +++ b/source/geometry/negation.h @@ -96,7 +96,7 @@ inline Coverage Negation::get_coverage(const BoundingBox &bbox) cons else if(coverage==NO_COVERAGE) return FULL_COVERAGE; else - return PARTIAL_COVERAGE; + return coverage; } } // namespace Geometry diff --git a/source/geometry/shape.h b/source/geometry/shape.h index 8eb3157..920e456 100644 --- a/source/geometry/shape.h +++ b/source/geometry/shape.h @@ -14,6 +14,7 @@ namespace Geometry { enum Coverage { NO_COVERAGE, + UNCERTAIN_COVERAGE, PARTIAL_COVERAGE, FULL_COVERAGE }; @@ -96,6 +97,17 @@ inline BoundingBox Shape::bisect_axis_aligned_bounding_box(unsigned const LinAl::Vector &min_pt = cell.bounding_box.get_minimum_point(); const LinAl::Vector &max_pt = cell.bounding_box.get_maximum_point(); + + // Skip cells that are already fully inside the established bounds. + bool internal = true; + for(unsigned i=0; (i=tight_min_pt[i] && max_pt[i]<=tight_max_pt[i]); + if(internal) + { + queue.pop_front(); + continue; + } + LinAl::Vector center = (min_pt+max_pt)/T(2); // Bisect each dimension. @@ -118,9 +130,8 @@ inline BoundingBox Shape::bisect_axis_aligned_bounding_box(unsigned child.coverage = get_coverage(child.bounding_box); if(child.coverage==FULL_COVERAGE || (child.level==detail && child.coverage!=NO_COVERAGE)) { - /* Adjust the bounds when we are certain that it's covered by at - least part of the shape. Also adjust for uncertain results if - we're on the last level. */ + /* Immediately merge cells with full coverage. Also merge cells + at the last level. */ for(unsigned j=0; j Shape::bisect_axis_aligned_bounding_box(unsigned } } else if(child.coverage==PARTIAL_COVERAGE) + { + /* Merge cells with confirmed partial coverage so the cell is + left just outside the bounding box. */ + for(unsigned j=0; j::get_intersections(const Ray &ray, template inline Coverage TransformedShape::get_coverage(const BoundingBox &bbox) const { - return shape->get_coverage(inverse_trans.transform(bbox)); + BoundingBox local_bbox = inverse_trans.transform(bbox); + Coverage coverage = shape->get_coverage(local_bbox); + if(coverage==PARTIAL_COVERAGE) + { + BoundingBox outer_bbox = transformation.transform(local_bbox); + LinAl::Vector min_pt = local_bbox.get_minimum_point(); + LinAl::Vector max_pt = local_bbox.get_maximum_point(); + for(unsigned i=0; i(min_pt, max_pt); + if(shape->get_coverage(local_bbox)>=PARTIAL_COVERAGE) + return PARTIAL_COVERAGE; + else + return UNCERTAIN_COVERAGE; + } + else + return coverage; } } // namespace Geometry diff --git a/source/geometry/union.h b/source/geometry/union.h index 738f1f2..8c02f2b 100644 --- a/source/geometry/union.h +++ b/source/geometry/union.h @@ -10,6 +10,7 @@ template struct UnionOps { static BoundingBox combine_aabb(const BoundingBox &a, const BoundingBox &b) { return a|b; } + static Coverage combine_coverage(Coverage a, Coverage b) { return std::max(a, b); } static bool shortcircuit(bool c) { return c; } }; -- 2.43.0