#include <perfect_spatial_hashing.h>

Inheritance diagram for vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >:

Classes
class	BinaryImage
struct	Dereferencer
class	HashTable
struct	Neighbor
struct	NeighboringEntryIterator
class	OffsetTable
struct	ReferenceType
struct	ReferenceType< TYPE * >
class	UniformGrid
Public Types
typedef vcg::Box3< ScalarType >	BoundingBoxType
enum	ConstructionApproach { FastConstructionApproach = 0, CompactConstructionApproach = 1 }
typedef vcg::Point3< ScalarType >	CoordinateType
typedef ReferenceType < ObjectType >::Type *	ObjectPointer
typedef OBJECT_TYPE	ObjectType
typedef SCALAR_TYPE	ScalarType
Public Member Functions
template<class OBJECT_POINT_DISTANCE_FUNCTOR , class OBJECT_MARKER , class OBJECT_POINTER_CONTAINER , class DISTANCE_CONTAINER , class POINT_CONTAINER >
unsigned int	GetInSphere (OBJECT_POINT_DISTANCE_FUNCTOR &distance_functor, OBJECT_MARKER &marker, const CoordinateType &sphere_center, const ScalarType &sphere_radius, OBJECT_POINTER_CONTAINER &objects, DISTANCE_CONTAINER &distances, POINT_CONTAINER &points, bool sort_per_distance=true, bool allow_zero_distance=true)
std::vector< ObjectPointer > *	operator[] (const CoordinateType &query)
std::vector< ObjectPointer > *	operator[] (const typename UniformGrid::CellCoordinate &query)
	PerfectSpatialHashing ()
template<class OBJECT_ITERATOR >
void	Set (const OBJECT_ITERATOR &bObj, const OBJECT_ITERATOR &eObj)
template<class OBJECT_ITERATOR >
void	Set (const OBJECT_ITERATOR &bObj, const OBJECT_ITERATOR &eObj, vcg::CallBackPos *callback)
template<class OBJECT_ITERATOR >
void	Set (const OBJECT_ITERATOR &bObj, const OBJECT_ITERATOR &eObj, const ConstructionApproach approach)
template<class OBJECT_ITERATOR >
void	Set (const OBJECT_ITERATOR &bObj, const OBJECT_ITERATOR &eObj, const ConstructionApproach approach, vcg::CallBackPos *callback)
	~PerfectSpatialHashing ()
Protected Member Functions
void	Finalize ()
int	GetUnefectiveOffsetTableSize (const int hash_table_size, const int offset_table_size)
bool	IsAValidOffset (const std::vector< typename UniformGrid::CellCoordinate > *pre_image, const typename OffsetTable::Offset &offset)
bool	OffsetTableConstructionSucceded (const int offset_table_size, vcg::CallBackPos *callback)
HashTable::EntryCoordinate	PerfectHashFunction (const typename UniformGrid::CellCoordinate &query)
void	PerformCompactConstruction (const int number_of_filled_cells, vcg::CallBackPos *callback)
void	PerformFastConstruction (const int number_of_filled_cells, vcg::CallBackPos *callback)
HashTable::EntryCoordinate	Shift (const vcg::Point3i &entry, const typename OffsetTable::Offset &offset)
Static Protected Member Functions
static const float	m_BOUNDING_BOX_EXPANSION_FACTOR ()
static const int	m_DIMENSION ()
static const int	m_MAX_NUM_OF_RANDOM_GENERATED_OFFSET ()
static const int	m_MAX_TRIALS_IN_COMPACT_CONSTRUCTION ()
static const float	m_SIGMA ()
Protected Attributes
BinaryImage	m_Bitmap
HashTable	m_HashTable
OffsetTable	m_OffsetTable
UniformGrid	m_UniformGrid

Detailed Description

template<class OBJECT_TYPE, class SCALAR_TYPE>
class vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >

This class implements the perfect spatial hashing by S.Lefebvre and H.Hoppe This is an spatial indexing structure such as the uniform grid, but with lower memory requirements, since all the empty cells of the uniform grid are removed. Access to a non-empty cell is performed looking up in two d-dimensional tables, the offset table and the hash table.

Parameters:

OBJECT_TYPE	(Template parameter) the type of objects to be indexed
SCALAR_TYPE	(Template parameter) the scalar type

Definition at line 76 of file perfect_spatial_hashing.h.

Member Typedef Documentation

template<class OBJECT_TYPE , class SCALAR_TYPE >

typedef vcg::Box3< ScalarType > vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::BoundingBoxType

Definition at line 100 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

typedef vcg::Point3< ScalarType > vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::CoordinateType

Definition at line 101 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

typedef ReferenceType< ObjectType >::Type* vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::ObjectPointer

Definition at line 99 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

typedef OBJECT_TYPE vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::ObjectType

Definition at line 98 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

typedef SCALAR_TYPE vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::ScalarType

Reimplemented from vcg::SpatialIndex< OBJECT_TYPE, SCALAR_TYPE >.

Definition at line 97 of file perfect_spatial_hashing.h.

Member Enumeration Documentation

template<class OBJECT_TYPE , class SCALAR_TYPE >

enum vcg::PerfectSpatialHashing::ConstructionApproach

The hash table can be constructed following two different approaches: the first is more fast, but might allocate a offset table bigger than the necessary the second try to construct the offset table up to m_MAX_TRIALS_IN_COMPACT_CONSTRUCTION times, and then chooses the minimum size for which the construction succeeded.

Enumerator:

FastConstructionApproach
CompactConstructionApproach

Definition at line 1086 of file perfect_spatial_hashing.h.

Constructor & Destructor Documentation

template<class OBJECT_TYPE , class SCALAR_TYPE >

vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::PerfectSpatialHashing ( ) [inline]

Default constructor

Definition at line 1091 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::~PerfectSpatialHashing ( ) [inline]

Destructor

Definition at line 1096 of file perfect_spatial_hashing.h.

Member Function Documentation

template<class OBJECT_TYPE , class SCALAR_TYPE >

void vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::Finalize ( ) [inline, protected]

Finalizes the data structures at the end of the offset-table construction. This function eliminates all unnecessary data, and encodes sparsity. TODO At the moment, the sparsity encoding is implemented thought a bitmap, i.e. a boolean grid where each slot tells if the relative UniformGrid has a valid entry in the HashTable.

Definition at line 1313 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

template<class OBJECT_POINT_DISTANCE_FUNCTOR , class OBJECT_MARKER , class OBJECT_POINTER_CONTAINER , class DISTANCE_CONTAINER , class POINT_CONTAINER >

unsigned int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::GetInSphere	(	OBJECT_POINT_DISTANCE_FUNCTOR &	distance_functor,
		OBJECT_MARKER &	marker,
		const CoordinateType &	sphere_center,
		const ScalarType &	sphere_radius,
		OBJECT_POINTER_CONTAINER &	objects,
		DISTANCE_CONTAINER &	distances,
		POINT_CONTAINER &	points,
		bool	sort_per_distance = `true`,
		bool	allow_zero_distance = `true`
	)		`[inline]`

Returns all the objects contained inside a specified sphere

Parameters:

[in]	distance_functor
[in]	marker
[in]	sphere_center
[in]	sphere_radius
[out]	objects
[out]	distances
[out]	points

Returns:

Definition at line 1193 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::GetUnefectiveOffsetTableSize	(	const int	hash_table_size,
		const int	offset_table_size
	)		`[inline, protected]`

Given the size of the hash table and an initial seed for the size of the offset table, returns an appropriate size for the offset table in order to avoid less effective constructions.

Parameters:

[in]	hash_table_size	The number of entries for each side of the hash-table.
[in]	offset_table_size	The number of entries for each side of the offset-table.

Returns:: The next appropriate size for the offset table.

Definition at line 1363 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

bool vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::IsAValidOffset	(	const std::vector< typename UniformGrid::CellCoordinate > *	pre_image,
		const typename OffsetTable::Offset &	offset
	)		`[inline, protected]`

Check if the given offset is valid for a set of domain cell.

Parameters:

[in]	pre_image
[in]	offset

Returns:

Definition at line 1331 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

static const float vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_BOUNDING_BOX_EXPANSION_FACTOR ( ) [inline, static, protected]

Definition at line 1573 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

static const int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_DIMENSION ( ) [inline, static, protected]

Definition at line 1577 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

static const int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_MAX_NUM_OF_RANDOM_GENERATED_OFFSET ( ) [inline, static, protected]

Definition at line 1576 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

static const int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_MAX_TRIALS_IN_COMPACT_CONSTRUCTION ( ) [inline, static, protected]

Definition at line 1575 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

static const float vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_SIGMA ( ) [inline, static, protected]

Definition at line 1574 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

bool vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::OffsetTableConstructionSucceded	(	const int	offset_table_size,
		vcg::CallBackPos *	callback
	)		`[inline, protected]`

Try to construct the offset table for a given size

Parameters:

[in] offset_table_size The size of the offset table.

Returns:: true if and only if the construction of the offset table succeeds.

Definition at line 1456 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

std::vector< ObjectPointer >* vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::operator[] ( const CoordinateType & query ) [inline]

Once the offset table has been built, this function can be used to access the data. Given a 3D point in the space, this function returns the set of ObjectPointers contained in the same UniformGrid cell where this point is contained.

Parameters:

[in] query The 3D query point.

Returns:: The pointer to the vector of ObjectPointers contained in the same UG of query. NULL if any.

Definition at line 1253 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

std::vector< ObjectPointer >* vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::operator[] ( const typename UniformGrid::CellCoordinate & query ) [inline]

Definition at line 1265 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

HashTable::EntryCoordinate vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::PerfectHashFunction ( const typename UniformGrid::CellCoordinate & query ) [inline, protected]

The injective mapping from the set of occupied cells to a slot in the hash-table

Parameters:

[in]	query	The index of a domain cell whose mapping has to be calculated.
[out]	result	The index of a entry in the hash-table where query is mapped into.

Definition at line 1282 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

void vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::PerformCompactConstruction	(	const int	number_of_filled_cells,
		vcg::CallBackPos *	callback
	)		`[inline, protected]`

Start the construction of the offset table trying to minimize its dimension. The offset table size is chosen by performing a binary search over possible values for the offset table size. For this reason, this method will generally require more time than PerformFastConstruction.

Definition at line 1396 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

void vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::PerformFastConstruction	(	const int	number_of_filled_cells,
		vcg::CallBackPos *	callback
	)		`[inline, protected]`

Start the construction of the offset table trying to complete as quickly as possible. Sometimes the dimension of the offset table will not be minimal.

Parameters:

[in] number_of_filled_cells The number of entries in the uniform grid containing some elements of the dataset.

Definition at line 1377 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

template<class OBJECT_ITERATOR >

void vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::Set	(	const OBJECT_ITERATOR &	bObj,
		const OBJECT_ITERATOR &	eObj
	)		`[inline]`

Definition at line 1099 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

template<class OBJECT_ITERATOR >

void vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::Set	(	const OBJECT_ITERATOR &	bObj,
		const OBJECT_ITERATOR &	eObj,
		vcg::CallBackPos *	callback
	)		`[inline]`

Definition at line 1103 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

template<class OBJECT_ITERATOR >

void vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::Set	(	const OBJECT_ITERATOR &	bObj,
		const OBJECT_ITERATOR &	eObj,
		const ConstructionApproach	approach
	)		`[inline]`

Definition at line 1107 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

template<class OBJECT_ITERATOR >

void vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::Set	(	const OBJECT_ITERATOR &	bObj,
		const OBJECT_ITERATOR &	eObj,
		const ConstructionApproach	approach,
		vcg::CallBackPos *	callback
	)		`[inline]`

Add the elements to the PerfectSpatialHashing data structure. Since this structure can handle only static dataset, the elements mustn't be changed while using this structure.

Parameters:

[in]	bObj	The iterator addressing the first element to be included in the hashing.
[in]	eObj	The iterator addressing the position after the last element to be included in the hashing.
[in]	approach	Either `FastConstructionApproach` or `CompactConstructionApproach`.
[in]	callback	The callback to call to provide information about the progress of the computation.

Definition at line 1119 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

HashTable::EntryCoordinate vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::Shift	(	const vcg::Point3i &	entry,
		const typename OffsetTable::Offset &	offset
	)		`[inline, protected]`

Performs the addition between a entry coordinate and an offset.

Parameters:

[in]	entry	The index of a given cell.
[in]	offset	The offset that must be applied to the entry.

Returns:: The entry resulting by the addition of entry and offset.

Definition at line 1297 of file perfect_spatial_hashing.h.

Member Data Documentation

template<class OBJECT_TYPE , class SCALAR_TYPE >

BinaryImage vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_Bitmap [protected]

Definition at line 1571 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

HashTable vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_HashTable [protected]

The hash table that will substitute the uniform grid.

Definition at line 1570 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

OffsetTable vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_OffsetTable [protected]

The offset table corresponding to $\Phi$ in the article.

Definition at line 1569 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >

UniformGrid vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_UniformGrid [protected]

The uniform grid used for partitioning the volume.

Definition at line 1568 of file perfect_spatial_hashing.h.

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

perfect_spatial_hashing.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

template<class OBJECT_TYPE, class SCALAR_TYPE> class vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class OBJECT_TYPE, class SCALAR_TYPE>
class vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >