1 // stb_connected_components - v0.95 - public domain connected components on grids
2 // http://github.com/nothings/stb
4 // Finds connected components on 2D grids for testing reachability between
5 // two points, with fast updates when changing reachability (e.g. on one machine
6 // it was typically 0.2ms w/ 1024x1024 grid). Each grid square must be "open" or
7 // "closed" (traversable or untraversable), and grid squares are only connected
8 // to their orthogonal neighbors, not diagonally.
10 // In one source file, create the implementation by doing something like this:
12 // #define STBCC_GRID_COUNT_X_LOG2 10
13 // #define STBCC_GRID_COUNT_Y_LOG2 10
14 // #define STB_CONNECTED_COMPONENTS_IMPLEMENTATION
15 // #include "stb_connected_components.h"
17 // The above creates an implementation that can run on maps up to 1024x1024.
18 // Map sizes must be a multiple of (1<<(LOG2/2)) on each axis (e.g. 32 if LOG2=10,
19 // 16 if LOG2=8, etc.) (You can just pad your map with untraversable space.)
23 // Uses about 6-7 bytes per grid square (e.g. 7MB for a 1024x1024 grid).
24 // Uses a single worst-case allocation which you pass in.
28 // On a core i7-2700K at 3.5 Ghz, for a particular 1024x1024 map (map_03.png):
30 // Creating map : 44.85 ms
31 // Making one square traversable: 0.27 ms (average over 29,448 calls)
32 // Making one square untraversable: 0.23 ms (average over 30,123 calls)
33 // Reachability query: 0.00001 ms (average over 4,000,000 calls)
35 // On non-degenerate maps update time is O(N^0.5), but on degenerate maps like
36 // checkerboards or 50% random, update time is O(N^0.75) (~2ms on above machine).
40 // 0.95 (2016-10-16) Bugfix if multiple clumps in one cluster connect to same clump in another
41 // 0.94 (2016-04-17) Bugfix & optimize worst case (checkerboard & random)
42 // 0.93 (2016-04-16) Reduce memory by 10x for 1Kx1K map; small speedup
43 // 0.92 (2016-04-16) Compute sqrt(N) cluster size by default
44 // 0.91 (2016-04-15) Initial release
47 // - better API documentation
49 // - try re-integrating naive algorithm & compare performance
50 // - more optimized batching (current approach still recomputes local clumps many times)
51 // - function for setting a grid of squares at once (just use batching)
55 // This software is dual-licensed to the public domain and under the following
56 // license: you are granted a perpetual, irrevocable license to copy, modify,
57 // publish, and distribute this file as you see fit.
61 // The NxN grid map is split into sqrt(N) x sqrt(N) blocks called
62 // "clusters". Each cluster independently computes a set of connected
63 // components within that cluster (ignoring all connectivity out of
64 // that cluster) using a union-find disjoint set forest. This produces a bunch
65 // of locally connected components called "clumps". Each clump is (a) connected
66 // within its cluster, (b) does not directly connect to any other clumps in the
67 // cluster (though it may connect to them by paths that lead outside the cluster,
68 // but those are ignored at this step), and (c) maintains an adjacency list of
69 // all clumps in adjacent clusters that it _is_ connected to. Then a second
70 // union-find disjoint set forest is used to compute connected clumps
71 // globally, across the whole map. Reachability is then computed by
72 // finding which clump each input point belongs to, and checking whether
73 // those clumps are in the same "global" connected component.
75 // The above data structure can be updated efficiently; on a change
76 // of a single grid square on the map, only one cluster changes its
77 // purely-local state, so only one cluster needs its clumps fully
78 // recomputed. Clumps in adjacent clusters need their adjacency lists
79 // updated: first to remove all references to the old clumps in the
80 // rebuilt cluster, then to add new references to the new clumps. Both
81 // of these operations can use the existing "find which clump each input
82 // point belongs to" query to compute that adjacency information rapidly.
84 #ifndef INCLUDE_STB_CONNECTED_COMPONENTS_H
85 #define INCLUDE_STB_CONNECTED_COMPONENTS_H
89 typedef struct st_stbcc_grid stbcc_grid
;
95 //////////////////////////////////////////////////////////////////////////////////////////
100 // you allocate the grid data structure to this size (note that it will be very big!!!)
101 extern size_t stbcc_grid_sizeof(void);
103 // initialize the grid, value of map[] is 0 = traversable, non-0 is solid
104 extern void stbcc_init_grid(stbcc_grid
*g
, unsigned char *map
, int w
, int h
);
107 //////////////////////////////////////////////////////////////////////////////////////////
109 // main functionality
112 // update a grid square state, 0 = traversable, non-0 is solid
113 // i can add a batch-update if it's needed
114 extern void stbcc_update_grid(stbcc_grid
*g
, int x
, int y
, int solid
);
116 // query if two grid squares are reachable from each other
117 extern int stbcc_query_grid_node_connection(stbcc_grid
*g
, int x1
, int y1
, int x2
, int y2
);
120 //////////////////////////////////////////////////////////////////////////////////////////
125 // wrap multiple stbcc_update_grid calls in these function to compute
126 // multiple updates more efficiently; cannot make queries inside batch
127 extern void stbcc_update_batch_begin(stbcc_grid
*g
);
128 extern void stbcc_update_batch_end(stbcc_grid
*g
);
130 // query the grid data structure for whether a given square is open or not
131 extern int stbcc_query_grid_open(stbcc_grid
*g
, int x
, int y
);
133 // get a unique id for the connected component this is in; it's not necessarily
134 // small, you'll need a hash table or something to remap it (or just use
135 extern unsigned int stbcc_get_unique_id(stbcc_grid
*g
, int x
, int y
);
136 #define STBCC_NULL_UNIQUE_ID 0xffffffff // returned for closed map squares
142 #endif // INCLUDE_STB_CONNECTED_COMPONENTS_H
144 #ifdef STB_CONNECTED_COMPONENTS_IMPLEMENTATION
147 #include <string.h> // memset
149 #if !defined(STBCC_GRID_COUNT_X_LOG2) || !defined(STBCC_GRID_COUNT_Y_LOG2)
150 #error "You must define STBCC_GRID_COUNT_X_LOG2 and STBCC_GRID_COUNT_Y_LOG2 to define the max grid supported."
153 #define STBCC__GRID_COUNT_X (1 << STBCC_GRID_COUNT_X_LOG2)
154 #define STBCC__GRID_COUNT_Y (1 << STBCC_GRID_COUNT_Y_LOG2)
156 #define STBCC__MAP_STRIDE (1 << (STBCC_GRID_COUNT_X_LOG2-3))
158 #ifndef STBCC_CLUSTER_SIZE_X_LOG2
159 #define STBCC_CLUSTER_SIZE_X_LOG2 (STBCC_GRID_COUNT_X_LOG2/2) // log2(sqrt(2^N)) = 1/2 * log2(2^N)) = 1/2 * N
160 #if STBCC_CLUSTER_SIZE_X_LOG2 > 6
161 #undef STBCC_CLUSTER_SIZE_X_LOG2
162 #define STBCC_CLUSTER_SIZE_X_LOG2 6
166 #ifndef STBCC_CLUSTER_SIZE_Y_LOG2
167 #define STBCC_CLUSTER_SIZE_Y_LOG2 (STBCC_GRID_COUNT_Y_LOG2/2)
168 #if STBCC_CLUSTER_SIZE_Y_LOG2 > 6
169 #undef STBCC_CLUSTER_SIZE_Y_LOG2
170 #define STBCC_CLUSTER_SIZE_Y_LOG2 6
174 #define STBCC__CLUSTER_SIZE_X (1 << STBCC_CLUSTER_SIZE_X_LOG2)
175 #define STBCC__CLUSTER_SIZE_Y (1 << STBCC_CLUSTER_SIZE_Y_LOG2)
177 #define STBCC__CLUSTER_COUNT_X_LOG2 (STBCC_GRID_COUNT_X_LOG2 - STBCC_CLUSTER_SIZE_X_LOG2)
178 #define STBCC__CLUSTER_COUNT_Y_LOG2 (STBCC_GRID_COUNT_Y_LOG2 - STBCC_CLUSTER_SIZE_Y_LOG2)
180 #define STBCC__CLUSTER_COUNT_X (1 << STBCC__CLUSTER_COUNT_X_LOG2)
181 #define STBCC__CLUSTER_COUNT_Y (1 << STBCC__CLUSTER_COUNT_Y_LOG2)
183 #if STBCC__CLUSTER_SIZE_X >= STBCC__GRID_COUNT_X || STBCC__CLUSTER_SIZE_Y >= STBCC__GRID_COUNT_Y
184 #error "STBCC_CLUSTER_SIZE_X/Y_LOG2 must be smaller than STBCC_GRID_COUNT_X/Y_LOG2"
187 // worst case # of clumps per cluster
188 #define STBCC__MAX_CLUMPS_PER_CLUSTER_LOG2 (STBCC_CLUSTER_SIZE_X_LOG2 + STBCC_CLUSTER_SIZE_Y_LOG2-1)
189 #define STBCC__MAX_CLUMPS_PER_CLUSTER (1 << STBCC__MAX_CLUMPS_PER_CLUSTER_LOG2)
190 #define STBCC__MAX_CLUMPS (STBCC__MAX_CLUMPS_PER_CLUSTER * STBCC__CLUSTER_COUNT_X * STBCC__CLUSTER_COUNT_Y)
191 #define STBCC__NULL_CLUMPID STBCC__MAX_CLUMPS_PER_CLUSTER
193 #define STBCC__CLUSTER_X_FOR_COORD_X(x) ((x) >> STBCC_CLUSTER_SIZE_X_LOG2)
194 #define STBCC__CLUSTER_Y_FOR_COORD_Y(y) ((y) >> STBCC_CLUSTER_SIZE_Y_LOG2)
196 #define STBCC__MAP_BYTE_MASK(x,y) (1 << ((x) & 7))
197 #define STBCC__MAP_BYTE(g,x,y) ((g)->map[y][(x) >> 3])
198 #define STBCC__MAP_OPEN(g,x,y) (STBCC__MAP_BYTE(g,x,y) & STBCC__MAP_BYTE_MASK(x,y))
200 typedef unsigned short stbcc__clumpid
;
201 typedef unsigned char stbcc__verify_max_clumps
[STBCC__MAX_CLUMPS_PER_CLUSTER
< (1 << (8*sizeof(stbcc__clumpid
))) ? 1 : -1];
203 #define STBCC__MAX_EXITS_PER_CLUSTER (STBCC__CLUSTER_SIZE_X + STBCC__CLUSTER_SIZE_Y) // 64 for 32x32
204 #define STBCC__MAX_EXITS_PER_CLUMP (STBCC__CLUSTER_SIZE_X + STBCC__CLUSTER_SIZE_Y) // 64 for 32x32
205 #define STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER (STBCC__MAX_EXITS_PER_CLUMP)
207 // 2^19 * 2^6 => 2^25 exits => 2^26 => 64MB for 1024x1024
209 // Logic for above on 4x4 grid:
211 // Many clumps: One clump:
219 // 8 exits either way
221 typedef unsigned char stbcc__verify_max_exits
[STBCC__MAX_EXITS_PER_CLUMP
<= 256];
225 unsigned short clump_index
:12;
226 signed short cluster_dx
:2;
227 signed short cluster_dy
:2;
228 } stbcc__relative_clumpid
;
233 unsigned int clump_index
:12;
234 unsigned int cluster_x
:10;
235 unsigned int cluster_y
:10;
238 } stbcc__global_clumpid
;
240 // rebuilt cluster 3,4
242 // what changes in cluster 2,4
246 stbcc__global_clumpid global_label
; // 4
247 unsigned char num_adjacent
; // 1
248 unsigned char max_adjacent
; // 1
249 unsigned char adjacent_clump_list_index
; // 1
250 unsigned char reserved
;
253 #define STBCC__CLUSTER_ADJACENCY_COUNT (STBCC__MAX_EXITS_PER_CLUSTER*2)
257 unsigned char num_edge_clumps
;
258 unsigned char rebuild_adjacency
;
259 stbcc__clump clump
[STBCC__MAX_CLUMPS_PER_CLUSTER
]; // 8 * 2^9 = 4KB
260 stbcc__relative_clumpid adjacency_storage
[STBCC__CLUSTER_ADJACENCY_COUNT
]; // 256 bytes
266 int in_batched_update
;
267 //unsigned char cluster_dirty[STBCC__CLUSTER_COUNT_Y][STBCC__CLUSTER_COUNT_X]; // could bitpack, but: 1K x 1K => 1KB
268 unsigned char map
[STBCC__GRID_COUNT_Y
][STBCC__MAP_STRIDE
]; // 1K x 1K => 1K x 128 => 128KB
269 stbcc__clumpid clump_for_node
[STBCC__GRID_COUNT_Y
][STBCC__GRID_COUNT_X
]; // 1K x 1K x 2 = 2MB
270 stbcc__cluster cluster
[STBCC__CLUSTER_COUNT_Y
][STBCC__CLUSTER_COUNT_X
]; // 1K x 4.5KB = 4.5MB
273 int stbcc_query_grid_node_connection(stbcc_grid
*g
, int x1
, int y1
, int x2
, int y2
)
275 stbcc__global_clumpid label1
, label2
;
276 stbcc__clumpid c1
= g
->clump_for_node
[y1
][x1
];
277 stbcc__clumpid c2
= g
->clump_for_node
[y2
][x2
];
278 int cx1
= STBCC__CLUSTER_X_FOR_COORD_X(x1
);
279 int cy1
= STBCC__CLUSTER_Y_FOR_COORD_Y(y1
);
280 int cx2
= STBCC__CLUSTER_X_FOR_COORD_X(x2
);
281 int cy2
= STBCC__CLUSTER_Y_FOR_COORD_Y(y2
);
282 assert(!g
->in_batched_update
);
283 if (c1
== STBCC__NULL_CLUMPID
|| c2
== STBCC__NULL_CLUMPID
)
285 label1
= g
->cluster
[cy1
][cx1
].clump
[c1
].global_label
;
286 label2
= g
->cluster
[cy2
][cx2
].clump
[c2
].global_label
;
287 if (label1
.c
== label2
.c
)
292 int stbcc_query_grid_open(stbcc_grid
*g
, int x
, int y
)
294 return STBCC__MAP_OPEN(g
, x
, y
) != 0;
297 unsigned int stbcc_get_unique_id(stbcc_grid
*g
, int x
, int y
)
299 stbcc__clumpid c
= g
->clump_for_node
[y
][x
];
300 int cx
= STBCC__CLUSTER_X_FOR_COORD_X(x
);
301 int cy
= STBCC__CLUSTER_Y_FOR_COORD_Y(y
);
302 assert(!g
->in_batched_update
);
303 if (c
== STBCC__NULL_CLUMPID
) return STBCC_NULL_UNIQUE_ID
;
304 return g
->cluster
[cy
][cx
].clump
[c
].global_label
.c
;
314 stbcc__tinypoint parent
[STBCC__CLUSTER_SIZE_Y
][STBCC__CLUSTER_SIZE_X
]; // 32x32 => 2KB
315 stbcc__clumpid label
[STBCC__CLUSTER_SIZE_Y
][STBCC__CLUSTER_SIZE_X
];
316 } stbcc__cluster_build_info
;
318 static void stbcc__build_clumps_for_cluster(stbcc_grid
*g
, int cx
, int cy
);
319 static void stbcc__remove_connections_to_adjacent_cluster(stbcc_grid
*g
, int cx
, int cy
, int dx
, int dy
);
320 static void stbcc__add_connections_to_adjacent_cluster(stbcc_grid
*g
, int cx
, int cy
, int dx
, int dy
);
322 static stbcc__global_clumpid
stbcc__clump_find(stbcc_grid
*g
, stbcc__global_clumpid n
)
324 stbcc__global_clumpid q
;
325 stbcc__clump
*c
= &g
->cluster
[n
.f
.cluster_y
][n
.f
.cluster_x
].clump
[n
.f
.clump_index
];
327 if (c
->global_label
.c
== n
.c
)
330 q
= stbcc__clump_find(g
, c
->global_label
);
337 unsigned int cluster_x
;
338 unsigned int cluster_y
;
339 unsigned int clump_index
;
340 } stbcc__unpacked_clumpid
;
342 static void stbcc__clump_union(stbcc_grid
*g
, stbcc__unpacked_clumpid m
, int x
, int y
, int idx
)
344 stbcc__clump
*mc
= &g
->cluster
[m
.cluster_y
][m
.cluster_x
].clump
[m
.clump_index
];
345 stbcc__clump
*nc
= &g
->cluster
[y
][x
].clump
[idx
];
346 stbcc__global_clumpid mp
= stbcc__clump_find(g
, mc
->global_label
);
347 stbcc__global_clumpid np
= stbcc__clump_find(g
, nc
->global_label
);
352 g
->cluster
[mp
.f
.cluster_y
][mp
.f
.cluster_x
].clump
[mp
.f
.clump_index
].global_label
= np
;
355 static void stbcc__build_connected_components_for_clumps(stbcc_grid
*g
)
359 for (j
=0; j
< STBCC__CLUSTER_COUNT_Y
; ++j
) {
360 for (i
=0; i
< STBCC__CLUSTER_COUNT_X
; ++i
) {
361 stbcc__cluster
*cluster
= &g
->cluster
[j
][i
];
362 for (k
=0; k
< (int) cluster
->num_edge_clumps
; ++k
) {
363 stbcc__global_clumpid m
;
367 assert((int) m
.f
.clump_index
== k
&& (int) m
.f
.cluster_x
== i
&& (int) m
.f
.cluster_y
== j
);
368 cluster
->clump
[k
].global_label
= m
;
373 for (j
=0; j
< STBCC__CLUSTER_COUNT_Y
; ++j
) {
374 for (i
=0; i
< STBCC__CLUSTER_COUNT_X
; ++i
) {
375 stbcc__cluster
*cluster
= &g
->cluster
[j
][i
];
376 for (k
=0; k
< (int) cluster
->num_edge_clumps
; ++k
) {
377 stbcc__clump
*clump
= &cluster
->clump
[k
];
378 stbcc__unpacked_clumpid m
;
379 stbcc__relative_clumpid
*adj
;
383 adj
= &cluster
->adjacency_storage
[clump
->adjacent_clump_list_index
];
384 for (h
=0; h
< clump
->num_adjacent
; ++h
) {
385 unsigned int clump_index
= adj
[h
].clump_index
;
386 unsigned int x
= adj
[h
].cluster_dx
+ i
;
387 unsigned int y
= adj
[h
].cluster_dy
+ j
;
388 stbcc__clump_union(g
, m
, x
, y
, clump_index
);
394 for (j
=0; j
< STBCC__CLUSTER_COUNT_Y
; ++j
) {
395 for (i
=0; i
< STBCC__CLUSTER_COUNT_X
; ++i
) {
396 stbcc__cluster
*cluster
= &g
->cluster
[j
][i
];
397 for (k
=0; k
< (int) cluster
->num_edge_clumps
; ++k
) {
398 stbcc__global_clumpid m
;
402 stbcc__clump_find(g
, m
);
408 static void stbcc__build_all_connections_for_cluster(stbcc_grid
*g
, int cx
, int cy
)
410 // in this particular case, we are fully non-incremental. that means we
411 // can discover the correct sizes for the arrays, but requires we build
412 // the data into temporary data structures, or just count the sizes, so
413 // for simplicity we do the latter
414 stbcc__cluster
*cluster
= &g
->cluster
[cy
][cx
];
415 unsigned char connected
[STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER
][STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER
/8]; // 64 x 8 => 1KB
416 unsigned char num_adj
[STBCC__MAX_CLUMPS_PER_CLUSTER
] = { 0 };
417 int x
= cx
* STBCC__CLUSTER_SIZE_X
;
418 int y
= cy
* STBCC__CLUSTER_SIZE_Y
;
419 int step_x
, step_y
=0, i
, j
, k
, n
, m
, dx
, dy
, total
;
422 g
->cluster
[cy
][cx
].rebuild_adjacency
= 0;
425 for (m
=0; m
< 4; ++m
) {
429 step_x
= 0, step_y
= 1;
430 i
= STBCC__CLUSTER_SIZE_X
-1;
432 n
= STBCC__CLUSTER_SIZE_Y
;
440 n
= STBCC__CLUSTER_SIZE_Y
;
448 n
= STBCC__CLUSTER_SIZE_X
;
453 j
= STBCC__CLUSTER_SIZE_Y
-1;
456 n
= STBCC__CLUSTER_SIZE_X
;
460 if (cx
+dx
< 0 || cx
+dx
>= g
->cw
|| cy
+dy
< 0 || cy
+dy
>= g
->ch
)
463 memset(connected
, 0, sizeof(connected
));
464 for (k
=0; k
< n
; ++k
) {
465 if (STBCC__MAP_OPEN(g
, x
+i
, y
+j
) && STBCC__MAP_OPEN(g
, x
+i
+dx
, y
+j
+dy
)) {
466 stbcc__clumpid src
= g
->clump_for_node
[y
+j
][x
+i
];
467 stbcc__clumpid dest
= g
->clump_for_node
[y
+j
+dy
][x
+i
+dx
];
468 if (0 == (connected
[src
][dest
>>3] & (1 << (dest
& 7)))) {
469 connected
[src
][dest
>>3] |= 1 << (dest
& 7);
479 assert(total
<= STBCC__CLUSTER_ADJACENCY_COUNT
);
481 // decide how to apportion unused adjacency slots; only clumps that lie
482 // on the edges of the cluster need adjacency slots, so divide them up
483 // evenly between those clumps
486 // extra = (STBCC__CLUSTER_ADJACENCY_COUNT - total) / cluster->num_edge_clumps;
487 // but we efficiently approximate this without a divide, because
488 // ignoring edge-vs-non-edge with 'num_adj[i]*2' was faster than
489 // 'num_adj[i]+extra' with the divide
490 if (total
+ (cluster
->num_edge_clumps
<<2) <= STBCC__CLUSTER_ADJACENCY_COUNT
)
492 else if (total
+ (cluster
->num_edge_clumps
<<1) <= STBCC__CLUSTER_ADJACENCY_COUNT
)
494 else if (total
+ (cluster
->num_edge_clumps
<<0) <= STBCC__CLUSTER_ADJACENCY_COUNT
)
500 for (i
=0; i
< (int) cluster
->num_edge_clumps
; ++i
) {
501 int alloc
= num_adj
[i
]+extra
;
502 if (alloc
> STBCC__MAX_EXITS_PER_CLUSTER
)
503 alloc
= STBCC__MAX_EXITS_PER_CLUSTER
;
504 assert(total
< 256); // must fit in byte
505 cluster
->clump
[i
].adjacent_clump_list_index
= (unsigned char) total
;
506 cluster
->clump
[i
].max_adjacent
= alloc
;
507 cluster
->clump
[i
].num_adjacent
= 0;
510 assert(total
<= STBCC__CLUSTER_ADJACENCY_COUNT
);
512 stbcc__add_connections_to_adjacent_cluster(g
, cx
, cy
, -1, 0);
513 stbcc__add_connections_to_adjacent_cluster(g
, cx
, cy
, 1, 0);
514 stbcc__add_connections_to_adjacent_cluster(g
, cx
, cy
, 0,-1);
515 stbcc__add_connections_to_adjacent_cluster(g
, cx
, cy
, 0, 1);
516 // make sure all of the above succeeded.
517 assert(g
->cluster
[cy
][cx
].rebuild_adjacency
== 0);
520 static void stbcc__add_connections_to_adjacent_cluster_with_rebuild(stbcc_grid
*g
, int cx
, int cy
, int dx
, int dy
)
522 if (cx
>= 0 && cx
< g
->cw
&& cy
>= 0 && cy
< g
->ch
) {
523 stbcc__add_connections_to_adjacent_cluster(g
, cx
, cy
, dx
, dy
);
524 if (g
->cluster
[cy
][cx
].rebuild_adjacency
)
525 stbcc__build_all_connections_for_cluster(g
, cx
, cy
);
529 void stbcc_update_grid(stbcc_grid
*g
, int x
, int y
, int solid
)
534 if (STBCC__MAP_OPEN(g
,x
,y
))
537 if (!STBCC__MAP_OPEN(g
,x
,y
))
541 cx
= STBCC__CLUSTER_X_FOR_COORD_X(x
);
542 cy
= STBCC__CLUSTER_Y_FOR_COORD_Y(y
);
544 stbcc__remove_connections_to_adjacent_cluster(g
, cx
-1, cy
, 1, 0);
545 stbcc__remove_connections_to_adjacent_cluster(g
, cx
+1, cy
, -1, 0);
546 stbcc__remove_connections_to_adjacent_cluster(g
, cx
, cy
-1, 0, 1);
547 stbcc__remove_connections_to_adjacent_cluster(g
, cx
, cy
+1, 0,-1);
550 STBCC__MAP_BYTE(g
,x
,y
) |= STBCC__MAP_BYTE_MASK(x
,y
);
552 STBCC__MAP_BYTE(g
,x
,y
) &= ~STBCC__MAP_BYTE_MASK(x
,y
);
554 stbcc__build_clumps_for_cluster(g
, cx
, cy
);
555 stbcc__build_all_connections_for_cluster(g
, cx
, cy
);
557 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g
, cx
-1, cy
, 1, 0);
558 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g
, cx
+1, cy
, -1, 0);
559 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g
, cx
, cy
-1, 0, 1);
560 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g
, cx
, cy
+1, 0,-1);
562 if (!g
->in_batched_update
)
563 stbcc__build_connected_components_for_clumps(g
);
566 g
->cluster_dirty
[cy
][cx
] = 1;
570 void stbcc_update_batch_begin(stbcc_grid
*g
)
572 assert(!g
->in_batched_update
);
573 g
->in_batched_update
= 1;
576 void stbcc_update_batch_end(stbcc_grid
*g
)
578 assert(g
->in_batched_update
);
579 g
->in_batched_update
= 0;
580 stbcc__build_connected_components_for_clumps(g
); // @OPTIMIZE: only do this if update was non-empty
583 size_t stbcc_grid_sizeof(void)
585 return sizeof(stbcc_grid
);
588 void stbcc_init_grid(stbcc_grid
*g
, unsigned char *map
, int w
, int h
)
591 assert(w
% STBCC__CLUSTER_SIZE_X
== 0);
592 assert(h
% STBCC__CLUSTER_SIZE_Y
== 0);
597 g
->cw
= w
>> STBCC_CLUSTER_SIZE_X_LOG2
;
598 g
->ch
= h
>> STBCC_CLUSTER_SIZE_Y_LOG2
;
599 g
->in_batched_update
= 0;
602 for (j
=0; j
< STBCC__CLUSTER_COUNT_Y
; ++j
)
603 for (i
=0; i
< STBCC__CLUSTER_COUNT_X
; ++i
)
604 g
->cluster_dirty
[j
][i
] = 0;
607 for (j
=0; j
< h
; ++j
) {
608 for (i
=0; i
< w
; i
+= 8) {
610 for (k
=0; k
< 8; ++k
)
611 if (map
[j
*w
+ (i
+k
)] == 0)
617 for (j
=0; j
< g
->ch
; ++j
)
618 for (i
=0; i
< g
->cw
; ++i
)
619 stbcc__build_clumps_for_cluster(g
, i
, j
);
621 for (j
=0; j
< g
->ch
; ++j
)
622 for (i
=0; i
< g
->cw
; ++i
)
623 stbcc__build_all_connections_for_cluster(g
, i
, j
);
625 stbcc__build_connected_components_for_clumps(g
);
627 for (j
=0; j
< g
->h
; ++j
)
628 for (i
=0; i
< g
->w
; ++i
)
629 assert(g
->clump_for_node
[j
][i
] <= STBCC__NULL_CLUMPID
);
633 static void stbcc__add_clump_connection(stbcc_grid
*g
, int x1
, int y1
, int x2
, int y2
)
635 stbcc__cluster
*cluster
;
638 int cx1
= STBCC__CLUSTER_X_FOR_COORD_X(x1
);
639 int cy1
= STBCC__CLUSTER_Y_FOR_COORD_Y(y1
);
640 int cx2
= STBCC__CLUSTER_X_FOR_COORD_X(x2
);
641 int cy2
= STBCC__CLUSTER_Y_FOR_COORD_Y(y2
);
643 stbcc__clumpid c1
= g
->clump_for_node
[y1
][x1
];
644 stbcc__clumpid c2
= g
->clump_for_node
[y2
][x2
];
646 stbcc__relative_clumpid rc
;
648 assert(cx1
!= cx2
|| cy1
!= cy2
);
649 assert(abs(cx1
-cx2
) + abs(cy1
-cy2
) == 1);
651 // add connection to c2 in c1
654 rc
.cluster_dx
= x2
-x1
;
655 rc
.cluster_dy
= y2
-y1
;
657 cluster
= &g
->cluster
[cy1
][cx1
];
658 clump
= &cluster
->clump
[c1
];
659 assert(clump
->num_adjacent
<= clump
->max_adjacent
);
660 if (clump
->num_adjacent
== clump
->max_adjacent
)
661 g
->cluster
[cy1
][cx1
].rebuild_adjacency
= 1;
663 stbcc__relative_clumpid
*adj
= &cluster
->adjacency_storage
[clump
->adjacent_clump_list_index
];
664 assert(clump
->num_adjacent
< STBCC__MAX_EXITS_PER_CLUMP
);
665 assert(clump
->adjacent_clump_list_index
+ clump
->num_adjacent
<= STBCC__CLUSTER_ADJACENCY_COUNT
);
666 adj
[clump
->num_adjacent
++] = rc
;
670 static void stbcc__remove_clump_connection(stbcc_grid
*g
, int x1
, int y1
, int x2
, int y2
)
672 stbcc__cluster
*cluster
;
674 stbcc__relative_clumpid
*adj
;
677 int cx1
= STBCC__CLUSTER_X_FOR_COORD_X(x1
);
678 int cy1
= STBCC__CLUSTER_Y_FOR_COORD_Y(y1
);
679 int cx2
= STBCC__CLUSTER_X_FOR_COORD_X(x2
);
680 int cy2
= STBCC__CLUSTER_Y_FOR_COORD_Y(y2
);
682 stbcc__clumpid c1
= g
->clump_for_node
[y1
][x1
];
683 stbcc__clumpid c2
= g
->clump_for_node
[y2
][x2
];
685 stbcc__relative_clumpid rc
;
687 assert(cx1
!= cx2
|| cy1
!= cy2
);
688 assert(abs(cx1
-cx2
) + abs(cy1
-cy2
) == 1);
690 // add connection to c2 in c1
693 rc
.cluster_dx
= x2
-x1
;
694 rc
.cluster_dy
= y2
-y1
;
696 cluster
= &g
->cluster
[cy1
][cx1
];
697 clump
= &cluster
->clump
[c1
];
698 adj
= &cluster
->adjacency_storage
[clump
->adjacent_clump_list_index
];
700 for (i
=0; i
< clump
->num_adjacent
; ++i
)
701 if (rc
.clump_index
== adj
[i
].clump_index
&&
702 rc
.cluster_dx
== adj
[i
].cluster_dx
&&
703 rc
.cluster_dy
== adj
[i
].cluster_dy
)
706 if (i
< clump
->num_adjacent
)
707 adj
[i
] = adj
[--clump
->num_adjacent
];
712 static void stbcc__add_connections_to_adjacent_cluster(stbcc_grid
*g
, int cx
, int cy
, int dx
, int dy
)
714 unsigned char connected
[STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER
][STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER
/8] = { 0 };
715 int x
= cx
* STBCC__CLUSTER_SIZE_X
;
716 int y
= cy
* STBCC__CLUSTER_SIZE_Y
;
717 int step_x
, step_y
=0, i
, j
, k
, n
;
719 if (cx
< 0 || cx
>= g
->cw
|| cy
< 0 || cy
>= g
->ch
)
722 if (cx
+dx
< 0 || cx
+dx
>= g
->cw
|| cy
+dy
< 0 || cy
+dy
>= g
->ch
)
725 if (g
->cluster
[cy
][cx
].rebuild_adjacency
)
728 assert(abs(dx
) + abs(dy
) == 1);
731 i
= STBCC__CLUSTER_SIZE_X
-1;
735 n
= STBCC__CLUSTER_SIZE_Y
;
736 } else if (dx
== -1) {
741 n
= STBCC__CLUSTER_SIZE_Y
;
742 } else if (dy
== -1) {
747 n
= STBCC__CLUSTER_SIZE_X
;
748 } else if (dy
== 1) {
750 j
= STBCC__CLUSTER_SIZE_Y
-1;
753 n
= STBCC__CLUSTER_SIZE_X
;
758 for (k
=0; k
< n
; ++k
) {
759 if (STBCC__MAP_OPEN(g
, x
+i
, y
+j
) && STBCC__MAP_OPEN(g
, x
+i
+dx
, y
+j
+dy
)) {
760 stbcc__clumpid src
= g
->clump_for_node
[y
+j
][x
+i
];
761 stbcc__clumpid dest
= g
->clump_for_node
[y
+j
+dy
][x
+i
+dx
];
762 if (0 == (connected
[src
][dest
>>3] & (1 << (dest
& 7)))) {
763 assert((dest
>>3) < sizeof(connected
));
764 connected
[src
][dest
>>3] |= 1 << (dest
& 7);
765 stbcc__add_clump_connection(g
, x
+i
, y
+j
, x
+i
+dx
, y
+j
+dy
);
766 if (g
->cluster
[cy
][cx
].rebuild_adjacency
)
775 static void stbcc__remove_connections_to_adjacent_cluster(stbcc_grid
*g
, int cx
, int cy
, int dx
, int dy
)
777 unsigned char disconnected
[STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER
][STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER
/8] = { 0 };
778 int x
= cx
* STBCC__CLUSTER_SIZE_X
;
779 int y
= cy
* STBCC__CLUSTER_SIZE_Y
;
780 int step_x
, step_y
=0, i
, j
, k
, n
;
782 if (cx
< 0 || cx
>= g
->cw
|| cy
< 0 || cy
>= g
->ch
)
785 if (cx
+dx
< 0 || cx
+dx
>= g
->cw
|| cy
+dy
< 0 || cy
+dy
>= g
->ch
)
788 assert(abs(dx
) + abs(dy
) == 1);
791 i
= STBCC__CLUSTER_SIZE_X
-1;
795 n
= STBCC__CLUSTER_SIZE_Y
;
796 } else if (dx
== -1) {
801 n
= STBCC__CLUSTER_SIZE_Y
;
802 } else if (dy
== -1) {
807 n
= STBCC__CLUSTER_SIZE_X
;
808 } else if (dy
== 1) {
810 j
= STBCC__CLUSTER_SIZE_Y
-1;
813 n
= STBCC__CLUSTER_SIZE_X
;
818 for (k
=0; k
< n
; ++k
) {
819 if (STBCC__MAP_OPEN(g
, x
+i
, y
+j
) && STBCC__MAP_OPEN(g
, x
+i
+dx
, y
+j
+dy
)) {
820 stbcc__clumpid src
= g
->clump_for_node
[y
+j
][x
+i
];
821 stbcc__clumpid dest
= g
->clump_for_node
[y
+j
+dy
][x
+i
+dx
];
822 if (0 == (disconnected
[src
][dest
>>3] & (1 << (dest
& 7)))) {
823 disconnected
[src
][dest
>>3] |= 1 << (dest
& 7);
824 stbcc__remove_clump_connection(g
, x
+i
, y
+j
, x
+i
+dx
, y
+j
+dy
);
832 static stbcc__tinypoint
stbcc__incluster_find(stbcc__cluster_build_info
*cbi
, int x
, int y
)
834 stbcc__tinypoint p
,q
;
835 p
= cbi
->parent
[y
][x
];
836 if (p
.x
== x
&& p
.y
== y
)
838 q
= stbcc__incluster_find(cbi
, p
.x
, p
.y
);
839 cbi
->parent
[y
][x
] = q
;
843 static void stbcc__incluster_union(stbcc__cluster_build_info
*cbi
, int x1
, int y1
, int x2
, int y2
)
845 stbcc__tinypoint p
= stbcc__incluster_find(cbi
, x1
,y1
);
846 stbcc__tinypoint q
= stbcc__incluster_find(cbi
, x2
,y2
);
848 if (p
.x
== q
.x
&& p
.y
== q
.y
)
851 cbi
->parent
[p
.y
][p
.x
] = q
;
854 static void stbcc__switch_root(stbcc__cluster_build_info
*cbi
, int x
, int y
, stbcc__tinypoint p
)
856 cbi
->parent
[p
.y
][p
.x
].x
= x
;
857 cbi
->parent
[p
.y
][p
.x
].y
= y
;
858 cbi
->parent
[y
][x
].x
= x
;
859 cbi
->parent
[y
][x
].y
= y
;
862 static void stbcc__build_clumps_for_cluster(stbcc_grid
*g
, int cx
, int cy
)
865 stbcc__cluster_build_info cbi
;
868 int x
= cx
* STBCC__CLUSTER_SIZE_X
;
869 int y
= cy
* STBCC__CLUSTER_SIZE_Y
;
871 // set initial disjoint set forest state
872 for (j
=0; j
< STBCC__CLUSTER_SIZE_Y
; ++j
) {
873 for (i
=0; i
< STBCC__CLUSTER_SIZE_X
; ++i
) {
874 cbi
.parent
[j
][i
].x
= i
;
875 cbi
.parent
[j
][i
].y
= j
;
879 // join all sets that are connected
880 for (j
=0; j
< STBCC__CLUSTER_SIZE_Y
; ++j
) {
881 // check down only if not on bottom row
882 if (j
< STBCC__CLUSTER_SIZE_Y
-1)
883 for (i
=0; i
< STBCC__CLUSTER_SIZE_X
; ++i
)
884 if (STBCC__MAP_OPEN(g
,x
+i
,y
+j
) && STBCC__MAP_OPEN(g
,x
+i
,y
+j
+1))
885 stbcc__incluster_union(&cbi
, i
,j
, i
,j
+1);
886 // check right for everything but rightmost column
887 for (i
=0; i
< STBCC__CLUSTER_SIZE_X
-1; ++i
)
888 if (STBCC__MAP_OPEN(g
,x
+i
,y
+j
) && STBCC__MAP_OPEN(g
,x
+i
+1,y
+j
))
889 stbcc__incluster_union(&cbi
, i
,j
, i
+1,j
);
892 // label all non-empty clumps along edges so that all edge clumps are first
893 // in list; this means in degenerate case we can skip traversing non-edge clumps.
894 // because in the first pass we only label leaders, we swap the leader to the
897 // first put solid labels on all the edges; these will get overwritten if they're open
898 for (j
=0; j
< STBCC__CLUSTER_SIZE_Y
; ++j
)
899 cbi
.label
[j
][0] = cbi
.label
[j
][STBCC__CLUSTER_SIZE_X
-1] = STBCC__NULL_CLUMPID
;
900 for (i
=0; i
< STBCC__CLUSTER_SIZE_X
; ++i
)
901 cbi
.label
[0][i
] = cbi
.label
[STBCC__CLUSTER_SIZE_Y
-1][i
] = STBCC__NULL_CLUMPID
;
903 for (j
=0; j
< STBCC__CLUSTER_SIZE_Y
; ++j
) {
905 if (STBCC__MAP_OPEN(g
, x
+i
, y
+j
)) {
906 stbcc__tinypoint p
= stbcc__incluster_find(&cbi
, i
,j
);
907 if (p
.x
== i
&& p
.y
== j
)
908 // if this is the leader, give it a label
909 cbi
.label
[j
][i
] = label
++;
910 else if (!(p
.x
== 0 || p
.x
== STBCC__CLUSTER_SIZE_X
-1 || p
.y
== 0 || p
.y
== STBCC__CLUSTER_SIZE_Y
-1)) {
911 // if leader is in interior, promote this edge node to leader and label
912 stbcc__switch_root(&cbi
, i
, j
, p
);
913 cbi
.label
[j
][i
] = label
++;
915 // else if leader is on edge, do nothing (it'll get labelled when we reach it)
917 i
= STBCC__CLUSTER_SIZE_X
-1;
918 if (STBCC__MAP_OPEN(g
, x
+i
, y
+j
)) {
919 stbcc__tinypoint p
= stbcc__incluster_find(&cbi
, i
,j
);
920 if (p
.x
== i
&& p
.y
== j
)
921 cbi
.label
[j
][i
] = label
++;
922 else if (!(p
.x
== 0 || p
.x
== STBCC__CLUSTER_SIZE_X
-1 || p
.y
== 0 || p
.y
== STBCC__CLUSTER_SIZE_Y
-1)) {
923 stbcc__switch_root(&cbi
, i
, j
, p
);
924 cbi
.label
[j
][i
] = label
++;
929 for (i
=1; i
< STBCC__CLUSTER_SIZE_Y
-1; ++i
) {
931 if (STBCC__MAP_OPEN(g
, x
+i
, y
+j
)) {
932 stbcc__tinypoint p
= stbcc__incluster_find(&cbi
, i
,j
);
933 if (p
.x
== i
&& p
.y
== j
)
934 cbi
.label
[j
][i
] = label
++;
935 else if (!(p
.x
== 0 || p
.x
== STBCC__CLUSTER_SIZE_X
-1 || p
.y
== 0 || p
.y
== STBCC__CLUSTER_SIZE_Y
-1)) {
936 stbcc__switch_root(&cbi
, i
, j
, p
);
937 cbi
.label
[j
][i
] = label
++;
940 j
= STBCC__CLUSTER_SIZE_Y
-1;
941 if (STBCC__MAP_OPEN(g
, x
+i
, y
+j
)) {
942 stbcc__tinypoint p
= stbcc__incluster_find(&cbi
, i
,j
);
943 if (p
.x
== i
&& p
.y
== j
)
944 cbi
.label
[j
][i
] = label
++;
945 else if (!(p
.x
== 0 || p
.x
== STBCC__CLUSTER_SIZE_X
-1 || p
.y
== 0 || p
.y
== STBCC__CLUSTER_SIZE_Y
-1)) {
946 stbcc__switch_root(&cbi
, i
, j
, p
);
947 cbi
.label
[j
][i
] = label
++;
952 c
= &g
->cluster
[cy
][cx
];
953 c
->num_edge_clumps
= label
;
955 // label any internal clusters
956 for (j
=1; j
< STBCC__CLUSTER_SIZE_Y
-1; ++j
) {
957 for (i
=1; i
< STBCC__CLUSTER_SIZE_X
-1; ++i
) {
958 stbcc__tinypoint p
= cbi
.parent
[j
][i
];
959 if (p
.x
== i
&& p
.y
== j
)
960 if (STBCC__MAP_OPEN(g
,x
+i
,y
+j
))
961 cbi
.label
[j
][i
] = label
++;
963 cbi
.label
[j
][i
] = STBCC__NULL_CLUMPID
;
967 // label all other nodes
968 for (j
=0; j
< STBCC__CLUSTER_SIZE_Y
; ++j
) {
969 for (i
=0; i
< STBCC__CLUSTER_SIZE_X
; ++i
) {
970 stbcc__tinypoint p
= stbcc__incluster_find(&cbi
, i
,j
);
971 if (p
.x
!= i
|| p
.y
!= j
) {
972 if (STBCC__MAP_OPEN(g
,x
+i
,y
+j
))
973 cbi
.label
[j
][i
] = cbi
.label
[p
.y
][p
.x
];
975 if (STBCC__MAP_OPEN(g
,x
+i
,y
+j
))
976 assert(cbi
.label
[j
][i
] != STBCC__NULL_CLUMPID
);
980 c
->num_clumps
= label
;
982 for (i
=0; i
< label
; ++i
) {
983 c
->clump
[i
].num_adjacent
= 0;
984 c
->clump
[i
].max_adjacent
= 0;
987 for (j
=0; j
< STBCC__CLUSTER_SIZE_Y
; ++j
)
988 for (i
=0; i
< STBCC__CLUSTER_SIZE_X
; ++i
) {
989 g
->clump_for_node
[y
+j
][x
+i
] = cbi
.label
[j
][i
]; // @OPTIMIZE: remove cbi.label entirely
990 assert(g
->clump_for_node
[y
+j
][x
+i
] <= STBCC__NULL_CLUMPID
);
993 // set the global label for all interior clumps since they can't have connections,
994 // so we don't have to do this on the global pass (brings from O(N) to O(N^0.75))
995 for (i
=(int) c
->num_edge_clumps
; i
< (int) c
->num_clumps
; ++i
) {
996 stbcc__global_clumpid gc
;
999 gc
.f
.clump_index
= i
;
1000 c
->clump
[i
].global_label
= gc
;
1003 c
->rebuild_adjacency
= 1; // flag that it has no valid adjacency data
1006 #endif // STB_CONNECTED_COMPONENTS_IMPLEMENTATION