X-Git-Url: http://git.tdb.fi/?p=libs%2Fmath.git;a=blobdiff_plain;f=source%2Fgeometry%2Fshape.h;h=920e4560454799d7828a50a9601e3ad4ba2295b7;hp=8eb3157a17a19237779838e22efa46c97a67b142;hb=2826730b5d68d1ad74dc6363af43ca796f96caa2;hpb=99ad80a76d53d090ddf602c085d80b675609b8ba

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<T, D> Shape<T, D>::bisect_axis_aligned_bounding_box(unsigned
 
 		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();
+
+		// Skip cells that are already fully inside the established bounds.
+		bool internal = true;
+		for(unsigned i=0; (i<D && internal); ++i)
+			internal = (min_pt[i]>=tight_min_pt[i] && max_pt[i]<=tight_max_pt[i]);
+		if(internal)
+		{
+			queue.pop_front();
+			continue;
+		}
+
 		LinAl::Vector<T, D> center = (min_pt+max_pt)/T(2);
 
 		// Bisect each dimension.
@@ -118,9 +130,8 @@ inline BoundingBox<T, D> Shape<T, D>::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<D; ++j)
 				{
 					tight_min_pt[j] = std::min(tight_min_pt[j], child_min_pt[j]);
@@ -128,6 +139,17 @@ inline BoundingBox<T, D> Shape<T, D>::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<D; ++j)
+				{
+					tight_min_pt[j] = std::min(tight_min_pt[j], child_max_pt[j]);
+					tight_max_pt[j] = std::max(tight_max_pt[j], child_min_pt[j]);
+				}
+			}
+
+			if(child.level<detail && child.coverage!=NO_COVERAGE && child.coverage!=FULL_COVERAGE)
 				queue.push_back(child);
 		}