A PackedBVH's nodes grouped by tree depth, deepest level first: the order in which BVH::refit() refits them, one level at a time. More...

#include <EBGeometry_BVHRefit.hpp>

Public Member Functions
template<class T , class P , size_t K>
	RefitSchedule (Pool &a_pool, const PackedBVH< T, P, K > &a_bvh)
	Group the nodes of `a_bvh` by depth.

size_t	numLevels () const noexcept
	Number of tree levels; 0 for an empty BVH.

Friends
template<class T , class P , size_t K, class BVConstructor >
void	refit (Pool &a_pool, const PackedBVH< T, P, K > &a_bvh, const RefitSchedule &a_schedule, const BVConstructor &a_bvConstructor)
	BVH::refit() reads the node list and the levels.

Detailed Description

A PackedBVH's nodes grouped by tree depth, deepest level first: the order in which BVH::refit() refits them, one level at a time.

Opt-in: only a BVH that is refitted with BVH::refit() needs one. Build it on the host after the BVH is built and before its pool is frozen: the node list, 4 bytes per node, is reserved from the BVH's pool, so a mirror of the pool carries it along, and one schedule serves the BVH in its own pool and in every mirror of it. The level boundaries stay in the schedule, on the host, which launches the levels. The tree's shape never changes in a refit, so a schedule is built once; a rebuilt BVH needs a new one.

Grouping by depth rather than refitting in one sweep is what lets a level's nodes run in parallel: a node needs its children's boxes, and every child is one level deeper. A schedule-free alternative, repeated passes over all nodes until the boxes settle (one per tree level after the leaves), needs no memory but measured 3 to 4 times slower than the schedule on a device (float and double, 1M and 4M boxes, K = 4, RTX 3080), from re-reading every node in every pass; it was ruled out.

Constructor & Destructor Documentation

◆ RefitSchedule()

template<class T , class P , size_t K>

EBGeometry::BVH::RefitSchedule::RefitSchedule	(	Pool &	a_pool,
		const PackedBVH< T, P, K > &	a_bvh
	)

Group the nodes of a_bvh by depth.

Aborts, in every build, if a_bvh does not live in a_pool or the pool is frozen.

Template Parameters

T	Floating-point precision.
P	Primitive type.
K	Branching factor.

Parameters

[in,out]	a_pool	The pool `a_bvh` lives in, which the node list is reserved from. It must not be frozen.
[in]	a_bvh	The BVH, on the host.

Member Function Documentation

◆ numLevels()

size_t EBGeometry::BVH::RefitSchedule::numLevels ( ) const

inlinenoexcept

Number of tree levels; 0 for an empty BVH.

Returns: The level count.

Friends And Related Symbol Documentation

◆ refit

template<class T , class P , size_t K, class BVConstructor >

void refit	(	Pool &	a_pool,
		const PackedBVH< T, P, K > &	a_bvh,
		const RefitSchedule &	a_schedule,
		const BVConstructor &	a_bvConstructor
	)

friend

BVH::refit() reads the node list and the levels.

The same boxes as PackedBVH::refit(), and the same use: for primitives that move without changing which primitives the BVH holds or their order (adding, removing or reordering them needs a rebuild), and not a substitute for a rebuild once a deformation is large enough to make the tree loose.

Runs where a_pool's memory is. On a device-accessible pool, every tree level is one GPU::parallelFor() with a thread per node: device kernels in a CUDA or HIP build, host loops in a host build (over emulated device memory). On a host pool it is PackedBVH::refit()'s sweep. a_pool is the BVH's own pool or any mirror of it (a device pool is frozen, as every mirror is). On a device, a_bvConstructor runs in the kernels, so it must be trivially copyable and EBGEOMETRY_HOST_DEVICE and read only memory the device can reach; in a CUDA or HIP translation unit it must be EBGEOMETRY_HOST_DEVICE whatever the pool, since the kernels are compiled for it. A constructor that is not trivially copyable is accepted for a host pool only.

How the primitives were moved is the caller's business (any kernel, any library, a copy from the host), as long as that work has finished: the levels run on the default stream, and refit() returns once the boxes are done. Work on a stream that does not synchronize with the default stream must be synchronized first.

Aborts, in every build, on a schedule built in a pool of another mirror chain or for another BVH (one with a different node count, or another BVH of the pool, or this one rebuilt), and, through PackedBVH::rebasedView(), when a_bvh does not fit in a_pool.