1 /**************************************************************************** 2 * VCGLib o o * 3 * Visual and Computer Graphics Library o o * 4 * _ O _ * 5 * Copyright(C) 2004-2016 \/)\/ * 6 * Visual Computing Lab /\/| * 7 * ISTI - Italian National Research Council | * 8 * \ * 9 * All rights reserved. * 10 * * 11 * This program is free software; you can redistribute it and/or modify * 12 * it under the terms of the GNU General Public License as published by * 13 * the Free Software Foundation; either version 2 of the License, or * 14 * (at your option) any later version. * 15 * * 16 * This program is distributed in the hope that it will be useful, * 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) * 20 * for more details. * 21 * * 22 ****************************************************************************/ 23 24 /**************************************************************************** 25 History 26 27 $Log: not supported by cvs2svn $ 28 Revision 1.1 2005/09/28 17:19:28 m_di_benedetto 29 First Commit. 30 31 32 ****************************************************************************/ 33 34 #ifndef __VCGLIB_SPATIALINDEX_H 35 #define __VCGLIB_SPATIALINDEX_H 36 37 // standard headers 38 #include <assert.h> 39 40 // vcg headers 41 #include <vcg/space/point3.h> 42 #include <vcg/space/ray3.h> 43 #include <vcg/space/box3.h> 44 45 namespace vcg { 46 47 /**************************************************************************** 48 Class SpatialIndex 49 50 Description: 51 This class exposes the base interface for all spatial indexing data 52 structures, i.e. grids, bounding volume trees. 53 54 Template Parameters: 55 OBJTYPE: Type of the indexed objects. 56 SCALARTYPE: Scalars type for structure's internal data (may differ from 57 object's scalar type). 58 59 ****************************************************************************/ 60 61 template <class OBJTYPE, class SCALARTYPE> 62 class SpatialIndex { 63 public: 64 /************************************************************************** 65 Commonly used typedefs. 66 **************************************************************************/ 67 typedef SpatialIndex<OBJTYPE, SCALARTYPE> ClassType; 68 typedef OBJTYPE ObjType; 69 typedef SCALARTYPE ScalarType; 70 typedef ObjType * ObjPtr; 71 typedef Point3<ScalarType> CoordType; 72 typedef vcg::Box3<ScalarType> BoxType; 73 74 /************************************************************************** 75 Method Set. 76 77 Description: 78 The Set method initializes the spatial structure. 79 80 Template Parameters: 81 OBJITER: Objects Container's iterator type. 82 83 Method Parameters: 84 _oBegin : [IN] begin objects container's iterator 85 _oEnd : [IN] end objects container's iterator 86 87 Return Value: 88 None. 89 90 **************************************************************************/ 91 template <class OBJITER> Set(const OBJITER & _oBegin,const OBJITER & _oEnd)92 void Set(const OBJITER & _oBegin, const OBJITER & _oEnd) { 93 assert(0); // this is a base interface. 94 (void)_oBegin; // avoid "unreferenced parameter" compiler warning. 95 (void)_oEnd; 96 } 97 98 /************************************************************************** 99 Method Empty. 100 Description: 101 check if the spatial structure is empty. 102 103 Return Value: 104 true if it is empty. 105 **************************************************************************/ 106 Empty()107 bool Empty() { 108 assert(0); // this is a base interface. 109 return true; 110 } 111 112 /************************************************************************** 113 Method GetClosest. 114 115 Description: 116 The GetClosest method finds the closest object given a point. 117 It also finds the closest point and minimum distance. 118 119 Template Parameters: 120 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 121 this type must implement an operator () with signature 122 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 123 where: 124 obj [IN] is a reference to the current object being tested, 125 p [IN] is the query point, 126 d [IN/OUT] is in input the reject distance and in output the closest distance, 127 q [OUT] is the closest point. 128 The operator returns true if the closest distance is less than input reject distance. 129 OBJMARKER : The type of a marker functor. 130 131 Method Parameters: 132 _getPointDistance : [IN] Functor for point-distance calculation. 133 _marker : [IN] Functor for marking objects already tested. 134 _p : [IN] The query point. 135 _maxDist : [IN] Maximum reject distance. 136 _minDist : [OUT] Closest distance. 137 _closestPt : [OUT] Closest point. 138 139 Return Value: 140 A pointer to the closest object (if any). 141 142 **************************************************************************/ 143 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER> GetClosest(OBJPOINTDISTFUNCTOR & _getPointDistance,OBJMARKER & _marker,const CoordType & _p,const ScalarType & _maxDist,ScalarType & _minDist,CoordType & _closestPt)144 ObjPtr GetClosest( 145 OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker, const CoordType & _p, const ScalarType & _maxDist, 146 ScalarType & _minDist, CoordType & _closestPt) { 147 assert(0); 148 (void)_getPointDistance; 149 (void)_marker; 150 (void)_p; 151 (void)_maxDist; 152 (void)_minDist; 153 (void)_closestPt; 154 return ((ObjPtr)0); 155 } 156 157 /************************************************************************** 158 Method GetKClosest. 159 160 Description: 161 The GetKClosest method finds the K closest object given a point. 162 It also finds the closest points and minimum distances. 163 164 Template Parameters: 165 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 166 this type must implement an operator () with signature 167 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 168 where: 169 obj [IN] is a reference to the current object being tested, 170 p [IN] is the query point, 171 d [IN/OUT] is in input the reject distance and in output the closest distance, 172 q [OUT] is the closest point. 173 The operator returns true if the closest distance is less than input reject distance. 174 OBJMARKER : The type of a marker functor. 175 OBJPTRCONTAINER : The type of a object pointers container. 176 DISTCONTAINER : The type of a container which, in return, will contain the closest distances. 177 POINTCONTAINER : The type of a container which, in return, will contain the closest points. 178 179 Method Parameters: 180 _getPointDistance : [IN] Functor for point-distance calculation. 181 _marker : [IN] Functor for marking objects already tested. 182 _k : [IN] The number of closest objects to search for. 183 _p : [IN] The query point. 184 _maxDist : [IN] Maximum reject distance. 185 _objectPtrs : [OUT] Container which, in return, will contain pointers to the closest objects. 186 _distances : [OUT] Container which, in return, will contain the closest distances. 187 _objectPtrs : [OUT] Container which, in return, will contain the closest points. 188 189 Return Value: 190 The number of closest objects found. 191 192 **************************************************************************/ 193 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER> GetKClosest(OBJPOINTDISTFUNCTOR & _getPointDistance,OBJMARKER & _marker,const unsigned int _k,const CoordType & _p,const ScalarType & _maxDist,OBJPTRCONTAINER & _objectPtrs,DISTCONTAINER & _distances,POINTCONTAINER & _points)194 unsigned int GetKClosest( 195 OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker, const unsigned int _k, const CoordType & _p, const ScalarType & _maxDist, 196 OBJPTRCONTAINER & _objectPtrs, DISTCONTAINER & _distances, POINTCONTAINER & _points) { 197 assert(0); 198 (void)_getPointDistance; 199 (void)_marker; 200 (void)_k; 201 (void)_p; 202 (void)_maxDist; 203 (void)_objectPtrs; 204 (void)_distances; 205 (void)_points; 206 return (0); 207 } 208 209 210 /************************************************************************** 211 Method GetInSphere. 212 213 Description: 214 The GetInSphere method finds all the objects in the specified sphere 215 216 Template Parameters: 217 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 218 this type must implement an operator () with signature 219 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 220 where: 221 obj [IN] is a reference to the current object being tested, 222 p [IN] is the query point, 223 d [IN/OUT] is in input the reject distance and in output the closest distance, 224 q [OUT] is the closest point. 225 The operator returns true if the closest distance is less than input reject distance. 226 OBJMARKER : The type of a marker functor. 227 OBJPTRCONTAINER : The type of a object pointers container. 228 DISTCONTAINER : The type of a container which, in return, will contain the closest distances. 229 POINTCONTAINER : The type of a container which, in return, will contain the closest points. 230 231 Method Parameters: 232 _getPointDistance : [IN] Functor for point-distance calculation. 233 _marker : [IN] Functor for marking objects already tested. 234 _p : [IN] The query point. 235 _r : [IN] The radius of the specified sphere. 236 _objectPtrs : [OUT] Container which, in return, will contain pointers to the in-sphere objects. 237 _distances : [OUT] Container which, in return, will contain the in-sphere distances. 238 _objectPtrs : [OUT] Container which, in return, will contain the in-sphere nearests points for each object. 239 240 Return Value: 241 The number of in-sphere objects found. 242 243 **************************************************************************/ 244 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER> GetInSphere(OBJPOINTDISTFUNCTOR & _getPointDistance,OBJMARKER & _marker,const CoordType & _p,const ScalarType & _r,OBJPTRCONTAINER & _objectPtrs,DISTCONTAINER & _distances,POINTCONTAINER & _points)245 unsigned int GetInSphere( 246 OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker,const CoordType & _p, const ScalarType & _r,OBJPTRCONTAINER & _objectPtrs, DISTCONTAINER & _distances, POINTCONTAINER & _points) { 247 assert(0); 248 (void)_getPointDistance; 249 (void)_marker; 250 (void)_p; 251 (void)_r; 252 (void)_objectPtrs; 253 (void)_distances; 254 (void)_points; 255 return (0); 256 } 257 258 /************************************************************************** 259 Method GetInBox. 260 261 Description: 262 The GetInBox returns all the object in the specified bbox 263 264 Template Parameters: 265 266 OBJMARKER : The type of a marker functor. 267 OBJPTRCONTAINER : The type of a object pointers container. 268 269 Method Parameters: 270 _marker : [IN] Functor for marking objects already tested. 271 _bbox : [IN] The bounding box of spatial query. 272 _objectPtrs : [OUT] Container which, in return, will contain pointers to the closest objects. 273 274 275 Return Value: 276 The number of in-box objects found. 277 278 **************************************************************************/ 279 template <class OBJMARKER, class OBJPTRCONTAINER> GetInBox(OBJMARKER & _marker,const BoxType _bbox,OBJPTRCONTAINER & _objectPtrs)280 unsigned int GetInBox(OBJMARKER & _marker, const BoxType _bbox,OBJPTRCONTAINER & _objectPtrs) { 281 assert(0); 282 (void)_marker; 283 (void)_bbox; 284 (void)_objectPtrs; 285 return (0); 286 } 287 288 289 290 /************************************************************************** 291 Method DoRay. 292 293 Description: 294 The DoRay method finds the first object in the structure hit by a ray. 295 296 Template Parameters: 297 OBJRAYISECTFUNCTOR : Object-Ray intersection functor type; 298 this type must implement an operator () with signature 299 bool operator () (const ObjType & obj, const Ray3<scalarType> ray, ScalarType & t) 300 where: 301 obj [IN] is a reference to the current object being tested, 302 ray [IN] is the query ray, 303 t [OUT] is the parameter of the ray equation at which intersection occurs. 304 The operator returns true if the the object has been hit by the ray (i.e. they intersect). 305 OBJMARKER : The type of a marker functor. 306 307 Method Parameters: 308 _rayIntersector : [IN] Functor for object-ray intersection. 309 _marker : [IN] Functor for marking objects already tested. 310 _ray : [IN] The query ray. 311 _maxDist : [IN] Maximum reject distance. 312 _t : [OUT] the parameter of the ray equation at which intersection occurs. 313 314 Return Value: 315 A pointer to the first object hit by the ray (if any). 316 317 **************************************************************************/ 318 template <class OBJRAYISECTFUNCTOR, class OBJMARKER> DoRay(OBJRAYISECTFUNCTOR & _rayIntersector,OBJMARKER & _marker,const Ray3<ScalarType> & _ray,const ScalarType & _maxDist,ScalarType & _t)319 ObjPtr DoRay(OBJRAYISECTFUNCTOR & _rayIntersector, OBJMARKER & _marker, const Ray3<ScalarType> & _ray, const ScalarType & _maxDist, ScalarType & _t) { 320 assert(0); 321 (void)_rayIntersector; 322 (void)_marker; 323 (void)_ray; 324 (void)_maxDist; 325 (void)_t; 326 return ((ObjPtr)0); 327 } 328 329 }; 330 331 } // end namespace vcg 332 333 #endif // #ifndef __VCGLIB_SPATIALINDEX_H 334