vcglib: grid_util.h Source File

00001 /****************************************************************************
00002 * VCGLib                                                            o o     *
00003 * Visual and Computer Graphics Library                            o     o   *
00004 *                                                                _   O  _   *
00005 * Copyright(C) 2005                                                \/)\/    *
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 History
00025 
00026 $Log: not supported by cvs2svn $
00027 Revision 1.12  2008/02/19 12:43:01  callieri
00028 in BestDim(...) changed int -> _int64 to cope with programs with a very large cell number (like plyMC)
00029 
00030 Revision 1.11  2008/02/04 19:18:44  ganovelli
00031 typo corrected
00032 
00033 Revision 1.10  2006/08/23 15:21:35  marfr960
00034 added some comments
00035 
00036 Revision 1.9  2005/12/02 00:27:22  cignoni
00037 removed excess typenames
00038 
00039 Revision 1.8  2005/10/03 16:21:10  spinelli
00040 erase wrong assert on boxToIbox function
00041 
00042 Revision 1.7  2005/10/02 23:16:26  cignoni
00043 English comment and moved typedef to public scope
00044 
00045 Revision 1.6  2005/09/30 13:12:46  pietroni
00046 basic grid class is derived from Indexing base class defined in base,h
00047 
00048 Revision 1.5  2005/09/16 11:56:38  cignoni
00049 removed wrong typename and added ending \n
00050 
00051 Revision 1.4  2005/08/02 11:01:05  pietroni
00052 added IPToP and IBoxToBox functions, modified BoxToIBox function in order to use PToIP function
00053 
00054 Revision 1.3  2005/07/28 06:11:12  cignoni
00055 corrected error in GridP (did not compile)
00056 
00057 Revision 1.2  2005/07/01 11:33:36  cignoni
00058 Added a class BasicGrid with some utility function that are scattered among similar classes
00059 
00060 Revision 1.1  2005/03/15 11:43:18  cignoni
00061 Removed BestDim function from the grid_static_ptr class and moved to a indipendent file (grid_util.h) for sake of generality.
00062 
00063 
00064 ****************************************************************************/
00065 #ifndef __VCGLIB_GRID_UTIL
00066 #define __VCGLIB_GRID_UTIL
00067 
00068 #include<vcg/space/index/base.h>
00069 #include<vcg/space/box3.h>
00070 #include <vcg/space/index/space_iterators.h>
00071 
00072 
00073 #ifndef WIN32
00074 #define __int64 long long
00075 #define __cdecl 
00076 #endif
00077 
00078 namespace vcg {
00079 
00094 template <class SCALARTYPE> 
00095 class BasicGrid //:public SpatialIndex<SCALARTYPE> 
00096 {
00097 public:
00098 
00099         typedef SCALARTYPE ScalarType;
00100         typedef Box3<ScalarType> Box3x;
00101         typedef Point3<ScalarType> CoordType;
00102         typedef BasicGrid<SCALARTYPE> GridType;
00103 
00104         Box3x bbox;
00105 
00106         CoordType dim;          
00107         Point3i siz;            
00108         CoordType voxel;        
00109 
00110         /*
00111          Derives the right values of Dim and voxel starting
00112          from the current values of siz and bbox
00113         */
00114         void ComputeDimAndVoxel()
00115                 {
00116                         this->dim  = this->bbox.max - this->bbox.min;
00117                         this->voxel[0] = this->dim[0]/this->siz[0];
00118                         this->voxel[1] = this->dim[1]/this->siz[1];
00119                         this->voxel[2] = this->dim[2]/this->siz[2];
00120                 }
00121         /* Given a 3D point, returns the coordinates of the cell where the point is
00122          * @param p is a 3D point
00123          * @return integer coordinates of the cell
00124          */
00125         inline Point3i GridP( const Point3<ScalarType> & p ) const 
00126         {
00127                 Point3i pi; 
00128                 PToIP(p, pi);
00129                 return pi;
00130         }
00131 
00132         /* Given a 3D point p, returns the index of the corresponding cell
00133          * @param p is a 3D point in the space
00134          * @return integer coordinates pi of the cell
00135          */
00136         inline void PToIP(const CoordType & p, Point3i &pi ) const
00137         {
00138                 CoordType t = p - bbox.min;
00139                 pi[0] = int( t[0] / voxel[0] );
00140                 pi[1] = int( t[1] / voxel[1] );
00141                 pi[2] = int( t[2] / voxel[2] );
00142         }
00143 
00144         /* Given a cell index return the lower corner of the cell
00145          * @param integer coordinates pi of the cell
00146          * @return p is a 3D point representing the lower corner of the cell
00147          */
00148         inline void IPiToPf(const Point3i & pi, CoordType &p ) const
00149         {
00150                 p[0] = ((ScalarType)pi[0])*voxel[0];
00151                 p[1] = ((ScalarType)pi[1])*voxel[1];
00152                 p[2] = ((ScalarType)pi[2])*voxel[2];
00153                 p += bbox.min;
00154         }
00155 
00156         /* Given a cell index return the corresponding box
00157          * @param integer coordinates pi of the cell
00158          * @return b is the corresponding box in <ScalarType> coordinates
00159          */
00160         inline void IPiToBox(const Point3i & pi, Box3x & b ) const
00161         {
00162                 CoordType p;
00163                 p[0] = ((ScalarType)pi[0])*voxel[0];
00164                 p[1] = ((ScalarType)pi[1])*voxel[1];
00165                 p[2] = ((ScalarType)pi[2])*voxel[2];
00166                 p += bbox.min;
00167                 b.min = p;
00168                 b.max = (p + voxel);
00169         }
00170 
00171         /* Given a cell index return the center of the cell itself
00172          * @param integer coordinates pi of the cell
00173          * @return b is the corresponding box in <ScalarType> coordinates
00174          */inline void IPiToBoxCenter(const Point3i & pi, CoordType & c ) const
00175         {
00176                 CoordType p;
00177                 IPiToPf(pi,p);
00178                 c = p + voxel/ScalarType(2.0);
00179         }
00180 
00181         // Same of IPiToPf but for the case that you just want to transform 
00182         // from a space to the other.
00183         inline void IPfToPf(const CoordType & pi, CoordType &p ) const
00184         {
00185                 p[0] = ((ScalarType)pi[0])*voxel[0];
00186                 p[1] = ((ScalarType)pi[1])*voxel[1];
00187                 p[2] = ((ScalarType)pi[2])*voxel[2];
00188                 p += bbox.min;
00189         }
00190         
00191         /* Given a cell in <ScalarType> coordinates, compute the corresponding cell in integer coordinates
00192          * @param b is the cell in <ScalarType> coordinates
00193          * @return ib is the correspondent box in integer coordinates
00194          */
00195         void BoxToIBox( const Box3x & b, Box3i & ib ) const
00196         {
00197                 PToIP(b.min, ib.min);
00198                 PToIP(b.max, ib.max);
00199                 //assert(ib.max[0]>=0 && ib.max[1]>=0 && ib.max[2]>=0); 
00200         }
00201 
00202         /* Given a cell in integer coordinates, compute the corresponding cell in <ScalarType> coordinates
00203          * @param ib is the cell in integer coordinates
00204          * @return b is the correspondent box in <ScalarType> coordinates
00205          */
00207         void IBoxToBox( const Box3i & ib, Box3x & b ) const
00208         {
00209                 IPToP(ib.min,b.min);
00210                 IPToP(ib.max,b.max);
00211         }
00212 };
00213 
00214 template<class scalar_type>
00215 void BestDim( const Box3<scalar_type> box, const scalar_type voxel_size, Point3i & dim )
00216 {
00217         Point3<scalar_type> box_size = box.max-box.min;
00218         __int64 elem_num = (__int64)(box_size[0]/voxel_size +0.5) *( __int64)(box_size[1]/voxel_size +0.5) * (__int64)(box_size[2]/voxel_size +0.5);
00219         BestDim(elem_num,box_size,dim);
00220 }       
00225         template<class scalar_type>
00226         void BestDim( const __int64 elems, const Point3<scalar_type> & size, Point3i & dim )
00227         {
00228                 const __int64 mincells   = 1;           // Numero minimo di celle
00229                 const double GFactor = 1;       // GridEntry = NumElem*GFactor
00230                 double diag = size.Norm();      // Diagonale del box
00231                 double eps  = diag*1e-4;                // Fattore di tolleranza
00232 
00233                 assert(elems>0);
00234                 assert(size[0]>=0.0);
00235                 assert(size[1]>=0.0);
00236                 assert(size[2]>=0.0);
00237 
00238 
00239                 __int64 ncell = (__int64)(elems*GFactor);       // Calcolo numero di voxel
00240                 if(ncell<mincells)
00241                         ncell = mincells;
00242 
00243                 dim[0] = 1;
00244                 dim[1] = 1;
00245                 dim[2] = 1;
00246 
00247                 if(size[0]>eps)
00248                 {
00249                         if(size[1]>eps)
00250                         {
00251                                 if(size[2]>eps)
00252                                 {
00253                                         double k = pow((double)(ncell/(size[0]*size[1]*size[2])),double(1.0/3.f));
00254                                         dim[0] = int(size[0] * k);
00255                                         dim[1] = int(size[1] * k);
00256                                         dim[2] = int(size[2] * k);
00257                                 } 
00258                                 else 
00259                                 {
00260                                         dim[0] = int(::sqrt(ncell*size[0]/size[1]));
00261                                         dim[1] = int(::sqrt(ncell*size[1]/size[0]));
00262                                 }
00263                         }
00264                         else
00265                         {
00266                                 if(size[2]>eps)
00267                                 {
00268                                         dim[0] = int(::sqrt(ncell*size[0]/size[2]));
00269                                         dim[2] = int(::sqrt(ncell*size[2]/size[0]));
00270                                 }
00271                                 else
00272                                         dim[0] = int(ncell);
00273                         }
00274                 }
00275                 else
00276                 {
00277                         if(size[1]>eps)
00278                         {
00279                                 if(size[2]>eps)
00280                                 {
00281                                         dim[1] = int(::sqrt(ncell*size[1]/size[2]));
00282                                         dim[2] = int(::sqrt(ncell*size[2]/size[1]));
00283                                 }
00284                                 else
00285                                         dim[1] = int(ncell);
00286                         }
00287                         else if(size[2]>eps)
00288                                 dim[2] = int(ncell);
00289                 }
00290                 dim[0] = math::Max(dim[0],1);
00291                 dim[1] = math::Max(dim[1],1);
00292                 dim[2] = math::Max(dim[2],1);
00293         }
00294 }
00295 #endif