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