KarrasRadixTree.cpp File Reference

#include "shambase/aliases_int.hpp"
#include "shambase/type_traits.hpp"
#include "shambackends/DeviceBuffer.hpp"
#include "shambackends/DeviceQueue.hpp"
#include "shambackends/DeviceScheduler.hpp"
#include "shambackends/kernel_call.hpp"
#include "shammath/sfc/morton.hpp"
#include "shamtree/KarrasRadixTree.hpp"
#include "shamtree/MortonCodeSet.hpp"
#include <utility>

Include dependency graph for KarrasRadixTree.cpp:

Go to the source code of this file.

Macros
#define	SGN(x)   (x == 0) ? 0 : ((x > 0) ? 1 : -1)
	Macro to get the sign of a number.

Functions
template<class u_morton >
void	__karras_alg (sham::DeviceQueue &queue, u32 internal_cell_count, sham::DeviceBuffer< u_morton > &in_morton, sham::DeviceBuffer< u32 > &out_buf_lchild_id, sham::DeviceBuffer< u32 > &out_buf_rchild_id, sham::DeviceBuffer< u8 > &out_buf_lchild_flag, sham::DeviceBuffer< u8 > &out_buf_rchild_flag, sham::DeviceBuffer< u32 > &out_buf_endrange)
	Karras 2012 algorithm with addition endrange buffer.
template<class Tmorton >
u32	shamtree::get_tree_depth ()
template<class Tmorton >
KarrasRadixTree	shamtree::karras_tree_from_morton_set (sham::DeviceScheduler_ptr dev_sched, u32 morton_count, sham::DeviceBuffer< Tmorton > &morton_codes, KarrasRadixTree &&recycled_tree)
	Constructs a KarrasRadixTree from a set of reduced Morton codes.
template<class Tmorton >
KarrasRadixTree	shamtree::karras_tree_from_morton_set (sham::DeviceScheduler_ptr dev_sched, u32 morton_count, sham::DeviceBuffer< Tmorton > &morton_codes)
	Constructs a KarrasRadixTree from a set of reduced Morton codes without reuse.
std::string	shamtree::karras_tree_to_dot_graph (KarrasRadixTree &recycled_tree)
	Get tree as dot graph.

Detailed Description

Author

Timothée David–Cléris (tim.s.nosp@m.hamr.nosp@m.ock@p.nosp@m.roto.nosp@m.n.me)

Definition in file KarrasRadixTree.cpp.

Macro Definition Documentation

SGN

#define SGN

(

x

)

(x == 0) ? 0 : ((x > 0) ? 1 : -1)

Macro to get the sign of a number.

Definition at line 28 of file KarrasRadixTree.cpp.

Function Documentation

__karras_alg()

template<class u_morton >

void __karras_alg	(	sham::DeviceQueue &	queue,
		u32	internal_cell_count,
		sham::DeviceBuffer< u_morton > &	in_morton,
		sham::DeviceBuffer< u32 > &	out_buf_lchild_id,
		sham::DeviceBuffer< u32 > &	out_buf_rchild_id,
		sham::DeviceBuffer< u8 > &	out_buf_lchild_flag,
		sham::DeviceBuffer< u8 > &	out_buf_rchild_flag,
		sham::DeviceBuffer< u32 > &	out_buf_endrange
	)

Karras 2012 algorithm with addition endrange buffer.

Given a list of morton codes, compute the left and right child id, left and right child flag, and the endrange for each cell using the Karras 2012 algorithm.

Parameters

[in]	queue	sycl queue
[in]	internal_cell_count	number of internal cells
[in]	in_morton	input morton codes
[out]	out_buf_lchild_id	left child id
[out]	out_buf_rchild_id	right child id
[out]	out_buf_lchild_flag	left child flag
[out]	out_buf_rchild_flag	right child flag
[out]	out_buf_endrange	endrange

Definition at line 46 of file KarrasRadixTree.cpp.

Here is the call graph for this function:

get_tree_depth()

template<class Tmorton >

u32 shamtree::get_tree_depth ( )

inline

Definition at line 148 of file KarrasRadixTree.cpp.

karras_tree_from_morton_set() [1/2]

template<class Tmorton >

KarrasRadixTree shamtree::karras_tree_from_morton_set	(	sham::DeviceScheduler_ptr	dev_sched,
		u32	morton_count,
		sham::DeviceBuffer< Tmorton > &	morton_codes
	)

Constructs a KarrasRadixTree from a set of reduced Morton codes without reuse.

Equivalent to karras_tree_from_morton_set but performs the allocations.

Template Parameters

Tmorton

The type of the Morton codes.

Parameters

[in]	dev_sched	A pointer to the device scheduler used for managing execution on the device.
[in]	morton_count	The number of Morton codes provided.
[in]	morton_codes	A device buffer containing the Morton codes.

Returns

A KarrasRadixTree object populated with the tree structure based on the provided Morton codes.

Definition at line 187 of file KarrasRadixTree.cpp.

Here is the call graph for this function:

karras_tree_from_morton_set() [2/2]

template<class Tmorton >

KarrasRadixTree shamtree::karras_tree_from_morton_set	(	sham::DeviceScheduler_ptr	dev_sched,
		u32	morton_count,
		sham::DeviceBuffer< Tmorton > &	morton_codes,
		KarrasRadixTree &&	recycled_tree
	)

Constructs a KarrasRadixTree from a set of reduced Morton codes.

This function builds a KarrasRadixTree using the provided set of Morton codes. The tree is constructed by resizing the buffers for left and right child IDs, child flags, and end ranges to accommodate the internal cells, then executing the Karras algorithm on the device scheduler's queue.

Template Parameters

Tmorton

The type of the Morton codes.

Parameters

[in]	dev_sched	A pointer to the device scheduler used for managing execution on the device.
[in]	morton_count	The number of Morton codes provided.
[in]	morton_codes	A device buffer containing the Morton codes.
[in,out]	recycled_tree	A KarrasRadixTree object from which we will reuse the allocs.

Returns

A KarrasRadixTree object populated with the tree structure based on the provided Morton codes.

Definition at line 153 of file KarrasRadixTree.cpp.

Here is the call graph for this function:

karras_tree_to_dot_graph()

std::string shamtree::karras_tree_to_dot_graph

(

KarrasRadixTree &

recycled_tree

)

Get tree as dot graph.

Definition at line 239 of file KarrasRadixTree.cpp.

Here is the call graph for this function: