From a29d2c17ca70a3ed5df1e863c92ccd851d5dba6b Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Tue, 18 Apr 2017 09:04:02 +0300
Subject: [PATCH] Add a function to test whether a shapes covers a bounding box

---
 source/geometry/compositeshape.h   | 18 +++++++++++++++
 source/geometry/extrudedshape.h    | 19 ++++++++++++++++
 source/geometry/halfspace.h        | 20 +++++++++++++++++
 source/geometry/hyperbox.h         | 20 +++++++++++++++++
 source/geometry/hypersphere.h      | 36 ++++++++++++++++++++++++++++++
 source/geometry/negation.h         | 13 +++++++++++
 source/geometry/shape.h            |  8 +++++++
 source/geometry/transformedshape.h |  7 ++++++
 8 files changed, 141 insertions(+)

diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
index e9aeadc..00ae55d 100644
--- a/source/geometry/compositeshape.h
+++ b/source/geometry/compositeshape.h
@@ -38,6 +38,7 @@ public:
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const { return max_isect; }
 	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, typename O>
@@ -190,6 +191,23 @@ inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray,
 	return n;
 }
 
+template<typename T, unsigned D, typename O>
+inline Coverage CompositeShape<T, D, O>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+	Coverage coverage = NO_COVERAGE;
+	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))
+			coverage = c;
+
+		if(coverage!=PARTIAL_COVERAGE && Ops::shortcircuit(coverage==FULL_COVERAGE))
+			break;
+	}
+
+	return coverage;
+}
+
 } // namespace Geometry
 } // namespace Msp
 
diff --git a/source/geometry/extrudedshape.h b/source/geometry/extrudedshape.h
index 78dfa49..e702f90 100644
--- a/source/geometry/extrudedshape.h
+++ b/source/geometry/extrudedshape.h
@@ -35,6 +35,7 @@ public:
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const;
 	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>
@@ -187,6 +188,24 @@ inline unsigned ExtrudedShape<T, D>::get_intersections(const Ray<T, D> &ray, Sur
 	return n;
 }
 
+template<typename T, unsigned D>
+inline Coverage ExtrudedShape<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+	T half_length = length/T(2);
+	if(bbox.get_maximum_coordinate(D-1)<-half_length || bbox.get_minimum_coordinate(D-1)>half_length)
+		return NO_COVERAGE;
+
+	BoundingBox<T, D-1> base_bbox(bbox.get_minimum_point().template slice<D-1>(0), bbox.get_maximum_point().template slice<D-1>(0));
+	Coverage coverage = base->get_coverage(base_bbox);
+	if(coverage==NO_COVERAGE)
+		return NO_COVERAGE;
+
+	if(bbox.get_minimum_coordinate(D-1)<-half_length || bbox.get_maximum_coordinate(D-1)>half_length)
+		return PARTIAL_COVERAGE;
+	else
+		return coverage;
+}
+
 } // namespace Geometry
 } // namespace Msp
 
diff --git a/source/geometry/halfspace.h b/source/geometry/halfspace.h
index b439851..09ec62c 100644
--- a/source/geometry/halfspace.h
+++ b/source/geometry/halfspace.h
@@ -28,6 +28,7 @@ public:
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const { return 1; }
 	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>
@@ -85,6 +86,25 @@ inline unsigned HalfSpace<T, D>::get_intersections(const Ray<T, D> &ray, Surface
 	return 0;
 }
 
+template<typename T, unsigned D>
+inline Coverage HalfSpace<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+	LinAl::Vector<T, D> low_point;
+	LinAl::Vector<T, D> high_point;
+	for(unsigned i=0; i<D; ++i)
+	{
+		low_point[i] = (normal[i]>=T(0) ? bbox.get_minimum_coordinate(i) : bbox.get_maximum_coordinate(i));
+		high_point[i] = (normal[i]>=T(0) ? bbox.get_maximum_coordinate(i) : bbox.get_minimum_coordinate(i));
+	}
+
+	if(contains(high_point))
+		return FULL_COVERAGE;
+	else if(contains(low_point))
+		return PARTIAL_COVERAGE;
+	else
+		return NO_COVERAGE;
+}
+
 } // namespace Geometry
 } // namespace Msp
 
diff --git a/source/geometry/hyperbox.h b/source/geometry/hyperbox.h
index b9fad33..c3bac57 100644
--- a/source/geometry/hyperbox.h
+++ b/source/geometry/hyperbox.h
@@ -33,6 +33,7 @@ public:
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const { return 2; }
 	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>
@@ -139,6 +140,25 @@ inline unsigned HyperBox<T, D>::get_intersections(const Ray<T, D> &ray, SurfaceP
 	return n;
 }
 
+template<typename T, unsigned D>
+inline Coverage HyperBox<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+	const LinAl::Vector<T, D> &min_pt = bbox.get_minimum_point();
+	const LinAl::Vector<T, D> &max_pt = bbox.get_maximum_point();
+	LinAl::Vector<T, D> half_dim = dimensions/T(2);
+
+	Coverage coverage = FULL_COVERAGE;
+	for(unsigned i=0; i<D; ++i)
+	{
+		if(max_pt[i]<-half_dim[i] || min_pt[i]>half_dim[i])
+			return NO_COVERAGE;
+		if(min_pt[i]<-half_dim[i] || max_pt[i]>half_dim[i])
+			coverage = PARTIAL_COVERAGE;
+	}
+
+	return coverage;
+}
+
 } // namespace Geometry
 } // namespace Msp
 
diff --git a/source/geometry/hypersphere.h b/source/geometry/hypersphere.h
index 6bb4352..8f21db1 100644
--- a/source/geometry/hypersphere.h
+++ b/source/geometry/hypersphere.h
@@ -31,6 +31,7 @@ public:
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	virtual unsigned get_max_ray_intersections() const { return 2; }
 	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>
@@ -95,6 +96,41 @@ inline unsigned HyperSphere<T, D>::get_intersections(const Ray<T, D> &ray, Surfa
 	return n;
 }
 
+template<typename T, unsigned D>
+inline Coverage HyperSphere<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+	const LinAl::Vector<T, D> &min_pt = bbox.get_minimum_point();
+	const LinAl::Vector<T, D> &max_pt = bbox.get_maximum_point();
+
+	LinAl::Vector<T, D> far_point;
+	for(unsigned i=0; i<D; ++i)
+		far_point[i] = std::max(std::abs(min_pt[i]), std::abs(max_pt[i]));
+
+	if(contains(far_point))
+		return FULL_COVERAGE;
+
+	unsigned spanned_dimensions = 0;
+	for(unsigned i=0; i<D; ++i)
+		if(min_pt[i]<T(0) && max_pt[i]>T(0))
+			spanned_dimensions |= 1<<i;
+
+	for(unsigned i=0; i<(1<<D); ++i)
+	{
+		if(i&spanned_dimensions)
+			continue;
+
+		LinAl::Vector<T, D> point;
+		for(unsigned j=0; j<D; ++j)
+			if(!((spanned_dimensions>>j)&1))
+				point[j] = ((i>>j)&1 ? max_pt[j] : min_pt[j]);
+
+		if(contains(point))
+			return PARTIAL_COVERAGE;
+	}
+
+	return NO_COVERAGE;
+}
+
 } // namespace Geometry
 } // namespace Msp
 
diff --git a/source/geometry/negation.h b/source/geometry/negation.h
index 8e2b3f4..d90c4de 100644
--- a/source/geometry/negation.h
+++ b/source/geometry/negation.h
@@ -30,6 +30,7 @@ public:
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	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>
@@ -86,6 +87,18 @@ inline unsigned Negation<T, D>::get_intersections(const Ray<T, D> &ray, SurfaceP
 	return count;
 }
 
+template<typename T, unsigned D>
+inline Coverage Negation<T, D>::get_coverage(const BoundingBox<T, D> &bbox) const
+{
+	Coverage coverage = shape->get_coverage(bbox);
+	if(coverage==FULL_COVERAGE)
+		return NO_COVERAGE;
+	else if(coverage==NO_COVERAGE)
+		return FULL_COVERAGE;
+	else
+		return PARTIAL_COVERAGE;
+}
+
 } // namespace Geometry
 } // namespace Msp
 
diff --git a/source/geometry/shape.h b/source/geometry/shape.h
index 22b1887..ded8f13 100644
--- a/source/geometry/shape.h
+++ b/source/geometry/shape.h
@@ -10,6 +10,13 @@
 namespace Msp {
 namespace Geometry {
 
+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
@@ -31,6 +38,7 @@ public:
 	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>
diff --git a/source/geometry/transformedshape.h b/source/geometry/transformedshape.h
index 6a14b0b..91790fc 100644
--- a/source/geometry/transformedshape.h
+++ b/source/geometry/transformedshape.h
@@ -33,6 +33,7 @@ public:
 	virtual bool contains(const LinAl::Vector<T, D> &) const;
 	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>
@@ -102,6 +103,12 @@ 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
+{
+	return shape->get_coverage(inverse_trans.transform(bbox));
+}
+
 } // namespace Geometry
 } // namespace Msp
 
-- 
2.43.0