Branch data Line data Source code
1 : : /*
2 : : * Copyright (C) 2022 James Westman <james@jwestman.net>
3 : : *
4 : : * This library is free software; you can redistribute it and/or
5 : : * modify it under the terms of the GNU Lesser General Public
6 : : * License as published by the Free Software Foundation; either
7 : : * version 2.1 of the License, or (at your option) any later version.
8 : : *
9 : : * This library is distributed in the hope that it will be useful,
10 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 : : * Lesser General Public License for more details.
13 : : *
14 : : * You should have received a copy of the GNU Lesser General Public
15 : : * License along with this library; if not, see <https://www.gnu.org/licenses/>.
16 : : */
17 : :
18 : : /* This is a simple implementation of an R-tree, used to detect overlapping
19 : : * markers. An R-tree is a spatial data structure which stores nodes by their
20 : : * bounding boxes. There are lots of fancy heuristics for R-trees to efficiently
21 : : * insert new nodes into the tree, but this implementation uses a fixed
22 : : * structure for simplicity.
23 : : *
24 : : * See <https://en.wikipedia.org/wiki/R-tree>. */
25 : :
26 : : #include <math.h>
27 : :
28 : : #include "shumate-vector-collision-private.h"
29 : :
30 : : #define NODES 4
31 : : /* Doesn't need to match the actual tile size */
32 : : #define BUCKET_SIZE 256
33 : :
34 : : #define LEN_SQ(x, y) (x*x + y*y)
35 : : #define MAX4(a, b, c, d) (MAX (MAX (a, b), MAX (c, d)))
36 : : #define MIN4(a, b, c, d) (MIN (MIN (a, b), MIN (c, d)))
37 : :
38 : : #define EMPTY_BOX ((Box){0, 0, 0, 0, 0, 0, 0})
39 : :
40 : : typedef struct {
41 : : gpointer tag;
42 : : double x;
43 : : double y;
44 : : double xextent;
45 : : double yextent;
46 : : double rotation;
47 : : double aaxextent;
48 : : double aayextent;
49 : : uint8_t overlap_never : 1;
50 : : } Box;
51 : :
52 : : typedef struct {
53 : : GArray *boxes;
54 : : Box bbox;
55 : : } RTreeCol;
56 : :
57 : : typedef struct {
58 : : RTreeCol cols[NODES];
59 : : Box bbox;
60 : : } RTreeRow;
61 : :
62 : : typedef struct {
63 : : RTreeRow rows[NODES];
64 : : Box bbox;
65 : : int n_boxes;
66 : : } RTreeBucketCol;
67 : :
68 : : typedef struct {
69 : : GHashTable *bucket_cols;
70 : : GPtrArray *bucket_cols_array;
71 : : Box bbox;
72 : : } RTreeBucketRow;
73 : :
74 : :
75 : : static RTreeBucketCol *
76 : 0 : bucket_col_new ()
77 : : {
78 : 0 : RTreeBucketCol *bucket_col = g_new0 (RTreeBucketCol, 1);
79 : 0 : bucket_col->bbox = EMPTY_BOX;
80 : 0 : return bucket_col;
81 : : }
82 : :
83 : :
84 : : static void
85 : 0 : bucket_col_free (RTreeBucketCol *tile_col)
86 : : {
87 [ # # ]: 0 : for (int x = 0; x < NODES; x ++)
88 [ # # ]: 0 : for (int y = 0; y < NODES; y ++)
89 [ # # ]: 0 : g_clear_pointer (&tile_col->rows[y].cols[x].boxes, g_array_unref);
90 : :
91 : 0 : g_free (tile_col);
92 : 0 : }
93 : :
94 : :
95 : : static RTreeBucketRow *
96 : 0 : bucket_row_new ()
97 : : {
98 : 0 : RTreeBucketRow *bucket_row = g_new0 (RTreeBucketRow, 1);
99 : 0 : bucket_row->bucket_cols = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, (GDestroyNotify) bucket_col_free);
100 : 0 : bucket_row->bucket_cols_array = g_ptr_array_new ();
101 : 0 : bucket_row->bbox = EMPTY_BOX;
102 : 0 : return bucket_row;
103 : : }
104 : :
105 : :
106 : : static void
107 : 0 : bucket_row_free (RTreeBucketRow *bucket_row)
108 : : {
109 : 0 : g_hash_table_unref (bucket_row->bucket_cols);
110 : 0 : g_ptr_array_unref (bucket_row->bucket_cols_array);
111 : 0 : g_free (bucket_row);
112 : 0 : }
113 : :
114 : :
115 : : ShumateVectorCollision *
116 : 0 : shumate_vector_collision_new ()
117 : : {
118 : 0 : ShumateVectorCollision *self = g_new0 (ShumateVectorCollision, 1);
119 : :
120 : 0 : self->bucket_rows = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, (GDestroyNotify) bucket_row_free);
121 : 0 : self->bucket_rows_array = g_ptr_array_new ();
122 : 0 : self->pending_boxes = g_array_new (FALSE, FALSE, sizeof (Box));
123 : :
124 : 0 : return self;
125 : : }
126 : :
127 : :
128 : : void
129 : 0 : shumate_vector_collision_free (ShumateVectorCollision *self)
130 : : {
131 : 0 : g_hash_table_unref (self->bucket_rows);
132 : 0 : g_array_unref (self->pending_boxes);
133 : 0 : g_ptr_array_unref (self->bucket_rows_array);
134 : 0 : g_free (self);
135 : 0 : }
136 : :
137 : :
138 : : static double
139 : 0 : dot (ShumateVectorPoint *a,
140 : : ShumateVectorPoint *b)
141 : : {
142 : 0 : return a->x * b->x + a->y * b->y;
143 : : }
144 : :
145 : :
146 : : static double
147 : 0 : project (ShumateVectorPoint *point,
148 : : ShumateVectorPoint *axis)
149 : : {
150 : 0 : ShumateVectorPoint tmp;
151 : 0 : double s = dot (point, axis) / LEN_SQ (axis->x, axis->y);
152 : 0 : tmp = *axis;
153 : 0 : tmp.x *= s;
154 : 0 : tmp.y *= s;
155 : 0 : return dot (&tmp, axis);
156 : : }
157 : :
158 : :
159 : : static ShumateVectorPoint
160 : 0 : corner (double x,
161 : : double y,
162 : : double xextent,
163 : : double yextent,
164 : : double rot_cos,
165 : : double rot_sin)
166 : : {
167 : 0 : return (ShumateVectorPoint) {
168 : 0 : .x = xextent * rot_cos - yextent * rot_sin + x,
169 : 0 : .y = xextent * rot_sin + yextent * rot_cos + y,
170 : : };
171 : : }
172 : :
173 : :
174 : : static gboolean
175 : 0 : rects_intersect_aa (Box *a,
176 : : Box *b)
177 : : {
178 : : /* Test whether the boxes' axis-aligned bounding boxes intersect. */
179 [ # # ]: 0 : return !((a->x + a->aaxextent < b->x - b->aaxextent)
180 [ # # ]: 0 : || (b->x + b->aaxextent < a->x - a->aaxextent)
181 [ # # ]: 0 : || (a->y + a->aayextent < b->y - b->aayextent)
182 [ # # ]: 0 : || (b->y + b->aayextent < a->y - a->aayextent));
183 : : }
184 : :
185 : :
186 : : static gboolean
187 : 0 : rects_intersect (Box *a,
188 : : Box *b)
189 : : {
190 : 0 : double cos_a, sin_a, cos_b, sin_b;
191 : 0 : ShumateVectorPoint axes[4], corners_a[4], corners_b[4];
192 : :
193 [ # # ]: 0 : if (!rects_intersect_aa (a, b))
194 : : return FALSE;
195 : :
196 [ # # # # ]: 0 : if (a->rotation == 0 && b->rotation == 0)
197 : : {
198 : : /* If both boxes' rotation is 0, then rects_intersect_aa is equivalent
199 : : to rects_intersect and would have returned FALSE already */
200 : : return TRUE;
201 : : }
202 : :
203 : : /* See <https://www.gamedev.net/articles/programming/general-and-gameplay-programming/2d-rotated-rectangle-collision-r2604/> */
204 : :
205 : 0 : cos_a = cosf (a->rotation);
206 : 0 : sin_a = sinf (a->rotation);
207 : 0 : cos_b = cosf (b->rotation);
208 : 0 : sin_b = sinf (b->rotation);
209 : :
210 : : /* Calculate the four axes of the two rectangles */
211 : 0 : axes[0] = (ShumateVectorPoint) { cos_a, sin_a };
212 : 0 : axes[1] = (ShumateVectorPoint) { -sin_a, cos_a };
213 : 0 : axes[2] = (ShumateVectorPoint) { cos_b, sin_b };
214 : 0 : axes[3] = (ShumateVectorPoint) { -sin_b, cos_b };
215 : :
216 : 0 : corners_a[0] = corner (a->x, a->y, a->xextent, a->yextent, cos_a, sin_a);
217 : 0 : corners_a[1] = corner (a->x, a->y, -a->xextent, a->yextent, cos_a, sin_a);
218 : 0 : corners_a[2] = corner (a->x, a->y, a->xextent, -a->yextent, cos_a, sin_a);
219 : 0 : corners_a[3] = corner (a->x, a->y, -a->xextent, -a->yextent, cos_a, sin_a);
220 : :
221 : 0 : corners_b[0] = corner (b->x, b->y, b->xextent, b->yextent, cos_b, sin_b);
222 : 0 : corners_b[1] = corner (b->x, b->y, -b->xextent, b->yextent, cos_b, sin_b);
223 : 0 : corners_b[2] = corner (b->x, b->y, b->xextent, -b->yextent, cos_b, sin_b);
224 : 0 : corners_b[3] = corner (b->x, b->y, -b->xextent, -b->yextent, cos_b, sin_b);
225 : :
226 [ # # ]: 0 : for (int i = 0; i < 4; i ++)
227 : : {
228 : 0 : ShumateVectorPoint *axis = &axes[i];
229 : :
230 : 0 : double proj_a[4], proj_b[4];
231 : :
232 : : /* Project the corners of the rectangles onto the axis */
233 [ # # ]: 0 : for (int j = 0; j < 4; j ++)
234 : : {
235 : 0 : proj_a[j] = project (&corners_a[j], axis);
236 : 0 : proj_b[j] = project (&corners_b[j], axis);
237 : : }
238 : :
239 : : /* If the projected points don't overlap, the rectangles don't overlap
240 : : * (i.e. either every item in proj_a is greater than or is less than every
241 : : * item in proj_b). */
242 [ # # # # : 0 : double min_a = MIN4 (proj_a[0], proj_a[1], proj_a[2], proj_a[3]);
# # ]
243 [ # # # # : 0 : double max_a = MAX4 (proj_a[0], proj_a[1], proj_a[2], proj_a[3]);
# # ]
244 [ # # # # : 0 : double min_b = MIN4 (proj_b[0], proj_b[1], proj_b[2], proj_b[3]);
# # ]
245 [ # # # # : 0 : double max_b = MAX4 (proj_b[0], proj_b[1], proj_b[2], proj_b[3]);
# # ]
246 : :
247 [ # # # # ]: 0 : if (min_a >= max_b || min_b >= max_a)
248 : 0 : return FALSE;
249 : : }
250 : :
251 : : return TRUE;
252 : : }
253 : :
254 : :
255 : : static void
256 : 0 : expand_rect (Box *a,
257 : : const Box *b)
258 : : {
259 [ # # # # : 0 : if (a->x == 0 && a->y == 0 && a->xextent == 0 && a->yextent == 0)
# # # # ]
260 : 0 : *a = *b;
261 : : else
262 : : {
263 [ # # ]: 0 : double left = MIN (a->x - a->aaxextent, b->x - b->aaxextent);
264 [ # # ]: 0 : double right = MAX (a->x + a->aaxextent, b->x + b->aaxextent);
265 [ # # ]: 0 : double top = MIN (a->y - a->aayextent, b->y - b->aayextent);
266 [ # # ]: 0 : double bottom = MAX (a->y + a->aayextent, b->y + b->aayextent);
267 : 0 : a->x = (left + right) / 2.0;
268 : 0 : a->y = (top + bottom) / 2.0;
269 : 0 : a->xextent = (right - left) / 2.0;
270 : 0 : a->yextent = (bottom - top) / 2.0;
271 : 0 : a->aaxextent = a->xextent;
272 : 0 : a->aayextent = a->yextent;
273 : : }
274 : 0 : }
275 : :
276 : :
277 : : static void
278 : 0 : axis_align (Box *box)
279 : : {
280 [ # # ]: 0 : if (box->rotation == 0)
281 : : {
282 : 0 : box->aaxextent = box->xextent;
283 : 0 : box->aayextent = box->yextent;
284 : : }
285 : : else
286 : : {
287 [ # # # # : 0 : box->aaxextent = MAX (
# # ]
288 : : ABS (cos (box->rotation) * box->xextent - sin (box->rotation) * box->yextent),
289 : : ABS (cos (box->rotation) * -box->xextent - sin (box->rotation) * box->yextent)
290 : : );
291 [ # # # # : 0 : box->aayextent = MAX (
# # ]
292 : : ABS (sin (box->rotation) * box->xextent + cos (box->rotation) * box->yextent),
293 : : ABS (sin (box->rotation) * -box->xextent + cos (box->rotation) * box->yextent)
294 : : );
295 : : }
296 : 0 : }
297 : :
298 : :
299 : : static int
300 : 0 : positive_mod (int i, int n)
301 : : {
302 : 0 : return (i % n + n) % n;
303 : : }
304 : :
305 : :
306 : : static int
307 : 0 : row_for_position (double coordinate)
308 : : {
309 : 0 : return positive_mod (coordinate, BUCKET_SIZE) * NODES / BUCKET_SIZE;
310 : : }
311 : :
312 : :
313 : : static gboolean
314 : 0 : detect_collision (ShumateVectorCollision *self,
315 : : Box *bbox)
316 : : {
317 [ # # ]: 0 : for (int i = 0; i < self->bucket_rows_array->len; i ++)
318 : : {
319 : 0 : RTreeBucketRow *bucket_row = g_ptr_array_index (self->bucket_rows_array, i);
320 : :
321 [ # # ]: 0 : if (!rects_intersect_aa (bbox, &bucket_row->bbox))
322 : 0 : continue;
323 : :
324 [ # # ]: 0 : for (int j = 0; j < bucket_row->bucket_cols_array->len; j ++)
325 : : {
326 : 0 : RTreeBucketCol *bucket_col = g_ptr_array_index (bucket_row->bucket_cols_array, j);
327 : :
328 [ # # ]: 0 : if (bucket_col->n_boxes == 0)
329 : 0 : continue;
330 : :
331 [ # # ]: 0 : if (!rects_intersect_aa (bbox, &bucket_col->bbox))
332 : 0 : continue;
333 : :
334 [ # # ]: 0 : for (int y = 0; y < NODES; y ++)
335 : : {
336 : 0 : RTreeRow *row = &bucket_col->rows[y];
337 : :
338 [ # # ]: 0 : if (!rects_intersect_aa (bbox, &row->bbox))
339 : 0 : continue;
340 : :
341 [ # # ]: 0 : for (int x = 0; x < NODES; x ++)
342 : : {
343 : 0 : RTreeCol *col = &row->cols[x];
344 : :
345 [ # # # # ]: 0 : if (col->boxes == NULL || !rects_intersect_aa (bbox, &col->bbox))
346 : 0 : continue;
347 : :
348 [ # # ]: 0 : for (int i = 0; i < col->boxes->len; i ++)
349 : : {
350 : 0 : Box *b = &((Box*)col->boxes->data)[i];
351 : :
352 [ # # # # ]: 0 : if (b->overlap_never || bbox->overlap_never)
353 : : {
354 [ # # ]: 0 : if (rects_intersect (bbox, b))
355 : : return TRUE;
356 : : }
357 : : }
358 : : }
359 : : }
360 : : }
361 : : }
362 : :
363 : : return FALSE;
364 : : }
365 : :
366 : :
367 : : gboolean
368 : 0 : shumate_vector_collision_check (ShumateVectorCollision *self,
369 : : double x,
370 : : double y,
371 : : double xextent,
372 : : double yextent,
373 : : double rotation,
374 : : ShumateVectorOverlap overlap,
375 : : gboolean ignore_placement,
376 : : gpointer tag)
377 : : {
378 : 0 : Box new_bbox = {
379 : : tag, x, y, xextent, yextent, rotation,
380 : 0 : .overlap_never = overlap == SHUMATE_VECTOR_OVERLAP_NEVER
381 : : };
382 : :
383 : 0 : axis_align (&new_bbox);
384 : :
385 [ # # ]: 0 : if (overlap != SHUMATE_VECTOR_OVERLAP_ALWAYS)
386 : : {
387 [ # # ]: 0 : if (detect_collision (self, &new_bbox))
388 : : return FALSE;
389 : : }
390 : :
391 [ # # ]: 0 : if (!ignore_placement)
392 : 0 : g_array_append_val (self->pending_boxes, new_bbox);
393 : :
394 : : return TRUE;
395 : : }
396 : :
397 : : int
398 : 0 : shumate_vector_collision_save_pending (ShumateVectorCollision *self)
399 : : {
400 : 0 : return self->pending_boxes->len;
401 : : }
402 : :
403 : : void
404 : 0 : shumate_vector_collision_rollback_pending (ShumateVectorCollision *self,
405 : : int save)
406 : : {
407 : 0 : g_array_set_size (self->pending_boxes, save);
408 : 0 : }
409 : :
410 : : void
411 : 0 : shumate_vector_collision_commit_pending (ShumateVectorCollision *self,
412 : : graphene_rect_t *bounds_out)
413 : : {
414 : 0 : int i;
415 : :
416 [ # # ]: 0 : for (i = 0; i < self->pending_boxes->len; i ++)
417 : : {
418 : 0 : Box bbox = g_array_index (self->pending_boxes, Box, i);
419 : 0 : RTreeBucketRow *bucket_row;
420 : 0 : RTreeBucketCol *bucket_col;
421 : 0 : RTreeRow *row;
422 : 0 : RTreeCol *col;
423 : 0 : gsize bucket_x = floor (bbox.x / BUCKET_SIZE);
424 : 0 : gsize bucket_y = floor (bbox.y / BUCKET_SIZE);
425 : 0 : graphene_rect_t bounds;
426 : :
427 : 0 : bucket_row = g_hash_table_lookup (self->bucket_rows, (gpointer) bucket_y);
428 [ # # ]: 0 : if (bucket_row == NULL)
429 : : {
430 : 0 : bucket_row = bucket_row_new ();
431 : 0 : g_hash_table_insert (self->bucket_rows, (gpointer) bucket_y, bucket_row);
432 : 0 : g_ptr_array_add (self->bucket_rows_array, bucket_row);
433 : : }
434 : :
435 : 0 : bucket_col = g_hash_table_lookup (bucket_row->bucket_cols, (gpointer) bucket_x);
436 [ # # ]: 0 : if (bucket_col == NULL)
437 : : {
438 : 0 : bucket_col = bucket_col_new ();
439 : 0 : g_hash_table_insert (bucket_row->bucket_cols, (gpointer) bucket_x, bucket_col);
440 : 0 : g_ptr_array_add (bucket_row->bucket_cols_array, bucket_col);
441 : : }
442 : :
443 : 0 : row = &bucket_col->rows[row_for_position (bbox.y)];
444 : 0 : col = &row->cols[row_for_position (bbox.x)];
445 : :
446 [ # # ]: 0 : if (col->boxes == NULL)
447 : 0 : col->boxes = g_array_new (FALSE, FALSE, sizeof (Box));
448 : 0 : g_array_append_val (col->boxes, bbox);
449 : :
450 : 0 : bucket_col->n_boxes ++;
451 : :
452 : : /* Expand the parents to fit the new marker */
453 : 0 : expand_rect (&bucket_row->bbox, &bbox);
454 : 0 : expand_rect (&bucket_col->bbox, &bbox);
455 : 0 : expand_rect (&row->bbox, &bbox);
456 : 0 : expand_rect (&col->bbox, &bbox);
457 : :
458 : 0 : bounds = GRAPHENE_RECT_INIT (bbox.x - bbox.aaxextent,
459 : : bbox.y - bbox.aayextent,
460 : : bbox.aaxextent * 2,
461 : : bbox.aayextent * 2);
462 [ # # ]: 0 : if (i == 0)
463 : 0 : *bounds_out = bounds;
464 : : else
465 : 0 : graphene_rect_union (bounds_out, &bounds, bounds_out);
466 : : }
467 : :
468 : : /* clear the pending boxes */
469 : 0 : g_array_set_size (self->pending_boxes, 0);
470 : 0 : }
471 : :
472 : :
473 : : static gboolean
474 : 0 : point_intersects_rect_aa (Box *box,
475 : : double x,
476 : : double y)
477 : : {
478 : 0 : return (x >= box->x - box->aaxextent &&
479 [ # # ]: 0 : x <= box->x + box->aaxextent &&
480 [ # # # # ]: 0 : y >= box->y - box->aayextent &&
481 [ # # ]: 0 : y <= box->y + box->aayextent);
482 : : }
483 : :
484 : :
485 : : static gboolean
486 : 0 : point_intersects_rect (Box *box,
487 : : double x,
488 : : double y)
489 : : {
490 : 0 : double x2, y2;
491 : 0 : x -= box->x;
492 : 0 : y -= box->y;
493 : :
494 : 0 : x2 = cosf (-box->rotation) * x - sinf (-box->rotation) * y;
495 : 0 : y2 = sinf (-box->rotation) * x + cosf (-box->rotation) * y;
496 : :
497 [ # # ]: 0 : return (x2 >= -box->xextent &&
498 : 0 : x2 <= box->xextent &&
499 [ # # # # : 0 : y2 >= -box->yextent &&
# # ]
500 : : y2 <= box->yextent);
501 : : }
502 : :
503 : :
504 : : gboolean
505 : 0 : shumate_vector_collision_query_point (ShumateVectorCollision *self,
506 : : double x,
507 : : double y,
508 : : gpointer tag)
509 : : {
510 [ # # ]: 0 : for (int i = 0; i < self->bucket_rows_array->len; i ++)
511 : : {
512 : 0 : RTreeBucketRow *bucket_row = g_ptr_array_index (self->bucket_rows_array, i);
513 : :
514 [ # # ]: 0 : if (!point_intersects_rect_aa (&bucket_row->bbox, x, y))
515 : 0 : continue;
516 : :
517 [ # # ]: 0 : for (int j = 0; j < bucket_row->bucket_cols_array->len; j ++)
518 : : {
519 : 0 : RTreeBucketCol *bucket_col = g_ptr_array_index (bucket_row->bucket_cols_array, j);
520 : :
521 [ # # ]: 0 : if (bucket_col->n_boxes == 0)
522 : 0 : continue;
523 : :
524 [ # # ]: 0 : if (!point_intersects_rect_aa (&bucket_col->bbox, x, y))
525 : 0 : continue;
526 : :
527 [ # # ]: 0 : for (int r = 0; r < NODES; r ++)
528 : : {
529 : 0 : RTreeRow *row = &bucket_col->rows[r];
530 : :
531 [ # # ]: 0 : if (!point_intersects_rect_aa (&row->bbox, x, y))
532 : 0 : continue;
533 : :
534 [ # # ]: 0 : for (int c = 0; c < NODES; c ++)
535 : : {
536 : 0 : RTreeCol *col = &row->cols[c];
537 : :
538 [ # # # # ]: 0 : if (col->boxes == NULL || !point_intersects_rect_aa (&col->bbox, x, y))
539 : 0 : continue;
540 : :
541 [ # # ]: 0 : for (int i = 0; i < col->boxes->len; i ++)
542 : : {
543 : 0 : Box *b = &((Box*)col->boxes->data)[i];
544 : :
545 [ # # # # : 0 : if (point_intersects_rect (b, x, y) && (tag == NULL || tag == b->tag))
# # ]
546 : : return TRUE;
547 : : }
548 : : }
549 : : }
550 : : }
551 : : }
552 : :
553 : : return FALSE;
554 : : }
555 : :
556 : :
557 : : void
558 : 0 : shumate_vector_collision_clear (ShumateVectorCollision *self)
559 : : {
560 : 0 : GHashTableIter bucket_rows;
561 : 0 : RTreeBucketRow *bucket_row;
562 : :
563 : 0 : g_hash_table_iter_init (&bucket_rows, self->bucket_rows);
564 : :
565 [ # # ]: 0 : while (g_hash_table_iter_next (&bucket_rows, NULL, (gpointer*) &bucket_row))
566 : : {
567 : 0 : GHashTableIter bucket_cols;
568 : 0 : RTreeBucketCol *bucket_col;
569 : :
570 : 0 : bucket_row->bbox = EMPTY_BOX;
571 : :
572 : 0 : g_hash_table_iter_init (&bucket_cols, bucket_row->bucket_cols);
573 : :
574 [ # # ]: 0 : while (g_hash_table_iter_next (&bucket_cols, NULL, (gpointer*) &bucket_col))
575 : : {
576 [ # # ]: 0 : if (bucket_col->n_boxes == 0)
577 : : {
578 : 0 : g_ptr_array_remove_fast (bucket_row->bucket_cols_array, bucket_col);
579 : 0 : g_hash_table_iter_remove (&bucket_cols);
580 : 0 : continue;
581 : : }
582 : :
583 : 0 : bucket_col->n_boxes = 0;
584 : 0 : bucket_col->bbox = EMPTY_BOX;
585 : :
586 [ # # ]: 0 : for (int y = 0; y < NODES; y ++)
587 : : {
588 : 0 : RTreeRow *row = &bucket_col->rows[y];
589 : 0 : row->bbox = EMPTY_BOX;
590 : :
591 [ # # ]: 0 : for (int x = 0; x < NODES; x ++)
592 : : {
593 : 0 : RTreeCol *col = &row->cols[x];
594 : 0 : col->bbox = EMPTY_BOX;
595 : :
596 [ # # ]: 0 : if (col->boxes != NULL)
597 : 0 : g_array_set_size (col->boxes, 0);
598 : : }
599 : : }
600 : : }
601 : :
602 [ # # ]: 0 : if (g_hash_table_size (bucket_row->bucket_cols) == 0)
603 : : {
604 : 0 : g_ptr_array_remove_fast (self->bucket_rows_array, bucket_row);
605 : 0 : g_hash_table_iter_remove (&bucket_rows);
606 : : }
607 : : }
608 : 0 : }
609 : :
610 : :
611 : : void
612 : 0 : shumate_vector_collision_visualize (ShumateVectorCollision *self,
613 : : GtkSnapshot *snapshot)
614 : : {
615 : 0 : GHashTableIter bucket_rows;
616 : 0 : RTreeBucketRow *bucket_row;
617 : :
618 : 0 : float width[4] = { 1, 1, 1, 1 };
619 : 0 : GdkRGBA color[4], color2[4];
620 : :
621 : 0 : gdk_rgba_parse (&color[0], "#FF0000");
622 : 0 : gdk_rgba_parse (&color[1], "#FF0000");
623 : 0 : gdk_rgba_parse (&color[2], "#FF0000");
624 : 0 : gdk_rgba_parse (&color[3], "#FF0000");
625 : :
626 : 0 : gdk_rgba_parse (&color2[0], "#00FF00");
627 : 0 : gdk_rgba_parse (&color2[1], "#00FF00");
628 : 0 : gdk_rgba_parse (&color2[2], "#00FF00");
629 : 0 : gdk_rgba_parse (&color2[3], "#00FF00");
630 : :
631 : 0 : g_hash_table_iter_init (&bucket_rows, self->bucket_rows);
632 : :
633 [ # # ]: 0 : while (g_hash_table_iter_next (&bucket_rows, NULL, (gpointer*) &bucket_row))
634 : : {
635 : 0 : GHashTableIter tile_cols;
636 : 0 : RTreeBucketCol *bucket_col;
637 : :
638 : 0 : gtk_snapshot_append_border (snapshot,
639 : 0 : &GSK_ROUNDED_RECT_INIT (bucket_row->bbox.x - bucket_row->bbox.aaxextent,
640 : : bucket_row->bbox.y - bucket_row->bbox.aayextent,
641 : : bucket_row->bbox.aaxextent * 2,
642 : : bucket_row->bbox.aayextent),
643 : : width,
644 : : color);
645 : :
646 : 0 : g_hash_table_iter_init (&tile_cols, bucket_row->bucket_cols);
647 : :
648 [ # # ]: 0 : while (g_hash_table_iter_next (&tile_cols, NULL, (gpointer*) &bucket_col))
649 : : {
650 [ # # ]: 0 : if (bucket_col->n_boxes == 0)
651 : 0 : continue;
652 : :
653 : 0 : gtk_snapshot_append_border (snapshot,
654 : 0 : &GSK_ROUNDED_RECT_INIT (bucket_col->bbox.x - bucket_col->bbox.aaxextent,
655 : : bucket_col->bbox.y - bucket_col->bbox.aayextent,
656 : : bucket_col->bbox.aaxextent * 2,
657 : : bucket_col->bbox.aayextent * 2),
658 : : width,
659 : : color);
660 : :
661 [ # # ]: 0 : for (int y = 0; y < NODES; y ++)
662 : : {
663 : 0 : RTreeRow *row = &bucket_col->rows[y];
664 : :
665 : 0 : gtk_snapshot_append_border (snapshot,
666 : 0 : &GSK_ROUNDED_RECT_INIT (row->bbox.x - row->bbox.aaxextent,
667 : : row->bbox.y - row->bbox.aayextent,
668 : : row->bbox.aaxextent * 2,
669 : : row->bbox.aayextent * 2),
670 : : width,
671 : : color);
672 : :
673 [ # # ]: 0 : for (int x = 0; x < NODES; x ++)
674 : : {
675 : 0 : RTreeCol *col = &row->cols[x];
676 : :
677 [ # # ]: 0 : if (col->boxes != NULL)
678 : : {
679 : :
680 : 0 : gtk_snapshot_append_border (snapshot,
681 : 0 : &GSK_ROUNDED_RECT_INIT (col->bbox.x - col->bbox.aaxextent,
682 : : col->bbox.y - col->bbox.aayextent,
683 : : col->bbox.aaxextent * 2,
684 : : col->bbox.aayextent * 2),
685 : : width,
686 : : color);
687 : :
688 [ # # ]: 0 : for (int i = 0; i < col->boxes->len; i ++)
689 : : {
690 : 0 : Box *b = &((Box*)col->boxes->data)[i];
691 : :
692 : 0 : gtk_snapshot_save (snapshot);
693 : 0 : gtk_snapshot_translate (snapshot, &GRAPHENE_POINT_INIT (b->x, b->y));
694 : 0 : gtk_snapshot_rotate (snapshot, b->rotation * 180 / G_PI);
695 : :
696 : 0 : gtk_snapshot_append_border (snapshot,
697 : 0 : &GSK_ROUNDED_RECT_INIT (-b->xextent,
698 : : -b->yextent,
699 : : b->xextent * 2,
700 : : b->yextent * 2),
701 : : width,
702 : : color2);
703 : :
704 : 0 : gtk_snapshot_restore (snapshot);
705 : : }
706 : : }
707 : : }
708 : : }
709 : : }
710 : : }
711 : 0 : }
|
