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         virtual BoundingBox<T, D> get_axis_aligned_bounding_box(unsigned detail = 0) const = 0;
  44 protected:
  45         BoundingBox<T, D> bisect_axis_aligned_bounding_box(unsigned) const;
  46 public:
  47         virtual bool contains(const LinAl::Vector<T, D> &) const = 0;
  48         bool check_intersection(const Ray<T, D> &) const;
  49         virtual unsigned get_max_ray_intersections() const = 0;
  50         virtual unsigned get_intersections(const Ray<T, D> &, SurfacePoint<T, D> *, unsigned) const = 0;
  51         std::vector<SurfacePoint<T, D> > get_intersections(const Ray<T, D> &) const;
  52         virtual Coverage get_coverage(const BoundingBox<T, D> &) const = 0;
  53 };
  54
  55 template<typename T, unsigned D>
  56 inline BoundingBox<T, D> Shape<T, D>::bisect_axis_aligned_bounding_box(unsigned detail) const
  57 {
  58         if(!detail)
  59                 throw std::invalid_argument("Shape::bisect_axis_aligned_bounding_box");
  60
  61         std::list<CoverageCell> queue;
  62         queue.push_back(CoverageCell());
  63         CoverageCell &root = queue.front();
  64         root.level = 0;
  65         root.bounding_box = get_axis_aligned_bounding_box();
  66         if(root.bounding_box.is_space())
  67                 return root.bounding_box;
  68
  69         root.coverage = get_coverage(root.bounding_box);
  70         if(root.coverage==FULL_COVERAGE)
  71                 return root.bounding_box;
  72
  73         LinAl::Vector<T, D> tight_min_pt = root.bounding_box.get_maximum_point();
  74         LinAl::Vector<T, D> tight_max_pt = root.bounding_box.get_minimum_point();
  75
  76         while(!queue.empty())
  77         {
  78                 CoverageCell &cell = queue.front();
  79
  80                 const LinAl::Vector<T, D> &min_pt = cell.bounding_box.get_minimum_point();
  81                 const LinAl::Vector<T, D> &max_pt = cell.bounding_box.get_maximum_point();
  82                 LinAl::Vector<T, D> center = (min_pt+max_pt)/T(2);
  83
  84                 for(unsigned i=0; i<(1<<D); ++i)
  85                 {
  86                         CoverageCell child;
  87                         child.level = cell.level+1;
  88
  89                         LinAl::Vector<T, D> child_min_pt = min_pt;
  90                         LinAl::Vector<T, D> child_max_pt = max_pt;
  91                         for(unsigned j=0; j<D; ++j)
  92                         {
  93                                 if((i>>j)&1)
  94                                         child_min_pt[j] = center[j];
  95                                 else
  96                                         child_max_pt[j] = center[j];
  97                         }
  98                         child.bounding_box = BoundingBox<T, D>(child_min_pt, child_max_pt);
  99
 100                         child.coverage = get_coverage(child.bounding_box);
 101                         if(child.coverage==FULL_COVERAGE || (child.level==detail && child.coverage!=NO_COVERAGE))
 102                         {
 103                                 for(unsigned j=0; j<D; ++j)
 104                                 {
 105                                         tight_min_pt[j] = std::min(tight_min_pt[j], child_min_pt[j]);
 106                                         tight_max_pt[j] = std::max(tight_max_pt[j], child_max_pt[j]);
 107                                 }
 108                         }
 109                         else if(child.coverage==PARTIAL_COVERAGE)
 110                                 queue.push_back(child);
 111                 }
 112
 113                 queue.pop_front();
 114         }
 115
 116         return BoundingBox<T, D>(tight_min_pt, tight_max_pt);
 117 }
 118
 119 template<typename T, unsigned D>
 120 inline bool Shape<T, D>::check_intersection(const Ray<T, D> &ray) const
 121 {
 122         return get_intersections(ray, 0, 1);
 123 }
 124
 125 template<typename T, unsigned D>
 126 inline std::vector<SurfacePoint<T, D> > Shape<T, D>::get_intersections(const Ray<T, D> &ray) const
 127 {
 128         unsigned max_isect = get_max_ray_intersections();
 129         std::vector<SurfacePoint<T, D> > points(max_isect);
 130         unsigned count = get_intersections(ray, &points[0], max_isect);
 131         points.resize(count);
 132         return points;
 133 }
 134
 135 } // namespace Geometry
 136 } // namespace Msp
 137
 138 #endif