All Classes Namespaces Files Functions Variables Typedefs Pages
lq2d.h
Go to the documentation of this file.
1 
7 /*
8 // ----------------------------------------------------------------------------
9 // Copyright (c) 2002-2003, Sony Computer Entertainment America
10 // Original author: Craig Reynolds <craig_reynolds@playstation.sony.com>
11 //
12 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
13 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
14 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
15 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
16 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
17 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
18 // DEALINGS IN THE SOFTWARE.
19 //
20 // ----------------------------------------------------------------------------
21 */
22 
23 /* ------------------------------------------------------------------ */
24 /* */
25 /* Locality Query (LQ) Facility */
26 /* */
27 /* ------------------------------------------------------------------ */
28 /*
29 
30  This utility is a spatial database which stores objects each of
31  which is associated with a 2d point (a location in a 2d space).
32  The points serve as the "search key" for the associated object.
33  It is intended to efficiently answer "sphere inclusion" queries,
34  also known as range queries: basically questions like:
35 
36  Which objects are within a radius R of the location L?
37 
38  In this context, "efficiently" means significantly faster than the
39  naive, brute force O(n) testing of all known points. Additionally
40  it is assumed that the objects move along unpredictable paths, so
41  that extensive preprocessing (for example, constructing a Delaunay
42  triangulation of the point set) may not be practical.
43 
44  Overview of usage: an application using this facility would first
45  create a database with lqCreateDatabase. For each client object
46  the application wants to put in the database it creates a
47  lqClientProxy and initializes it with lqInitClientProxy. When a
48  client object moves, the application calls lqUpdateForNewLocation.
49  To perform a query lqMapOverAllObjectsInLocality is passed an
50  application-supplied call-back function to be applied to all
51  client objects in the locality. See lqCallBackFunction below for
52  more detail. The lqFindNearestNeighborWithinRadius function can
53  be used to find a single nearest neighbor using the database.
54 
55  Note that "locality query" is also known as neighborhood query,
56  neighborhood search, near neighbor search, and range query. For
57  additional information on this and related topics see:
58  http://www.red3d.com/cwr/boids/ips.html
59 
60 */
61 #ifndef _lq2D_h
62 #define _lq2D_h
63 
64 
65 /* ------------------------------------------------------------------ */
66 /* */
67 /* Data types use by LQ */
68 /* */
69 /* ------------------------------------------------------------------ */
70 /* ------------------------------------------------------------------ */
71 /* This structure is a proxy for (and contains a pointer to) a client
72  (application) object in the spatial database. One of these exists
73  for each client object. This might be included within the
74  structure of a client object, or could be allocated separately. */
75 
76 typedef struct lqClientProxy2D
77 {
78  /* previous object in this bin, or NULL */
79  struct lqClientProxy2D* prev;
80 
81  /* next object in this bin, or NULL */
82  struct lqClientProxy2D* next;
83 
84  /* bin ID (pointer to pointer to bin contents list) */
85  struct lqClientProxy2D** bin;
86 
87  /* pointer to client object */
88  void* object;
89 
90  /* the object's location ("key point") used for spatial sorting */
91  float x;
92  float y;
93 } lqClientProxy2D;
94 
95 
96 /* ------------------------------------------------------------------ */
97 /* This structure represents the spatial database. Typically one of
98  these would be created, by a call to lqCreateDatabase, for a given
99  application. */
100 
101 typedef struct lqInternalDB2D
102 {
103  /* the origin is the super-brick corner minimum coordinates */
104  float originx, originy;
105 
106  /* length of the edges of the super-brick */
107  float sizex, sizey;
108 
109  /* number of sub-brick divisions in each direction */
110  int divx, divy;
111 
112  /* pointer to an array of pointers, one for each bin */
113  lqClientProxy2D** bins;
114 
115  /* extra bin for "everything else" (points outside super-brick) */
116  lqClientProxy2D* other;
117 
118 } lqInternalDB2D;
119 
120 /* ------------------------------------------------------------------ */
121 /* */
122 /* Basic API */
123 /* */
124 /* ------------------------------------------------------------------ */
125 /* Allocate and initialize an LQ database, returns a pointer to it.
126  The application needs to call this before using the LQ facility.
127  The nine parameters define the properties of the "super-brick":
128  (1) origin: coordinates of one corner of the super-brick, its
129  minimum x, and y extent.
130  (2) size: the width, height and depth of the super-brick.
131  (3) the number of subdivisions (sub-bricks) along each axis.
132  This routine also allocates the bin array, and initialize its
133  contents. */
134 
135 
136 lqInternalDB2D* lqCreateDatabase2D (float originx, float originy,
137  float sizex, float sizey,
138  int divx, int divy);
139 
140 
141 /* ------------------------------------------------------------------ */
142 /* Deallocates the LQ database */
143 
144 
145 void lqDeleteDatabase2D (lqInternalDB2D*);
146 
147 
148 /* ------------------------------------------------------------------ */
149 /* The application needs to call this once on each lqClientProxy at
150  setup time to initialize its list pointers and associate the proxy
151  with its client object. */
152 
153 
154 void lqInitClientProxy2D (lqClientProxy2D* proxy, void* clientObject);
155 
156 
157 /* ------------------------------------------------------------------ */
158 /* Call for each client object every time its location changes. For
159  example, in an animation application, this would be called each
160  frame for every moving object. */
161 
162 
163 void lqUpdateForNewLocation (lqInternalDB2D* lq,
164  lqClientProxy2D* object,
165  float x, float y);
166 
167 
168 /* ------------------------------------------------------------------ */
169 /* Apply an application-specific function to all objects in a certain
170  locality. The locality is specified as a sphere with a given
171  center and radius. All objects whose location (key-point) is
172  within this sphere are identified and the function is applied to
173  them. The application-supplied function takes three arguments:
174 
175  (1) a void* pointer to an lqClientProxy's "object".
176  (2) the square of the distance from the center of the search
177  locality disc (x,y) to object's key-point.
178  (3) a void* pointer to the caller-supplied "client query state"
179  object -- typically NULL, but can be used to store state
180  between calls to the lqCallBackFunction.
181 
182  This routine uses the LQ database to quickly reject any objects in
183  bins which do not overlap with the sphere of interest. Incremental
184  calculation of index values is used to efficiently traverse the
185  bins of interest. */
186 
187 
188 /* type for a pointer to a function used to map over client objects */
189 typedef void (* lqCallBackFunction2D) (void* clientObject,
190  float distanceSquared,
191  void* clientQueryState);
192 
193 
194 void lqMapOverAllObjectsInLocality (lqInternalDB2D* lq,
195  float x, float y,
196  float dirx, float diry,
197  float radius,
198  bool restrictedView,
199  lqCallBackFunction2D func,
200  void* clientQueryState);
201 
202 /* Given a bin's list of client proxies, traverse the list and invoke
203  the given lqCallBackFunction on each object that falls within the
204  search radius. */
205 void lqTraverseBinClientObjectList(lqClientProxy2D* object,
206  float x, float y,
207  float dirx, float diry,
208  float radiusSquared,
209  bool restrictedView,
210  lqCallBackFunction2D func,
211  void* clientQueryState);
212 
213 
214 /* ------------------------------------------------------------------ */
215 /* */
216 /* Other API */
217 /* */
218 /* ------------------------------------------------------------------ */
219 /* Search the database to find the object whose key-point is nearest
220  to a given location yet within a given radius. That is, it finds
221  the object (if any) within a given search sphere which is nearest
222  to the sphere's center. The ignoreObject argument can be used to
223  exclude an object from consideration (or it can be NULL). This is
224  useful when looking for the nearest neighbor of an object in the
225  database, since otherwise it would be its own nearest neighbor.
226  The function returns a void* pointer to the nearest object, or
227  NULL if none is found. */
228 
229 
230 void* lqFindNearestNeighborWithinRadius (lqInternalDB2D* lq,
231  float x, float y,
232  float dirx, float diry,
233  float radius,
234  void* ignoreObject);
235 
236 
237 /* ------------------------------------------------------------------ */
238 /* Adds a given client object to a given bin, linking it into the bin
239  contents list. */
240 
241 
242 void lqAddToBin (lqClientProxy2D* object, lqClientProxy2D** bin);
243 
244 
245 /* ------------------------------------------------------------------ */
246 /* Removes a given client object from its current bin, unlinking it
247  from the bin contents list. */
248 
249 
250 void lqRemoveFromBin (lqClientProxy2D* object);
251 
252 
253 /* ------------------------------------------------------------------ */
254 /* Given an LQ database object and the nine basic parameters: fill in
255  the object's slots, allocate the bin array, and initialize its
256  contents. Normally the application does NOT call this directly, it
257  is called by lqCreateDatabase. */
258 
259 
260 void lqInitDatabase2D (lqInternalDB2D* lq,
261  float originx, float originy,
262  float sizex, float sizey,
263  int divx, int divy);
264 
265 
266 /* ------------------------------------------------------------------ */
267 /* Find the bin ID for a location in space. The location is given in
268  terms of its XYZ coordinates. The bin ID is a pointer to a pointer
269  to the bin contents list. */
270 
271 
272 lqClientProxy2D** lqBinForLocation2D (lqInternalDB2D* lq, float x, float y);
273 
274 /* ------------------------------------------------------------------ */
275 /* Apply a user-supplied function to all objects in the database,
276  regardless of locality (cf lqMapOverAllObjectsInLocality) */
277 
278 
279 void lqMapOverAllObjects (lqInternalDB2D* lq,
280  lqCallBackFunction2D func,
281  void* clientQueryState);
282 
283 
284 /* ------------------------------------------------------------------ */
285 /* Removes (all proxies for) all objects from all bins */
286 
287 
288 void lqRemoveAllObjects (lqInternalDB2D* lq);
289 
290 /* ------------------------------------------------------------------ */
291 
292 
293 #ifndef NULL
294 #define NULL 0
295 #endif
296 /* ------------------------------------------------------------------ */
297 
298 #endif /* _lq_h */