28 #define BVH_TRY_ALL_AXES 0
36 template<
typename T,u
int NAXES>
50 "UT::Box should be POD, for better performance in UT_Array, etc.");
52 for (
uint axis = 0; axis < NAXES; ++axis) {
53 vals[axis][0] =
T(other.vals[axis][0]);
54 vals[axis][1] =
T(other.vals[axis][1]);
58 template<
typename TS >
63 for (
uint axis = 0; axis < NAXES; ++axis) {
64 vals[axis][0] = pt[axis];
65 vals[axis][1] = pt[axis];
71 for (
uint axis = 0; axis < NAXES; ++axis) {
72 vals[axis][0] =
T(other.vals[axis][0]);
73 vals[axis][1] =
T(other.vals[axis][1]);
88 for (
uint axis = 0; axis < NAXES; ++axis) {
97 for (
uint axis = 0; axis < NAXES; ++axis) {
98 vals[axis][0] =
src.vals[axis][0];
99 vals[axis][1] =
src.vals[axis][1];
106 for (
uint axis = 0; axis < NAXES; ++axis) {
107 vals[axis][0] =
SYSmin(src0.vals[axis][0], src1.vals[axis][0]);
108 vals[axis][1] =
SYSmax(src0.vals[axis][1], src1.vals[axis][1]);
112 for (
uint axis = 0; axis < NAXES; ++axis) {
113 T& minv =
vals[axis][0];
114 T& maxv =
vals[axis][1];
115 const T curminv =
src.vals[axis][0];
116 const T curmaxv =
src.vals[axis][1];
117 minv = (minv < curminv) ? minv : curminv;
118 maxv = (maxv > curmaxv) ? maxv : curmaxv;
125 template<
typename TS >
131 for (
uint axis = 0; axis < NAXES; ++axis) {
132 vals[axis][0] = pt[axis];
133 vals[axis][1] = pt[axis];
137 template<
typename TS >
146 for (
uint axis = 0; axis < NAXES; ++axis) {
152 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 >
187 for (
uint axis = 0; axis < NAXES; ++axis) {
188 v[axis] =
vals[axis][0];
196 for (
uint axis = 0; axis < NAXES; ++axis) {
197 v[axis] =
vals[axis][1];
205 for (
uint axis = 1; axis < NAXES; ++axis) {
206 diff = (
vals[axis][1]-
vals[axis][0]);
213 for (
uint axis = 1; axis < NAXES; ++axis) {
214 product *= (
vals[axis][1]-
vals[axis][0]);
219 if constexpr (NAXES==1) {
225 else if constexpr (NAXES==2) {
230 else if constexpr (NAXES==3) {
234 return d0*d1 + d1*d2 + d2*d0;
236 else if constexpr (NAXES==4) {
242 const T d0d1 = d0*d1;
243 const T d2d3 = d2*d3;
244 return d0d1*(d2+d3) + d2d3*(d0+d1);
248 for (
uint skipped_axis = 0; skipped_axis < NAXES; ++skipped_axis) {
250 for (
uint axis = 0; axis < NAXES; ++axis) {
251 if (axis != skipped_axis) {
252 product *= (
vals[axis][1]-
vals[axis][0]);
261 for (
uint axis = 1; axis < NAXES; ++axis) {
262 sum += (
vals[axis][1]-
vals[axis][0]);
274 for (
int axis = 0; axis < NAXES; ++axis)
277 T t1 = (
vals[axis][sign] - origin[axis]) * inverse_direction[axis];
278 T t2 = (
vals[axis][sign^1] - origin[axis]) * inverse_direction[axis];
279 box_tmin =
SYSmax(t1, box_tmin);
280 box_tmax =
SYSmin(t2, box_tmax);
292 for (
int axis = 0; axis < NAXES; ++axis)
296 vals[axis][0] - tolerance,
297 vals[axis][1] + tolerance
299 T t1 = (local_vals[sign] - origin[axis]) * inverse_direction[axis];
300 T t2 = (local_vals[sign^1] - origin[axis]) * inverse_direction[axis];
301 box_tmin =
SYSmax(t1, box_tmin);
302 box_tmax =
SYSmin(t2, box_tmax);
306 for (
int axis = 0; axis < NAXES; ++axis)
308 dest.vals[axis][0] =
SYSmax(
vals[axis][0], other.vals[axis][0]);
309 dest.vals[axis][1] =
SYSmin(
vals[axis][1], other.vals[axis][1]);
318 for (
int axis = 1; axis < NAXES; ++axis)
331 for (
int axis = 1; axis < NAXES; ++axis)
339 template<
typename TS >
340 auto isInside(
const TS &pt)
const noexcept -> decltype(
vals[0][0] <= pt[0])
346 vals[0][0] <= pt[0] &&
vals[0][1] >= pt[0] &&
347 vals[1][0] <= pt[1] && vals[1][1] >= pt[1] &&
348 vals[2][0] <= pt[2] && vals[2][1] >= pt[2];
441 template<BVH_Heuristic H,
typename T,u
int NAXES,
typename BOX_TYPE,
typename SRC_INT_TYPE=INT_TYPE>
442 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;
445 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;
482 template<
typename LOCAL_DATA,
typename FUNCTORS>
485 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
493 template<typename LOCAL_DATA,typename FUNCTORS>
497 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
513 template<typename LOCAL_DATA,typename FUNCTORS>
516 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
521 template<typename SRC_INT_TYPE>
525 template<typename LOCAL_DATA,typename FUNCTORS>
530 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
532 template<typename LOCAL_DATA,typename FUNCTORS>
533 void traverseParallelHelper(
539 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
541 template<typename LOCAL_DATA,typename FUNCTORS>
542 void traverseVectorHelper(
546 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
548 template<typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
549 static
void computeFullBoundingBox(
Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, const
INT_TYPE nboxes, SRC_INT_TYPE* indices) noexcept;
551 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
552 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;
554 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
555 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;
557 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
558 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;
560 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
561 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;
564 template<BVH_Heuristic H,
typename T,u
int NAXES,
typename BOX_TYPE,
typename SRC_INT_TYPE>
565 static void splitMiddleCountAxis(
const INT_TYPE axis, T &best_heuristic,
const BOX_TYPE* boxes, SRC_INT_TYPE* indices,
INT_TYPE nboxes, SRC_INT_TYPE*& split_indices,
Box<T,NAXES>* split_boxes) noexcept;
567 template<BVH_Heuristic H,
typename T,u
int NAXES,
typename BOX_TYPE,
typename SRC_INT_TYPE>
568 static void splitLargeCountAxis(
569 const INT_TYPE axis,
const T axis_min,
const T axis_length,
576 const BOX_TYPE* boxes, SRC_INT_TYPE* indices,
INT_TYPE nboxes) noexcept;
579 template<INT_TYPE PARALLEL_THRESHOLD,
typename SRC_INT_TYPE>
582 template<
typename T,
typename BOX_TYPE,
typename SRC_INT_TYPE>
583 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;
585 template<
typename T,
typename BOX_TYPE,
typename SRC_INT_TYPE>
586 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;
594 return nboxes/2 + nboxes/(2*(N-1));
597 template<BVH_Heuristic H,
typename T, u
int NAXES>
600 return box.axis_sum();
603 return box.half_surface_area();
609 T diameter2 = box.diameter2();
610 return SYSsqrt(diameter2);
613 return box.diameter2();
616 T diameter2 = box.diameter2();
617 return diameter2*SYSsqrt(diameter2);
619 UT_ASSERT_MSG(0,
"BVH_Heuristic::MEDIAN_MAX_AXIS should be handled separately by caller!");
623 int getMaxDepthHelper(
INT_TYPE curnode,
int depth)
const noexcept;
624 int getPureInternalDepthHelper(
INT_TYPE curnode,
int depth)
const noexcept;
627 static constexpr
INT_TYPE NSPANS = 16;
628 static constexpr
INT_TYPE NSPLITS = NSPANS-1;
631 static constexpr
INT_TYPE MIN_FRACTION = 16;
637 template<u
int BVH_N,
typename ITEM_BOX,
typename NODE_BOX>
640 const ITEM_BOX* item_boxes,
641 NODE_BOX* node_boxes) noexcept;
646 template<u
int NAXES,
typename T,u
int BVH_N,
typename ITEM_BOX,
typename NODE_BOX>
649 const ITEM_BOX* item_boxes,
650 NODE_BOX* node_boxes,
651 float expand_factor=0.0
f) noexcept;
656 template<
uint NAXES,typename T,typename ITEM_BOX,typename NODE_BOX,typename INT_TYPE0=
uint>
658 const UT::BVH<4>& bvh,
659 const ITEM_BOX* item_boxes,
660 NODE_BOX* node_boxes,
661 const
v4uu* node_nitems,
662 const INT_TYPE0* indices_mapping=
nullptr) noexcept;
671 template<
uint NAXES,typename INT_TYPE>
673 const UT::
BVH<4>& bvh,
674 const UT::
Box<
v4uf,NAXES>* node_boxes,
675 const UT::
Box<
float,NAXES>& query_box,
679 template<
uint NAXES,typename INT_TYPE>
681 const UT::
BVH<4>& bvh,
682 const UT::
Box<v4uf,NAXES>* node_boxes,
683 const UT::
Box<
float,NAXES>& query_box,
687 template<
uint NAXES,typename INT_TYPE>
689 const UT::
BVH<4>& bvh,
690 const UT::
Box<v4uf,NAXES>* node_boxes,
691 const UT::
Box<
float,NAXES>& query_box,
695 template<
uint NAXES,typename INT_TYPE,
int BATCH_SIZE>
697 const UT::
BVH<4>& bvh,
698 const UT::
Box<v4uf,NAXES>* node_boxes,
699 const UT::
Box<
float,NAXES> *query_box,
705 const UT::
BVH<4>& bvh,
707 exint nitems) noexcept;
715 SYS_FORCE_INLINE BVHOrderedStackEntry(const BVHOrderedStackEntry& other) noexcept = default;
716 SYS_FORCE_INLINE BVHOrderedStackEntry(BVHOrderedStackEntry&& other) noexcept = default;
717 SYS_FORCE_INLINE BVHOrderedStackEntry& operator=(const BVHOrderedStackEntry& other) noexcept = default;
718 SYS_FORCE_INLINE BVHOrderedStackEntry& operator=(BVHOrderedStackEntry&& other) noexcept = default;
720 : myDistSquared(dist_squared)
744 return !(*
this == other);
778 constexpr
bool allRadiiZero(
const T*
const array) noexcept {
return !array; }
780 template<
typename QUERY_POINT>
801 template<
typename POSITION,
typename RADIUS_ARRAY>
804 return myQueryPoint.queryDistance2(tree_point, radii, index);
810 template<
bool farthest,u
int NAXES>
813 return myQueryPoint.template boxHitAndDist2<farthest>(boxes, max_dist_squared, internal_node_num, dist2);
825 template<
bool farthest,
bool reordered,
bool use_max_po
ints,u
int NAXES,
typename QUERY_POINT,
typename INT_TYPE0,
typename POSITION_ARRAY,
typename RADIUS_ARRAY>
829 const v4uu* node_nitems,
830 const INT_TYPE0* indices_mapping,
831 const POSITION_ARRAY& positions,
832 QUERY_POINT& query_point,
835 const RADIUS_ARRAY& radii = ZeroRadiiWrapper(),
844 #undef BVH_TRY_ALL_AXES
SYS_FORCE_INLINE bool operator==(const BVHOrderedStackEntry &other) const
SYS_FORCE_INLINE uint boxHitAndDist2(const UT::Box< v4uf, NAXES > &boxes, const float max_dist_squared, const uint internal_node_num, v4uf &dist2) const
#define SYS_STATIC_ASSERT(expr)
GLsizei GLenum const void * indices
constexpr bool allRadiiZero(const T &array) noexcept
static constexpr INT_TYPE EMPTY
void findClosestPoints(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const v4uu *node_nitems, const INT_TYPE0 *indices_mapping, const POSITION_ARRAY &positions, QUERY_POINT &query_point, BVHOrderedStack &stack, BVHOrderedStack &output_queue, const RADIUS_ARRAY &radii=ZeroRadiiWrapper(), exint max_points=std::numeric_limits< exint >::max(), float max_dist_squared=std::numeric_limits< float >::max()) noexcept
SYS_FORCE_INLINE void combine(const TS &pt) noexcept
SYS_FORCE_INLINE void intersect(const Box &other, Box &dest) const noexcept
void traverseParallel(INT_TYPE parallel_threshold, FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
#define SYS_STATIC_ASSERT_MSG(expr, msg)
T half_surface_area() const noexcept
static SYS_FORCE_INLINE INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept
int getPureInternalDepth() const noexcept
Returns the minimum depth of the first non-internal node.
SYS_FORCE_INLINE bool operator!=(const BVHOrderedStackEntry &other) const
SYS_FORCE_INLINE void initBounds(const Box< T, NAXES > &src) noexcept
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMin() const noexcept
SYS_FORCE_INLINE constexpr SingleRadiusWrapper(const float radius)
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
SYS_FORCE_INLINE void initBounds() noexcept
SYS_FORCE_INLINE void enlargeBounds(const TS &pt) noexcept
SYS_FORCE_INLINE BVHQueryPointWrapper(QUERY_POINT &query_point)
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMax() const noexcept
SYS_FORCE_INLINE bool operator>(const BVHOrderedStackEntry &other) const
int getMaxDepth() const noexcept
Returns the maximum depth of any leaf.
SYS_FORCE_INLINE constexpr float operator[](exint i) const noexcept
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
void getIntersectingBoxesFromStack(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
#define UT_ASSERT_MSG(ZZ,...)
SYS_FORCE_INLINE void clear() noexcept
SYS_FORCE_INLINE T * operator[](const size_t axis) noexcept
T axis_sum() const noexcept
UT::BVH< 4 >::INT_TYPE myNode
void computeNodeNItems(const UT::BVH< 4 > &bvh, v4uu *node_nitems, exint nitems) noexcept
Computes the number of items per node entry and fills in node_nitems.
SYS_FORCE_INLINE void initBounds(const TS &min, const TS &max) noexcept
void getIntersectingNodes(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
QUERY_POINT & myQueryPoint
SYS_FORCE_INLINE Box() noexcept=default
SYS_FORCE_INLINE bool operator>=(const BVHOrderedStackEntry &other) const
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
SYS_FORCE_INLINE bool operator<=(const BVHOrderedStackEntry &other) const
SYS_FORCE_INLINE const Node * getNodes() const noexcept
void debugDump() const
Prints a text representation of the tree to stdout.
SYS_FORCE_INLINE BVH() noexcept
T diameter2() const noexcept
SYS_FORCE_INLINE void createBVHNodeBoxes(const UT::BVH< BVH_N > &bvh, const ITEM_BOX *item_boxes, NODE_BOX *node_boxes) noexcept
SYS_FORCE_INLINE void createBVHInterleavedBoxes(const UT::BVH< BVH_N > &bvh, const ITEM_BOX *item_boxes, NODE_BOX *node_boxes, float expand_factor=0.0f) noexcept
STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r)
IMATH_HOSTDEVICE constexpr int sign(T a) IMATH_NOEXCEPT
auto isInside(const TS &pt) const noexcept-> decltype(vals[0][0]<=pt[0])
GLint GLint GLsizei GLsizei GLsizei depth
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
void traverse(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
static void createTrivialIndices(SRC_INT_TYPE *indices, const INT_TYPE n) noexcept
static constexpr bool theAllPointsValid
isValid() doesn't need to be called if theAllPointsValid is true.
static SYS_FORCE_INLINE INT_TYPE getInternalNum(INT_TYPE node_int) noexcept
SYS_FORCE_INLINE float queryDistance2(const POSITION &tree_point, const RADIUS_ARRAY &radii, uint index) const
This must be the exact distance squared.
SYS_FORCE_INLINE Box & operator=(const Box< S, NAXES > &other) noexcept
SYS_FORCE_INLINE void intersectTol(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, T tolerance) const noexcept
Intersect the box expanded by the specified tolerance in all axes.
void getIntersectingBoxesBatch(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > *query_box, UT_Array< INT_TYPE > *box_indices, BVHUnorderedStack &stack) noexcept
UT_Array< BVHOrderedStackEntry > BVHOrderedStack
SYS_FORCE_INLINE void initBounds(const TS &pt) noexcept
SYS_FORCE_INLINE INT_TYPE getNumNodes() const noexcept
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GA_API const UT_StringHolder N
SYS_FORCE_INLINE void initBoundsUnordered(const TS &p0, const TS &p1) 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 constexpr INT_TYPE INTERNAL_BIT
static constexpr INT_TYPE theN
SYS_FORCE_INLINE void initBoundsUnordered(const Box< T, NAXES > &src0, const Box< T, NAXES > &src1) noexcept
T volume() const noexcept
void getIntersectingBoxes(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
constexpr float operator[](exint i) const noexcept
static SYS_FORCE_INLINE bool isInternal(INT_TYPE node_int) noexcept
SYS_FORCE_INLINE Box(const TS &pt) noexcept
SYS_FORCE_INLINE bool operator<(const BVHOrderedStackEntry &other) const
SYS_FORCE_INLINE void enlargeBounds(const Box< T, NAXES > &src) noexcept
SYS_FORCE_INLINE void combine(const Box< T, NAXES > &src) noexcept
void traverseVector(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
SYS_FORCE_INLINE const T * operator[](const size_t axis) const noexcept
constexpr ZeroRadiiWrapper()=default
SYS_FORCE_INLINE bool isValid(uint tree_point_index) const