source/geometry/shape.h

   1 #ifndef MSP_GEOMETRY_SHAPE_H_
   2 #define MSP_GEOMETRY_SHAPE_H_
   3
   4 #include <list>
   5 #include <vector>
   6 #include <msp/linal/vector.h>
   7 #include "boundingbox.h"
   8 #include "ray.h"
   9 #include "surfacepoint.h"
  10
  11 namespace Msp {
  12 namespace Geometry {
  13
  14 enum Coverage
  15 {
  16         NO_COVERAGE,
  17         PARTIAL_COVERAGE,
  18         FULL_COVERAGE
  19 };
  20
  21 /**
  22 Base class and interface for geometric shapes.  Shapes may be bounded or
  23 unbounded.  They are always considered to be solid, i.e. have a distinct inside
  24 and an outside.
  25 */
  26 template<typename T, unsigned D>
  27 class Shape
  28 {
  29 protected:
  30         struct CoverageCell
  31         {
  32                 unsigned level;
  33                 BoundingBox<T, D> bounding_box;
  34                 Coverage coverage;
  35         };
  36
  37         Shape() { }
  38 public:
  39         virtual ~Shape() { }
  40
  41         virtual Shape *clone() const = 0;
  42
  43         /** Returns the bounding box of the shape.  The detail parameter controls
  44         the tightness of the box.  Higher detail will take more time to compute. */
  45         virtual BoundingBox<T, D> get_axis_aligned_bounding_box(unsigned detail = 0) const = 0;
  46 protected:
  47         BoundingBox<T, D> bisect_axis_aligned_bounding_box(unsigned) const;
  48
  49 public:
  50         /** Checks if a point is contained within the shape. */
  51         virtual bool contains(const LinAl::Vector<T, D> &) const = 0;
  52
  53         bool check_intersection(const Ray<T, D> &) const;
  54         virtual unsigned get_max_ray_intersections() const = 0;
  55
  56         /** Determines intersection points between the shape and a ray. */
  57         virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const = 0;
  58
  59         /** Returns a vector with all of the intersections between the shape and a
  60         ray. */
  61         std::vector<SurfacePoint<T, D> > get_intersections(const Ray<T, D> &) const;
  62
  63         /** Determines whether the shape covers a bounding box. */
  64         virtual Coverage get_coverage(const BoundingBox<T, D> &) const = 0;
  65 };
  66
  67 template<typename T, unsigned D>
  68 inline BoundingBox<T, D> Shape<T, D>::bisect_axis_aligned_bounding_box(unsigned detail) const
  69 {
  70         if(!detail)
  71                 throw std::invalid_argument("Shape::bisect_axis_aligned_bounding_box");
  72
  73         // Form the root cell from the loosest approximation of a bounding box.
  74         std::list<CoverageCell> queue;
  75         queue.push_back(CoverageCell());
  76         CoverageCell &root = queue.front();
  77         root.level = 0;
  78         root.bounding_box = get_axis_aligned_bounding_box();
  79         // There's no point bisecting if the bounding box fills the entire space.
  80         if(root.bounding_box.is_space())
  81                 return root.bounding_box;
  82
  83         root.coverage = get_coverage(root.bounding_box);
  84         // If the bounding box is fully covered it's already tight.
  85         if(root.coverage==FULL_COVERAGE)
  86                 return root.bounding_box;
  87
  88         /* Initialize bounds to the opposite edges because we don't yet know which
  89         part of the bounding box the shape occupies. */
  90         LinAl::Vector<T, D> tight_min_pt = root.bounding_box.get_maximum_point();
  91         LinAl::Vector<T, D> tight_max_pt = root.bounding_box.get_minimum_point();
  92
  93         while(!queue.empty())
  94         {
  95                 CoverageCell &cell = queue.front();
  96
  97                 const LinAl::Vector<T, D> &min_pt = cell.bounding_box.get_minimum_point();
  98                 const LinAl::Vector<T, D> &max_pt = cell.bounding_box.get_maximum_point();
  99                 LinAl::Vector<T, D> center = (min_pt+max_pt)/T(2);
 100
 101                 // Bisect each dimension.
 102                 for(unsigned i=0; i<(1<<D); ++i)
 103                 {
 104                         CoverageCell child;
 105                         child.level = cell.level+1;
 106
 107                         LinAl::Vector<T, D> child_min_pt = min_pt;
 108                         LinAl::Vector<T, D> child_max_pt = max_pt;
 109                         for(unsigned j=0; j<D; ++j)
 110                         {
 111                                 if((i>>j)&1)
 112                                         child_min_pt[j] = center[j];
 113                                 else
 114                                         child_max_pt[j] = center[j];
 115                         }
 116                         child.bounding_box = BoundingBox<T, D>(child_min_pt, child_max_pt);
 117
 118                         child.coverage = get_coverage(child.bounding_box);
 119                         if(child.coverage==FULL_COVERAGE || (child.level==detail && child.coverage!=NO_COVERAGE))
 120                         {
 121                                 /* Adjust the bounds when we are certain that it's covered by at
 122                                 least part of the shape.  Also adjust for uncertain results if
 123                                 we're on the last level. */
 124                                 for(unsigned j=0; j<D; ++j)
 125                                 {
 126                                         tight_min_pt[j] = std::min(tight_min_pt[j], child_min_pt[j]);
 127                                         tight_max_pt[j] = std::max(tight_max_pt[j], child_max_pt[j]);
 128                                 }
 129                         }
 130                         else if(child.coverage==PARTIAL_COVERAGE)
 131                                 queue.push_back(child);
 132                 }
 133
 134                 queue.pop_front();
 135         }
 136
 137         return BoundingBox<T, D>(tight_min_pt, tight_max_pt);
 138 }
 139
 140 template<typename T, unsigned D>
 141 inline bool Shape<T, D>::check_intersection(const Ray<T, D> &ray) const
 142 {
 143         return get_intersections(ray, 0, 1);
 144 }
 145
 146 template<typename T, unsigned D>
 147 inline std::vector<SurfacePoint<T, D> > Shape<T, D>::get_intersections(const Ray<T, D> &ray) const
 148 {
 149         unsigned max_isect = get_max_ray_intersections();
 150         std::vector<SurfacePoint<T, D> > points(max_isect);
 151         unsigned count = get_intersections(ray, &points[0], max_isect);
 152         points.resize(count);
 153         return points;
 154 }
 155
 156 } // namespace Geometry
 157 } // namespace Msp
 158
 159 #endif