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 /**************************************************************************** 00025 History 00026 00027 ****************************************************************************/ 00028 00029 #ifndef __VCGLIB_SPATIALINDEX_2DH 00030 #define __VCGLIB_SPATIALINDEX_2DH 00031 00032 // standard headers 00033 #include <assert.h> 00034 00035 // vcg headers 00036 #include <vcg/space/point2.h> 00037 #include <vcg/space/ray2.h> 00038 #include <vcg/space/box2.h> 00039 00040 namespace vcg { 00041 00042 /**************************************************************************** 00043 Class SpatialIndex 00044 00045 Description: 00046 This class exposes the base interface for all spatial indexing data 00047 structures, i.e. grids, bounding volume trees. 00048 00049 Template Parameters: 00050 OBJTYPE: Type of the indexed objects. 00051 SCALARTYPE: Scalars type for structure's internal data (may differ from 00052 object's scalar type). 00053 00054 ****************************************************************************/ 00055 00056 template <class OBJTYPE, class SCALARTYPE> 00057 class SpatialIndex2D { 00058 public: 00059 /************************************************************************** 00060 Commonly used typedefs. 00061 **************************************************************************/ 00062 typedef SpatialIndex2D<OBJTYPE, SCALARTYPE> ClassType; 00063 typedef OBJTYPE ObjType; 00064 typedef SCALARTYPE ScalarType; 00065 typedef ObjType * ObjPtr; 00066 typedef Point2<ScalarType> CoordType; 00067 typedef vcg::Box2<ScalarType> BoxType; 00068 00069 /************************************************************************** 00070 Method Set. 00071 00072 Description: 00073 The Set method initializes the spatial structure. 00074 00075 Template Parameters: 00076 OBJITER: Objects Container's iterator type. 00077 00078 Method Parameters: 00079 _oBegin : [IN] begin objects container's iterator 00080 _oEnd : [IN] end objects container's iterator 00081 00082 Return Value: 00083 None. 00084 00085 **************************************************************************/ 00086 template <class OBJITER> 00087 void Set(const OBJITER & _oBegin, const OBJITER & _oEnd) { 00088 assert(0); // this is a base interface. 00089 (void)_oBegin; // avoid "unreferenced parameter" compiler warning. 00090 (void)_oEnd; 00091 } 00092 00093 /************************************************************************** 00094 Method Empty. 00095 Description: 00096 check if the spatial structure is empty. 00097 00098 Return Value: 00099 true if it is empty. 00100 **************************************************************************/ 00101 00102 bool Empty() { 00103 assert(0); // this is a base interface. 00104 return true; 00105 } 00106 00107 /************************************************************************** 00108 Method GetClosest. 00109 00110 Description: 00111 The GetClosest method finds the closest object given a point. 00112 It also finds the closest point and minimum distance. 00113 00114 Template Parameters: 00115 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 00116 this type must implement an operator () with signature 00117 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 00118 where: 00119 obj [IN] is a reference to the current object being tested, 00120 p [IN] is the query point, 00121 d [IN/OUT] is in input the reject distance and in output the closest distance, 00122 q [OUT] is the closest point. 00123 The operator returns true if the closest distance is less than input reject distance. 00124 OBJMARKER : The type of a marker functor. 00125 00126 Method Parameters: 00127 _getPointDistance : [IN] Functor for point-distance calculation. 00128 _marker : [IN] Functor for marking objects already tested. 00129 _p : [IN] The query point. 00130 _maxDist : [IN] Maximum reject distance. 00131 _minDist : [OUT] Closest distance. 00132 _closestPt : [OUT] Closest point. 00133 00134 Return Value: 00135 A pointer to the closest object (if any). 00136 00137 **************************************************************************/ 00138 /*template <class OBJPOINTDISTFUNCTOR, class OBJMARKER> 00139 ObjPtr GetClosest( 00140 OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker, const CoordType & _p, const ScalarType & _maxDist, 00141 ScalarType & _minDist, CoordType & _closestPt) { 00142 assert(0); 00143 (void)_getPointDistance; 00144 (void)_marker; 00145 (void)_p; 00146 (void)_maxDist; 00147 (void)_minDist; 00148 (void)_closestPt; 00149 return ((ObjPtr)0); 00150 }*/ 00151 00152 /************************************************************************** 00153 Method GetKClosest. 00154 00155 Description: 00156 The GetKClosest method finds the K closest object given a point. 00157 It also finds the closest points and minimum distances. 00158 00159 Template Parameters: 00160 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 00161 this type must implement an operator () with signature 00162 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 00163 where: 00164 obj [IN] is a reference to the current object being tested, 00165 p [IN] is the query point, 00166 d [IN/OUT] is in input the reject distance and in output the closest distance, 00167 q [OUT] is the closest point. 00168 The operator returns true if the closest distance is less than input reject distance. 00169 OBJMARKER : The type of a marker functor. 00170 OBJPTRCONTAINER : The type of a object pointers container. 00171 DISTCONTAINER : The type of a container which, in return, will contain the closest distances. 00172 POINTCONTAINER : The type of a container which, in return, will contain the closest points. 00173 00174 Method Parameters: 00175 _getPointDistance : [IN] Functor for point-distance calculation. 00176 _marker : [IN] Functor for marking objects already tested. 00177 _k : [IN] The number of closest objects to search for. 00178 _p : [IN] The query point. 00179 _maxDist : [IN] Maximum reject distance. 00180 _objectPtrs : [OUT] Container which, in return, will contain pointers to the closest objects. 00181 _distances : [OUT] Container which, in return, will contain the closest distances. 00182 _objectPtrs : [OUT] Container which, in return, will contain the closest points. 00183 00184 Return Value: 00185 The number of closest objects found. 00186 00187 **************************************************************************/ 00188 //template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER> 00189 //unsigned int GetKClosest( 00190 // OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker, const unsigned int _k, const CoordType & _p, const ScalarType & _maxDist, 00191 // OBJPTRCONTAINER & _objectPtrs, DISTCONTAINER & _distances, POINTCONTAINER & _points) { 00192 // assert(0); 00193 // (void)_getPointDistance; 00194 // (void)_marker; 00195 // (void)_k; 00196 // (void)_p; 00197 // (void)_maxDist; 00198 // (void)_objectPtrs; 00199 // (void)_distances; 00200 // (void)_points; 00201 // return (0); 00202 //} 00203 00204 00205 /************************************************************************** 00206 Method GetInSphere. 00207 00208 Description: 00209 The GetInSphere method finds all the objects in the specified sphere 00210 00211 Template Parameters: 00212 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 00213 this type must implement an operator () with signature 00214 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 00215 where: 00216 obj [IN] is a reference to the current object being tested, 00217 p [IN] is the query point, 00218 d [IN/OUT] is in input the reject distance and in output the closest distance, 00219 q [OUT] is the closest point. 00220 The operator returns true if the closest distance is less than input reject distance. 00221 OBJMARKER : The type of a marker functor. 00222 OBJPTRCONTAINER : The type of a object pointers container. 00223 DISTCONTAINER : The type of a container which, in return, will contain the closest distances. 00224 POINTCONTAINER : The type of a container which, in return, will contain the closest points. 00225 00226 Method Parameters: 00227 _getPointDistance : [IN] Functor for point-distance calculation. 00228 _marker : [IN] Functor for marking objects already tested. 00229 _p : [IN] The query point. 00230 _r : [IN] The radius of the specified sphere. 00231 _objectPtrs : [OUT] Container which, in return, will contain pointers to the in-sphere objects. 00232 _distances : [OUT] Container which, in return, will contain the in-sphere distances. 00233 _objectPtrs : [OUT] Container which, in return, will contain the in-sphere nearests points for each object. 00234 00235 Return Value: 00236 The number of in-sphere objects found. 00237 00238 **************************************************************************/ 00239 //template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER> 00240 //unsigned int GetInCircle( 00241 // OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker,const CoordType & _p, const ScalarType & _r,OBJPTRCONTAINER & _objectPtrs, DISTCONTAINER & _distances, POINTCONTAINER & _points) { 00242 // assert(0); 00243 // (void)_getPointDistance; 00244 // (void)_marker; 00245 // (void)_p; 00246 // (void)_r; 00247 // (void)_objectPtrs; 00248 // (void)_distances; 00249 // (void)_points; 00250 // return (0); 00251 //} 00252 00253 /************************************************************************** 00254 Method GetInBox. 00255 00256 Description: 00257 The GetInBox returns all the object in the specified bbox 00258 00259 Template Parameters: 00260 00261 OBJMARKER : The type of a marker functor. 00262 OBJPTRCONTAINER : The type of a object pointers container. 00263 00264 Method Parameters: 00265 _marker : [IN] Functor for marking objects already tested. 00266 _bbox : [IN] The bounding box of spatial query. 00267 _objectPtrs : [OUT] Container which, in return, will contain pointers to the closest objects. 00268 00269 00270 Return Value: 00271 The number of in-box objects found. 00272 00273 **************************************************************************/ 00274 template <class OBJMARKER, class OBJPTRCONTAINER> 00275 unsigned int GetInBox(OBJMARKER & _marker, const BoxType _bbox,OBJPTRCONTAINER & _objectPtrs) { 00276 assert(0); 00277 (void)_marker; 00278 (void)_bbox; 00279 (void)_objectPtrs; 00280 return (0); 00281 } 00282 00283 00284 00285 /************************************************************************** 00286 Method DoRay. 00287 00288 Description: 00289 The DoRay method finds the first object in the structure hit by a ray. 00290 00291 Template Parameters: 00292 OBJRAYISECTFUNCTOR : Object-Ray intersection functor type; 00293 this type must implement an operator () with signature 00294 bool operator () (const ObjType & obj, const Ray3<scalarType> ray, ScalarType & t) 00295 where: 00296 obj [IN] is a reference to the current object being tested, 00297 ray [IN] is the query ray, 00298 t [OUT] is the parameter of the ray equation at which intersection occurs. 00299 The operator returns true if the the object has been hit by the ray (i.e. they intersect). 00300 OBJMARKER : The type of a marker functor. 00301 00302 Method Parameters: 00303 _rayIntersector : [IN] Functor for object-ray intersection. 00304 _marker : [IN] Functor for marking objects already tested. 00305 _ray : [IN] The query ray. 00306 _maxDist : [IN] Maximum reject distance. 00307 _t : [OUT] the parameter of the ray equation at which intersection occurs. 00308 00309 Return Value: 00310 A pointer to the first object hit by the ray (if any). 00311 00312 **************************************************************************/ 00313 /*template <class OBJRAYISECTFUNCTOR, class OBJMARKER> 00314 ObjPtr DoRay(OBJRAYISECTFUNCTOR & _rayIntersector, OBJMARKER & _marker, const Ray3<ScalarType> & _ray, const ScalarType & _maxDist, ScalarType & _t) { 00315 assert(0); 00316 (void)_rayIntersector; 00317 (void)_marker; 00318 (void)_ray; 00319 (void)_maxDist; 00320 (void)_t; 00321 return ((ObjPtr)0); 00322 }*/ 00323 00324 }; 00325 00326 } // end namespace vcg 00327 00328 #endif // #ifndef __VCGLIB_SPATIALINDEX_H