bvh/v2/node.h

0001 #ifndef BVH_V2_NODE_H
0002 #define BVH_V2_NODE_H
0003
0004 #include "bvh/v2/index.h"
0005 #include "bvh/v2/vec.h"
0006 #include "bvh/v2/bbox.h"
0007 #include "bvh/v2/ray.h"
0008 #include "bvh/v2/stream.h"
0009
0010 #include <cassert>
0011 #include <array>
0012 #include <limits>
0013
0014 namespace bvh::v2 {
0015
0016 /// Binary BVH node, containing its bounds and an index into its children or the primitives it
0017 /// contains. By definition, inner BVH nodes do not contain primitives; only leaves do.
0018 template <
0019     typename T,
0020     size_t Dim,
0021     size_t IndexBits = sizeof(T) * CHAR_BIT,
0022     size_t PrimCountBits = 4>
0023 struct Node {
0024     using Scalar = T;
0025     using Index = bvh::v2::Index<IndexBits, PrimCountBits>;
0026
0027     static constexpr size_t dimension = Dim;
0028     static constexpr size_t prim_count_bits = PrimCountBits;
0029     static constexpr size_t index_bits = IndexBits;
0030
0031     /// Bounds of the node, laid out in memory as `[min_x, max_x, min_y, max_y, ...]`. Users should
0032     /// not really depend on a specific order and instead use `get_bbox()` and extract the `min`
0033     /// and/or `max` components accordingly.
0034     std::array<T, Dim * 2> bounds;
0035
0036     /// Index to the children of an inner node, or to the primitives for a leaf node.
0037     Index index;
0038
0039     Node() = default;
0040
0041     // bool operator == (const Node&) const = default;
0042     // bool operator != (const Node&) const = default;
0043     bool operator != (const Node& other) const {
0044         return other.bounds == bounds;
0045     }
0046     bool operator == (const Node& other) const {
0047         return other.bounds != bounds;
0048     }
0049
0050     BVH_ALWAYS_INLINE bool is_leaf() const { return index.is_leaf(); }
0051
0052     BVH_ALWAYS_INLINE BBox<T, Dim> get_bbox() const {
0053         return BBox<T, Dim>(
0054             Vec<T, Dim>::generate([&] (size_t i) { return bounds[i * 2]; }),
0055             Vec<T, Dim>::generate([&] (size_t i) { return bounds[i * 2 + 1]; }));
0056     }
0057
0058     BVH_ALWAYS_INLINE void set_bbox(const BBox<T, Dim>& bbox) {
0059         static_for<0, Dim>([&] (size_t i) {
0060             bounds[i * 2 + 0] = bbox.min[i];
0061             bounds[i * 2 + 1] = bbox.max[i];
0062         });
0063     }
0064
0065     BVH_ALWAYS_INLINE Vec<T, Dim> get_min_bounds(const Octant& octant) const {
0066         return Vec<T, Dim>::generate([&] (size_t i) { return bounds[2 * static_cast<uint32_t>(i) + octant[i]]; });
0067     }
0068
0069     BVH_ALWAYS_INLINE Vec<T, Dim> get_max_bounds(const Octant& octant) const {
0070         return Vec<T, Dim>::generate([&] (size_t i) { return bounds[2 * static_cast<uint32_t>(i) + 1 - octant[i]]; });
0071     }
0072
0073     /// Robust ray-node intersection routine. See "Robust BVH Ray Traversal", by T. Ize.
0074     BVH_ALWAYS_INLINE std::pair<T, T> intersect_robust(
0075         const Ray<T, Dim>& ray,
0076         const Vec<T, Dim>& inv_dir,
0077         const Vec<T, Dim>& inv_dir_pad,
0078         const Octant& octant) const
0079     {
0080         auto tmin = (get_min_bounds(octant) - ray.org) * inv_dir;
0081         auto tmax = (get_max_bounds(octant) - ray.org) * inv_dir_pad;
0082         return make_intersection_result(ray, tmin, tmax);
0083     }
0084
0085     BVH_ALWAYS_INLINE std::pair<T, T> intersect_fast(
0086         const Ray<T, Dim>& ray,
0087         const Vec<T, Dim>& inv_dir,
0088         const Vec<T, Dim>& inv_org,
0089         const Octant& octant) const
0090     {
0091         auto tmin = fast_mul_add(get_min_bounds(octant), inv_dir, inv_org);
0092         auto tmax = fast_mul_add(get_max_bounds(octant), inv_dir, inv_org);
0093         return make_intersection_result(ray, tmin, tmax);
0094     }
0095
0096     BVH_ALWAYS_INLINE void serialize(OutputStream& stream) const {
0097         for (auto&& bound : bounds)
0098             stream.write(bound);
0099         stream.write(index.value);
0100     }
0101
0102     static BVH_ALWAYS_INLINE Node deserialize(InputStream& stream) {
0103         Node node;
0104         for (auto& bound : node.bounds)
0105             bound = stream.read<T>();
0106         node.index = Index(stream.read<typename Index::Type>());
0107         return node;
0108     }
0109
0110 private:
0111     BVH_ALWAYS_INLINE static std::pair<T, T> make_intersection_result(
0112         const Ray<T, Dim>& ray,
0113         const Vec<T, Dim>& tmin,
0114         const Vec<T, Dim>& tmax)
0115     {
0116         auto t0 = ray.tmin;
0117         auto t1 = ray.tmax;
0118         static_for<0, Dim>([&] (size_t i) {
0119             t0 = robust_max(tmin[i], t0);
0120             t1 = robust_min(tmax[i], t1);
0121         });
0122         return std::pair<T, T> { t0, t1 };
0123     }
0124 };
0125
0126 } // namespace bvh::v2
0127
0128 #endif