1 #ifndef MSP_GEOMETRY_SHAPE_H_
2 #define MSP_GEOMETRY_SHAPE_H_
6 #include <msp/linal/vector.h>
7 #include "boundingbox.h"
9 #include "surfacepoint.h"
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
27 template<typename T, unsigned D>
34 BoundingBox<T, D> bounding_box;
42 virtual Shape *clone() const = 0;
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;
48 BoundingBox<T, D> bisect_axis_aligned_bounding_box(unsigned) const;
51 /** Checks if a point is contained within the shape. */
52 virtual bool contains(const LinAl::Vector<T, D> &) const = 0;
54 bool check_intersection(const Ray<T, D> &) const;
55 virtual unsigned get_max_ray_intersections() const = 0;
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;
60 /** Returns a vector with all of the intersections between the shape and a
62 std::vector<SurfacePoint<T, D> > get_intersections(const Ray<T, D> &) const;
64 /** Determines whether the shape covers a bounding box. */
65 virtual Coverage get_coverage(const BoundingBox<T, D> &) const = 0;
68 template<typename T, unsigned D>
69 inline BoundingBox<T, D> Shape<T, D>::bisect_axis_aligned_bounding_box(unsigned detail) const
72 throw std::invalid_argument("Shape::bisect_axis_aligned_bounding_box");
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();
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;
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;
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();
96 CoverageCell &cell = queue.front();
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();
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]);
111 LinAl::Vector<T, D> center = (min_pt+max_pt)/T(2);
113 // Bisect each dimension.
114 for(unsigned i=0; i<(1<<D); ++i)
117 child.level = cell.level+1;
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)
124 child_min_pt[j] = center[j];
126 child_max_pt[j] = center[j];
128 child.bounding_box = BoundingBox<T, D>(child_min_pt, child_max_pt);
130 child.coverage = get_coverage(child.bounding_box);
131 if(child.coverage==FULL_COVERAGE || (child.level==detail && child.coverage!=NO_COVERAGE))
133 /* Immediately merge cells with full coverage. Also merge cells
134 at the last level. */
135 for(unsigned j=0; j<D; ++j)
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]);
141 else if(child.coverage==PARTIAL_COVERAGE)
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)
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]);
152 if(child.level<detail && child.coverage!=NO_COVERAGE && child.coverage!=FULL_COVERAGE)
153 queue.push_back(child);
159 return BoundingBox<T, D>(tight_min_pt, tight_max_pt);
162 template<typename T, unsigned D>
163 inline bool Shape<T, D>::check_intersection(const Ray<T, D> &ray) const
165 return get_intersections(ray, 0, 1);
168 template<typename T, unsigned D>
169 inline std::vector<SurfacePoint<T, D> > Shape<T, D>::get_intersections(const Ray<T, D> &ray) const
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);
178 } // namespace Geometry