vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE > Class Template Reference
[Index]

#include <perfect_spatial_hashing.h>

Inheritance diagram for vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >:
Inheritance graph
[legend]

List of all members.

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 CoordType &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 typename UniformGrid::CellCoordinate &query)
std::vector< ObjectPointer > * operator[] (const CoordinateType &query)
 PerfectSpatialHashing ()
template<class OBJECT_ITERATOR >
void Set (const OBJECT_ITERATOR &bObj, const OBJECT_ITERATOR &eObj, const ConstructionApproach approach, 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, vcg::CallBackPos *callback)
template<class OBJECT_ITERATOR >
void Set (const OBJECT_ITERATOR &bObj, const OBJECT_ITERATOR &eObj)
 ~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)

Protected Attributes

BinaryImage m_Bitmap
HashTable m_HashTable
OffsetTable m_OffsetTable
UniformGrid m_UniformGrid

Static Protected Attributes

static const float m_BOUNDING_BOX_EXPANSION_FACTOR = SCALAR_TYPE(0.035)
static const int m_DIMENSION = 3
static const int m_MAX_NUM_OF_RANDOM_GENERATED_OFFSET = 32
static const int m_MAX_TRIALS_IN_COMPACT_CONSTRUCTION = 5
static const float m_SIGMA = SCALAR_TYPE(1.0f/(2.0f*SCALAR_TYPE(m_DIMENSION)))

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 CoordType &  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 >
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 typename UniformGrid::CellCoordinate &  query  )  [inline]

Definition at line 1265 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 >
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,
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 >
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,
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 
) [inline]

Definition at line 1099 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 >
const SCALAR_TYPE vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_BOUNDING_BOX_EXPANSION_FACTOR = SCALAR_TYPE(0.035) [inline, static, protected]

Definition at line 1573 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >
const int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_DIMENSION = 3 [inline, static, protected]

Definition at line 1577 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 >
const int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_MAX_NUM_OF_RANDOM_GENERATED_OFFSET = 32 [inline, static, protected]

Definition at line 1576 of file perfect_spatial_hashing.h.

template<class OBJECT_TYPE , class SCALAR_TYPE >
const int vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_MAX_TRIALS_IN_COMPACT_CONSTRUCTION = 5 [inline, static, protected]

Definition at line 1575 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 >
const SCALAR_TYPE vcg::PerfectSpatialHashing< OBJECT_TYPE, SCALAR_TYPE >::m_SIGMA = SCALAR_TYPE(1.0f/(2.0f*SCALAR_TYPE(m_DIMENSION))) [inline, static, protected]

Definition at line 1574 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:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

vcglib
Author(s): Christian Bersch
autogenerated on Fri Jan 11 09:23:04 2013