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

diff --git a/source/geometry/shape.h b/source/geometry/shape.h
index 528a77c..920e456 100644
--- a/source/geometry/shape.h
+++ b/source/geometry/shape.h
@@ -1,29 +1,180 @@
 #ifndef MSP_GEOMETRY_SHAPE_H_
 #define MSP_GEOMETRY_SHAPE_H_
 
+#include <list>
+#include <vector>
+#include <msp/linal/vector.h>
+#include "boundingbox.h"
+#include "ray.h"
+#include "surfacepoint.h"
+
 namespace Msp {
 namespace Geometry {
 
-template<typename T, unsigned D>
-class HyperBox;
-
-template<typename T, unsigned D>
-class Ray;
+enum Coverage
+{
+	NO_COVERAGE,
+	UNCERTAIN_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
+and an outside.
+*/
 template<typename T, unsigned D>
 class Shape
 {
 protected:
+	struct CoverageCell
+	{
+		unsigned level;
+		BoundingBox<T, D> bounding_box;
+		Coverage coverage;
+	};
+
 	Shape() { }
 public:
 	virtual ~Shape() { }
 
 	virtual Shape *clone() const = 0;
 
-	virtual HyperBox<T, D> get_axis_aligned_bounding_box() const = 0;
-	virtual bool check_intersection(const Ray<T, D> &) const = 0;
+	/** Returns the bounding box of the shape.  The detail parameter controls
+	the tightness of the box.  Higher detail will take more time to compute. */
+	virtual BoundingBox<T, D> get_axis_aligned_bounding_box(unsigned detail = 0) const = 0;
+protected:
+	BoundingBox<T, D> bisect_axis_aligned_bounding_box(unsigned) const;
+
+public:
+	/** Checks if a point is contained within the shape. */
+	virtual bool contains(const LinAl::Vector<T, D> &) const = 0;
+
+	bool check_intersection(const Ray<T, D> &) const;
+	virtual unsigned get_max_ray_intersections() const = 0;
+
+	/** Determines intersection points between the shape and a ray. */
+	virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const = 0;
+
+	/** Returns a vector with all of the intersections between the shape and a
+	ray. */
+	std::vector<SurfacePoint<T, D> > get_intersections(const Ray<T, D> &) const;
+
+	/** Determines whether the shape covers a bounding box. */
+	virtual Coverage get_coverage(const BoundingBox<T, D> &) const = 0;
 };
 
+template<typename T, unsigned D>
+inline BoundingBox<T, D> Shape<T, D>::bisect_axis_aligned_bounding_box(unsigned detail) const
+{
+	if(!detail)
+		throw std::invalid_argument("Shape::bisect_axis_aligned_bounding_box");
+
+	// Form the root cell from the loosest approximation of a bounding box.
+	std::list<CoverageCell> queue;
+	queue.push_back(CoverageCell());
+	CoverageCell &root = queue.front();
+	root.level = 0;
+	root.bounding_box = get_axis_aligned_bounding_box();
+	// There's no point bisecting if the bounding box fills the entire space.
+	if(root.bounding_box.is_space())
+		return root.bounding_box;
+
+	root.coverage = get_coverage(root.bounding_box);
+	// If the bounding box is fully covered it's already tight.
+	if(root.coverage==FULL_COVERAGE)
+		return root.bounding_box;
+
+	/* Initialize bounds to the opposite edges because we don't yet know which
+	part of the bounding box the shape occupies. */
+	LinAl::Vector<T, D> tight_min_pt = root.bounding_box.get_maximum_point();
+	LinAl::Vector<T, D> tight_max_pt = root.bounding_box.get_minimum_point();
+
+	while(!queue.empty())
+	{
+		CoverageCell &cell = queue.front();
+
+		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.
+		for(unsigned i=0; i<(1<<D); ++i)
+		{
+			CoverageCell child;
+			child.level = cell.level+1;
+
+			LinAl::Vector<T, D> child_min_pt = min_pt;
+			LinAl::Vector<T, D> child_max_pt = max_pt;
+			for(unsigned j=0; j<D; ++j)
+			{
+				if((i>>j)&1)
+					child_min_pt[j] = center[j];
+				else
+					child_max_pt[j] = center[j];
+			}
+			child.bounding_box = BoundingBox<T, D>(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))
+			{
+				/* 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]);
+					tight_max_pt[j] = std::max(tight_max_pt[j], child_max_pt[j]);
+				}
+			}
+			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);
+		}
+
+		queue.pop_front();
+	}
+
+	return BoundingBox<T, D>(tight_min_pt, tight_max_pt);
+}
+
+template<typename T, unsigned D>
+inline bool Shape<T, D>::check_intersection(const Ray<T, D> &ray) const
+{
+	return get_intersections(ray, 0, 1);
+}
+
+template<typename T, unsigned D>
+inline std::vector<SurfacePoint<T, D> > Shape<T, D>::get_intersections(const Ray<T, D> &ray) const
+{
+	unsigned max_isect = get_max_ray_intersections();
+	std::vector<SurfacePoint<T, D> > points(max_isect);
+	unsigned count = get_intersections(ray, &points[0], max_isect);
+	points.resize(count);
+	return points;
+}
+
 } // namespace Geometry
 } // namespace Msp