#include <Boctree.h>

Inheritance diagram for BOctTree< T >:

Public Member Functions
void	AllPoints (vector< T * > &vp)

	BOctTree ()

	BOctTree (const BOctTree &other, unsigned char *mem_ptr, unsigned int mem_max)

template<class P >
	BOctTree (P const pts, int n, T voxelSize, PointType _pointtype=PointType(), bool _earlystop=false)

	BOctTree (std::string filename)

template<class P >
	BOctTree (vector< P * > &pts, T voxelSize, PointType _pointtype=PointType(), bool _earlystop=false)

long	countLeaves ()

long	countNodes ()

long	countOctLeaves ()

void	deserialize (std::string filename)

const T *	getCenter () const

void	getCenter (double _center[3]) const

unsigned int	getMaxDepth () const

const T *	getMaxs () const

unsigned int	getMemorySize ()
	Size of the whole tree structure, including the main class, its serialize critical allocated variables and nodes, not the allocator. More...

const T *	getMins () const

void	GetOctTreeCenter (vector< T * > &c)

void	GetOctTreeRandom (vector< T * > &c)

void	GetOctTreeRandom (vector< T * > &c, unsigned int ptspervoxel)

unsigned int	getPointdim () const

const bitoct &	getRoot () const

T	getSize () const

void	init ()

T *	pickPoint (bitoct &node)

void	serialize (std::string filename)

virtual	~BOctTree ()

Public Member Functions inherited from SearchTree
virtual void	getPtPairs (vector< PtPair > pairs, double source_alignxf, const DataXYZ &xyz_r, unsigned int startindex, unsigned int endindex, int thread_num, int rnd, double max_dist_match2, double &sum, double centroid_m, double centroid_d)

virtual void	getPtPairs (vector< PtPair > pairs, double source_alignxf, double const q_points, unsigned int startindex, unsigned int endindex, int thread_num, int rnd, double max_dist_match2, double &sum, double centroid_m, double centroid_d)

virtual void	lock ()

	SearchTree ()

	SearchTree (double **pts, int n)

virtual void	unlock ()

virtual	~SearchTree ()

Public Member Functions inherited from Tree
virtual	~Tree ()

Static Public Member Functions
static void	childcenter (const T pcenter, T ccenter, T size, unsigned char i)

static void	childcenter (int x, int y, int z, int &cx, int &cy, int &cz, char i, int size)

static void	deserialize (std::string filename, vector< Point > &points)

static PointType	readType (std::string filename)

Protected Member Functions
void	_FindClosest (int threadNum, bitoct &node, int size, int x, int y, int z) const

void	AllPoints (bitoct &node, vector< T * > &vp)

template<class P >
void *	branch (bitoct &node, P const splitPoints, int n, T _center[3], T _size)

template<class P >
void *	branch (bitoct &node, vector< P * > &splitPoints, T _center[3], T _size)

template<class P >
unsigned char	childIndex (const T center, const P point)

long	countLeaves (bitoct &node)

long	countNodes (bitoct &node)

long	countOctLeaves (bitoct &node)

template<class P >
void	countPointsAndQueue (vector< P * > &i_points, T center[8][3], T size, bitoct &parent, T *pcenter)

template<class P >
void	countPointsAndQueueFast (P const points, int n, T center[8][3], T size, bitoct &parent, T pcenter[3])

void	deletetNodes (bitoct &node)

void	deserialize (std::ifstream &f, bitoct &node)

double *	FindClosest (double *point, double maxdist2, int threadNum) const

double *	FindClosestInBucket (double *point, double maxdist2, int threadNum)

void	findClosestInLeaf (bitunion< T > *node, int threadNum) const

template<class P >
void	fullsort (P const points, int n, T splitval[3], P const blocks[9])

void	getByIndex (T point, T &points, unsigned int &length)

void	GetOctTreeCenter (vector< T * > &c, bitoct &node, T *center, T size)

void	GetOctTreeRandom (vector< T * > &c, bitoct &node)

void	GetOctTreeRandom (vector< T * > &c, unsigned int ptspervoxel, bitoct &node)

void	serialize (std::ofstream &of, bitoct &node)

template<class P >
P const	sort (P const points, unsigned int n, T splitval, unsigned char index)

Static Protected Member Functions
static void	deserialize (std::ifstream &f, vector< Point > &vpoints, PointType &pointtype)

Protected Attributes
T	add [3]
	Offset and real voxelsize inverse factor for manipulation points. More...

Allocator *	alloc
	Allocator used for creating nodes in the constructor. More...

T	center [3]
	storing the center More...

ip::offset_ptr< unsigned int >	child_bit_depth

ip::offset_ptr< unsigned int >	child_bit_depth_inv

bool	earlystop
	Whether to stop subdividing at N<10 nodes or not. More...

int	largest_index

unsigned char	max_depth
	? More...

ip::offset_ptr< T >	maxs

ip::offset_ptr< T >	mins
	storing minimal and maximal values for all dimensions More...

T	mult

unsigned int	POINTDIM
	Dimension of each point: 3 (xyz) + N (attributes) More...

PointType	pointtype
	Details of point attributes. More...

T	real_voxelSize
	The real voxelsize of the leaves. More...

ip::offset_ptr< bitoct >	root
	the root of the octree More...

T	size
	storing the dimension More...

ip::offset_ptr< bitunion< T > >	uroot

T	voxelSize
	storing the voxel size More...

Static Protected Attributes
static NNParams	params [100]
	Threadlocal storage of parameters used in SearchTree operations. More...

Private Member Functions
void	copy_children (const bitoct &other, bitoct &my)

unsigned int	sizeChildren (const bitoct &node)
	Recursive size of a node's children. More...

Detailed Description

template<typename T>
class BOctTree< T >

Octree.

A cubic bounding box is calculated from the given 3D points. Then it is recusivly subdivided into smaller subboxes

Definition at line 215 of file Boctree.h.

Constructor & Destructor Documentation

◆ BOctTree() [1/5]

template<typename T >

BOctTree< T >::BOctTree ( )

inline

Definition at line 217 of file Boctree.h.

◆ BOctTree() [2/5]

template<typename T >

template<class P >

BOctTree< T >::BOctTree	(	P const	pts,
		int	n,
		T	voxelSize,
		PointType	_pointtype = `PointType()`,
		bool	_earlystop = `false`
	)

inline

Definition at line 221 of file Boctree.h.

◆ BOctTree() [3/5]

template<typename T >

BOctTree< T >::BOctTree ( std::string filename )

inline

Definition at line 266 of file Boctree.h.

◆ BOctTree() [4/5]

template<typename T >

template<class P >

BOctTree< T >::BOctTree	(	vector< P * > &	pts,
		T	voxelSize,
		PointType	_pointtype = `PointType()`,
		bool	_earlystop = `false`
	)

inline

Definition at line 273 of file Boctree.h.

◆ ~BOctTree()

template<typename T >

virtual BOctTree< T >::~BOctTree ( )

inlinevirtual

Definition at line 318 of file Boctree.h.

◆ BOctTree() [5/5]

template<typename T >

BOctTree< T >::BOctTree	(	const BOctTree< T > &	other,
		unsigned char *	mem_ptr,
		unsigned int	mem_max
	)

inline

Copies another (via new constructed) octtree into cache allocated memory and makes it position independant

Definition at line 1440 of file Boctree.h.

Member Function Documentation

◆ _FindClosest()

template<typename T >

void BOctTree< T >::_FindClosest	(	int	threadNum,
		bitoct &	node,
		int	size,
		int	x,
		int	y,
		int	z
	)		const

inlineprotected

This is the heavy duty search function doing most of the (theoretically unneccesary) work. The tree is recursively searched. Depending on which of the 8 child-voxels is closer to the query point, the children are examined in a special order. This order is defined in map, imap is its inverse and sequence2ci is a speedup structure for faster access to the child indices.

Definition at line 1264 of file Boctree.h.

◆ AllPoints() [1/2]

template<typename T >

void BOctTree< T >::AllPoints	(	bitoct &	node,
		vector< T * > &	vp
	)

inlineprotected

Definition at line 692 of file Boctree.h.

◆ AllPoints() [2/2]

template<typename T >

void BOctTree< T >::AllPoints ( vector< T * > & vp )

inline

Definition at line 427 of file Boctree.h.

◆ branch() [1/2]

template<typename T >

template<class P >

void* BOctTree< T >::branch	(	bitoct &	node,
		P const	splitPoints,
		int	n,
		T	_center[3],
		T	_size
	)

inlineprotected

Definition at line 987 of file Boctree.h.

◆ branch() [2/2]

template<typename T >

template<class P >

void* BOctTree< T >::branch	(	bitoct &	node,
		vector< P * > &	splitPoints,
		T	_center[3],
		T	_size
	)

inlineprotected

Definition at line 1020 of file Boctree.h.

◆ childcenter() [1/2]

template<typename T >

static void BOctTree< T >::childcenter	(	const T *	pcenter,
		T *	ccenter,
		T	size,
		unsigned char	i
	)

inlinestatic

Definition at line 596 of file Boctree.h.

◆ childcenter() [2/2]

template<typename T >

static void BOctTree< T >::childcenter	(	int	x,
		int	y,
		int	z,
		int &	cx,
		int &	cy,
		int &	cz,
		char	i,
		int	size
	)

inlinestatic

Definition at line 643 of file Boctree.h.

◆ childIndex()

template<typename T >

template<class P >

unsigned char BOctTree< T >::childIndex	(	const T *	center,
		const P *	point
	)

inlineprotected

Definition at line 1153 of file Boctree.h.

◆ copy_children()

template<typename T >

void BOctTree< T >::copy_children	(	const bitoct &	other,
		bitoct &	my
	)

inlineprivate

Definition at line 1487 of file Boctree.h.

◆ countLeaves() [1/2]

template<typename T >

long BOctTree< T >::countLeaves ( )

inline

Definition at line 430 of file Boctree.h.

◆ countLeaves() [2/2]

template<typename T >

long BOctTree< T >::countLeaves ( bitoct & node )

inlineprotected

Definition at line 923 of file Boctree.h.

◆ countNodes() [1/2]

template<typename T >

long BOctTree< T >::countNodes ( )

inline

Definition at line 429 of file Boctree.h.

◆ countNodes() [2/2]

template<typename T >

long BOctTree< T >::countNodes ( bitoct & node )

inlineprotected

Definition at line 905 of file Boctree.h.

◆ countOctLeaves() [1/2]

template<typename T >

long BOctTree< T >::countOctLeaves ( )

inline

Definition at line 431 of file Boctree.h.

◆ countOctLeaves() [2/2]

template<typename T >

long BOctTree< T >::countOctLeaves ( bitoct & node )

inlineprotected

Definition at line 942 of file Boctree.h.

◆ countPointsAndQueue()

template<typename T >

template<class P >

void BOctTree< T >::countPointsAndQueue	(	vector< P * > &	i_points,
		T	center[8][3],
		T	size,
		bitoct &	parent,
		T *	pcenter
	)

inlineprotected

Definition at line 1052 of file Boctree.h.

◆ countPointsAndQueueFast()

template<typename T >

template<class P >

void BOctTree< T >::countPointsAndQueueFast	(	P const	points,
		int	n,
		T	center[8][3],
		T	size,
		bitoct &	parent,
		T	pcenter[3]
	)

inlineprotected

Definition at line 1090 of file Boctree.h.

◆ deletetNodes()

template<typename T >

void BOctTree< T >::deletetNodes ( bitoct & node )

inlineprotected

Definition at line 961 of file Boctree.h.

◆ deserialize() [1/4]

template<typename T >

void BOctTree< T >::deserialize	(	std::ifstream &	f,
		bitoct &	node
	)

inlineprotected

Definition at line 752 of file Boctree.h.

◆ deserialize() [2/4]

template<typename T >

static void BOctTree< T >::deserialize	(	std::ifstream &	f,
		vector< Point > &	vpoints,
		PointType &	pointtype
	)

inlinestaticprotected

Definition at line 726 of file Boctree.h.

◆ deserialize() [3/4]

template<typename T >

void BOctTree< T >::deserialize ( std::string filename )

inline

Definition at line 433 of file Boctree.h.

◆ deserialize() [4/4]

template<typename T >

static void BOctTree< T >::deserialize	(	std::string	filename,
		vector< Point > &	points
	)

inlinestatic

Definition at line 476 of file Boctree.h.

◆ FindClosest()

template<typename T >

double* BOctTree< T >::FindClosest	(	double *	point,
		double	maxdist2,
		int	threadNum
	)		const

inlineprotectedvirtual

This function finds the closest point in the octree given a specified radius. This implementation is quit complex, although it is already simplified. The simplification incurs a significant loss in speed, as several calculations have to be performed repeatedly and a high number of unnecessary jumps are executed.

Implements SearchTree.

Definition at line 1190 of file Boctree.h.

◆ FindClosestInBucket()

template<typename T >

double* BOctTree< T >::FindClosestInBucket	(	double *	point,
		double	maxdist2,
		int	threadNum
	)

inlineprotected

This function shows the possible speedup that can be gained by using the octree for nearest neighbour search, if a more sophisticated implementation were given. Here, only the bucket in which the query point falls is looked up. If doing the same thing in the kd-tree search, this function is about 3-5 times as fast

Definition at line 1308 of file Boctree.h.

◆ findClosestInLeaf()

template<typename T >

void BOctTree< T >::findClosestInLeaf	(	bitunion< T > *	node,
		int	threadNum
	)		const

inlineprotected

Given a leaf node, this function looks for the closest point to params[threadNum].closest in the list of points.

Definition at line 1161 of file Boctree.h.

◆ fullsort()

template<typename T >

template<class P >

void BOctTree< T >::fullsort	(	P const	points,
		int	n,
		T	splitval[3],
		P const	blocks[9]
	)

inlineprotected

Definition at line 1354 of file Boctree.h.

◆ getByIndex()

template<typename T >

void BOctTree< T >::getByIndex	(	T *	point,
		T *&	points,
		unsigned int &	length
	)

inlineprotected

Definition at line 1126 of file Boctree.h.

◆ getCenter() [1/2]

template<typename T >

const T* BOctTree< T >::getCenter ( ) const

inline

Definition at line 412 of file Boctree.h.

◆ getCenter() [2/2]

template<typename T >

void BOctTree< T >::getCenter ( double _center[3] ) const

inline

Definition at line 418 of file Boctree.h.

◆ getMaxDepth()

template<typename T >

unsigned int BOctTree< T >::getMaxDepth ( ) const

inline

Definition at line 416 of file Boctree.h.

◆ getMaxs()

template<typename T >

const T* BOctTree< T >::getMaxs ( ) const

inline

Definition at line 411 of file Boctree.h.

◆ getMemorySize()

template<typename T >

unsigned int BOctTree< T >::getMemorySize ( )

inline

Size of the whole tree structure, including the main class, its serialize critical allocated variables and nodes, not the allocator.

Definition at line 1525 of file Boctree.h.

◆ getMins()

template<typename T >

const T* BOctTree< T >::getMins ( ) const

inline

Definition at line 410 of file Boctree.h.

◆ GetOctTreeCenter() [1/2]

template<typename T >

void BOctTree< T >::GetOctTreeCenter ( vector< T * > & c )

inline

Definition at line 424 of file Boctree.h.

◆ GetOctTreeCenter() [2/2]

template<typename T >

void BOctTree< T >::GetOctTreeCenter	(	vector< T * > &	c,
		bitoct &	node,
		T *	center,
		T	size
	)

inlineprotected

Definition at line 813 of file Boctree.h.

◆ GetOctTreeRandom() [1/4]

template<typename T >

void BOctTree< T >::GetOctTreeRandom ( vector< T * > & c )

inline

Definition at line 425 of file Boctree.h.

◆ GetOctTreeRandom() [2/4]

template<typename T >

void BOctTree< T >::GetOctTreeRandom	(	vector< T * > &	c,
		bitoct &	node
	)

inlineprotected

Definition at line 835 of file Boctree.h.

◆ GetOctTreeRandom() [3/4]

template<typename T >

void BOctTree< T >::GetOctTreeRandom	(	vector< T * > &	c,
		unsigned int	ptspervoxel
	)

inline

Definition at line 426 of file Boctree.h.

◆ GetOctTreeRandom() [4/4]

template<typename T >

void BOctTree< T >::GetOctTreeRandom	(	vector< T * > &	c,
		unsigned int	ptspervoxel,
		bitoct &	node
	)

inlineprotected

Definition at line 870 of file Boctree.h.

◆ getPointdim()

template<typename T >

unsigned int BOctTree< T >::getPointdim ( ) const

inline

Definition at line 414 of file Boctree.h.

◆ getRoot()

template<typename T >

const bitoct& BOctTree< T >::getRoot ( ) const

inline

Definition at line 415 of file Boctree.h.

◆ getSize()

template<typename T >

T BOctTree< T >::getSize ( ) const

inline

Definition at line 413 of file Boctree.h.

◆ init()

template<typename T >

void BOctTree< T >::init ( )

inline

Definition at line 325 of file Boctree.h.

◆ pickPoint()

template<typename T >

T* BOctTree< T >::pickPoint ( bitoct & node )

inline

Picks the first point in depth first order starting from the given node

Definition at line 576 of file Boctree.h.

◆ readType()

template<typename T >

static PointType BOctTree< T >::readType ( std::string filename )

inlinestatic

Definition at line 549 of file Boctree.h.

◆ serialize() [1/2]

template<typename T >

void BOctTree< T >::serialize	(	std::ofstream &	of,
		bitoct &	node
	)

inlineprotected

Definition at line 786 of file Boctree.h.

◆ serialize() [2/2]

template<typename T >

void BOctTree< T >::serialize ( std::string filename )

inline

Definition at line 507 of file Boctree.h.

◆ sizeChildren()

template<typename T >

unsigned int BOctTree< T >::sizeChildren ( const bitoct & node )

inlineprivate

Recursive size of a node's children.

Definition at line 1536 of file Boctree.h.

◆ sort()

template<typename T >

template<class P >

P* const * BOctTree< T >::sort	(	P const	points,
		unsigned int	n,
		T	splitval,
		unsigned char	index
	)

inlineprotected

Definition at line 1401 of file Boctree.h.

Member Data Documentation

◆ add

template<typename T >

T BOctTree< T >::add[3]

protected

Offset and real voxelsize inverse factor for manipulation points.

Definition at line 372 of file Boctree.h.

◆ alloc

template<typename T >

Allocator* BOctTree< T >::alloc

protected

Allocator used for creating nodes in the constructor.

Definition at line 406 of file Boctree.h.

◆ center

template<typename T >

T BOctTree< T >::center[3]

protected

storing the center

Definition at line 360 of file Boctree.h.

◆ child_bit_depth

template<typename T >

ip::offset_ptr<unsigned int> BOctTree< T >::child_bit_depth

protected

Definition at line 387 of file Boctree.h.

◆ child_bit_depth_inv

template<typename T >

ip::offset_ptr<unsigned int> BOctTree< T >::child_bit_depth_inv

protected

Definition at line 388 of file Boctree.h.

◆ earlystop

template<typename T >

bool BOctTree< T >::earlystop

protected

Whether to stop subdividing at N<10 nodes or not.

Serialization uncritical, runtime irrelevant variables (constructor-stuff)

Definition at line 403 of file Boctree.h.

◆ largest_index

template<typename T >

int BOctTree< T >::largest_index

protected

Definition at line 389 of file Boctree.h.

◆ max_depth

template<typename T >

unsigned char BOctTree< T >::max_depth

protected

?

Definition at line 386 of file Boctree.h.

◆ maxs

template<typename T >

ip::offset_ptr<T> BOctTree< T >::maxs

protected

Definition at line 380 of file Boctree.h.

◆ mins

template<typename T >

ip::offset_ptr<T> BOctTree< T >::mins

protected

storing minimal and maximal values for all dimensions

Definition at line 379 of file Boctree.h.

◆ mult

template<typename T >

T BOctTree< T >::mult

protected

Definition at line 373 of file Boctree.h.

◆ params

template<class T >

NNParams BOctTree< T >::params

staticprotected

Threadlocal storage of parameters used in SearchTree operations.

Serialization uncritical, runtime relevant variables

Definition at line 396 of file Boctree.h.

◆ POINTDIM

template<typename T >

unsigned int BOctTree< T >::POINTDIM

protected

Dimension of each point: 3 (xyz) + N (attributes)

Definition at line 376 of file Boctree.h.

◆ pointtype

template<typename T >

PointType BOctTree< T >::pointtype

protected

Details of point attributes.

Definition at line 383 of file Boctree.h.

◆ real_voxelSize

template<typename T >

T BOctTree< T >::real_voxelSize

protected

The real voxelsize of the leaves.

Definition at line 369 of file Boctree.h.

◆ root

template<typename T >

ip::offset_ptr<bitoct> BOctTree< T >::root

protected

the root of the octree

Serialization critical variables

Definition at line 356 of file Boctree.h.

◆ size

template<typename T >

T BOctTree< T >::size

protected

storing the dimension

Definition at line 363 of file Boctree.h.

◆ uroot

template<typename T >

ip::offset_ptr<bitunion<T> > BOctTree< T >::uroot

protected

Definition at line 357 of file Boctree.h.

◆ voxelSize

template<typename T >

T BOctTree< T >::voxelSize

protected

storing the voxel size

Definition at line 366 of file Boctree.h.

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

Boctree.h

Public Member Functions

Static Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Static Protected Attributes

Private Member Functions

Detailed Description

template<typename T> class BOctTree< T >

Constructor & Destructor Documentation

◆ BOctTree() [1/5]

◆ BOctTree() [2/5]

◆ BOctTree() [3/5]

◆ BOctTree() [4/5]

◆ ~BOctTree()

◆ BOctTree() [5/5]

Member Function Documentation

◆ _FindClosest()

◆ AllPoints() [1/2]

◆ AllPoints() [2/2]

◆ branch() [1/2]

◆ branch() [2/2]

◆ childcenter() [1/2]

◆ childcenter() [2/2]

◆ childIndex()

◆ copy_children()

◆ countLeaves() [1/2]

◆ countLeaves() [2/2]

◆ countNodes() [1/2]

◆ countNodes() [2/2]

◆ countOctLeaves() [1/2]

◆ countOctLeaves() [2/2]

◆ countPointsAndQueue()

◆ countPointsAndQueueFast()

◆ deletetNodes()

◆ deserialize() [1/4]

◆ deserialize() [2/4]

◆ deserialize() [3/4]

◆ deserialize() [4/4]

◆ FindClosest()

◆ FindClosestInBucket()

◆ findClosestInLeaf()

◆ fullsort()

◆ getByIndex()

◆ getCenter() [1/2]

◆ getCenter() [2/2]

◆ getMaxDepth()

◆ getMaxs()

◆ getMemorySize()

◆ getMins()

◆ GetOctTreeCenter() [1/2]

◆ GetOctTreeCenter() [2/2]

◆ GetOctTreeRandom() [1/4]

◆ GetOctTreeRandom() [2/4]

◆ GetOctTreeRandom() [3/4]

◆ GetOctTreeRandom() [4/4]

◆ getPointdim()

◆ getRoot()

◆ getSize()

◆ init()

◆ pickPoint()

◆ readType()

◆ serialize() [1/2]

◆ serialize() [2/2]

◆ sizeChildren()

◆ sort()

Member Data Documentation

◆ add

◆ alloc

◆ center

◆ child_bit_depth

◆ child_bit_depth_inv

◆ earlystop

◆ largest_index

◆ max_depth

◆ maxs

◆ mins

◆ mult

◆ params

◆ POINTDIM

template<typename T>
class BOctTree< T >