vcglib: spatial_hashing.h Source File

00001 /****************************************************************************
00002 * VCGLib                                                            o o     *
00003 * Visual and Computer Graphics Library                            o     o   *
00004 *                                                                _   O  _   *
00005 * Copyright(C) 2004                                                \/)\/    *
00006 * Visual Computing Lab                                            /\/|      *
00007 * ISTI - Italian National Research Council                           |      *
00008 *                                                                    \      *
00009 * All rights reserved.                                                      *
00010 *                                                                           *
00011 * This program is free software; you can redistribute it and/or modify      *
00012 * it under the terms of the GNU General Public License as published by      *
00013 * the Free Software Foundation; either version 2 of the License, or         *
00014 * (at your option) any later version.                                       *
00015 *                                                                           *
00016 * This program is distributed in the hope that it will be useful,           *
00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
00019 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
00020 * for more details.                                                         *
00021 *                                                                           *
00022 ****************************************************************************/
00023 
00024 #ifndef VCGLIB_SPATIAL_HASHING
00025 #define VCGLIB_SPATIAL_HASHING
00026 
00027 #include <vcg/space/index/grid_util.h>
00028 #include <vcg/space/index/grid_closest.h>
00029 //#include <map>
00030 #include <vector>
00031 #include <algorithm>
00032 #ifdef _WIN32
00033  #ifndef __MINGW32__
00034   #include <hash_map>
00035   #define STDEXT stdext
00036  #else
00037   #include <ext/hash_map>
00038   #define STDEXT __gnu_cxx
00039  #endif
00040 #else
00041  #include <ext/hash_map>
00042  #define STDEXT __gnu_cxx
00043 #endif
00044 
00045 
00046 namespace vcg{
00047 
00048 
00049 
00050         // hashing function
00051         struct HashFunctor : public std::unary_function<Point3i, size_t>
00052         {
00053                 enum
00054                   { // parameters for hash table
00055                                 bucket_size = 4, // 0 < bucket_size
00056                                 min_buckets = 8
00057                         };
00058 
00059                 size_t operator()(const Point3i &p) const
00060                 {
00061                         const size_t _HASH_P0 = 73856093u;
00062                         const size_t _HASH_P1 = 19349663u;
00063                         const size_t _HASH_P2 = 83492791u;
00064 
00065                         return size_t(p.V(0))*_HASH_P0 ^  size_t(p.V(1))*_HASH_P1 ^  size_t(p.V(2))*_HASH_P2;
00066                 }
00067 
00068                 bool operator()(const Point3i &s1, const Point3i &s2) const
00069                 { // test if s1 ordered before s2
00070                         return (s1 < s2);
00071                 }
00072         };
00073 
00074 
00075 
00076 
00082         template < typename ObjType,class FLT=double>
00083         class SpatialHashTable:public BasicGrid<FLT>, public SpatialIndex<ObjType,FLT>
00084         {
00085 
00086         public:
00087         typedef SpatialHashTable SpatialHashType;
00088         typedef ObjType* ObjPtr;
00089         typedef typename ObjType::ScalarType ScalarType;
00090         typedef Point3<ScalarType> CoordType;
00091         typedef typename BasicGrid<FLT>::Box3x Box3x;
00092 
00093         // Hash table definition
00094         // the hash index directly the grid structure. 
00095         // We use a MultiMap because we need to store many object (faces) inside each cell of the grid. 
00096 
00097         typedef typename STDEXT::hash_multimap<Point3i, ObjType *, HashFunctor> HashType;
00098         typedef typename HashType::iterator HashIterator;
00099         HashType hash_table; // The real HASH TABLE **************************************
00100         
00101         // This vector is just a handy reference to all the allocated cells,
00102         // becouse hashed multimaps does not expose a direct list of all the different keys. 
00103         std::vector<Point3i> AllocatedCells;
00104                 
00105         // Class to abstract a HashIterator (that stores also the key, 
00106         // while the interface of the generic spatial indexing need only simple object (face) pointers.
00107         
00108         struct CellIterator
00109         {
00110                 CellIterator(){}
00111                 HashIterator t;
00112                 ObjPtr &operator *(){return (t->second); }
00113                 ObjPtr operator *() const {return (t->second); }
00114                 bool operator != (const CellIterator & p) const {return t!=p.t;}
00115                 void operator ++() {t++;}
00116         };
00117         
00118 
00119     size_t CellSize(const Point3i &cell)
00120     {
00121         return hash_table.count(cell);
00122     }
00123                 
00124                 inline bool EmptyCell(const Point3i &cell) const
00125                 {
00126                  return hash_table.find(cell) == hash_table.end();
00127                 }
00128                 
00129                 void UpdateAllocatedCells()
00130                 {
00131                         AllocatedCells.clear();
00132                         if(hash_table.empty()) return;
00133                         AllocatedCells.push_back(hash_table.begin()->first);
00134                         for(HashIterator fi=hash_table.begin();fi!=hash_table.end();++fi)
00135                         {
00136                                 if(AllocatedCells.back()!=fi->first) AllocatedCells.push_back(fi->first);                               
00137                         }
00138                 }
00139 protected:
00140 
00142         void InsertObject(ObjType* s, const Point3i &cell)
00143         {
00144                 //if(hash_table.count(cell)==0) AllocatedCells.push_back(cell);
00145                 hash_table.insert(typename HashType::value_type(cell, s));
00146         }
00147 
00149     void RemoveCell(const Point3i &cell)
00150     {
00151     }
00152 
00153 
00154     bool RemoveObject(ObjType* s, const Point3i &cell)
00155     {
00156         std::pair<HashIterator,HashIterator> CellRange = hash_table.equal_range(cell);
00157         CellIterator first; first.t=CellRange.first;
00158         CellIterator end; end.t=CellRange.second;
00159         for(CellIterator ci = first; ci!=end;++ci)
00160         {
00161             if (*ci == s)
00162                {
00163                    hash_table.erase(ci.t);
00164                    return true;
00165                }
00166         }
00167         return false;
00168     }
00169 
00170         public:
00171 
00172                 vcg::Box3i Add( ObjType* s)
00173                 {
00174                         Box3<ScalarType> b;
00175                         s->GetBBox(b);
00176                         vcg::Box3i bb;
00177                         BoxToIBox(b,bb);
00178                         //then insert all the cell of bb
00179                         for (int i=bb.min.X();i<=bb.max.X();i++)
00180                                 for (int j=bb.min.Y();j<=bb.max.Y();j++)
00181                                         for (int k=bb.min.Z();k<=bb.max.Z();k++)
00182                                                 InsertObject(s,vcg::Point3i(i,j,k));
00183 
00184                         return bb;
00185                 }
00186 
00188         // it removes s too.
00189         bool RemoveCell(ObjType* s)
00190         {
00191             Point3i pi;
00192             PToIP(s->cP(),pi);
00193             std::pair<HashIterator,HashIterator> CellRange = hash_table.equal_range(pi);
00194             hash_table.erase(CellRange.first,CellRange.second);
00195             return true;
00196         }    
00197 
00198         int RemoveInSphere(const Point3<ScalarType> &p, const ScalarType radius)
00199         {
00200             Box3x b(p-Point3f(radius,radius,radius),p+Point3f(radius,radius,radius));
00201             vcg::Box3i bb;
00202             BoxToIBox(b,bb);
00203             ScalarType r2=radius*radius;
00204             int cnt=0;
00205             std::vector<HashIterator> toDel;
00206 
00207                         for (int i=bb.min.X();i<=bb.max.X();i++)
00208                                 for (int j=bb.min.Y();j<=bb.max.Y();j++)
00209                                         for (int k=bb.min.Z();k<=bb.max.Z();k++)
00210                                         {
00211                 std::pair<HashIterator,HashIterator> CellRange = hash_table.equal_range(Point3i(i,j,k));
00212                 for(HashIterator hi = CellRange.first; hi!=CellRange.second;++hi)
00213                 {
00214                     if(SquaredDistance(p,hi->second->cP()) <= r2)
00215                     {
00216                         cnt++;
00217                         toDel.push_back(hi);
00218                     }
00219                 }
00220             }
00221             for(typename std::vector<HashIterator>::iterator vi=toDel.begin(); vi!=toDel.end();++vi)
00222                 hash_table.erase(*vi);
00223 
00224             return cnt;
00225         }
00226 
00227                 // Thsi version of the removal is specialized for the case where
00228                 // an object has a pointshaped box and using the generic bbox interface is just a waste of time.
00229                 
00230                 void RemovePunctual( ObjType *s)
00231         {
00232             Point3i pi;
00233             PToIP(s->cP(),pi);
00234             std::pair<HashIterator,HashIterator> CellRange = hash_table.equal_range(pi);
00235             for(HashIterator hi = CellRange.first; hi!=CellRange.second;++hi)
00236             {
00237                 if (hi->second == s)
00238                    {
00239                        hash_table.erase(hi);
00240                        return;
00241                    }
00242             }
00243         }
00244 
00245         void Remove( ObjType* s)
00246         {
00247             Box3<ScalarType> b;
00248             s->GetBBox(b);
00249             vcg::Box3i bb;
00250             BoxToIBox(b,bb);
00251             //then remove the obj from all the cell of bb
00252             for (int i=bb.min.X();i<=bb.max.X();i++)
00253                 for (int j=bb.min.Y();j<=bb.max.Y();j++)
00254                     for (int k=bb.min.Z();k<=bb.max.Z();k++)
00255                         RemoveObject(s,vcg::Point3i(i,j,k));
00256         }
00257                 
00259                 void InitEmpty(const Box3x &_bbox, vcg::Point3i grid_size)
00260                 {
00261                         Box3x b;
00262                         Box3x &bbox = this->bbox;
00263                         CoordType &dim = this->dim;
00264                         Point3i &siz = this->siz;
00265                         CoordType &voxel = this->voxel;
00266 
00267                         assert(!_bbox.IsNull());
00268                         bbox=_bbox;
00269                         dim  = bbox.max - bbox.min;
00270                         assert((grid_size.V(0)>0)&&(grid_size.V(1)>0)&&(grid_size.V(2)>0));
00271                         siz=grid_size;
00272 
00273                         voxel[0] = dim[0]/siz[0];
00274                         voxel[1] = dim[1]/siz[1];
00275                         voxel[2] = dim[2]/siz[2];
00276             hash_table.clear();
00277                 }
00278 
00280                 template <class OBJITER>
00281                         void Set(const OBJITER & _oBegin, const OBJITER & _oEnd, const Box3x &_bbox=Box3x() )
00282                 {
00283                         OBJITER i;
00284                         Box3x b;
00285                         Box3x &bbox = this->bbox;
00286                         CoordType &dim = this->dim;
00287                         Point3i &siz = this->siz;
00288                         CoordType &voxel = this->voxel;
00289 
00290                         int _size=(int)std::distance<OBJITER>(_oBegin,_oEnd);
00291                         if(!_bbox.IsNull()) this->bbox=_bbox;
00292                         else
00293                         {
00294                                 for(i = _oBegin; i!= _oEnd; ++i)
00295                                 {
00296                                         (*i).GetBBox(b);
00297                                         this->bbox.Add(b);
00298                                 }
00300                                 bbox.Offset(bbox.Diag()/100.0) ;
00301                         }
00302 
00303                         dim  = bbox.max - bbox.min;
00304                         BestDim( _size, dim, siz );
00305                         // find voxel size
00306                         voxel[0] = dim[0]/siz[0];
00307                         voxel[1] = dim[1]/siz[1];
00308                         voxel[2] = dim[2]/siz[2];
00309 
00310                         for(i = _oBegin; i!= _oEnd; ++i)
00311                                 Add(&(*i));
00312                 }
00313 
00314 
00316                 void GridReal( const Point3<ScalarType> & p, CellIterator & first, CellIterator & last )
00317                 {
00318                         vcg::Point3i _c;
00319                         this->PToIP(p,_c);
00320                         Grid(_c,first,last);
00321                 }
00322 
00324                 void Grid( int x,int y,int z, CellIterator & first, CellIterator & last )
00325                 {
00326                         this->Grid(vcg::Point3i(x,y,z),first,last);
00327                 }
00328 
00330                 void Grid( const Point3i & _c, CellIterator & first, CellIterator & end )
00331                 {
00332                         std::pair<HashIterator,HashIterator> CellRange = hash_table.equal_range(_c);
00333                         first.t=CellRange.first;
00334                         end.t=CellRange.second;
00335                 }
00336 
00337                 void Clear()
00338                 {
00339                         hash_table.clear();
00340                         AllocatedCells.clear();
00341                 }
00342 
00343 
00344                 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER>
00345                         ObjPtr  GetClosest(OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker,
00346                         const CoordType & _p, const ScalarType & _maxDist,ScalarType & _minDist, CoordType & _closestPt)
00347                 {
00348                         return (vcg::GridClosest<SpatialHashType,OBJPOINTDISTFUNCTOR,OBJMARKER>(*this,_getPointDistance,_marker, _p,_maxDist,_minDist,_closestPt));
00349                 }
00350 
00351 
00352                 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER,class DISTCONTAINER, class POINTCONTAINER>
00353                         unsigned int GetKClosest(OBJPOINTDISTFUNCTOR & _getPointDistance,OBJMARKER & _marker,
00354                         const unsigned int _k, const CoordType & _p, const ScalarType & _maxDist,OBJPTRCONTAINER & _objectPtrs,
00355                         DISTCONTAINER & _distances, POINTCONTAINER & _points)
00356                 {
00357                         return (vcg::GridGetKClosest<SpatialHashType,
00358                                 OBJPOINTDISTFUNCTOR,OBJMARKER,OBJPTRCONTAINER,DISTCONTAINER,POINTCONTAINER>
00359                                 (*this,_getPointDistance,_marker,_k,_p,_maxDist,_objectPtrs,_distances,_points));
00360                 }
00361 
00362                 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER>
00363                 unsigned int GetInSphere(OBJPOINTDISTFUNCTOR & _getPointDistance,
00364                 OBJMARKER & _marker,
00365                 const CoordType & _p,
00366                 const ScalarType & _r,
00367                 OBJPTRCONTAINER & _objectPtrs,
00368                 DISTCONTAINER & _distances,
00369                 POINTCONTAINER & _points)
00370                 {
00371                         return(vcg::GridGetInSphere<SpatialHashType,
00372                                 OBJPOINTDISTFUNCTOR,OBJMARKER,OBJPTRCONTAINER,DISTCONTAINER,POINTCONTAINER>
00373                                 (*this,_getPointDistance,_marker,_p,_r,_objectPtrs,_distances,_points));
00374                 }
00375 
00376                 template <class OBJMARKER, class OBJPTRCONTAINER>
00377                         unsigned int GetInBox(OBJMARKER & _marker,
00378             const Box3x _bbox,
00379                         OBJPTRCONTAINER & _objectPtrs)
00380                 {
00381                         return(vcg::GridGetInBox<SpatialHashType,OBJMARKER,OBJPTRCONTAINER>
00382                                   (*this,_marker,_bbox,_objectPtrs));
00383                 }
00384 
00385                 template <class OBJRAYISECTFUNCTOR, class OBJMARKER>
00386                         ObjPtr DoRay(OBJRAYISECTFUNCTOR & _rayIntersector, OBJMARKER & _marker, const Ray3<ScalarType> & _ray, const ScalarType & _maxDist, ScalarType & _t)
00387                 {
00388                         return(vcg::GridDoRay<SpatialHashType,OBJRAYISECTFUNCTOR,OBJMARKER>
00389                                   (*this,_rayIntersector,_marker,_ray,_maxDist,_t));
00390                 }
00391 
00392 
00393         }; // end class
00394 
00399         template < typename ContainerType,class FLT=double>
00400         class DynamicSpatialHashTable: public SpatialHashTable<ContainerType,FLT>
00401         {
00402         public:
00403         typedef typename SpatialHashTable<ContainerType,FLT>::CoordType CoordType;
00404         typedef typename SpatialHashTable<ContainerType,FLT>::ObjType ObjType;
00405         typedef typename SpatialHashTable<ContainerType,FLT>::ObjPtr ObjPtr;
00406         typedef typename SpatialHashTable<ContainerType,FLT>::Box3x Box3x;
00407         typedef typename SpatialHashTable<ContainerType,FLT>::CellIterator CellIterator;
00408 
00409                 void _UpdateHMark(ObjType* s){ s->HMark() = this->tempMark;}
00410 
00411                 void getInCellUpdated(vcg::Point3i cell,std::vector<ObjPtr> &elems)
00412                 {
00413                         CellIterator first,last,l;
00414                         Grid(cell,first,last);
00415                         for (l=first;l!=last;l++)
00416                         {
00417                                 if ((l->second)>=(**l).HMark())
00418                                         elems.push_back(&(**l));
00419                         }
00420                 }
00421 
00422         };
00423 
00424 
00425 
00426 
00427 
00428 }// end namespace
00429 
00430 #endif