base.h
Go to the documentation of this file.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 GetClosest. 00100 00101 Description: 00102 The GetClosest method finds the closest object given a point. 00103 It also finds the closest point and minimum distance. 00104 00105 Template Parameters: 00106 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 00107 this type must implement an operator () with signature 00108 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 00109 where: 00110 obj [IN] is a reference to the current object being tested, 00111 p [IN] is the query point, 00112 d [IN/OUT] is in input the reject distance and in output the closest distance, 00113 q [OUT] is the closest point. 00114 The operator returns true if the closest distance is less than input reject distance. 00115 OBJMARKER : The type of a marker functor. 00116 00117 Method Parameters: 00118 _getPointDistance : [IN] Functor for point-distance calculation. 00119 _marker : [IN] Functor for marking objects already tested. 00120 _p : [IN] The query point. 00121 _maxDist : [IN] Maximum reject distance. 00122 _minDist : [OUT] Closest distance. 00123 _closestPt : [OUT] Closest point. 00124 00125 Return Value: 00126 A pointer to the closest object (if any). 00127 00128 **************************************************************************/ 00129 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER> 00130 ObjPtr GetClosest( 00131 OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker, const CoordType & _p, const ScalarType & _maxDist, 00132 ScalarType & _minDist, CoordType & _closestPt) { 00133 assert(0); 00134 (void)_getPointDistance; 00135 (void)_marker; 00136 (void)_p; 00137 (void)_maxDist; 00138 (void)_minDist; 00139 (void)_closestPt; 00140 return ((ObjPtr)0); 00141 } 00142 00143 /************************************************************************** 00144 Method GetKClosest. 00145 00146 Description: 00147 The GetKClosest method finds the K closest object given a point. 00148 It also finds the closest points and minimum distances. 00149 00150 Template Parameters: 00151 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 00152 this type must implement an operator () with signature 00153 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 00154 where: 00155 obj [IN] is a reference to the current object being tested, 00156 p [IN] is the query point, 00157 d [IN/OUT] is in input the reject distance and in output the closest distance, 00158 q [OUT] is the closest point. 00159 The operator returns true if the closest distance is less than input reject distance. 00160 OBJMARKER : The type of a marker functor. 00161 OBJPTRCONTAINER : The type of a object pointers container. 00162 DISTCONTAINER : The type of a container which, in return, will contain the closest distances. 00163 POINTCONTAINER : The type of a container which, in return, will contain the closest points. 00164 00165 Method Parameters: 00166 _getPointDistance : [IN] Functor for point-distance calculation. 00167 _marker : [IN] Functor for marking objects already tested. 00168 _k : [IN] The number of closest objects to search for. 00169 _p : [IN] The query point. 00170 _maxDist : [IN] Maximum reject distance. 00171 _objectPtrs : [OUT] Container which, in return, will contain pointers to the closest objects. 00172 _distances : [OUT] Container which, in return, will contain the closest distances. 00173 _objectPtrs : [OUT] Container which, in return, will contain the closest points. 00174 00175 Return Value: 00176 The number of closest objects found. 00177 00178 **************************************************************************/ 00179 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER> 00180 unsigned int GetKClosest( 00181 OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker, const unsigned int _k, const CoordType & _p, const ScalarType & _maxDist, 00182 OBJPTRCONTAINER & _objectPtrs, DISTCONTAINER & _distances, POINTCONTAINER & _points) { 00183 assert(0); 00184 (void)_getPointDistance; 00185 (void)_marker; 00186 (void)_k; 00187 (void)_p; 00188 (void)_maxDist; 00189 (void)_objectPtrs; 00190 (void)_distances; 00191 (void)_points; 00192 return (0); 00193 } 00194 00195 00196 /************************************************************************** 00197 Method GetInSphere. 00198 00199 Description: 00200 The GetInSphere method finds all the objects in the specified sphere 00201 00202 Template Parameters: 00203 OBJPOINTDISTFUNCTOR : Object-Point distance functor type; 00204 this type must implement an operator () with signature 00205 bool operator () (const ObjType & obj, const CoordType & p, ScalarType & d, CoordType & q) 00206 where: 00207 obj [IN] is a reference to the current object being tested, 00208 p [IN] is the query point, 00209 d [IN/OUT] is in input the reject distance and in output the closest distance, 00210 q [OUT] is the closest point. 00211 The operator returns true if the closest distance is less than input reject distance. 00212 OBJMARKER : The type of a marker functor. 00213 OBJPTRCONTAINER : The type of a object pointers container. 00214 DISTCONTAINER : The type of a container which, in return, will contain the closest distances. 00215 POINTCONTAINER : The type of a container which, in return, will contain the closest points. 00216 00217 Method Parameters: 00218 _getPointDistance : [IN] Functor for point-distance calculation. 00219 _marker : [IN] Functor for marking objects already tested. 00220 _p : [IN] The query point. 00221 _r : [IN] The radius of the specified sphere. 00222 _objectPtrs : [OUT] Container which, in return, will contain pointers to the in-sphere objects. 00223 _distances : [OUT] Container which, in return, will contain the in-sphere distances. 00224 _objectPtrs : [OUT] Container which, in return, will contain the in-sphere nearests points for each object. 00225 00226 Return Value: 00227 The number of in-sphere objects found. 00228 00229 **************************************************************************/ 00230 template <class OBJPOINTDISTFUNCTOR, class OBJMARKER, class OBJPTRCONTAINER, class DISTCONTAINER, class POINTCONTAINER> 00231 unsigned int GetInSphere( 00232 OBJPOINTDISTFUNCTOR & _getPointDistance, OBJMARKER & _marker,const CoordType & _p, const ScalarType & _r,OBJPTRCONTAINER & _objectPtrs, DISTCONTAINER & _distances, POINTCONTAINER & _points) { 00233 assert(0); 00234 (void)_getPointDistance; 00235 (void)_marker; 00236 (void)_p; 00237 (void)_r; 00238 (void)_objectPtrs; 00239 (void)_distances; 00240 (void)_points; 00241 return (0); 00242 } 00243 00244 /************************************************************************** 00245 Method GetInBox. 00246 00247 Description: 00248 The GetInBox returns all the object in the specified bbox 00249 00250 Template Parameters: 00251 00252 OBJMARKER : The type of a marker functor. 00253 OBJPTRCONTAINER : The type of a object pointers container. 00254 00255 Method Parameters: 00256 _marker : [IN] Functor for marking objects already tested. 00257 _bbox : [IN] The bounding box of spatial query. 00258 _objectPtrs : [OUT] Container which, in return, will contain pointers to the closest objects. 00259 00260 00261 Return Value: 00262 The number of in-box objects found. 00263 00264 **************************************************************************/ 00265 template <class OBJMARKER, class OBJPTRCONTAINER> 00266 unsigned int GetInBox(OBJMARKER & _marker, const BoxType _bbox,OBJPTRCONTAINER & _objectPtrs) { 00267 assert(0); 00268 (void)_marker; 00269 (void)_bbox; 00270 (void)_objectPtrs; 00271 return (0); 00272 } 00273 00274 00275 00276 /************************************************************************** 00277 Method DoRay. 00278 00279 Description: 00280 The DoRay method finds the first object in the structure hit by a ray. 00281 00282 Template Parameters: 00283 OBJRAYISECTFUNCTOR : Object-Ray intersection functor type; 00284 this type must implement an operator () with signature 00285 bool operator () (const ObjType & obj, const Ray3<scalarType> ray, ScalarType & t) 00286 where: 00287 obj [IN] is a reference to the current object being tested, 00288 ray [IN] is the query ray, 00289 t [OUT] is the parameter of the ray equation at which intersection occurs. 00290 The operator returns true if the the object has been hit by the ray (i.e. they intersect). 00291 OBJMARKER : The type of a marker functor. 00292 00293 Method Parameters: 00294 _rayIntersector : [IN] Functor for object-ray intersection. 00295 _marker : [IN] Functor for marking objects already tested. 00296 _ray : [IN] The query ray. 00297 _maxDist : [IN] Maximum reject distance. 00298 _t : [OUT] the parameter of the ray equation at which intersection occurs. 00299 00300 Return Value: 00301 A pointer to the first object hit by the ray (if any). 00302 00303 **************************************************************************/ 00304 template <class OBJRAYISECTFUNCTOR, class OBJMARKER> 00305 ObjPtr DoRay(OBJRAYISECTFUNCTOR & _rayIntersector, OBJMARKER & _marker, const Ray3<ScalarType> & _ray, const ScalarType & _maxDist, ScalarType & _t) { 00306 assert(0); 00307 (void)_rayIntersector; 00308 (void)_marker; 00309 (void)_ray; 00310 (void)_maxDist; 00311 (void)_t; 00312 return ((ObjPtr)0); 00313 } 00314 00315 }; 00316 00317 } // end namespace vcg 00318 00319 #endif // #ifndef __VCGLIB_SPATIALINDEX_H