scpr_intersector.c (24408B)
1 /* Copyright (C) 2016-2018, 2021-2024 |Méso|Star> (contact@meso-star.com) 2 * 3 * This program is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published by 5 * the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with this program. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #include "scpr.h" 17 #include "scpr_c.h" 18 19 #include <polygon.h> 20 #include <rsys/logger.h> 21 #include <rsys/ref_count.h> 22 #include <rsys/mem_allocator.h> 23 #include <rsys/rsys.h> 24 #include <rsys/double2.h> 25 #include <rsys/double3.h> 26 27 #include <stdlib.h> 28 29 /******************************************************************************* 30 * Helper functions 31 ******************************************************************************/ 32 static void 33 init_dimension 34 (struct mem_allocator* allocator, 35 struct intersector_dimension* dim, 36 enum segment_interaction overlap, 37 enum segment_interaction share) 38 { 39 ASSERT(dim && allocator); 40 htable_range_point_idx_init(allocator, &dim->unsorted); 41 darray_range_points_init(allocator, &dim->sorted); 42 dim->range[0] = INT64_MAX; 43 dim->range[1] = INT64_MIN; 44 dim->overlap= overlap; 45 dim->contact = share; 46 } 47 48 static void 49 release_dimension 50 (struct intersector_dimension* dim) 51 { 52 ASSERT(dim); 53 htable_range_point_idx_release(&dim->unsorted); 54 darray_range_points_release(&dim->sorted); 55 } 56 57 static void 58 intersector_release(ref_T* ref) 59 { 60 struct scpr_intersector* intersector; 61 struct mem_allocator* allocator; 62 ASSERT(ref); 63 intersector = CONTAINER_OF(ref, struct scpr_intersector, ref); 64 allocator = intersector->device->allocator; 65 darray_segments_release(&intersector->segments); 66 release_dimension(intersector->dimensions); 67 release_dimension(intersector->dimensions + 1); 68 SCPR(device_ref_put(intersector->device)); 69 htable_interacting_segments_release(&intersector->interacting_segments); 70 htable_registered_components_release(&intersector->registered_components); 71 darray_components_release(&intersector->components); 72 MEM_RM(allocator, intersector); 73 } 74 75 /* Register a point (a segment end) against a dimension */ 76 static res_T 77 register_point 78 (struct scpr_intersector* intersector, 79 const int dim_idx, 80 const int64_t coord, 81 const uint32_t seg_idx) 82 { 83 uint32_t* pidx; 84 uint32_t rp_idx; 85 struct intersector_dimension* dim; 86 struct intersector_range_point* sorted; 87 res_T res = RES_OK; 88 ASSERT(intersector); 89 90 dim = intersector->dimensions + dim_idx; 91 pidx = htable_range_point_idx_find(&dim->unsorted, &coord); 92 if(!pidx) { 93 /* First time this point: create it in sorted and store its index in unsorted */ 94 char one = 1; 95 size_t count = darray_range_points_size_get(&dim->sorted); 96 ERR(darray_range_points_resize(&dim->sorted, 1+count)); 97 sorted = darray_range_points_data_get(&dim->sorted); 98 rp_idx = (uint32_t)count; 99 sorted[rp_idx].coord = coord; 100 /* Register this segment at this range point */ 101 ERR(htable_segment_idx_set(&sorted[rp_idx].segments, &seg_idx, &one)); 102 /* Update range */ 103 if(dim->range[0] > coord) dim->range[0] = coord; 104 if(dim->range[1] < coord) dim->range[1] = coord; 105 } else { 106 /* This point is already known: look for seg_idx already there */ 107 char *found, one_or_two; 108 rp_idx = *pidx; 109 sorted = darray_range_points_data_get(&dim->sorted); 110 found = htable_segment_idx_find(&sorted[rp_idx].segments, &seg_idx); 111 one_or_two = found ? 2 : 1; 112 ERR(htable_segment_idx_set(&sorted[rp_idx].segments, &seg_idx, &one_or_two)); 113 } 114 ERR(htable_range_point_idx_set(&dim->unsorted, &coord, &rp_idx)); 115 116 exit: 117 return res; 118 error: 119 goto exit; 120 } 121 122 /* Compare 2 range_points */ 123 static int 124 compare_range_points(const void* a, const void* b) 125 { 126 struct intersector_range_point *pa = (struct intersector_range_point*)a; 127 struct intersector_range_point *pb = (struct intersector_range_point*)b; 128 ASSERT(a && b && pa->coord != pb->coord); 129 return (int)(pa->coord - pb->coord); 130 } 131 132 /* Sort the range points by increasing coordinates */ 133 static void 134 sort_points 135 (struct intersector_dimension* dim) 136 { 137 size_t count; 138 struct intersector_range_point* sorted; 139 ASSERT(dim); 140 141 /* All the range points are already in sorted; just need to sort them */ 142 count = darray_range_points_size_get(&dim->sorted); 143 ASSERT(count == htable_range_point_idx_size_get(&dim->unsorted)); 144 sorted = darray_range_points_data_get(&dim->sorted); 145 qsort(sorted, count, sizeof(*sorted), compare_range_points); 146 } 147 148 /* Create a segment pair suitable for use as an htable key 149 * To ensure unicity, pairs are ordered */ 150 static void 151 init_segment_pair 152 (struct intersector_segment_pair* pair, 153 const uint32_t seg_idx1, 154 const uint32_t seg_idx2) 155 { 156 ASSERT(pair); 157 pair->rank1 = seg_idx1; 158 pair->rank2 = seg_idx2; 159 if(pair->rank1 > pair->rank2) { 160 SWAP(uint32_t, pair->rank1, pair->rank2); 161 } 162 } 163 164 #ifndef NDEBUG 165 static int 166 segments_bbox_interacts_1_core 167 (int64_t lower1, int64_t upper1, int64_t lower2, int64_t upper2) 168 { 169 if(lower1 > upper2) return 0; 170 if(lower2 > upper1) return 0; 171 return 1; 172 } 173 174 /* Check if 2 polygon Bbox interact */ 175 static int 176 segments_bbox_interacts 177 (Clipper2Lib::Point64 *v11, 178 Clipper2Lib::Point64 *v12, 179 Clipper2Lib::Point64 *v21, 180 Clipper2Lib::Point64 *v22) 181 { 182 int64_t lower1[2], upper1[2], lower2[2], upper2[2]; 183 ASSERT(v11 && v12 && v21 && v22); 184 lower1[0] = MMIN(v11->x, v12->x); 185 lower1[1] = MMIN(v11->y, v12->y); 186 lower2[0] = MMIN(v21->x, v22->x); 187 lower2[1] = MMIN(v21->y, v22->y); 188 upper1[0] = MMAX(v11->x, v12->x); 189 upper1[1] = MMAX(v11->y, v12->y); 190 upper2[0] = MMAX(v21->x, v22->x); 191 upper2[1] = MMAX(v21->y, v22->y); 192 if(!segments_bbox_interacts_1_core(lower1[0], upper1[0], lower2[0], upper2[0])) 193 return 0; 194 return segments_bbox_interacts_1_core(lower1[1], upper1[1], lower2[1], upper2[1]); 195 } 196 197 static int 198 segments_bbox_interacts_1 199 (uint32_t seg_idx1, 200 uint32_t seg_idx2, 201 enum segment_interaction inter, 202 struct scpr_intersector* intersector) 203 { 204 const struct intersector_segment *segments, *seg1, *seg2; 205 Clipper2Lib::Point64 *v11, * v12, *v21, *v22; 206 int64_t lower1, upper1, lower2, upper2; 207 size_t count, r11, r12, r21, r22; 208 const struct intersector_component* components; 209 struct scpr_polygon *polygon1, *polygon2; 210 uint32_t comp_idx1, comp_idx2; 211 212 segments = darray_segments_cdata_get(&intersector->segments); 213 seg1 = segments + seg_idx1; 214 seg2 = segments + seg_idx2; 215 components = darray_components_cdata_get(&intersector->components); 216 comp_idx1 = components[seg1->component].component; 217 comp_idx2 = components[seg2->component].component; 218 polygon1 = components[seg1->component].polygon; 219 polygon2 = components[seg2->component].polygon; 220 221 /* Get vertices */ 222 r11 = seg1->first_vertex; 223 SCPR(polygon_get_vertices_count(polygon1, comp_idx1, &count)); 224 r12 = (r11 + 1) % count; 225 r21 = seg2->first_vertex; 226 SCPR(polygon_get_vertices_count(polygon2, comp_idx2, &count)); 227 r22 = (r21 + 1) % count; 228 v11 = &polygon1->paths[comp_idx1][r11]; 229 v12 = &polygon1->paths[comp_idx1][r12]; 230 v21 = &polygon2->paths[comp_idx2][r21]; 231 v22 = &polygon2->paths[comp_idx2][r22]; 232 if(inter & SOMETHING_X) { 233 lower1 = MMIN(v11->x, v12->x); 234 upper1 = MMAX(v11->x, v12->x); 235 lower2 = MMIN(v21->x, v22->x); 236 upper2 = MMAX(v21->x, v22->x); 237 } else { 238 lower1 = MMIN(v11->y, v12->y); 239 upper1 = MMAX(v11->y, v12->y); 240 lower2 = MMIN(v21->y, v22->y); 241 upper2 = MMAX(v21->y, v22->y); 242 } 243 return segments_bbox_interacts_1_core(lower1, upper1, lower2, upper2); 244 } 245 #endif 246 247 /* Register interaction of 2 segments along 1 dimension */ 248 static res_T 249 register_segment_interaction 250 (const uint32_t seg_idx1, 251 const uint32_t seg_idx2, 252 const int allow_pair_creation, 253 const enum segment_interaction inter, 254 struct scpr_intersector* intersector) 255 { 256 res_T res = RES_OK; 257 struct intersector_segment_pair pair; 258 unsigned char *pinteract; 259 260 ASSERT(intersector); 261 if(seg_idx1 != seg_idx2) { 262 ASSERT(segments_bbox_interacts_1(seg_idx1, seg_idx2, inter, intersector)); 263 264 /* Fill a record for this pair of segments */ 265 init_segment_pair(&pair, seg_idx1, seg_idx2); 266 pinteract = 267 htable_interacting_segments_find(&intersector->interacting_segments, &pair); 268 if(pinteract || allow_pair_creation) { 269 unsigned char interact; 270 if(!pinteract) { /* First occurence of this pair: create empty record */ 271 interact = (unsigned char)inter; 272 } else { 273 ASSERT((*pinteract | inter) < UCHAR_MAX); 274 interact = (unsigned char)(*pinteract | inter); 275 } 276 277 /* Register this interaction */ 278 ERR(htable_interacting_segments_set(&intersector->interacting_segments, 279 &pair, &interact)); 280 } 281 } 282 283 exit: 284 return res; 285 error: 286 goto exit; 287 } 288 289 /* Register interaction of segment of seg_idx with all the segments in 290 * open_segments along 1 dimension */ 291 static res_T 292 register_segment_interactions 293 (const uint32_t seg_idx, 294 struct htable_segment_idx* open_segments, 295 const int allow_pair_creation, 296 const enum segment_interaction inter, 297 struct scpr_intersector* intersector) 298 { 299 res_T res = RES_OK; 300 struct htable_segment_idx_iterator it, end; 301 302 ASSERT(open_segments && intersector); 303 304 htable_segment_idx_begin(open_segments, &it); 305 htable_segment_idx_end(open_segments, &end); 306 /* Loop on segments using this point */ 307 while(!htable_segment_idx_iterator_eq(&it, &end)) { 308 uint32_t seg2_idx = *htable_segment_idx_iterator_key_get(&it); 309 ERR(register_segment_interaction(seg_idx, seg2_idx, allow_pair_creation, 310 inter, intersector)); 311 htable_segment_idx_iterator_next(&it); 312 } 313 314 exit: 315 return res; 316 error: 317 goto exit; 318 } 319 320 /* Register segments interaction along 1 dimension */ 321 static res_T 322 register_interaction 323 (const int dim_idx, 324 struct scpr_intersector* intersector) 325 { 326 res_T res = RES_OK; 327 size_t count, i; 328 struct intersector_range_point* points; 329 struct htable_segment_idx open_segments; 330 struct mem_allocator* allocator; 331 struct intersector_dimension* dimension; 332 char *begins = NULL, *ends = NULL; 333 uint32_t* seg_index = NULL; 334 ASSERT(intersector); 335 336 allocator = intersector->device->allocator; 337 dimension = intersector->dimensions + dim_idx; 338 htable_segment_idx_init(allocator, &open_segments); 339 count = darray_range_points_size_get(&dimension->sorted); 340 points = darray_range_points_data_get(&dimension->sorted); 341 for(i = 0; i < count; i++) { 342 struct intersector_range_point* point = points + i; 343 struct htable_segment_idx_iterator it, end; 344 size_t scount, s; 345 346 /* 0) Init begins, ends and seg_index 347 * Cannot recompute them on the fly as found will change */ 348 scount = htable_segment_idx_size_get(&point->segments); 349 begins = (char*)MEM_REALLOC(allocator, begins, scount * sizeof(*begins)); 350 ends = (char*)MEM_REALLOC(allocator, ends, scount * sizeof(*ends)); 351 seg_index = (uint32_t*)MEM_REALLOC(allocator, seg_index, 352 scount * sizeof(*seg_index)); 353 if(!begins || !ends || !seg_index) { 354 res = RES_MEM_ERR; 355 goto error; 356 } 357 s = 0; 358 htable_segment_idx_begin(&point->segments, &it); 359 htable_segment_idx_end(&point->segments, &end); 360 while(!htable_segment_idx_iterator_eq(&it, &end)) { 361 char c = *htable_segment_idx_iterator_data_get(&it); 362 uint32_t seg_idx = *htable_segment_idx_iterator_key_get(&it); 363 if(c == 2) { /* Both ends of the segment at this point */ 364 ends[s] = begins[s] = 1; 365 } else { 366 char* found = htable_segment_idx_find(&open_segments, &seg_idx); 367 begins[s] = (found == NULL); 368 ends[s] = (found != NULL); 369 } 370 seg_index[s] = seg_idx; 371 s++; 372 htable_segment_idx_iterator_next(&it); 373 } 374 ASSERT(s == scount); 375 376 /* 1) Segments beginning and ending at this point overlap other segments that 377 * begin and end at the same point and contact segments that only begin or 378 * only end at this point */ 379 for(s = 0; s < scount; s++) { 380 if(begins[s] && ends[s]) { 381 size_t j; 382 for(j = 0; j < scount; j++) { 383 if(j > s && begins[j] && ends[j]) { 384 ERR(register_segment_interaction(seg_index[s], seg_index[j], !dim_idx, 385 dimension->overlap, intersector)); 386 } 387 else if(begins[j] ^ ends[j]) { 388 ERR(register_segment_interaction(seg_index[s], seg_index[j], !dim_idx, 389 dimension->contact, intersector)); 390 } 391 } 392 } 393 } 394 395 /* 2) Segments only ending at this point overlap open segments */ 396 for(s = 0; s < scount; s++) { 397 if(!begins[s] && ends[s]) { 398 ERR(register_segment_interactions(seg_index[s], &open_segments, !dim_idx, 399 dimension->overlap, intersector)); 400 } 401 } 402 403 /* 3) Segments ending at this point are now closed */ 404 for(s = 0; s < scount; s++) { 405 if(ends[s]) { 406 size_t n = htable_segment_idx_erase(&open_segments, seg_index + s); 407 CHK(n == (begins[s] ? 0 : 1)); 408 } 409 } 410 411 /* 4) Segments beginning and ending at this point overlap open segments */ 412 for(s = 0; s < scount; s++) { 413 if(begins[s] && ends[s]) { 414 ERR(register_segment_interactions(seg_index[s], &open_segments, !dim_idx, 415 dimension->overlap, intersector)); 416 } 417 } 418 419 /* 5) Segments only beginning at this point are now open */ 420 for(s = 0; s < scount; s++) { 421 if(begins[s] && !ends[s]) { 422 char one = 1; 423 ERR(htable_segment_idx_set(&open_segments, seg_index + s, &one)); 424 } 425 } 426 427 /* 6) Segments only beginning at this point overlap open segments */ 428 for(s = 0; s < scount; s++) { 429 if(begins[s] && !ends[s]) { 430 ERR(register_segment_interactions(seg_index[s], &open_segments, !dim_idx, 431 dimension->overlap, intersector)); 432 } 433 } 434 } 435 436 exit: 437 MEM_RM(allocator, begins); 438 MEM_RM(allocator, ends); 439 MEM_RM(allocator, seg_index); 440 htable_segment_idx_release(&open_segments); 441 return res; 442 error: 443 goto exit; 444 } 445 446 static int64_t 447 safe_mul 448 (int64_t a, 449 int64_t b, 450 int* ovflw) 451 { 452 int64_t r; 453 if(b == 0) return 0; 454 r = a * b; 455 if (r / b != a) *ovflw = 1; 456 return r; 457 } 458 459 /* Check if a triangle is CCW (>0), CW (<0), or flat (=0) */ 460 static int 461 is_ccw 462 (Clipper2Lib::Point64* v1, 463 Clipper2Lib::Point64* v2, 464 Clipper2Lib::Point64* v3, 465 int* ovflw) 466 { 467 int64_t tmp1, tmp2; 468 ASSERT(v1 && v2 && v3); 469 /* Limited coordinate range garanties that sub computations stay in int64_t 470 * range */ 471 tmp1 = safe_mul(v2->x - v1->x, v3->y - v1->y, ovflw); 472 tmp2 = safe_mul(v3->x - v1->x, v2->y - v1->y, ovflw); 473 if(tmp1 < tmp2) return -1; 474 if(tmp1 > tmp2) return +1; 475 return 0; 476 } 477 478 /* Check if 2 segments intersect */ 479 static res_T 480 check_two_segments_intersection 481 (const struct intersector_segment* seg1, 482 const struct intersector_segment* seg2, 483 struct scpr_intersector_check_callbacks* callbacks, 484 struct scpr_intersector* intersector, 485 void* data) 486 { 487 res_T res = RES_OK; 488 size_t count, r11, r12, r21, r22; 489 Clipper2Lib::Point64 *v11, * v12, *v21, *v22; 490 int ccw1, ccw2, ccw3, ccw4, ovflw = 0; 491 const struct intersector_component* components; 492 struct scpr_polygon *polygon1, *polygon2; 493 uint32_t comp_idx1, comp_idx2; 494 495 ASSERT(seg1 && seg2 && callbacks); 496 497 components = darray_components_cdata_get(&intersector->components); 498 comp_idx1 = components[seg1->component].component; 499 comp_idx2 = components[seg2->component].component; 500 polygon1 = components[seg1->component].polygon; 501 polygon2 = components[seg2->component].polygon; 502 503 /* Get vertices */ 504 r11 = seg1->first_vertex; 505 ERR(scpr_polygon_get_vertices_count(polygon1, comp_idx1, &count)); 506 r12 = (r11 + 1) % count; 507 r21 = seg2->first_vertex; 508 ERR(scpr_polygon_get_vertices_count(polygon2, comp_idx2, &count)); 509 r22 = (r21 + 1) % count; 510 v11 = &polygon1->paths[comp_idx1][r11]; 511 v12 = &polygon1->paths[comp_idx1][r12]; 512 v21 = &polygon2->paths[comp_idx2][r21]; 513 v22 = &polygon2->paths[comp_idx2][r22]; 514 ASSERT(segments_bbox_interacts(v11, v12, v21, v22)); 515 516 /* Test triangles orientation */ 517 ccw1 = is_ccw(v11, v12, v21, &ovflw); 518 ccw2 = is_ccw(v11, v12, v22, &ovflw); 519 ccw3 = is_ccw(v21, v22, v11, &ovflw); 520 ccw4 = is_ccw(v21, v22, v12, &ovflw); 521 if(ovflw) { 522 res = RES_BAD_ARG; 523 goto error; 524 } 525 /* Analyse ccw results */ 526 if(ccw1 * ccw2 > 0 && ccw3 * ccw4 > 0) { 527 /* No intersection at all */ 528 } 529 else if(ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0) { 530 /* overlapping segments */ 531 if(callbacks->overlapping_segments) { 532 struct scpr_callback_segment arg1, arg2; 533 arg1.polygon = polygon1; 534 arg1.component = comp_idx1; 535 arg1.first_vertex = r11; 536 arg1.last_vertex = r12; 537 arg2.polygon = polygon2; 538 arg2.component = comp_idx2; 539 arg2.first_vertex = r21; 540 arg2.last_vertex = r22; 541 if(callbacks->overlapping_segments(&arg1, &arg2, data)) { 542 res = RES_BAD_ARG; 543 goto error; 544 } 545 } 546 } 547 else if(ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0) { 548 /* Basic segment intersection */ 549 if(callbacks->simple_intersection) { 550 struct scpr_callback_segment arg1, arg2; 551 arg1.polygon = polygon1; 552 arg1.component = comp_idx1; 553 arg1.first_vertex = r11; 554 arg1.last_vertex = r12; 555 arg2.polygon = polygon2; 556 arg2.component = comp_idx2; 557 arg2.first_vertex = r21; 558 arg2.last_vertex = r22; 559 if(callbacks->simple_intersection(&arg1, &arg2, data)) { 560 res = RES_BAD_ARG; 561 goto error; 562 } 563 } 564 } 565 566 exit: 567 return res; 568 error: 569 goto exit; 570 } 571 572 /* Test intersection of all the registered pairs of interacting segments */ 573 static res_T 574 check_interacting_pairs 575 (struct scpr_intersector* intersector, 576 struct scpr_intersector_check_callbacks* callbacks, 577 void* data) 578 { 579 res_T res = RES_OK; 580 struct htable_interacting_segments_iterator it, end; 581 const struct intersector_segment* segments; 582 583 ASSERT(intersector && callbacks); 584 585 segments = darray_segments_cdata_get(&intersector->segments); 586 htable_interacting_segments_begin(&intersector->interacting_segments, &it); 587 htable_interacting_segments_end(&intersector->interacting_segments, &end); 588 /* Loop on interacting segments */ 589 while(!htable_interacting_segments_iterator_eq(&it, &end)) { 590 unsigned char overlapping 591 = *htable_interacting_segments_iterator_data_get(&it); 592 if(overlapping & SOME_OVERLAP 593 && overlapping & SOMETHING_X && overlapping & SOMETHING_Y) 594 { 595 struct intersector_segment_pair* pair 596 = htable_interacting_segments_iterator_key_get(&it); 597 const struct intersector_segment* seg1 = segments + pair->rank1; 598 const struct intersector_segment* seg2 = segments + pair->rank2; 599 ERR(check_two_segments_intersection(seg1, seg2, callbacks, intersector, data)); 600 } 601 htable_interacting_segments_iterator_next(&it); 602 } 603 604 exit: 605 return res; 606 error: 607 goto exit; 608 } 609 610 /******************************************************************************* 611 * Exported functions 612 ******************************************************************************/ 613 res_T 614 scpr_intersector_create 615 (struct scpr_device* device, 616 struct scpr_intersector** out_intersector) 617 { 618 res_T res = RES_OK; 619 struct scpr_intersector* intersector = NULL; 620 struct mem_allocator* allocator; 621 622 if(!device || ! out_intersector) { 623 res = RES_BAD_ARG; 624 goto error; 625 } 626 627 allocator = device->allocator; 628 intersector = (struct scpr_intersector*)MEM_ALLOC(allocator, sizeof(*intersector)); 629 if(!intersector) { 630 res = RES_MEM_ERR; 631 goto error; 632 } 633 ref_init(&intersector->ref); 634 intersector->device = device; 635 ERR(scpr_device_ref_get(device)); 636 darray_segments_init(allocator, &intersector->segments); 637 init_dimension(allocator, intersector->dimensions, OVERLAP_X, CONTACT_X); 638 init_dimension(allocator, intersector->dimensions + 1, OVERLAP_Y, CONTACT_Y); 639 htable_interacting_segments_init(allocator, &intersector->interacting_segments); 640 htable_registered_components_init(allocator, &intersector->registered_components); 641 darray_components_init(allocator, &intersector->components); 642 643 exit: 644 if(out_intersector) *out_intersector = intersector; 645 return res; 646 error: 647 if(intersector) { 648 SCPR(intersector_ref_put(intersector)); 649 intersector = NULL; 650 } 651 goto exit; 652 } 653 654 res_T 655 scpr_intersector_ref_get 656 (struct scpr_intersector* intersector) 657 { 658 if(!intersector) return RES_BAD_ARG; 659 ref_get(&intersector->ref); 660 return RES_OK; 661 } 662 663 res_T 664 scpr_intersector_ref_put 665 (struct scpr_intersector* intersector) 666 { 667 if(!intersector) return RES_BAD_ARG; 668 ref_put(&intersector->ref, intersector_release); 669 return RES_OK; 670 } 671 672 res_T 673 scpr_intersector_register_polygon 674 (struct scpr_intersector* intersector, 675 struct scpr_polygon* polygon) 676 { 677 res_T res = RES_OK; 678 size_t i; 679 680 if(!intersector || !polygon) { 681 res = RES_BAD_ARG; 682 goto error; 683 } 684 685 for(i = 0; i < polygon->paths.size(); i++) { 686 ERR(scpr_intersector_register_component(intersector, polygon, i)); 687 } 688 689 exit: 690 return res; 691 error: 692 goto exit; 693 } 694 695 res_T 696 scpr_intersector_register_component 697 (struct scpr_intersector* intersector, 698 struct scpr_polygon* polygon, 699 const size_t icomponent) 700 { 701 res_T res = RES_OK; 702 uint32_t i; 703 size_t new_count, prev_count, c; 704 struct intersector_component comp; 705 char *found, one = 1; 706 707 if(!intersector || !polygon || icomponent >= polygon->paths.size()) { 708 res = RES_BAD_ARG; 709 goto error; 710 } 711 712 /* Check single registration */ 713 comp.polygon = polygon; 714 comp.component = (uint32_t)icomponent; 715 found = htable_registered_components_find(&intersector->registered_components, 716 &comp); 717 if(found) { 718 logger_print(intersector->device->logger, LOG_ERROR, 719 "Component %zu already registered.\n", icomponent); 720 res = RES_BAD_ARG; 721 goto error; 722 } 723 c = htable_registered_components_size_get(&intersector->registered_components); 724 if(c >= UINT32_MAX) { 725 logger_print(intersector->device->logger, LOG_ERROR, 726 "Too many components registered.\n"); 727 res = RES_BAD_ARG; 728 goto error; 729 } 730 ASSERT(c == darray_components_size_get(&intersector->components)); 731 ERR(htable_registered_components_set(&intersector->registered_components, 732 &comp, &one)); 733 ERR(darray_components_push_back(&intersector->components, &comp)); 734 735 prev_count = darray_segments_size_get(&intersector->segments); 736 ASSERT(prev_count <= UINT32_MAX); 737 new_count = polygon->paths[icomponent].size(); 738 if(prev_count + new_count > UINT32_MAX) { 739 logger_print(intersector->device->logger, LOG_ERROR, 740 "Too many segments registered.\n"); 741 res = RES_BAD_ARG; 742 goto error; 743 } 744 ERR(darray_segments_resize(&intersector->segments, 745 (uint32_t)(prev_count + new_count))); 746 747 for(i = 0; i < new_count; i++) { 748 Clipper2Lib::Point64 *p0, *p1; 749 uint32_t seg_idx = (uint32_t)(prev_count + i); 750 struct intersector_segment* segment 751 = darray_segments_data_get(&intersector->segments) + seg_idx; 752 segment->component = (uint32_t)c; 753 segment->first_vertex = i; 754 p0 = &polygon->paths[icomponent][i]; 755 p1 = &polygon->paths[icomponent][(i+1)%new_count]; 756 ERR(register_point(intersector, 0, p0->x, seg_idx)); 757 ERR(register_point(intersector, 0, p1->x, seg_idx)); 758 ERR(register_point(intersector, 1, p0->y, seg_idx)); 759 ERR(register_point(intersector, 1, p1->y, seg_idx)); 760 } 761 762 exit: 763 return res; 764 error: 765 goto exit; 766 } 767 768 res_T 769 scpr_intersector_check 770 (struct scpr_intersector* intersector, 771 struct scpr_intersector_check_callbacks* callbacks, 772 void* data) 773 { 774 int i; 775 res_T res = RES_OK; 776 777 if(!intersector || !callbacks 778 || (!callbacks->simple_intersection && !callbacks->overlapping_segments)) 779 { 780 res = RES_BAD_ARG; 781 goto error; 782 } 783 784 /* Construct candidates for intersection */ 785 for(i = 0; i < 2; i++) { 786 sort_points(&intersector->dimensions[i]); 787 ERR(register_interaction(i, intersector)); 788 } 789 /* Check intersections */ 790 ERR(check_interacting_pairs(intersector, callbacks, data)); 791 792 exit: 793 return res; 794 error: 795 goto exit; 796 }