00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00076
00077
00078
00079
00080
00081
00082
00084
00085
00086
00087 #ifndef __VCGLIB_GRID_CLOSEST
00088 #define __VCGLIB_GRID_CLOSEST
00089
00090 #include <vcg/space/index/space_iterators.h>
00091
00092 namespace vcg{
00093
00094 template <class SPATIAL_INDEX, class OBJPOINTDISTFUNCTOR, class OBJMARKER>
00095 typename SPATIAL_INDEX::ObjPtr GridClosest(SPATIAL_INDEX &Si,
00096 OBJPOINTDISTFUNCTOR _getPointDistance,
00097 OBJMARKER & _marker,
00098 const typename OBJPOINTDISTFUNCTOR::QueryType & _p_obj,
00099 const typename SPATIAL_INDEX::ScalarType & _maxDist,
00100 typename SPATIAL_INDEX::ScalarType & _minDist,
00101 typename SPATIAL_INDEX:: CoordType &_closestPt)
00102 {
00103 typedef typename SPATIAL_INDEX::ObjPtr ObjPtr;
00104 typedef SPATIAL_INDEX SpatialIndex;
00105 typedef typename SPATIAL_INDEX::CoordType CoordType;
00106 typedef typename SPATIAL_INDEX::ScalarType ScalarType;
00107 typedef typename SPATIAL_INDEX::Box3x Box3x;
00108
00109 Point3<ScalarType> _p = OBJPOINTDISTFUNCTOR::Pos(_p_obj);
00110
00111 _minDist = _maxDist;
00112
00113 ObjPtr winner=NULL;
00114 _marker.UnMarkAll();
00115 ScalarType newradius = Si.voxel.Norm();
00116 ScalarType radius;
00117 Box3i iboxdone,iboxtodo;
00118 CoordType t_res;
00119 typename SPATIAL_INDEX::CellIterator first,last,l;
00120 if(Si.bbox.IsInEx(_p))
00121 {
00122 Point3i _ip;
00123 Si.PToIP(_p,_ip);
00124 Si.Grid( _ip[0],_ip[1],_ip[2], first, last );
00125 for(l=first;l!=last;++l)
00126 {
00127 ObjPtr elem=&(**l);
00128 if (!elem->IsD())
00129 {
00130 if (_getPointDistance((**l), _p_obj,_minDist, t_res))
00131 {
00132 winner=elem;
00133 _closestPt=t_res;
00134 newradius=_minDist;
00135 }
00136 _marker.Mark(elem);
00137 }
00138 }
00139 iboxdone=Box3i(_ip,_ip);
00140 }
00141
00142 int ix,iy,iz;
00143 Box3i ibox(Point3i(0,0,0),Si.siz-Point3i(1,1,1));
00144 do
00145 {
00146 radius=newradius;
00147 Box3x boxtodo=Box3x(_p,radius);
00148
00149 Si.BoxToIBox(boxtodo, iboxtodo);
00150 iboxtodo.Intersect(ibox);
00151 if(!boxtodo.IsNull())
00152 {
00153 for (ix=iboxtodo.min[0]; ix<=iboxtodo.max[0]; ix++)
00154 for (iy=iboxtodo.min[1]; iy<=iboxtodo.max[1]; iy++)
00155 for (iz=iboxtodo.min[2]; iz<=iboxtodo.max[2]; iz++)
00156 if(ix<iboxdone.min[0] || ix>iboxdone.max[0] ||
00157 iy<iboxdone.min[1] || iy>iboxdone.max[1] ||
00158 iz<iboxdone.min[2] || iz>iboxdone.max[2] )
00159 {
00160 Si.Grid( ix, iy, iz, first, last );
00161 for(l=first;l!=last;++l) if (!(**l).IsD())
00162 {
00163 ObjPtr elem=&(**l);
00164 if (!elem->IsD())
00165 {
00166 if( ! _marker.IsMarked(elem))
00167 {
00168 if (_getPointDistance((**l), _p_obj, _minDist, t_res))
00169 {
00170 winner=elem;
00171 _closestPt=t_res;
00172 };
00173 _marker.Mark(elem);
00174 }
00175 }
00176 }
00177 }
00178 }
00179 if(!winner) newradius=radius+Si.voxel.Norm();
00180 else newradius = _minDist;
00181 }
00182 while (_minDist>radius);
00183
00184 return winner;
00185 }
00186
00187 template <class SPATIALINDEXING,class OBJPOINTDISTFUNCTOR, class OBJMARKER,
00188 class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER>
00189 unsigned int GridGetKClosest(SPATIALINDEXING &_Si,
00190 OBJPOINTDISTFUNCTOR & _getPointDistance,
00191 OBJMARKER & _marker,
00192 const unsigned int _k,
00193 const typename SPATIALINDEXING::CoordType & _p,
00194 const typename SPATIALINDEXING::ScalarType & _maxDist,
00195 OBJPTRCONTAINER & _objectPtrs,
00196 DISTCONTAINER & _distances,
00197 POINTCONTAINER & _points)
00198 {
00199 typedef vcg::ClosestIterator<SPATIALINDEXING,OBJPOINTDISTFUNCTOR,OBJMARKER> ClosestIteratorType;
00200 ClosestIteratorType Cli=ClosestIteratorType(_Si,_getPointDistance);
00201 Cli.SetMarker(_marker);
00202 Cli.Init(_p,_maxDist);
00203 unsigned int i=0;
00204 _objectPtrs.clear();
00205 _distances.clear();
00206 _points.clear();
00207 while ((!Cli.End())&&(i<_k))
00208 {
00209 _objectPtrs.push_back(&(*Cli));
00210 _distances.push_back(Cli.Dist());
00211 _points.push_back(Cli.NearestPoint());
00212 ++Cli;
00213 i++;
00214 }
00215 return (i);
00216 }
00217
00218 template <class SPATIALINDEXING,class OBJRAYISECTFUNCTOR, class OBJMARKER>
00219 typename SPATIALINDEXING::ObjPtr GridDoRay(SPATIALINDEXING &_Si,
00220 OBJRAYISECTFUNCTOR &_rayIntersector,
00221 OBJMARKER &_marker,
00222 const Ray3<typename SPATIALINDEXING::ScalarType> & _ray,
00223 const typename SPATIALINDEXING::ScalarType & _maxDist,
00224 typename SPATIALINDEXING::ScalarType & _t)
00225 {
00226 typedef vcg::RayIterator<SPATIALINDEXING,OBJRAYISECTFUNCTOR,OBJMARKER> RayIteratorType;
00227 RayIteratorType RayIte=RayIteratorType(_Si,_rayIntersector,_maxDist);
00228 RayIte.SetMarker(_marker);
00229 RayIte.Init(_ray);
00230
00231 if (!RayIte.End())
00232 {
00233 _t=RayIte.Dist();
00234 return(&(*RayIte));
00235 }
00236 return 0;
00237 }
00238
00239
00240 template <class SPATIALINDEXING, class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER>
00241 unsigned int GridGetInSphere(SPATIALINDEXING &_Si,
00242 OBJPOINTDISTFUNCTOR & _getPointDistance,
00243 OBJMARKER & _marker,
00244 const typename SPATIALINDEXING::CoordType & _p,
00245 const typename SPATIALINDEXING::ScalarType & _r,
00246 OBJPTRCONTAINER & _objectPtrs,
00247 DISTCONTAINER & _distances,
00248 POINTCONTAINER & _points)
00249 {
00250 typedef vcg::ClosestIterator<SPATIALINDEXING,OBJPOINTDISTFUNCTOR,OBJMARKER> ClosestIteratorType;
00251 ClosestIteratorType Cli=ClosestIteratorType(_Si,_getPointDistance);
00252 Cli.SetMarker(_marker);
00253 Cli.Init(_p,_r);
00254 _objectPtrs.clear();
00255 _distances.clear();
00256 _points.clear();
00257 while (!Cli.End())
00258 {
00259 _objectPtrs.push_back(&(*Cli));
00260 _distances.push_back(Cli.Dist());
00261 _points.push_back(Cli.NearestPoint());
00262 ++Cli;
00263 }
00264 return ((int)_objectPtrs.size());
00265 }
00266
00267 template <class SPATIALINDEXING,class OBJMARKER, class OBJPTRCONTAINER>
00268 unsigned int GridGetInBox(SPATIALINDEXING &_Si,
00269 OBJMARKER & _marker,
00270 const vcg::Box3<typename SPATIALINDEXING::ScalarType> &_bbox,
00271 OBJPTRCONTAINER & _objectPtrs)
00272 {
00273 typename SPATIALINDEXING::CellIterator first,last,l;
00274 _objectPtrs.clear();
00275 vcg::Box3i ibbox;
00276 Box3i Si_ibox(Point3i(0,0,0),_Si.siz-Point3i(1,1,1));
00277 _Si.BoxToIBox(_bbox, ibbox);
00278 ibbox.Intersect(Si_ibox);
00279 _marker.UnMarkAll();
00280 if (ibbox.IsNull())
00281 return 0;
00282 else
00283 {
00284 int ix,iy,iz;
00285 for (ix=ibbox.min[0]; ix<=ibbox.max[0]; ix++)
00286 for (iy=ibbox.min[1]; iy<=ibbox.max[1]; iy++)
00287 for (iz=ibbox.min[2]; iz<=ibbox.max[2]; iz++)
00288 {
00289 _Si.Grid( ix, iy, iz, first, last );
00290 for(l=first;l!=last;++l)
00291 if (!(**l).IsD())
00292 {
00293 typename SPATIALINDEXING::ObjPtr elem=&(**l);
00294 vcg::Box3<typename SPATIALINDEXING::ScalarType> box_elem;
00295 elem->GetBBox(box_elem);
00296 if(( ! _marker.IsMarked(elem))&&(box_elem.Collide(_bbox))){
00297 _objectPtrs.push_back(elem);
00298 _marker.Mark(elem);
00299 }
00300 }
00301 }
00302 return (static_cast<unsigned int>(_objectPtrs.size()));
00303 }
00304 }
00305
00306 }
00307 #endif
00308
