28 #define BVH_TRY_ALL_AXES 0
36 template<
typename T,u
int NAXES>
49 "UT::Box should be POD, for better performance in UT_Array, etc.");
51 for (
uint axis = 0; axis < NAXES; ++axis) {
52 vals[axis][0] =
T(other.vals[axis][0]);
53 vals[axis][1] =
T(other.vals[axis][1]);
56 template<
typename S,
bool INSTANTIATED>
58 for (
uint axis = 0; axis < NAXES; ++axis) {
59 vals[axis][0] = pt[axis];
60 vals[axis][1] = pt[axis];
65 for (
uint axis = 0; axis < NAXES; ++axis) {
66 vals[axis][0] =
T(other.vals[axis][0]);
67 vals[axis][1] =
T(other.vals[axis][1]);
82 for (
uint axis = 0; axis < NAXES; ++axis) {
91 for (
uint axis = 0; axis < NAXES; ++axis) {
92 vals[axis][0] =
src.vals[axis][0];
93 vals[axis][1] =
src.vals[axis][1];
100 for (
uint axis = 0; axis < NAXES; ++axis) {
101 vals[axis][0] =
SYSmin(src0.vals[axis][0], src1.vals[axis][0]);
102 vals[axis][1] =
SYSmax(src0.vals[axis][1], src1.vals[axis][1]);
106 for (
uint axis = 0; axis < NAXES; ++axis) {
107 T& minv =
vals[axis][0];
108 T& maxv =
vals[axis][1];
109 const T curminv =
src.vals[axis][0];
110 const T curmaxv =
src.vals[axis][1];
111 minv = (minv < curminv) ? minv : curminv;
112 maxv = (maxv > curmaxv) ? maxv : curmaxv;
119 template<
typename S,
bool INSTANTIATED>
122 for (
uint axis = 0; axis < NAXES; ++axis) {
123 vals[axis][0] = pt[axis];
124 vals[axis][1] = pt[axis];
127 template<
bool INSTANTIATED>
130 for (
uint axis = 0; axis < NAXES; ++axis) {
135 template<
bool INSTANTIATED>
138 for (
uint axis = 0; axis < NAXES; ++axis) {
143 template<
bool INSTANTIATED>
146 for (
uint axis = 0; axis < NAXES; ++axis) {
151 template<
bool INSTANTIATED>
159 for (
uint axis = 0; axis < NAXES; ++axis) {
160 v[axis] =
vals[axis][0];
168 for (
uint axis = 0; axis < NAXES; ++axis) {
169 v[axis] =
vals[axis][1];
177 for (
uint axis = 1; axis < NAXES; ++axis) {
178 diff = (
vals[axis][1]-
vals[axis][0]);
185 for (
uint axis = 1; axis < NAXES; ++axis) {
186 product *= (
vals[axis][1]-
vals[axis][0]);
206 return d0*d1 + d1*d2 + d2*d0;
214 const T d0d1 = d0*d1;
215 const T d2d3 = d2*d3;
216 return d0d1*(d2+d3) + d2d3*(d0+d1);
220 for (
uint skipped_axis = 0; skipped_axis < NAXES; ++skipped_axis) {
222 for (
uint axis = 0; axis < NAXES; ++axis) {
223 if (axis != skipped_axis) {
224 product *= (
vals[axis][1]-
vals[axis][0]);
233 for (
uint axis = 1; axis < NAXES; ++axis) {
234 sum += (
vals[axis][1]-
vals[axis][0]);
238 template<
bool INSTANTIATED0,
bool INSTANTIATED1>
246 for (
int axis = 0; axis < NAXES; ++axis)
249 T t1 = (
vals[axis][
sign] - origin[axis]) * inverse_direction[axis];
250 T t2 = (
vals[axis][sign^1] - origin[axis]) * inverse_direction[axis];
251 box_tmin =
SYSmax(t1, box_tmin);
252 box_tmax =
SYSmin(t2, box_tmax);
256 template<
bool INSTANTIATED0,
bool INSTANTIATED1>
265 for (
int axis = 0; axis < NAXES; ++axis)
269 vals[axis][0] - tolerance,
270 vals[axis][1] + tolerance
272 T t1 = (local_vals[
sign] - origin[axis]) * inverse_direction[axis];
273 T t2 = (local_vals[sign^1] - origin[axis]) * inverse_direction[axis];
274 box_tmin =
SYSmax(t1, box_tmin);
275 box_tmax =
SYSmin(t2, box_tmax);
279 for (
int axis = 0; axis < NAXES; ++axis)
281 dest.vals[axis][0] =
SYSmax(
vals[axis][0], other.vals[axis][0]);
282 dest.vals[axis][1] =
SYSmin(
vals[axis][1], other.vals[axis][1]);
285 template<
bool INSTANTIATED>
291 for (
int axis = 1; axis < NAXES; ++axis)
298 template<
bool INSTANTIATED>
304 for (
int axis = 1; axis < NAXES; ++axis)
311 template<
bool INSTANTIATED0>
315 vals[0][0] <= pt[0] &&
vals[0][1] >= pt[0] &&
316 vals[1][0] <= pt[1] && vals[1][1] >= pt[1] &&
317 vals[2][0] <= pt[2] && vals[2][1] >= pt[2];
407 template<BVH_Heuristic H,
typename T,u
int NAXES,
typename BOX_TYPE,
typename SRC_INT_TYPE=INT_TYPE>
408 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;
411 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;
448 template<
typename LOCAL_DATA,
typename FUNCTORS>
451 LOCAL_DATA *data_for_parent=
nullptr)
const noexcept;
459 template<typename LOCAL_DATA,typename FUNCTORS>
463 LOCAL_DATA *data_for_parent=
nullptr)
const noexcept;
479 template<typename LOCAL_DATA,typename FUNCTORS>
482 LOCAL_DATA *data_for_parent=
nullptr)
const noexcept;
487 template<typename SRC_INT_TYPE>
491 template<typename LOCAL_DATA,typename FUNCTORS>
496 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
498 template<typename LOCAL_DATA,typename FUNCTORS>
499 void traverseParallelHelper(
505 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
507 template<typename LOCAL_DATA,typename FUNCTORS>
508 void traverseVectorHelper(
512 LOCAL_DATA *data_for_parent=
nullptr) const noexcept;
514 template<typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
515 static
void computeFullBoundingBox(
Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, const
INT_TYPE nboxes, SRC_INT_TYPE* indices) noexcept;
517 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
518 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;
520 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
521 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;
523 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
524 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;
526 template<
BVH_Heuristic H,typename T,
uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
527 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;
530 template<BVH_Heuristic H,
typename T,u
int NAXES,
typename BOX_TYPE,
typename SRC_INT_TYPE>
531 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;
533 template<BVH_Heuristic H,
typename T,u
int NAXES,
typename BOX_TYPE,
typename SRC_INT_TYPE>
534 static void splitLargeCountAxis(
535 const INT_TYPE axis,
const T axis_min,
const T axis_length,
542 const BOX_TYPE* boxes, SRC_INT_TYPE* indices,
INT_TYPE nboxes) noexcept;
545 template<INT_TYPE PARALLEL_THRESHOLD,
typename SRC_INT_TYPE>
548 template<
typename T,
typename BOX_TYPE,
typename SRC_INT_TYPE>
549 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;
551 template<
typename T,
typename BOX_TYPE,
typename SRC_INT_TYPE>
552 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;
560 return nboxes/2 + nboxes/(2*(N-1));
563 template<BVH_Heuristic H,
typename T, u
int NAXES>
566 return box.axis_sum();
569 return box.half_surface_area();
575 T diameter2 = box.diameter2();
576 return SYSsqrt(diameter2);
579 return box.diameter2();
582 T diameter2 = box.diameter2();
583 return diameter2*SYSsqrt(diameter2);
585 UT_ASSERT_MSG(0,
"BVH_Heuristic::MEDIAN_MAX_AXIS should be handled separately by caller!");
589 int getMaxDepthHelper(
INT_TYPE curnode,
int depth)
const noexcept;
590 int getPureInternalDepthHelper(
INT_TYPE curnode,
int depth)
const noexcept;
593 static constexpr
INT_TYPE NSPANS = 16;
594 static constexpr
INT_TYPE NSPLITS = NSPANS-1;
597 static constexpr
INT_TYPE MIN_FRACTION = 16;
603 template<u
int BVH_N,
typename ITEM_BOX,
typename NODE_BOX>
606 const ITEM_BOX* item_boxes,
607 NODE_BOX* node_boxes) noexcept;
612 template<u
int NAXES,
typename T,u
int BVH_N,
typename ITEM_BOX,
typename NODE_BOX>
615 const ITEM_BOX* item_boxes,
616 NODE_BOX* node_boxes,
617 float expand_factor=0.0
f) noexcept;
622 template<
uint NAXES,typename T,typename ITEM_BOX,typename NODE_BOX,typename INT_TYPE0=
uint>
624 const UT::BVH<4>& bvh,
625 const ITEM_BOX* item_boxes,
626 NODE_BOX* node_boxes,
627 const
v4uu* node_nitems,
628 const INT_TYPE0* indices_mapping=
nullptr) noexcept;
637 template<
uint NAXES,typename INT_TYPE>
639 const UT::
BVH<4>& bvh,
640 const UT::
Box<
v4uf,NAXES>* node_boxes,
641 const UT::
Box<
float,NAXES>& query_box,
645 template<
uint NAXES,typename INT_TYPE>
647 const UT::
BVH<4>& bvh,
648 const UT::
Box<v4uf,NAXES>* node_boxes,
649 const UT::
Box<
float,NAXES>& query_box,
653 template<
uint NAXES,typename INT_TYPE>
655 const UT::
BVH<4>& bvh,
656 const UT::
Box<v4uf,NAXES>* node_boxes,
657 const UT::
Box<
float,NAXES>& query_box,
661 template<
uint NAXES,typename INT_TYPE,
int BATCH_SIZE>
663 const UT::
BVH<4>& bvh,
664 const UT::
Box<v4uf,NAXES>* node_boxes,
665 const UT::
Box<
float,NAXES> *query_box,
671 const UT::
BVH<4>& bvh,
673 exint nitems) noexcept;
680 SYS_FORCE_INLINE BVHOrderedStackEntry(const BVHOrderedStackEntry& other) noexcept = default;
681 SYS_FORCE_INLINE BVHOrderedStackEntry(BVHOrderedStackEntry&& other) noexcept = default;
682 SYS_FORCE_INLINE BVHOrderedStackEntry& operator=(const BVHOrderedStackEntry& other) noexcept = default;
683 SYS_FORCE_INLINE BVHOrderedStackEntry& operator=(BVHOrderedStackEntry&& other) noexcept = default;
685 : myDistSquared(dist_squared)
709 return !(*
this == other);
743 template<
typename QUERY_POINT>
763 template<
typename POSITION,
typename RADIUS_ARRAY>
766 return myQueryPoint.distance2(tree_point, radii, index);
772 template<
bool farthest,u
int NAXES>
775 return myQueryPoint.template boxHitAndDist2<farthest>(boxes, max_dist_squared, internal_node_num, dist2);
787 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>
791 const v4uu* node_nitems,
792 const INT_TYPE0* indices_mapping,
793 const POSITION_ARRAY& positions,
794 QUERY_POINT& query_point,
797 const RADIUS_ARRAY& radii = ZeroRadiiWrapper(),
806 #undef BVH_TRY_ALL_AXES
SYS_FORCE_INLINE bool operator==(const BVHOrderedStackEntry &other) const
vint4 max(const vint4 &a, const vint4 &b)
SYS_FORCE_INLINE uint boxHitAndDist2(const UT::Box< v4uf, NAXES > &boxes, const float max_dist_squared, const uint internal_node_num, v4uf &dist2) const
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 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 void intersectTol(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES, INSTANTIATED0 > &signs, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &origin, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &inverse_direction, T tolerance) const noexcept
Intersect the box expanded by the specified tolerance in all axes.
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) const noexcept
SYS_FORCE_INLINE bool operator!=(const BVHOrderedStackEntry &other) const
SYS_FORCE_INLINE void enlargeBounds(const UT_FixedVector< T, NAXES, INSTANTIATED > &pt) noexcept
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)
auto isInside(const UT_FixedVector< T, NAXES, INSTANTIATED0 > &pt) const noexcept-> decltype(vals[0][0]<=pt[0])
SYS_FORCE_INLINE void initBounds() noexcept
SYS_FORCE_INLINE Box(const UT_FixedVector< S, NAXES, INSTANTIATED > &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
SYS_FORCE_INLINE void intersect(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES, INSTANTIATED0 > &signs, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &origin, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &inverse_direction) 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
#define UT_ASSERT_MSG(ZZ,...)
SYS_FORCE_INLINE void clear() noexcept
SYS_FORCE_INLINE void combine(const UT_FixedVector< T, NAXES, INSTANTIATED > &pt) noexcept
SYS_FORCE_INLINE T * operator[](const size_t axis) noexcept
T axis_sum() const noexcept
SYS_FORCE_INLINE void initBoundsUnordered(const UT_FixedVector< T, NAXES, INSTANTIATED > &p0, const UT_FixedVector< T, NAXES, INSTANTIATED > &p1) noexcept
SYS_FORCE_INLINE void initBounds(const UT_FixedVector< S, NAXES, INSTANTIATED > &pt) 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.
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 float distance2(const POSITION &tree_point, const RADIUS_ARRAY &radii, uint index) const
This must be the exact distance squared.
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.
GLuint GLuint GLsizei GLenum const void * indices
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
SYS_FORCE_INLINE void initBounds(const UT_FixedVector< T, NAXES, INSTANTIATED > &min, const UT_FixedVector< T, NAXES, INSTANTIATED > &max) 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
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 Box & operator=(const Box< S, NAXES > &other) noexcept
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
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
SYS_FORCE_INLINE INT_TYPE getNumNodes() const noexcept
GA_API const UT_StringHolder N
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
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) 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
vint4 min(const vint4 &a, const vint4 &b)
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
GLint GLint GLsizei GLsizei GLsizei depth
SYS_FORCE_INLINE bool isValid(uint tree_point_index) const