pbat::gpu::impl::geometry::Bvh Class Reference

Radix-tree linear BVH. More...

Public Types
using	OverlapType = cuda::std::pair<GpuIndex, GpuIndex>
using	MortonCodeType = pbat::geometry::MortonCodeType

Public Member Functions
	Bvh (GpuIndex nBoxes)
void	Build (Aabb< kDims > &aabbs, Morton::Bound const &min, Morton::Bound const &max)
	Build BVH from primitive aabbs.
void	SortByMortonCode (Aabb< kDims > &aabbs, Morton::Bound const &min, Morton::Bound const &max)
void	BuildTree (GpuIndex n)
	Builds the BVH's hierarchy, assuming primitives have been sorted.
void	ConstructBoxes (Aabb< kDims > &aabbs)
	Computes internal node bounding boxes, assuming the BVH's hierarchy is built.
template<class FOnOverlapDetected>
void	DetectOverlaps (Aabb< kDims > const &aabbs, FOnOverlapDetected &&fOnOverlapDetected)
template<class FOnOverlapDetected, auto kStackSize = 64>
void	DetectOverlaps (Aabb< kDims > const &leafAabbs, Aabb< kDims > const &queryAabbs, FOnOverlapDetected fOnOverlapDetected)
template<class FGetQueryObject, class FMinDistanceToBox, class FDistanceToLeaf, class FDistanceUpperBound, class FOnNearestNeighbourFound, auto kQueueSize = 8, auto kStackSize = 64>
void	NearestNeighbours (Aabb< kDims > const &aabbs, GpuIndex nQueries, FGetQueryObject fGetQueryObject, FMinDistanceToBox fMinDistanceToBox, FDistanceToLeaf fDistanceToleaf, FDistanceUpperBound fDistanceUpperBound, FOnNearestNeighbourFound fOnNearestNeighbourFound, GpuScalar eps=GpuScalar(0))
template<class FGetQueryObject, class FMinDistanceToBox, class FDistanceToLeaf, class FDistanceUpperBound, class FOnFound, auto kStackSize = 64>
void	RangeSearch (Aabb< kDims > const &aabbs, GpuIndex nQueries, FGetQueryObject fGetQueryObject, FMinDistanceToBox fMinDistanceToBox, FDistanceToLeaf fDistanceToleaf, FDistanceUpperBound fDistanceUpperBound, FOnFound fOnFound)

Public Attributes
common::Buffer< GpuIndex >	inds
	n leaf box indices
Morton	morton
	Morton codes of leaf boxes.
common::Buffer< GpuIndex, 2 >	child
common::Buffer< GpuIndex >	parent
common::Buffer< GpuIndex, 2 >	rightmost
Aabb< kDims >	iaabbs
common::Buffer< GpuIndex >	visits

Static Public Attributes
static auto constexpr	kDims = 3

Friends
class	BvhQuery

Detailed Description

Radix-tree linear BVH.

Implements of [6]

Constructor & Destructor Documentation

Bvh()

pbat::gpu::impl::geometry::Bvh::Bvh

(

GpuIndex

nBoxes

)

Parameters

nBoxes

Member Function Documentation

Build()

void pbat::gpu::impl::geometry::Bvh::Build	(	Aabb< kDims > &	aabbs,
		Morton::Bound const &	min,
		Morton::Bound const &	max )

Build BVH from primitive aabbs.

Parameters

aabbs	Primitive aabbs
min	World bounding box minimum
max	World bounding box maximum

BuildTree()

void pbat::gpu::impl::geometry::Bvh::BuildTree

(

GpuIndex

n

)

Builds the BVH's hierarchy, assuming primitives have been sorted.

Parameters

n	Number of leaf boxes

ConstructBoxes()

void pbat::gpu::impl::geometry::Bvh::ConstructBoxes

(

Aabb< kDims > &

aabbs

)

Computes internal node bounding boxes, assuming the BVH's hierarchy is built.

Parameters

aabbs

DetectOverlaps() [1/2]

template<class FOnOverlapDetected>

void pbat::gpu::impl::geometry::Bvh::DetectOverlaps ( Aabb< kDims > const & aabbs, FOnOverlapDetected && fOnOverlapDetected )

inline

Template Parameters

FOnOverlapDetected

Parameters

aabbs	The same aabbs that were given to Build(), otherwise undefined behavior.
fOnOverlapDetected	Callback called on detected overlaps with signature void f(GpuIndex,GpuIndex)

DetectOverlaps() [2/2]

template<class FOnOverlapDetected, auto kStackSize>

void pbat::gpu::impl::geometry::Bvh::DetectOverlaps ( Aabb< kDims > const & leafAabbs, Aabb< kDims > const & queryAabbs, FOnOverlapDetected fOnOverlapDetected )

inline

Template Parameters

FOnOverlapDetected
kStackSize

Parameters

leafAabbs
queryAabbs
fOnOverlapDetected	Callback called on detected overlaps with signature void f(GpuIndex q, GpuIndex i)

NearestNeighbours()

template<class FGetQueryObject, class FMinDistanceToBox, class FDistanceToLeaf, class FDistanceUpperBound, class FOnNearestNeighbourFound, auto kQueueSize, auto kStackSize>

void pbat::gpu::impl::geometry::Bvh::NearestNeighbours ( Aabb< kDims > const & aabbs, GpuIndex nQueries, FGetQueryObject fGetQueryObject, FMinDistanceToBox fMinDistanceToBox, FDistanceToLeaf fDistanceToleaf, FDistanceUpperBound fDistanceUpperBound, FOnNearestNeighbourFound fOnNearestNeighbourFound, GpuScalar eps = GpuScalar(0) )

inline

Template Parameters

FGetQueryObject	Callable with signature TQuery f(GpuIndex)
FMinDistanceToBox	Callable with signature GpuScalar f(TQuery, Point, Point) where Point=pbat::math::linalg::mini::SVector<GpuScalar, 3>
FDistanceToLeaf	Callable with signature GpuScalar f(GpuIndex q, TQuery query, GpuIndex leaf, " "GpuIndex i)
FDistanceUpperBound	Callable with signature GpuScalar f(GpuIndex)
FOnNearestNeighbourFound	Callable with signature void f(GpuIndex query, GpuIndex i, GpuScalar d, GpuIndex k)
kQueueSize	Nearest neighbour queue size
kStackSize	Branch and bound minimization's depth-first search stack size

Parameters

aabbs	The same aabbs that were given to Build(), otherwise undefined behavior.
nQueries	Number of queries
fGetQueryObject	Callable to get query object with signature TQuery f(GpuIndex)
fMinDistanceToBox	Callable to get minimum distance to box with signature GpuScalar f(TQuery, Point, Point)
fDistanceToleaf	Callable to get distance to leaf with signature f(GpuIndex q, TQuery query, GpuIndex leaf, " "GpuIndex i)
fDistanceUpperBound	Callable to get query q's distance upper bound with signature GpuScalar f(GpuIndex)
fOnNearestNeighbourFound	Callable to get nearest neighbour with signature void f(GpuIndex q, GpuIndex i, GpuScalar d, GpuIndex k)
eps	Epsilon for distance comparison

RangeSearch()

template<class FGetQueryObject, class FMinDistanceToBox, class FDistanceToLeaf, class FDistanceUpperBound, class FOnFound, auto kStackSize>

void pbat::gpu::impl::geometry::Bvh::RangeSearch ( Aabb< kDims > const & aabbs, GpuIndex nQueries, FGetQueryObject fGetQueryObject, FMinDistanceToBox fMinDistanceToBox, FDistanceToLeaf fDistanceToleaf, FDistanceUpperBound fDistanceUpperBound, FOnFound fOnFound )

inline

Template Parameters

FGetQueryObject	Callable with signature TQuery f(GpuIndex)
FMinDistanceToBox	Callable with signature GpuScalar f(TQuery, Point, Point) where Point=pbat::math::linalg::mini::SVector<GpuScalar, 3>
FDistanceToLeaf	Callable with signature GpuScalar f(GpuIndex q, TQuery query, GpuIndex leaf, GpuIndex i)
FDistanceUpperBound	Callable with signature GpuScalar f(GpuIndex)
FOnFound	Callable with signature void f(GpuIndex q, TQuery query, GpuIndex leafIdx, GpuIndex i, TLeaf leaf, GpuScalar d)
kStackSize	Branch and bound minimization's depth-first search stack size

Parameters

aabbs	The same aabbs that were given to Build(), otherwise undefined behavior.
nQueries	Number of queries
fGetQueryObject	Callable to get query object with signature TQuery f(GpuIndex)
fMinDistanceToBox	Callable to get minimum distance to box with signature GpuScalar
fDistanceToleaf	Callable to get distance to leaf with signature GpuScalar f(GpuIndex q, TQuery query, GpuIndex leaf, GpuIndex i)
fDistanceUpperBound	Callable to get query q's distance upper bound with signature GpuScalar f(GpuIndex)
fOnFound	Callable for handling satisfied queries with signature void f(GpuIndex q, GpuIndex leafIdx, GpuIndex i, GpuScalar d)

SortByMortonCode()

void pbat::gpu::impl::geometry::Bvh::SortByMortonCode	(	Aabb< kDims > &	aabbs,
		Morton::Bound const &	min,
		Morton::Bound const &	max )

Parameters

aabbs
min
max

Member Data Documentation

child

common::Buffer<GpuIndex, 2> pbat::gpu::impl::geometry::Bvh::child

(n-1)x2 left and right children. If child[lr][i] > n - 2, then it is a leaf node, otherwise an internal node. lr == 0 -> left child buffer, while lr == 1 -> right child buffer. i == 0 -> root node.

iaabbs

Aabb<kDims> pbat::gpu::impl::geometry::Bvh::iaabbs

(n-1) internal node bounding boxes for n leaf node bounding boxes. The box 0 is always the root.

parent

common::Buffer<GpuIndex> pbat::gpu::impl::geometry::Bvh::parent

(2n-1) parent map, s.t. parent[i] -> index of parent node of node i. parent[0] == -1 <=> root node has no parent.

rightmost

common::Buffer<GpuIndex, 2> pbat::gpu::impl::geometry::Bvh::rightmost

(n-1) rightmost map, s.t. rightmost[lr][i] -> right most leaf in left (lr == 0) or right (lr == 1) subtree.

visits

common::Buffer<GpuIndex> pbat::gpu::impl::geometry::Bvh::visits

(n-1) atomic counters of internal node visits for bottom-up bounding box computations

---

The documentation for this class was generated from the following files:

• C:/git/PhysicsBasedAnimationToolkit/source/pbat/gpu/impl/geometry/Bvh.cuh
• C:/git/PhysicsBasedAnimationToolkit/source/pbat/gpu/impl/geometry/Bvh.cu