#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;
-
-template<typename T, unsigned D>
-class SurfacePoint;
+enum Coverage
+{
+ NO_COVERAGE,
+ UNCERTAIN_COVERAGE,
+ PARTIAL_COVERAGE,
+ FULL_COVERAGE
+};
/**
Base class and interface for geometric shapes. Shapes may be bounded or
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;
+ /** 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
{
projects / libs / math.git / blobdiff