KDTreeNode Class Reference

A node of a k-d tree. More...

#include <KDTreeNode.h>

Classes
struct	Intersection
	A struct binding a pointer to an Object3D, a distance, and a pointer to a KDTreeNode. More...

Public Member Functions
	KDTreeNode ()
	Default constructor. Everything is set to 0 by default. More...
	KDTreeNode (std::vector< Object3D * > objects, unsigned int maxObjectNumber, unsigned int maxDepth, KDTreeNode *parent=nullptr, unsigned int depth=0)
	One of the main constructors. More...
	KDTreeNode (std::vector< Object3D * > objects, DoubleVec3D minCoord, DoubleVec3D maxCoord, unsigned int maxObjectNumber, unsigned int maxDepth, KDTreeNode *parent=nullptr, unsigned int depth=0)
	One of the main constructors. More...
	~KDTreeNode ()
	Destructor. More...
unsigned int	getDepth () const
	Getter for this node's depth. More...
DoubleVec3D	getMinCoord () const
	Getter for this node's minimum coordinate. More...
DoubleVec3D	getMaxCoord () const
	Getter for this node's maximum coordinate. More...
std::vector< Object3D * >	getObjects () const
	Getter for this node's objects. More...
KDTreeNode *	getParent () const
	Getter for this node's parent. More...
KDTreeNode *	getChildSmaller () const
	Getter for this node's smaller child. More...
KDTreeNode *	getChildGreater () const
	Getter for this node's greater child. More...
unsigned int	getMaxDepth () const
	Gives the maximum depth of this tree. More...
unsigned int	getMaxObjectNumberLeaf () const
	Gives the maximum number of objects in a leaf of this tree. More...
double	intersectionDistance (const Ray &ray) const
	Gives the distance to the closest intersection between this node's surface and a ray. More...
bool	isIn (DoubleVec3D point) const
	Returns whether a point is inside this node's cuboid-shaped volume. More...
Intersection	getIntersectionForward (const Ray &ray) const
	Computes the intersection going from the top to the bottom of the tree. More...
Intersection	getIntersectionBackwards (const Ray &ray, const KDTreeNode *ignore=nullptr) const
	Computes the intersection going from the bottom to the top of the tree. More...

Detailed Description

A node of a k-d tree.

See my TM's report for further information on this data structure.

Constructor & Destructor Documentation

KDTreeNode() [1/3]

KDTreeNode::KDTreeNode

(

)

Default constructor. Everything is set to 0 by default.

KDTreeNode() [2/3]

KDTreeNode::KDTreeNode	(	std::vector< Object3D * >	objects,
		unsigned int	maxObjectNumber,
		unsigned int	maxDepth,
		KDTreeNode *	parent = nullptr,
		unsigned int	depth = 0
	)

One of the main constructors.

Computes the minimum and maximum coordinates according to the objects in parameters using getMinPoint(std::vector<Object3D*> objects) and getMaxPoint(std::vector<Object3D*> objects). Then calls the other main constructor.

Parameters

objects	The objects that are in this node.
maxObjectNumber	Maximum number of objects in a k-d tree leaf. One of the two recursion stop conditions. If one of them is fulfilled, stops the recursion.
maxDepth	Maximum recursion depth. One of the two recursion stop conditions. If one of them is fulfilled, stops the recursion.
parent	A pointer to this node's parent.
depth	The current recursive depth.

See also

getMinPoint(std::vector<Object3D*> objects), getMaxPoint(std::vector<Object3D*> objects)

KDTreeNode() [3/3]

KDTreeNode::KDTreeNode	(	std::vector< Object3D * >	objects,
		DoubleVec3D	minCoord,
		DoubleVec3D	maxCoord,
		unsigned int	maxObjectNumber,
		unsigned int	maxDepth,
		KDTreeNode *	parent = nullptr,
		unsigned int	depth = 0
	)

One of the main constructors.

Recursively creates children. See the list of parameters to know when the recursion stops. After having finished, deletes leaves (node that do not have any child) that have the exact same number of objects as their parent.

Parameters

objects	The objects that are in this node.
minCoord	The minimum coordinate of this node.
maxCoord	The maximum coordinate of this node.
maxObjectNumber	Maximum number of objects in a k-d tree leaf. One of the two recursion stop conditions. If one of them is fulfilled, stops the recursion.
maxDepth	Maximum recursion depth. One of the two recursion stop conditions. If one of them is fulfilled, stops the recursion.
parent	A pointer to this node's parent.
depth	The current recursive depth.

~KDTreeNode()

KDTreeNode::~KDTreeNode

(

)

Destructor.

Member Function Documentation

getChildGreater()

KDTreeNode * KDTreeNode::getChildGreater

(

)

const

Getter for this node's greater child.

The greater child and the smaller one are distinguished by their position to the cut.

Returns

The greater child of this node.

getChildSmaller()

KDTreeNode * KDTreeNode::getChildSmaller

(

)

const

Getter for this node's smaller child.

The smaller child and the greater one are distinguished by their position to the cut.

Returns

The smaller child of this node.

getDepth()

unsigned int KDTreeNode::getDepth

(

)

const

Getter for this node's depth.

Returns

This recursive depth of this node.

getIntersectionBackwards()

KDTreeNode::Intersection KDTreeNode::getIntersectionBackwards	(	const Ray &	ray,
		const KDTreeNode *	ignore = nullptr
	)		const

Computes the intersection going from the bottom to the top of the tree.

Starts at a bottom node and alternates between backwards and forward intersection.

Parameters

ray	The ray with which the intersection is computed.
ignore	A KDTreeNode that will be ignored when computing a forward intersection.

Returns

The intersection.

getIntersectionForward()

KDTreeNode::Intersection KDTreeNode::getIntersectionForward

(

const Ray &

ray

)

const

Computes the intersection going from the top to the bottom of the tree.

Parameters

ray	The ray with which the intersection is computed.

Returns

The intersection.

getMaxCoord()

DoubleVec3D KDTreeNode::getMaxCoord

(

)

const

Getter for this node's maximum coordinate.

Returns

The maximum coordinate of this node's cuboid-shaped volume.

getMaxDepth()

unsigned int KDTreeNode::getMaxDepth

(

)

const

Gives the maximum depth of this tree.

This function must be called from the root node of a tree.

Returns

Its own depth, if it has no child; the maximum between the maximum depth of both its children, else.

See also

KDTreeNode::getMaxObjectNumberLeaf()

getMaxObjectNumberLeaf()

unsigned int KDTreeNode::getMaxObjectNumberLeaf

(

)

const

Gives the maximum number of objects in a leaf of this tree.

This function must be called from the root node of a tree.

Returns

Its number of objects, if it has not child; the maximum between the maximum number of objects in a leaf given by both its children, else.

See also

KDTreeNode::getMaxDepth()

getMinCoord()

DoubleVec3D KDTreeNode::getMinCoord

(

)

const

Getter for this node's minimum coordinate.

Returns

The minimum coordinate of this node's cuboid-shaped volume.

getObjects()

std::vector< Object3D * > KDTreeNode::getObjects

(

)

const

Getter for this node's objects.

Returns

The objects contained in this node.

getParent()

KDTreeNode * KDTreeNode::getParent

(

)

const

Getter for this node's parent.

Returns

The parent of this node.

intersectionDistance()

double KDTreeNode::intersectionDistance

(

const Ray &

ray

)

const

Gives the distance to the closest intersection between this node's surface and a ray.

Parameters

ray	The ray with which it computes the distance.

Returns

The distance to the closest intersection between this node's surface and the ray.

isIn()

bool KDTreeNode::isIn

(

DoubleVec3D

point

)

const

Returns whether a point is inside this node's cuboid-shaped volume.

Parameters

point

The point for which we want this information.

Returns

Whether a point is inside this node.

---

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

• D:/PathTracer/PathTracer/KDTreeNode.h
• D:/PathTracer/PathTracer/KDTreeNode.cpp