32 #ifndef __HDK_UT_BVH_h__
33 #define __HDK_UT_BVH_h__
48 namespace HDK_Sample {
52 template<
typename T,u
int NAXES>
65 "UT::Box should be POD, for better performance in UT_Array, etc.");
67 for (
uint axis = 0; axis < NAXES; ++axis) {
68 vals[axis][0] =
T(other.vals[axis][0]);
69 vals[axis][1] =
T(other.vals[axis][1]);
73 template<
typename TS >
78 for (
uint axis = 0; axis < NAXES; ++axis) {
79 vals[axis][0] = pt[axis];
80 vals[axis][1] = pt[axis];
86 for (
uint axis = 0; axis < NAXES; ++axis) {
87 vals[axis][0] =
T(other.vals[axis][0]);
88 vals[axis][1] =
T(other.vals[axis][1]);
103 for (
uint axis = 0; axis < NAXES; ++axis) {
112 for (
uint axis = 0; axis < NAXES; ++axis) {
113 vals[axis][0] =
src.vals[axis][0];
114 vals[axis][1] =
src.vals[axis][1];
121 for (
uint axis = 0; axis < NAXES; ++axis) {
122 vals[axis][0] =
SYSmin(src0.vals[axis][0], src1.vals[axis][0]);
123 vals[axis][1] =
SYSmax(src0.vals[axis][1], src1.vals[axis][1]);
127 for (
uint axis = 0; axis < NAXES; ++axis) {
128 T& minv =
vals[axis][0];
129 T& maxv =
vals[axis][1];
130 const T curminv =
src.vals[axis][0];
131 const T curmaxv =
src.vals[axis][1];
132 minv = (minv < curminv) ? minv : curminv;
133 maxv = (maxv > curmaxv) ? maxv : curmaxv;
137 template<
typename TS >
143 for (
uint axis = 0; axis < NAXES; ++axis) {
144 vals[axis][0] = pt[axis];
145 vals[axis][1] = pt[axis];
149 template<
typename TS >
158 for (
uint axis = 0; axis < NAXES; ++axis) {
164 template<
typename TS >
170 for (
uint axis = 0; axis < NAXES; ++axis) {
176 template<
typename TS >
182 for (
uint axis = 0; axis < NAXES; ++axis) {
188 template<
typename TS >
199 for (
uint axis = 0; axis < NAXES; ++axis) {
200 v[axis] =
vals[axis][0];
208 for (
uint axis = 0; axis < NAXES; ++axis) {
209 v[axis] =
vals[axis][1];
217 for (
uint axis = 1; axis < NAXES; ++axis) {
218 diff = (
vals[axis][1]-
vals[axis][0]);
225 for (
uint axis = 1; axis < NAXES; ++axis) {
226 product *= (
vals[axis][1]-
vals[axis][0]);
246 return d0*d1 + d1*d2 + d2*d0;
254 const T d0d1 = d0*d1;
255 const T d2d3 = d2*d3;
256 return d0d1*(d2+d3) + d2d3*(d0+d1);
260 for (
uint skipped_axis = 0; skipped_axis < NAXES; ++skipped_axis) {
262 for (
uint axis = 0; axis < NAXES; ++axis) {
263 if (axis != skipped_axis) {
264 product *= (
vals[axis][1]-
vals[axis][0]);
273 for (
uint axis = 1; axis < NAXES; ++axis) {
274 sum += (
vals[axis][1]-
vals[axis][0]);
285 for (
int axis = 0; axis < NAXES; ++axis)
288 T t1 = (
vals[axis][
sign] - origin[axis]) * inverse_direction[axis];
289 T t2 = (
vals[axis][sign^1] - origin[axis]) * inverse_direction[axis];
290 box_tmin =
SYSmax(t1, box_tmin);
291 box_tmax =
SYSmin(t2, box_tmax);
295 for (
int axis = 0; axis < NAXES; ++axis)
297 dest.vals[axis][0] =
SYSmax(
vals[axis][0], other.vals[axis][0]);
298 dest.vals[axis][1] =
SYSmin(
vals[axis][1], other.vals[axis][1]);
306 for (
int axis = 1; axis < NAXES; ++axis)
318 for (
int axis = 1; axis < NAXES; ++axis)
412 template<BVH_Heuristic H,
typename T,u
int NAXES,
typename BOX_TYPE,
typename SRC_INT_TYPE=INT_TYPE>
413 void init(
const BOX_TYPE* boxes,
const INT_TYPE nboxes, SRC_INT_TYPE*
indices=
nullptr,
bool reorder_indices=
false,
INT_TYPE max_items_per_leaf=1) noexcept;
416 void init(
Box<T,NAXES> axes_minmax,
const BOX_TYPE* boxes,
INT_TYPE nboxes, SRC_INT_TYPE*
indices=
nullptr,
bool reorder_indices=false,
INT_TYPE max_items_per_leaf=1) noexcept;
447 template<
typename LOCAL_DATA,
typename FUNCTORS>
450 LOCAL_DATA *data_for_parent=
nullptr)
const noexcept;
458 template<typename LOCAL_DATA,typename FUNCTORS>
462 LOCAL_DATA *data_for_parent=
nullptr)
const noexcept;
478 template<typename LOCAL_DATA,typename FUNCTORS>
481 LOCAL_DATA *data_for_parent=
nullptr)
const noexcept;
486 template<typename SRC_INT_TYPE>
490 template<typename LOCAL_DATA,typename FUNCTORS>
495 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
497 template<typename LOCAL_DATA,typename FUNCTORS>
498 void traverseParallelHelper(
504 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
506 template<typename LOCAL_DATA,typename FUNCTORS>
507 void traverseVectorHelper(
511 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
513 template<typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
514 static
void computeFullBoundingBox(
Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, const
INT_TYPE nboxes, SRC_INT_TYPE* indices) noexcept;
516 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
517 static
void initNode(
UT_Array<
Node>& nodes,
Node &node, const
Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices, const
INT_TYPE nboxes) noexcept;
519 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
520 static
void initNodeReorder(
UT_Array<
Node>& nodes,
Node &node, const
Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices, const
INT_TYPE nboxes, const
INT_TYPE indices_offset, const
INT_TYPE max_items_per_leaf) noexcept;
522 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
523 static
void multiSplit(const
Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices,
INT_TYPE nboxes, SRC_INT_TYPE* sub_indices[
N+1],
Box<T,NAXES> sub_boxes[N]) noexcept;
525 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
526 static
void split(const
Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices,
INT_TYPE nboxes, SRC_INT_TYPE*& split_indices,
Box<T,NAXES>* split_boxes) noexcept;
528 template<
INT_TYPE PARALLEL_THRESHOLD, typename SRC_INT_TYPE>
531 template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
532 static
void nthElement(const BOX_TYPE* boxes, SRC_INT_TYPE* indices, const SRC_INT_TYPE* indices_end, const
uint axis, SRC_INT_TYPE*const nth) noexcept;
534 template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
535 static
void partitionByCentre(const BOX_TYPE* boxes, SRC_INT_TYPE*const indices, const SRC_INT_TYPE*const indices_end, const
uint axis, const T pivotx2, SRC_INT_TYPE*& ppivot_start, SRC_INT_TYPE*& ppivot_end) noexcept;
543 return nboxes/2 + nboxes/(2*(N-1));
546 template<BVH_Heuristic H,
typename T, u
int NAXES>
549 return box.axis_sum();
552 return box.half_surface_area();
558 T diameter2 = box.diameter2();
559 return SYSsqrt(diameter2);
562 return box.diameter2();
565 T diameter2 = box.diameter2();
566 return diameter2*SYSsqrt(diameter2);
568 UT_ASSERT_MSG(0,
"BVH_Heuristic::MEDIAN_MAX_AXIS should be handled separately by caller!");
573 static constexpr
INT_TYPE NSPANS = 16;
574 static constexpr
INT_TYPE NSPLITS = NSPANS-1;
577 static constexpr
INT_TYPE MIN_FRACTION = 16;
SYS_FORCE_INLINE void initBounds(const TS &min, const TS &max) noexcept
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMax() const noexcept
void traverseParallel(INT_TYPE parallel_threshold, FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
#define SYS_STATIC_ASSERT(expr)
GLsizei GLenum const void * indices
static SYS_FORCE_INLINE INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept
SYS_FORCE_INLINE void initBounds(const TS &pt) noexcept
#define SYS_STATIC_ASSERT_MSG(expr, msg)
SYS_FORCE_INLINE void initBounds() noexcept
T half_surface_area() const noexcept
SYS_FORCE_INLINE T * operator[](const size_t axis) noexcept
SYS_FORCE_INLINE void initBounds(const Box< T, NAXES > &src) noexcept
static void createTrivialIndices(SRC_INT_TYPE *indices, const INT_TYPE n) noexcept
void debugDump() const
Prints a text representation of the tree to stdout.
SYS_FORCE_INLINE BVH() noexcept
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
SYS_FORCE_INLINE Box() noexcept=default
SYS_FORCE_INLINE Box & operator=(const Box< S, NAXES > &other) noexcept
SYS_FORCE_INLINE INT_TYPE getNumNodes() const noexcept
void traverse(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
SYS_FORCE_INLINE const Node * getNodes() const noexcept
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
T diameter2() const noexcept
SYS_FORCE_INLINE void combine(const TS &pt) noexcept
#define UT_ASSERT_MSG(ZZ,...)
T axis_sum() const noexcept
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
SYS_FORCE_INLINE void intersect(const Box &other, Box &dest) const noexcept
SYS_FORCE_INLINE void initBoundsUnordered(const Box< T, NAXES > &src0, const Box< T, NAXES > &src1) noexcept
static constexpr INT_TYPE EMPTY
SYS_FORCE_INLINE const T * operator[](const size_t axis) const noexcept
STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r)
SYS_FORCE_INLINE Box(const TS &pt) noexcept
IMATH_HOSTDEVICE constexpr int sign(T a) IMATH_NOEXCEPT
void init(const BOX_TYPE *boxes, const INT_TYPE nboxes, SRC_INT_TYPE *indices=nullptr, bool reorder_indices=false, INT_TYPE max_items_per_leaf=1) noexcept
SYS_FORCE_INLINE void initBoundsUnordered(const TS &p0, const TS &p1) noexcept
SYS_FORCE_INLINE void clear() noexcept
static constexpr INT_TYPE theN
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMin() const noexcept
SYS_FORCE_INLINE void enlargeBounds(const TS &pt) noexcept
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GA_API const UT_StringHolder N
void traverseVector(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
SYS_FORCE_INLINE void intersect(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES > &signs, const UT_FixedVector< T, NAXES > &origin, const UT_FixedVector< T, NAXES > &inverse_direction) const noexcept
static SYS_FORCE_INLINE bool isInternal(INT_TYPE node_int) noexcept
T volume() const noexcept
SYS_FORCE_INLINE void combine(const Box< T, NAXES > &src) noexcept
static SYS_FORCE_INLINE INT_TYPE getInternalNum(INT_TYPE node_int) noexcept
static constexpr INT_TYPE INTERNAL_BIT