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