Classes
struct	Entry

struct	Node

struct	Page

Public Types
typedef unsigned int	NodeIndex

typedef unsigned int	PageIndex

Public Member Functions
	SpatialIndex ()

	~SpatialIndex ()

Bool	insert (const DATA_ID globalId, const Vector3d &pos)

Bool	insert (const DATA_ID globalId, const Vector3d &pos, const UInt64 key)

Bool	remove (const DATA_ID globalId)

Bool	update (const DATA_ID globalId, const Vector3d &pos)

std::vector< DATA_ID >	nearestNeighbors (const Vector3d &loc, double distanceInMeter) const

std::vector< DATA_ID >	objectsWithin (const Vector3d &min, const Vector3d &max) const

std::vector< DATA_ID >	objectsWithin (const Vector2d &minLatLonDeg, const Vector2d &maxLatLonDeg) const

std::vector< DATA_ID >	objectsNearChord (const Vector3d &pointA, const Vector3d &pointB, const double delta) const

std::vector< DATA_ID >	spatialTreeWalk (UInt32 &totalDataCnt) const

bool	isDistanceToLineWithin (const Vector3d &pointC, double distance, const Vector3d &lineA, const Vector3d &lineB) const

bool	isWholeGlobeRegion (const Vector3d &pos1, const Vector3d &pos2) const

void	reset ()

void	endFrame ()

Static Public Member Functions
static Vector2d	geocToSpherical (const Vector3d &pos)

static UInt64	my_pdep_u64 (UInt64 val, UInt64 mask)

static UInt64	geocentricToSpatialKey (const Vector3d &pos)

Protected Member Functions
void	growNodes (int count)

void	growPages (int count)

int	findNodeToAdd (const UInt64 key)

Bool	needSplit (const NodeIndex nodeIdx) const

Bool	canSplit (const NodeIndex nodeIdx) const

Bool	splitNode (NodeIndex n)

int	nextNode ()

int	nextPage ()

NodeIndex	findNodeContaining (NodeIndex, const UInt64 key) const

NodeIndex	findCommonRootNode (NodeIndex idx, const UInt64 key1, const UInt64 key2) const

bool	generateMinMaxKeys (const Vector3d &pos1, const Vector3d &pos2, UInt64 &minKey, UInt64 &maxKey, Vector3d &minPos, Vector3d &maxPos) const

bool	generateMinMaxKeys (const Vector3d &pos1, const Vector3d &pos2, UInt64 &minKey, UInt64 &maxKey) const

UInt32	objectsWithinNode (const NodeIndex idx, const UInt64 minKey, const UInt64 maxKey, const Vector3d &absMin, const Vector3d &absMax, std::vector< DATA_ID > &result) const

UInt32	objectsWithinNode (const NodeIndex idx, const UInt64 minKey, const UInt64 maxKey, const Vector3d &pos1, const Vector3d &pos2, const double distance, std::vector< DATA_ID > &result) const

UInt32	objectsWithinNode (const NodeIndex idx, const Vector2d &latLong1, const Vector2d &latLong2, std::vector< DATA_ID > &result) const

void	eraseFromPage (Page &p, DATA_ID globalId)

void	addToPage (Page &p, DATA_ID globalId, UInt64 key, const Vector3d &loc)

bool	contains (UInt64 key, NodeIndex n)

bool	isPositionWithin (const Vector3d &min, const Vector3d &max, const Vector3d &pos) const

bool	isPositionWithin (const Vector2d &latLong1, const Vector2d &latLong2, const Vector3d &pos) const

Protected Attributes
UInt32	myNodeCount

UInt32	myPageCount

std::queue< int >	myFreePageQueue

std::vector< Node >	myNodes

std::vector< Page >	myPages

std::mutex	myPageMutex

std::mutex	myNodeMutex

std::unordered_map< DATA_ID, int >	myReverseLookup

Static Protected Attributes
static const UInt64	MASK_AZIMUTH_ODD_BITS = (0x5555555555555555ULL)

static const UInt64	MASK_ELEVATION_EVEN_BITS = (0xAAAAAAAAAAAAAAAAULL)

static const UInt64	MASK_AZIMUTH_OBITS_REVERSE = ~(0x5555555555555555ULL)

static const UInt64	MASK_ELEVATION_EBITS_REVERSE = ~(0xAAAAAAAAAAAAAAAAULL)

static const int	SpatialMaxNodeDepth = 31

static const int	thePageSize = 100

Static Private Attributes
static const int	BITS_PER_COMPONENT = 30

static const int	BITS_PER_COMPONENT_AND_REGION = 31

Member Typedef Documentation

template<typename DATA_ID >

typedef unsigned int MAK::SpatialIndex< DATA_ID >::NodeIndex

template<typename DATA_ID >

typedef unsigned int MAK::SpatialIndex< DATA_ID >::PageIndex

Constructor & Destructor Documentation

template<typename DATA_ID >

MAK::SpatialIndex< DATA_ID >::SpatialIndex ( )

Public APIs.

template<typename DATA_ID >

MAK::SpatialIndex< DATA_ID >::~SpatialIndex ( )

Member Function Documentation

template<typename DATA_ID >

Bool MAK::SpatialIndex< DATA_ID >::insert	(	const DATA_ID	globalId,
		const Vector3d &	pos
	)

Generate spatial key and insert entity's global ID and location into spatial tree.

template<typename DATA_ID >

Bool MAK::SpatialIndex< DATA_ID >::insert	(	const DATA_ID	globalId,
		const Vector3d &	pos,
		const UInt64	key
	)

Insert the spatial key and entity's global ID and location into spatial tree.

template<typename DATA_ID >

Bool MAK::SpatialIndex< DATA_ID >::remove ( const DATA_ID globalId )

Find the entity data identified by globalId and remove the object from the spatial tree.

template<typename DATA_ID >

Bool MAK::SpatialIndex< DATA_ID >::update	(	const DATA_ID	globalId,
		const Vector3d &	pos
	)

Update entity's location.

template<typename DATA_ID >

std::vector<DATA_ID> MAK::SpatialIndex< DATA_ID >::nearestNeighbors	(	const Vector3d &	loc,
		double	distanceInMeter
	)		const

Find nearest neighbors from the input location, neighbors x/y/z locations are <= distanceInMeter. It returns an array of global IDs.

template<typename DATA_ID >

std::vector<DATA_ID> MAK::SpatialIndex< DATA_ID >::objectsWithin	(	const Vector3d &	min,
		const Vector3d &	max
	)		const

Find objects within the area of min and max locations, including the min & max locations.

template<typename DATA_ID >

std::vector<DATA_ID> MAK::SpatialIndex< DATA_ID >::objectsWithin	(	const Vector2d &	minLatLonDeg,
		const Vector2d &	maxLatLonDeg
	)		const

Find objects within the area of latitude and longitude specified in degree.

template<typename DATA_ID >

std::vector<DATA_ID> MAK::SpatialIndex< DATA_ID >::objectsNearChord	(	const Vector3d &	pointA,
		const Vector3d &	pointB,
		const double	delta
	)		const

Find objects within the delta distance from the chord defined by npoint A & B.

template<typename DATA_ID >

std::vector<DATA_ID> MAK::SpatialIndex< DATA_ID >::spatialTreeWalk ( UInt32 & totalDataCnt ) const

template<typename DATA_ID >

bool MAK::SpatialIndex< DATA_ID >::isDistanceToLineWithin	(	const Vector3d &	pointC,
		double	distance,
		const Vector3d &	lineA,
		const Vector3d &	lineB
	)		const

Find the shortest distance from the point C to the line.

template<typename DATA_ID >

bool MAK::SpatialIndex< DATA_ID >::isWholeGlobeRegion	(	const Vector3d &	pos1,
		const Vector3d &	pos2
	)		const

template<typename DATA_ID >

void MAK::SpatialIndex< DATA_ID >::reset ( )

Reset the entity entries, but maintains the node tree since that is likely useful the next frame.

template<typename DATA_ID >

void MAK::SpatialIndex< DATA_ID >::endFrame ( )

template<typename DATA_ID >

static Vector2d MAK::SpatialIndex< DATA_ID >::geocToSpherical ( const Vector3d & pos )

inlinestatic

spatial key generation specific static member functions

Referenced by MAK::SpatialIndex< DATA_ID >::geocentricToSpatialKey().

template<typename DATA_ID >

static UInt64 MAK::SpatialIndex< DATA_ID >::my_pdep_u64	(	UInt64	val,
		UInt64	mask
	)

inlinestatic

Referenced by MAK::SpatialIndex< DATA_ID >::geocentricToSpatialKey().

template<typename DATA_ID >

static UInt64 MAK::SpatialIndex< DATA_ID >::geocentricToSpatialKey ( const Vector3d & pos )

inlinestatic

References MAK::SpatialIndex< DATA_ID >::BITS_PER_COMPONENT, MAK::SpatialIndex< DATA_ID >::geocToSpherical(), and MAK::SpatialIndex< DATA_ID >::my_pdep_u64().

template<typename DATA_ID >

void MAK::SpatialIndex< DATA_ID >::growNodes ( int count )

protected

template<typename DATA_ID >

void MAK::SpatialIndex< DATA_ID >::growPages ( int count )

protected

template<typename DATA_ID >

int MAK::SpatialIndex< DATA_ID >::findNodeToAdd ( const UInt64 key )

protected

NodeIndex findNodeToAdd(const UInt64 key);.

template<typename DATA_ID >

Bool MAK::SpatialIndex< DATA_ID >::needSplit ( const NodeIndex nodeIdx ) const

protected

template<typename DATA_ID >

Bool MAK::SpatialIndex< DATA_ID >::canSplit ( const NodeIndex nodeIdx ) const

protected

template<typename DATA_ID >

Bool MAK::SpatialIndex< DATA_ID >::splitNode ( NodeIndex n )

protected

template<typename DATA_ID >

int MAK::SpatialIndex< DATA_ID >::nextNode ( )

protected

template<typename DATA_ID >

int MAK::SpatialIndex< DATA_ID >::nextPage ( )

protected

template<typename DATA_ID >

NodeIndex MAK::SpatialIndex< DATA_ID >::findNodeContaining	(	NodeIndex	,
		const UInt64	key
	)		const

protected

template<typename DATA_ID >

NodeIndex MAK::SpatialIndex< DATA_ID >::findCommonRootNode	(	NodeIndex	idx,
		const UInt64	key1,
		const UInt64	key2
	)		const

protected

template<typename DATA_ID >

bool MAK::SpatialIndex< DATA_ID >::generateMinMaxKeys	(	const Vector3d &	pos1,
		const Vector3d &	pos2,
		UInt64 &	minKey,
		UInt64 &	maxKey,
		Vector3d &	minPos,
		Vector3d &	maxPos
	)		const

protected

template<typename DATA_ID >

bool MAK::SpatialIndex< DATA_ID >::generateMinMaxKeys	(	const Vector3d &	pos1,
		const Vector3d &	pos2,
		UInt64 &	minKey,
		UInt64 &	maxKey
	)		const

protected

template<typename DATA_ID >

UInt32 MAK::SpatialIndex< DATA_ID >::objectsWithinNode	(	const NodeIndex	idx,
		const UInt64	minKey,
		const UInt64	maxKey,
		const Vector3d &	absMin,
		const Vector3d &	absMax,
		std::vector< DATA_ID > &	result
	)		const

protected

template<typename DATA_ID >

UInt32 MAK::SpatialIndex< DATA_ID >::objectsWithinNode	(	const NodeIndex	idx,
		const UInt64	minKey,
		const UInt64	maxKey,
		const Vector3d &	pos1,
		const Vector3d &	pos2,
		const double	distance,
		std::vector< DATA_ID > &	result
	)		const

protected

template<typename DATA_ID >

UInt32 MAK::SpatialIndex< DATA_ID >::objectsWithinNode	(	const NodeIndex	idx,
		const Vector2d &	latLong1,
		const Vector2d &	latLong2,
		std::vector< DATA_ID > &	result
	)		const

protected

template<typename DATA_ID >

void MAK::SpatialIndex< DATA_ID >::eraseFromPage	(	Page &	p,
		DATA_ID	globalId
	)

protected

template<typename DATA_ID >

void MAK::SpatialIndex< DATA_ID >::addToPage	(	Page &	p,
		DATA_ID	globalId,
		UInt64	key,
		const Vector3d &	loc
	)

protected

template<typename DATA_ID >

bool MAK::SpatialIndex< DATA_ID >::contains	(	UInt64	key,
		NodeIndex	n
	)

protected

template<typename DATA_ID >

bool MAK::SpatialIndex< DATA_ID >::isPositionWithin	(	const Vector3d &	min,
		const Vector3d &	max,
		const Vector3d &	pos
	)		const

protected

template<typename DATA_ID >

bool MAK::SpatialIndex< DATA_ID >::isPositionWithin	(	const Vector2d &	latLong1,
		const Vector2d &	latLong2,
		const Vector3d &	pos
	)		const

protected

Member Data Documentation

template<typename DATA_ID >

const int MAK::SpatialIndex< DATA_ID >::BITS_PER_COMPONENT = 30

staticprivate

Referenced by MAK::SpatialIndex< DATA_ID >::geocentricToSpatialKey().

template<typename DATA_ID >

const int MAK::SpatialIndex< DATA_ID >::BITS_PER_COMPONENT_AND_REGION = 31

staticprivate

template<typename DATA_ID >

const UInt64 MAK::SpatialIndex< DATA_ID >::MASK_AZIMUTH_ODD_BITS = (0x5555555555555555ULL)

staticprotected

60 bits masks used to encode or decode spatial keys (AZIMUTH, ELEVATION), Top 2 most significant bits are not used, the 61th-62th bits are spatial regionID

template<typename DATA_ID >

const UInt64 MAK::SpatialIndex< DATA_ID >::MASK_ELEVATION_EVEN_BITS = (0xAAAAAAAAAAAAAAAAULL)

staticprotected

template<typename DATA_ID >

const UInt64 MAK::SpatialIndex< DATA_ID >::MASK_AZIMUTH_OBITS_REVERSE = ~(0x5555555555555555ULL)

staticprotected

template<typename DATA_ID >

const UInt64 MAK::SpatialIndex< DATA_ID >::MASK_ELEVATION_EBITS_REVERSE = ~(0xAAAAAAAAAAAAAAAAULL)

staticprotected

template<typename DATA_ID >

const int MAK::SpatialIndex< DATA_ID >::SpatialMaxNodeDepth = 31

staticprotected

template<typename DATA_ID >

const int MAK::SpatialIndex< DATA_ID >::thePageSize = 100

staticprotected

Referenced by MAK::SpatialIndex< DATA_ID >::Page::Page().

template<typename DATA_ID >

UInt32 MAK::SpatialIndex< DATA_ID >::myNodeCount

protected

template<typename DATA_ID >

UInt32 MAK::SpatialIndex< DATA_ID >::myPageCount

protected

template<typename DATA_ID >

std::queue<int> MAK::SpatialIndex< DATA_ID >::myFreePageQueue

protected

template<typename DATA_ID >

std::vector<Node> MAK::SpatialIndex< DATA_ID >::myNodes

protected

template<typename DATA_ID >

std::vector<Page> MAK::SpatialIndex< DATA_ID >::myPages

protected

template<typename DATA_ID >

std::mutex MAK::SpatialIndex< DATA_ID >::myPageMutex

protected

template<typename DATA_ID >

std::mutex MAK::SpatialIndex< DATA_ID >::myNodeMutex

protected

template<typename DATA_ID >

std::unordered_map<DATA_ID, int> MAK::SpatialIndex< DATA_ID >::myReverseLookup

protected

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

/data/exports/nrhent7-1/nightly/docs/vrForces.vrf5-0-branch/include/vrfobjcore/spatial.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Static Private Attributes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation