#include <kDOP.h>

Public Types
typedef COLL_DATA_PROVIDER	DataProviderType

typedef TkDOPNode< DataProviderType, KDOP_IDX_TYPE >	NodeType

typedef COLL_DATA_PROVIDER	DataProviderType

typedef TkDOPNode< DataProviderType, KDOP_IDX_TYPE >	NodeType

Public Member Functions
	TkDOPNode ()

FBox	SplitTriangleList (int32 Start, int32 NumTris, TArray< FkDOPBuildCollisionTriangle< KDOP_IDX_TYPE > > &BuildTriangles, kDOPArray< FTriangleSOA > &SOATriangles, kDOPArray< NodeType > &Nodes)

void	LineCheckBounds (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, FVector4 &HitTime, int32 NodeHit[4]) const

bool	LineCheck (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, TTraversalHistory< KDOP_IDX_TYPE > History) const

bool	LineCheckPreCalculated (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, const FVector4 &NodeHitTime, TTraversalHistory< KDOP_IDX_TYPE > History, int32 *NodeHit) const

bool	LineCheckTriangles (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, const TTraversalHistory< KDOP_IDX_TYPE > &History) const

FORCEINLINE	TkDOPNode ()

FBox	SplitTriangleList (int32 Start, int32 NumTris, TArray< FkDOPBuildCollisionTriangle< KDOP_IDX_TYPE > > &BuildTriangles, kDOPArray< FTriangleSOA > &SOATriangles, kDOPArray< NodeType > &Nodes)

FORCEINLINE void	LineCheckBounds (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, FVector4 &HitTime, int32 NodeHit[4]) const

bool	LineCheck (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, TTraversalHistory< KDOP_IDX_TYPE > History) const

bool	LineCheckPreCalculated (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, const FVector4 &NodeHitTime, TTraversalHistory< KDOP_IDX_TYPE > History, int32 *NodeHit) const

bool	LineCheckTriangles (TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &Check, const TTraversalHistory< KDOP_IDX_TYPE > &History) const

Public Attributes
FFourBox	BoundingVolumes

bool	bIsLeaf

uint8	Occupancy

union {

struct {

KDOP_IDX_TYPE LeftNode

KDOP_IDX_TYPE RightNode

} n

struct {

KDOP_IDX_TYPE NumTriangles

KDOP_IDX_TYPE StartIndex

} t

};

union {

struct {

KDOP_IDX_TYPE LeftNode

KDOP_IDX_TYPE RightNode

} n

struct {

KDOP_IDX_TYPE NumTriangles

KDOP_IDX_TYPE StartIndex

} t

};

Detailed Description

template<typename COLL_DATA_PROVIDER, typename KDOP_IDX_TYPE>
struct TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >

A node in the kDOP tree. The node contains the kDOP volume that encompasses it's children and/or triangles

Member Typedef Documentation

◆ DataProviderType [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

typedef COLL_DATA_PROVIDER TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::DataProviderType

Exposes data provider type to clients.

◆ DataProviderType [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

typedef COLL_DATA_PROVIDER TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::DataProviderType

Exposes data provider type to clients.

◆ NodeType [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

typedef TkDOPNode<DataProviderType,KDOP_IDX_TYPE> TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::NodeType

Exposes node type to clients.

◆ NodeType [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

typedef TkDOPNode<DataProviderType,KDOP_IDX_TYPE> TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::NodeType

Exposes node type to clients.

Constructor & Destructor Documentation

◆ TkDOPNode() [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::TkDOPNode ( )

inline

Inits the data to no child nodes and an inverted volume

◆ TkDOPNode() [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

FORCEINLINE TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::TkDOPNode ( )

inline

Inits the data to no child nodes and an inverted volume

Member Function Documentation

◆ LineCheck() [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

bool TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheck	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		TTraversalHistory< KDOP_IDX_TYPE >	History
	)		const

inline

Determines the line in the FkDOPLineCollisionCheck intersects this node. It also will check the child nodes if it is not a leaf, otherwise it will check against the triangle data.

Parameters

Check – The aggregated line check data

◆ LineCheck() [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

bool TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheck	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		TTraversalHistory< KDOP_IDX_TYPE >	History
	)		const

inline

Determines the line in the FkDOPLineCollisionCheck intersects this node. It also will check the child nodes if it is not a leaf, otherwise it will check against the triangle data.

Parameters

Check – The aggregated line check data

◆ LineCheckBounds() [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

void TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheckBounds	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		FVector4 &	HitTime,
		int32	NodeHit[4]
	)		const

inline

The slab testing algorithm is based on the following papers. We chose to use the faster final hit determination, which means we'll get some false positives.

"A Cross-Platform Framework for Interactive Ray Tracing" Markus Geimer, Stefan Mueller http://www.uni-koblenz.de/~cg/publikationen/cp_raytrace.pdf

"Efficiency Issues for Ray Tracing" Brian Smits http://www.cs.utah.edu/~bes/papers/fastRT/paper-node10.html

We don't need to handle +/- INF, but we have permission to use Thierry Berger-Perrin trick available below.

http://www.flipcode.com/archives/SSE_RayBox_Intersection_Test.shtml

Parameters

Check	Information about the ray to trace
HitTime	[out] Time of hit

◆ LineCheckBounds() [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

FORCEINLINE void TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheckBounds	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		FVector4 &	HitTime,
		int32	NodeHit[4]
	)		const

inline

The slab testing algorithm is based on the following papers. We chose to use the faster final hit determination, which means we'll get some false positives.

"A Cross-Platform Framework for Interactive Ray Tracing" Markus Geimer, Stefan Mueller http://www.uni-koblenz.de/~cg/publikationen/cp_raytrace.pdf

"Efficiency Issues for Ray Tracing" Brian Smits http://www.cs.utah.edu/~bes/papers/fastRT/paper-node10.html

We don't need to handle +/- INF, but we have permission to use Thierry Berger-Perrin trick available below.

http://www.flipcode.com/archives/SSE_RayBox_Intersection_Test.shtml

Parameters

Check	Information about the ray to trace
HitTime	[out] Time of hit

◆ LineCheckPreCalculated() [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

bool TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheckPreCalculated	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		const FVector4 &	NodeHitTime,
		TTraversalHistory< KDOP_IDX_TYPE >	History,
		int32 *	NodeHit
	)		const

inline

Determines the line in the FkDOPLineCollisionCheck intersects this node. It also will check the child nodes if it is not a leaf, otherwise it will check against the triangle data.

Parameters

Check – The aggregated line check data

◆ LineCheckPreCalculated() [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

bool TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheckPreCalculated	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		const FVector4 &	NodeHitTime,
		TTraversalHistory< KDOP_IDX_TYPE >	History,
		int32 *	NodeHit
	)		const

inline

Determines the line in the FkDOPLineCollisionCheck intersects this node. It also will check the child nodes if it is not a leaf, otherwise it will check against the triangle data.

Parameters

Check – The aggregated line check data

◆ LineCheckTriangles() [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

bool TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheckTriangles	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		const TTraversalHistory< KDOP_IDX_TYPE > &	History
	)		const

inline

Works through the list of triangles in this node checking each one for a collision.

Parameters

Check – The aggregated line check data

◆ LineCheckTriangles() [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

bool TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::LineCheckTriangles	(	TkDOPLineCollisionCheck< COLL_DATA_PROVIDER, KDOP_IDX_TYPE > &	Check,
		const TTraversalHistory< KDOP_IDX_TYPE > &	History
	)		const

inline

Works through the list of triangles in this node checking each one for a collision.

Parameters

Check – The aggregated line check data

◆ SplitTriangleList() [1/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

FBox TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::SplitTriangleList	(	int32	Start,
		int32	NumTris,
		TArray< FkDOPBuildCollisionTriangle< KDOP_IDX_TYPE > > &	BuildTriangles,
		kDOPArray< FTriangleSOA > &	SOATriangles,
		kDOPArray< NodeType > &	Nodes
	)

inline

Determines if the node is a leaf or not. If it is not a leaf, it subdivides the list of triangles again adding two child nodes and splitting them on the mean (splatter method). Otherwise it sets up the triangle information.

Parameters

Start	– The triangle index to start processing with
NumTris	– The number of triangles to process
BuildTriangles	– The list of triangles to use for the build process
Nodes	– The list of nodes in this tree

Returns: bounding box for this node

◆ SplitTriangleList() [2/2]

template<typename COLL_DATA_PROVIDER , typename KDOP_IDX_TYPE >

FBox TkDOPNode< COLL_DATA_PROVIDER, KDOP_IDX_TYPE >::SplitTriangleList	(	int32	Start,
		int32	NumTris,
		TArray< FkDOPBuildCollisionTriangle< KDOP_IDX_TYPE > > &	BuildTriangles,
		kDOPArray< FTriangleSOA > &	SOATriangles,
		kDOPArray< NodeType > &	Nodes
	)

inline

Determines if the node is a leaf or not. If it is not a leaf, it subdivides the list of triangles again adding two child nodes and splitting them on the mean (splatter method). Otherwise it sets up the triangle information.

Parameters

Start	– The triangle index to start processing with
NumTris	– The number of triangles to process
BuildTriangles	– The list of triangles to use for the build process
Nodes	– The list of nodes in this tree