Blender V5.3
scanfill.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
17
18#include <cstdio>
19#include <cstdlib>
20#include <cstring>
21
22#include <algorithm>
23
24#include "MEM_guardedalloc.h"
25
26#include "DNA_listBase.h"
27
28#include "BLI_array_utils.hh"
29#include "BLI_listbase.hh"
30#include "BLI_math_geom_c.hh"
31#include "BLI_math_matrix_c.hh"
32#include "BLI_math_vector_c.hh"
33#include "BLI_memarena.hh"
34#include "BLI_utildefines.hh"
35
36#include "BLI_scanfill.hh" /* own include */
37
38#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
39
40namespace blender {
41
42namespace {
43
44/* local types */
45struct PolyFill {
46 uint edges, verts;
47 float min_xy[2], max_xy[2];
48 ushort nr;
49 uchar f;
50};
51
52struct ScanFillVertLink {
53 ScanFillVert *vert;
54 ScanFillEdge *edge_first, *edge_last;
55};
56
57} // namespace
58
59/* Local functions. */
60
61#define SF_EPSILON 0.00003f
62#define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)
63
65#define SF_VERT_NEW 0 /* all new verts have this flag set */
66#define SF_VERT_AVAILABLE 1 /* available - in an edge */
67#define SF_VERT_ZERO_LEN 2
68
70/* Optionally set ScanFillEdge f to this to mark original boundary edges.
71 * Only needed if there are internal diagonal edges passed to BLI_scanfill_calc. */
72#define SF_EDGE_NEW 0 /* all new edges have this flag set */
73// #define SF_EDGE_BOUNDARY 1 /* UNUSED */
74#define SF_EDGE_INTERNAL 2 /* edge is created while scan-filling */
75
77#define SF_POLY_NEW 0 /* all polys initialized to this */
78#define SF_POLY_VALID 1 /* has at least 3 verts */
79
80/* **** FUNCTIONS FOR QSORT *************************** */
81
82static int vergscdata(const void *a1, const void *a2)
83{
84 const ScanFillVertLink *x1 = static_cast<const ScanFillVertLink *>(a1);
85 const ScanFillVertLink *x2 = static_cast<const ScanFillVertLink *>(a2);
86
87 if (x1->vert->xy[1] < x2->vert->xy[1]) {
88 return 1;
89 }
90 if (x1->vert->xy[1] > x2->vert->xy[1]) {
91 return -1;
92 }
93 if (x1->vert->xy[0] > x2->vert->xy[0]) {
94 return 1;
95 }
96 if (x1->vert->xy[0] < x2->vert->xy[0]) {
97 return -1;
98 }
99
100 return 0;
101}
102
103/* **** FILL ROUTINES *************************** */
104
106{
107 ScanFillVert *sf_v;
108
110
111 BLI_addtail(&sf_ctx->fillvertbase, sf_v);
112
113 sf_v->tmp.p = nullptr;
114 copy_v3_v3(sf_v->co, vec);
115
116 /* just zero out the rest */
117 zero_v2(sf_v->xy);
118 sf_v->keyindex = 0;
119 sf_v->poly_nr = sf_ctx->poly_nr;
120 sf_v->edge_count = 0;
121 sf_v->f = SF_VERT_NEW;
122 sf_v->user_flag = 0;
123
124 return sf_v;
125}
126
128{
129 ScanFillEdge *sf_ed;
130
132 BLI_addtail(&sf_ctx->filledgebase, sf_ed);
133
134 sf_ed->v1 = v1;
135 sf_ed->v2 = v2;
136
137 /* just zero out the rest */
138 sf_ed->poly_nr = sf_ctx->poly_nr;
139 sf_ed->f = SF_EDGE_NEW;
140 sf_ed->user_flag = 0;
141 sf_ed->tmp.c = 0;
142
143 return sf_ed;
144}
145
146static void addfillface(ScanFillContext *sf_ctx,
147 ScanFillVert *v1,
149 ScanFillVert *v3)
150{
151 /* does not make edges */
152 ScanFillFace *sf_tri;
153
154 sf_tri = BLI_memarena_alloc<ScanFillFace>(sf_ctx->arena);
155 BLI_addtail(&sf_ctx->fillfacebase, sf_tri);
156
157 sf_tri->v1 = v1;
158 sf_tri->v2 = v2;
159 sf_tri->v3 = v3;
160}
161
162static bool boundisect(const PolyFill *pf2, const PolyFill *pf1)
163{
164 /* has pf2 been touched (intersected) by pf1 ? with bounding box */
165 /* test first if polys exist */
166
167 if (pf1->edges == 0 || pf2->edges == 0) {
168 return false;
169 }
170
171 if (pf2->max_xy[0] < pf1->min_xy[0]) {
172 return false;
173 }
174 if (pf2->max_xy[1] < pf1->min_xy[1]) {
175 return false;
176 }
177
178 if (pf2->min_xy[0] > pf1->max_xy[0]) {
179 return false;
180 }
181 if (pf2->min_xy[1] > pf1->max_xy[1]) {
182 return false;
183 }
184
185 return true;
186}
187
188static void fill_target_map_recursive(const PolyFill *__restrict pf_list,
189 const uint pf_len,
190 const uint pf_target,
191 const uint pf_test,
192 uint *__restrict target_map)
193{
194 const PolyFill *pf_a = pf_list + pf_test;
195 for (uint pf_b_index = pf_target + 1; pf_b_index < pf_len; pf_b_index++) {
196 if (target_map[pf_b_index] != pf_b_index) {
197 /* All intersections have already been identified for this polygon. */
198 continue;
199 }
200 BLI_assert(pf_b_index != pf_test);
201 const PolyFill *pf_b = pf_list + pf_b_index;
202 if (boundisect(pf_a, pf_b)) {
203 target_map[pf_b_index] = pf_target;
204 fill_target_map_recursive(pf_list, pf_len, pf_target, pf_b_index, target_map);
205 }
206 }
207}
208
209/* add pf2 to pf1 */
210static void mergepolysSimp(ScanFillContext *sf_ctx, PolyFill *pf1, PolyFill *pf2)
211{
212 /* replace old poly numbers */
213 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
214 if (eve.poly_nr == pf2->nr) {
215 eve.poly_nr = pf1->nr;
216 }
217 }
218
219 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
220 if (eed.poly_nr == pf2->nr) {
221 eed.poly_nr = pf1->nr;
222 }
223 }
224
225 /* Join. */
226 pf1->verts += pf2->verts;
227 pf1->edges += pf2->edges;
228
229 pf1->max_xy[0] = std::max(pf1->max_xy[0], pf2->max_xy[0]);
230 pf1->max_xy[1] = std::max(pf1->max_xy[1], pf2->max_xy[1]);
231
232 pf1->min_xy[0] = std::min(pf1->min_xy[0], pf2->min_xy[0]);
233 pf1->min_xy[1] = std::min(pf1->min_xy[1], pf2->min_xy[1]);
234
235 pf1->f = (pf1->f | pf2->f);
236
237 /* Clear the other one. */
238 pf2->verts = pf2->edges = 0;
239}
240
241static bool testedgeside(const float v1[2], const float v2[2], const float v3[2])
242/* is v3 to the right of v1-v2 ? With exception: v3 == v1 || v3 == v2 */
243{
244 float inp;
245
246 inp = (v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] - v2[1]) * (v1[0] - v3[0]);
247
248 if (inp < 0.0f) {
249 return false;
250 }
251 if (inp == 0.0f) {
252 if (v1[0] == v3[0] && v1[1] == v3[1]) {
253 return false;
254 }
255 if (v2[0] == v3[0] && v2[1] == v3[1]) {
256 return false;
257 }
258 }
259 return true;
260}
261
262static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed)
263{
264 /* find first edge to the right of eed, and insert eed before that */
266 float fac, fac1, x, y;
267
268 if (sc->edge_first == nullptr) {
269 sc->edge_first = sc->edge_last = eed;
270 eed->prev = eed->next = nullptr;
271 return true;
272 }
273
274 x = eed->v1->xy[0];
275 y = eed->v1->xy[1];
276
277 fac1 = eed->v2->xy[1] - y;
278 if (fac1 == 0.0f) {
279 fac1 = 1.0e10f * (eed->v2->xy[0] - x);
280 }
281 else {
282 fac1 = (x - eed->v2->xy[0]) / fac1;
283 }
284
285 for (ed = sc->edge_first; ed; ed = ed->next) {
286
287 if (ed->v2 == eed->v2) {
288 return false;
289 }
290
291 fac = ed->v2->xy[1] - y;
292 if (fac == 0.0f) {
293 fac = 1.0e10f * (ed->v2->xy[0] - x);
294 }
295 else {
296 fac = (x - ed->v2->xy[0]) / fac;
297 }
298
299 if (fac > fac1) {
300 break;
301 }
302 }
303 if (ed) {
304 BLI_insertlinkbefore(reinterpret_cast<ListBase *>(&(sc->edge_first)), ed, eed);
305 }
306 else {
307 BLI_addtail(reinterpret_cast<ListBase *>(&(sc->edge_first)), eed);
308 }
309
310 return true;
311}
312
313static ScanFillVertLink *addedgetoscanlist(ScanFillVertLink *scdata, ScanFillEdge *eed, uint len)
314{
315 /* inserts edge at correct location in ScanFillVertLink list */
316 /* returns sc when edge already exists */
317 ScanFillVertLink *sc, scsearch;
318 ScanFillVert *eve;
319
320 /* which vert is left-top? */
321 if (eed->v1->xy[1] == eed->v2->xy[1]) {
322 if (eed->v1->xy[0] > eed->v2->xy[0]) {
323 eve = eed->v1;
324 eed->v1 = eed->v2;
325 eed->v2 = eve;
326 }
327 }
328 else if (eed->v1->xy[1] < eed->v2->xy[1]) {
329 eve = eed->v1;
330 eed->v1 = eed->v2;
331 eed->v2 = eve;
332 }
333 /* find location in list */
334 scsearch.vert = eed->v1;
335 sc = static_cast<ScanFillVertLink *>(
336 bsearch(&scsearch, scdata, len, sizeof(ScanFillVertLink), vergscdata));
337
338 if (sc == nullptr) [[unlikely]] {
339 printf("Error in search edge: %p\n", static_cast<void *>(eed));
340 }
341 else if (addedgetoscanvert(sc, eed) == false) {
342 return sc;
343 }
344
345 return nullptr;
346}
347
351static bool boundinsideEV(const ScanFillEdge *eed, const ScanFillVert *eve)
352{
353 float minx, maxx, miny, maxy;
354
355 if (eed->v1->xy[0] < eed->v2->xy[0]) {
356 minx = eed->v1->xy[0];
357 maxx = eed->v2->xy[0];
358 }
359 else {
360 minx = eed->v2->xy[0];
361 maxx = eed->v1->xy[0];
362 }
363 if (eve->xy[0] >= minx && eve->xy[0] <= maxx) {
364 if (eed->v1->xy[1] < eed->v2->xy[1]) {
365 miny = eed->v1->xy[1];
366 maxy = eed->v2->xy[1];
367 }
368 else {
369 miny = eed->v2->xy[1];
370 maxy = eed->v1->xy[1];
371 }
372 if (eve->xy[1] >= miny && eve->xy[1] <= maxy) {
373 return true;
374 }
375 }
376 return false;
377}
378
380{
381 /* only vertices with (->edge_count == 1) are being tested for
382 * being close to an edge, if true insert */
383
384 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
385 if (eve.edge_count == 1) {
386 /* find the edge which has vertex eve,
387 * NOTE: we _know_ this will crash if 'ed1' becomes nullptr
388 * but this will never happen. */
389 ScanFillEdge *ed1 = sf_ctx->filledgebase.first();
390 for (; !(ed1->v1 == &eve || ed1->v2 == &eve); ed1 = ed1->next) {
391 /* do nothing */
392 }
393
394 if (ed1->v1 == &eve) {
395 ed1->v1 = ed1->v2;
396 ed1->v2 = &eve;
397 }
398
399 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
400 if (&eve != eed.v1 && &eve != eed.v2 && eve.poly_nr == eed.poly_nr) {
401 if (compare_v2v2(eve.xy, eed.v1->xy, SF_EPSILON)) {
402 ed1->v2 = eed.v1;
403 eed.v1->edge_count++;
404 eve.edge_count = 0;
405 break;
406 }
407 if (compare_v2v2(eve.xy, eed.v2->xy, SF_EPSILON)) {
408 ed1->v2 = eed.v2;
409 eed.v2->edge_count++;
410 eve.edge_count = 0;
411 break;
412 }
413
414 if (boundinsideEV(&eed, &eve)) {
415 const float dist = dist_squared_to_line_v2(eed.v1->xy, eed.v2->xy, eve.xy);
416 if (dist < SF_EPSILON_SQ) {
417 /* new edge */
418 ed1 = BLI_scanfill_edge_add(sf_ctx, eed.v1, &eve);
419
420 // printf("fill: vertex near edge %x\n", eve);
421 ed1->poly_nr = eed.poly_nr;
422 eed.v1 = &eve;
423 eve.edge_count = 3;
424 break;
425 }
426 }
427 }
428 }
429 }
430 }
431}
432
433static void splitlist(ScanFillContext *sf_ctx,
434 ListBaseT<ScanFillVert> *tempve,
435 ListBaseT<ScanFillEdge> *temped,
436 ushort nr)
437{
438 /* Everything is in temp-list, write only poly nr to fill-list. */
439 BLI_movelisttolist(tempve, &sf_ctx->fillvertbase);
440 BLI_movelisttolist(temped, &sf_ctx->filledgebase);
441
442 for (ScanFillVert &eve : tempve->items_mutable()) {
443 if (eve.poly_nr == nr) {
444 BLI_remlink(tempve, &eve);
445 BLI_addtail(&sf_ctx->fillvertbase, &eve);
446 }
447 }
448
449 for (ScanFillEdge &eed : temped->items_mutable()) {
450 if (eed.poly_nr == nr) {
451 BLI_remlink(temped, &eed);
452 BLI_addtail(&sf_ctx->filledgebase, &eed);
453 }
454 }
455}
456
457static uint scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
458{
459 ScanFillVertLink *scdata;
460 ScanFillVertLink *sc = nullptr, *sc1;
461 ScanFillVert *v1, *v2, *v3;
462 uint a, b, verts, maxface, totface;
463 const ushort nr = pf->nr;
464 bool twoconnected = false;
465
466 /* PRINTS */
467#if 0
468 verts = pf->verts;
469 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
470 printf("vert: %x co: %f %f\n", &eve, eve.xy[0], eve.xy[1]);
471 }
472
473 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
474 printf("edge: %x verts: %x %x\n", &eed, eed.v1, eed.v2);
475 }
476#endif
477
478 /* STEP 0: remove zero sized edges */
480 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
481 if (equals_v2v2(eed.v1->xy, eed.v2->xy)) {
482 if (eed.v1->f == SF_VERT_ZERO_LEN && eed.v2->f != SF_VERT_ZERO_LEN) {
483 eed.v2->f = SF_VERT_ZERO_LEN;
484 eed.v2->tmp.v = eed.v1->tmp.v;
485 }
486 else if (eed.v2->f == SF_VERT_ZERO_LEN && eed.v1->f != SF_VERT_ZERO_LEN) {
487 eed.v1->f = SF_VERT_ZERO_LEN;
488 eed.v1->tmp.v = eed.v2->tmp.v;
489 }
490 else if (eed.v2->f == SF_VERT_ZERO_LEN && eed.v1->f == SF_VERT_ZERO_LEN) {
491 eed.v1->tmp.v = eed.v2->tmp.v;
492 }
493 else {
494 eed.v2->f = SF_VERT_ZERO_LEN;
495 eed.v2->tmp.v = eed.v1;
496 }
497 }
498 }
499 }
500
501 /* STEP 1: make using FillVert and FillEdge lists a sorted
502 * ScanFillVertLink list
503 */
504 sc = scdata = MEM_new_array_uninitialized<ScanFillVertLink>(pf->verts, "Scanfill1");
505 verts = 0;
506 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
507 if (eve.poly_nr == nr) {
508 if (eve.f != SF_VERT_ZERO_LEN) {
509 verts++;
510 eve.f = SF_VERT_NEW; /* Flag for connect edges later on. */
511 sc->vert = &eve;
512 sc->edge_first = sc->edge_last = nullptr;
513 /* NOTE: debug print only will work for curve poly-fill, union is in use for mesh. */
514#if 0
515 if (even->tmp.v == nullptr) {
516 eve->tmp.u = verts;
517 }
518#endif
519 sc++;
520 }
521 }
522 }
523
524 qsort(scdata, verts, sizeof(ScanFillVertLink), vergscdata);
525
527 for (ScanFillEdge &eed : sf_ctx->filledgebase.items_mutable()) {
528 BLI_remlink(&sf_ctx->filledgebase, &eed);
529 /* This code is for handling zero-length edges that get
530 * collapsed in step 0. It was removed for some time to
531 * fix trunk bug #4544, so if that comes back, this code
532 * may need some work, or there will have to be a better
533 * fix to #4544.
534 *
535 * warning, this can hang on un-ordered edges, see: #33281.
536 * for now disable #BLI_SCANFILL_CALC_REMOVE_DOUBLES for ngons.
537 */
538 if (eed.v1->f == SF_VERT_ZERO_LEN) {
539 v1 = eed.v1;
540 while ((eed.v1->f == SF_VERT_ZERO_LEN) && (eed.v1->tmp.v != v1) &&
541 (eed.v1 != eed.v1->tmp.v))
542 {
543 eed.v1 = eed.v1->tmp.v;
544 }
545 }
546 if (eed.v2->f == SF_VERT_ZERO_LEN) {
547 v2 = eed.v2;
548 while ((eed.v2->f == SF_VERT_ZERO_LEN) && (eed.v2->tmp.v != v2) &&
549 (eed.v2 != eed.v2->tmp.v))
550 {
551 eed.v2 = eed.v2->tmp.v;
552 }
553 }
554 if (eed.v1 != eed.v2) {
555 addedgetoscanlist(scdata, &eed, verts);
556 }
557 }
558 }
559 else {
560 for (ScanFillEdge &eed : sf_ctx->filledgebase.items_mutable()) {
561 BLI_remlink(&sf_ctx->filledgebase, &eed);
562 if (eed.v1 != eed.v2) {
563 addedgetoscanlist(scdata, &eed, verts);
564 }
565 }
566 }
567#if 0
568 sc = sf_ctx->_scdata;
569 for (a = 0; a < verts; a++) {
570 printf("\nscvert: %x\n", sc->vert);
571 for (eed = sc->edge_first; eed; eed = eed->next) {
572 printf(" ed %x %x %x\n", eed, eed->v1, eed->v2);
573 }
574 sc++;
575 }
576#endif
577
578 /* STEP 2: FILL LOOP */
579
580 if (pf->f == SF_POLY_NEW) {
581 twoconnected = true;
582 }
583
584 /* (temporal) security: never much more faces than vertices */
585 totface = 0;
586 if (flag & BLI_SCANFILL_CALC_HOLES) {
587 maxface = 2 * verts; /* 2*verts: based at a filled circle within a triangle */
588 }
589 else {
590 /* when we don't calc any holes, we assume face is a non overlapping loop */
591 maxface = verts - 2;
592 }
593
594 sc = scdata;
595 for (a = 0; a < verts; a++) {
596 // printf("VERTEX %d index %d\n", a, sc->vert->tmp.u);
597 /* Set connect-flags. */
598 ScanFillEdge *ed1, *ed2, *ed3, *eed_next;
599 for (ed1 = sc->edge_first; ed1; ed1 = eed_next) {
600 eed_next = ed1->next;
601 if (ed1->v1->edge_count == 1 || ed1->v2->edge_count == 1) {
602 BLI_remlink(reinterpret_cast<ListBase *>(&(sc->edge_first)), ed1);
603 BLI_addtail(&sf_ctx->filledgebase, ed1);
604 if (ed1->v1->edge_count > 1) {
605 ed1->v1->edge_count--;
606 }
607 if (ed1->v2->edge_count > 1) {
608 ed1->v2->edge_count--;
609 }
610 }
611 else {
612 ed1->v2->f = SF_VERT_AVAILABLE;
613 }
614 }
615 while (sc->edge_first) { /* for as long there are edges */
616 ed1 = sc->edge_first;
617 ed2 = ed1->next;
618
619 /* Commented out: the ESC here delivers corrupted memory
620 * (and doesn't work during grab). */
621#if 0
622 if (callLocalInterruptCallBack()){
623 break;
624 }
625#endif
626 if (totface >= maxface) {
627 // printf("Fill error: endless loop. Escaped at vert %d, tot: %d.\n", a, verts);
628 a = verts;
629 break;
630 }
631 if (ed2 == nullptr) {
632 sc->edge_first = sc->edge_last = nullptr;
633 // printf("just 1 edge to vert\n");
634 BLI_addtail(&sf_ctx->filledgebase, ed1);
635 ed1->v2->f = SF_VERT_NEW;
636 ed1->v1->edge_count--;
637 ed1->v2->edge_count--;
638 }
639 else {
640 /* test rest of vertices */
641 ScanFillVertLink *best_sc = nullptr;
642 float angle_best_cos = -1.0f;
643 float miny;
644 bool firsttime = false;
645
646 v1 = ed1->v2;
647 v2 = ed1->v1;
648 v3 = ed2->v2;
649
650 /* this happens with a serial of overlapping edges */
651 if (v1 == v2 || v2 == v3) {
652 break;
653 }
654
655 // printf("test verts %d %d %d\n", v1->tmp.u, v2->tmp.u, v3->tmp.u);
656 miny = min_ff(v1->xy[1], v3->xy[1]);
657 sc1 = sc + 1;
658
659 for (b = a + 1; b < verts; b++, sc1++) {
660 if (sc1->vert->f == SF_VERT_NEW) {
661 if (sc1->vert->xy[1] <= miny) {
662 break;
663 }
664 if (testedgeside(v1->xy, v2->xy, sc1->vert->xy)) {
665 if (testedgeside(v2->xy, v3->xy, sc1->vert->xy)) {
666 if (testedgeside(v3->xy, v1->xy, sc1->vert->xy)) {
667 /* point is in triangle */
668
669 /* Because multiple points can be inside triangle
670 * (concave holes) we continue searching and pick the
671 * one with sharpest corner. */
672 if (best_sc == nullptr) {
673 /* even without holes we need to keep checking #35861. */
674 best_sc = sc1;
675 }
676 else {
677 /* Prevent angle calc for the simple cases
678 * only 1 vertex is found. */
679 if (firsttime == false) {
680 angle_best_cos = cos_v2v2v2(v2->xy, v1->xy, best_sc->vert->xy);
681 firsttime = true;
682 }
683
684 const float angle_test_cos = cos_v2v2v2(v2->xy, v1->xy, sc1->vert->xy);
685 if (angle_test_cos > angle_best_cos) {
686 best_sc = sc1;
687 angle_best_cos = angle_test_cos;
688 }
689 }
690 }
691 }
692 }
693 }
694 }
695
696 if (best_sc) {
697 /* make new edge, and start over */
698 // printf("add new edge %d %d and start again\n", v2->tmp.u, best_sc->vert->tmp.u);
699
700 ed3 = BLI_scanfill_edge_add(sf_ctx, v2, best_sc->vert);
701 BLI_remlink(&sf_ctx->filledgebase, ed3);
702 BLI_insertlinkbefore(reinterpret_cast<ListBase *>(&(sc->edge_first)), ed2, ed3);
703 ed3->v2->f = SF_VERT_AVAILABLE;
704 ed3->f = SF_EDGE_INTERNAL;
705 ed3->v1->edge_count++;
706 ed3->v2->edge_count++;
707 }
708 else {
709 /* new triangle */
710 // printf("add face %d %d %d\n", v1->tmp.u, v2->tmp.u, v3->tmp.u);
711 addfillface(sf_ctx, v1, v2, v3);
712 totface++;
713 BLI_remlink(reinterpret_cast<ListBase *>(&(sc->edge_first)), ed1);
714 BLI_addtail(&sf_ctx->filledgebase, ed1);
715 ed1->v2->f = SF_VERT_NEW;
716 ed1->v1->edge_count--;
717 ed1->v2->edge_count--;
718 /* ed2 can be removed when it's a boundary edge */
719 if (((ed2->f == SF_EDGE_NEW) && twoconnected) /* || (ed2->f == SF_EDGE_BOUNDARY) */) {
720 BLI_remlink(reinterpret_cast<ListBase *>(&(sc->edge_first)), ed2);
721 BLI_addtail(&sf_ctx->filledgebase, ed2);
722 ed2->v2->f = SF_VERT_NEW;
723 ed2->v1->edge_count--;
724 ed2->v2->edge_count--;
725 }
726
727 /* new edge */
728 ed3 = BLI_scanfill_edge_add(sf_ctx, v1, v3);
729 BLI_remlink(&sf_ctx->filledgebase, ed3);
730 ed3->f = SF_EDGE_INTERNAL;
731 ed3->v1->edge_count++;
732 ed3->v2->edge_count++;
733
734 // printf("add new edge %x %x\n", v1, v3);
735 sc1 = addedgetoscanlist(scdata, ed3, verts);
736
737 if (sc1) { /* ed3 already exists: remove if a boundary */
738 // printf("Edge exists\n");
739 ed3->v1->edge_count--;
740 ed3->v2->edge_count--;
741
742 for (ed3 = sc1->edge_first; ed3; ed3 = ed3->next) {
743 if ((ed3->v1 == v1 && ed3->v2 == v3) || (ed3->v1 == v3 && ed3->v2 == v1)) {
744 if (twoconnected /* || (ed3->f == SF_EDGE_BOUNDARY) */) {
745 BLI_remlink(reinterpret_cast<ListBase *>(&(sc1->edge_first)), ed3);
746 BLI_addtail(&sf_ctx->filledgebase, ed3);
747 ed3->v1->edge_count--;
748 ed3->v2->edge_count--;
749 }
750 break;
751 }
752 }
753 }
754 }
755 }
756
757 /* test for loose edges */
758 for (ed1 = sc->edge_first; ed1; ed1 = eed_next) {
759 eed_next = ed1->next;
760 if (ed1->v1->edge_count < 2 || ed1->v2->edge_count < 2) {
761 BLI_remlink(reinterpret_cast<ListBase *>(&(sc->edge_first)), ed1);
762 BLI_addtail(&sf_ctx->filledgebase, ed1);
763 if (ed1->v1->edge_count > 1) {
764 ed1->v1->edge_count--;
765 }
766 if (ed1->v2->edge_count > 1) {
767 ed1->v2->edge_count--;
768 }
769 }
770 }
771 /* done with loose edges */
772 }
773
774 sc++;
775 }
776
777 MEM_delete(scdata);
778
779 BLI_assert(totface <= maxface);
780
781 return totface;
782}
783
785{
786 memset(sf_ctx, 0, sizeof(*sf_ctx));
787 sf_ctx->poly_nr = SF_POLY_UNSET;
789}
790
792{
793 memset(sf_ctx, 0, sizeof(*sf_ctx));
794 sf_ctx->poly_nr = SF_POLY_UNSET;
795 sf_ctx->arena = arena;
796}
797
799{
800 BLI_memarena_free(sf_ctx->arena);
801 sf_ctx->arena = nullptr;
802
803 sf_ctx->fillvertbase.clear_no_delete();
804 sf_ctx->filledgebase.clear_no_delete();
805 sf_ctx->fillfacebase.clear_no_delete();
806}
807
809{
810 BLI_memarena_clear(arena);
811 BLI_assert(sf_ctx->arena == arena);
812
813 sf_ctx->fillvertbase.clear_no_delete();
814 sf_ctx->filledgebase.clear_no_delete();
815 sf_ctx->fillfacebase.clear_no_delete();
816}
817
818uint BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const float nor_proj[3])
819{
820 /*
821 * - fill works with its own lists, so create that first (no faces!)
822 * - for vertices, put in ->tmp.v the old pointer
823 * - struct elements xs en ys are not used here: don't hide stuff in it
824 * - edge flag ->f becomes 2 when it's a new edge
825 * - mode: & 1 is check for crossings, then create edges (TO DO )
826 * - returns number of triangle faces added.
827 */
828 ListBaseT<ScanFillVert> tempve;
829 ListBaseT<ScanFillEdge> temped;
830 PolyFill *pflist, *pf;
831 float *min_xy_p, *max_xy_p;
832 uint totfaces = 0; /* total faces added */
833 ushort a, poly = 0;
834 bool ok;
835 float mat_2d[3][3];
836
837 BLI_assert(!nor_proj || len_squared_v3(nor_proj) > FLT_EPSILON);
838
839#ifndef NDEBUG
840 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
841 /* These values used to be set,
842 * however they should always be zeroed so check instead. */
843 BLI_assert(eve.f == 0);
844 BLI_assert(sf_ctx->poly_nr || eve.poly_nr == 0);
845 BLI_assert(eve.edge_count == 0);
846 }
847#endif
848
849 /* first test vertices if they are in edges */
850 /* including resetting of flags */
851 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
853 eed.v1->f = SF_VERT_AVAILABLE;
854 eed.v2->f = SF_VERT_AVAILABLE;
855 }
856
857 bool vert_available = false;
858 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
859 if (eve.f == SF_VERT_AVAILABLE) {
860 vert_available = true;
861 break;
862 }
863 }
864
865 if (!vert_available) [[unlikely]] {
866 return 0;
867 }
868
869 float n[3];
870
871 if (nor_proj) {
872 copy_v3_v3(n, nor_proj);
873 }
874 else {
875 /* define projection: with 'best' normal */
876 /* Newell's Method */
877 /* Similar code used elsewhere, but this checks for double ups
878 * which historically this function supports so better not change */
879
880 /* WARNING: this only gives stable direction with single polygons,
881 * ideally we'd calculate connectivity and each polys normal, see #41047 */
882 const float *v_prev;
883
884 zero_v3(n);
885 v_prev = sf_ctx->fillvertbase.last()->co;
886
887 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
888 if (!compare_v3v3(v_prev, eve.co, SF_EPSILON)) [[likely]] {
889 add_newell_cross_v3_v3v3(n, v_prev, eve.co);
890 v_prev = eve.co;
891 }
892 }
893 }
894
895 if (normalize_v3(n) == 0.0f) [[unlikely]] {
896 return 0;
897 }
898
900
901 /* STEP 1: COUNT POLYS */
902 if (sf_ctx->poly_nr != SF_POLY_UNSET) {
903 poly = ushort(sf_ctx->poly_nr + 1);
904 sf_ctx->poly_nr = SF_POLY_UNSET;
905 }
906
907 if (flag & BLI_SCANFILL_CALC_POLYS && (poly == 0)) {
908 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
909 mul_v2_m3v3(eve.xy, mat_2d, eve.co);
910
911 /* get first vertex with no poly number */
912 if (eve.poly_nr == SF_POLY_UNSET) {
913 uint toggle = 0;
914 /* now a sort of select connected */
915 ok = true;
916 eve.poly_nr = poly;
917
918 while (ok) {
919
920 ok = false;
921
922 toggle++;
923 ScanFillEdge *eed = (toggle & 1) ? sf_ctx->filledgebase.first() :
924 sf_ctx->filledgebase.last();
925 for (; eed; eed = (toggle & 1) ? eed->next : eed->prev) {
926 if (eed->v1->poly_nr == SF_POLY_UNSET && eed->v2->poly_nr == poly) {
927 eed->v1->poly_nr = poly;
928 eed->poly_nr = poly;
929 ok = true;
930 }
931 else if (eed->v2->poly_nr == SF_POLY_UNSET && eed->v1->poly_nr == poly) {
932 eed->v2->poly_nr = poly;
933 eed->poly_nr = poly;
934 ok = true;
935 }
936 else if (eed->poly_nr == SF_POLY_UNSET) {
937 if (eed->v1->poly_nr == poly && eed->v2->poly_nr == poly) {
938 eed->poly_nr = poly;
939 ok = true;
940 }
941 }
942 }
943 }
944
945 poly++;
946 }
947 }
948 // printf("amount of poly's: %d\n", poly);
949 }
950 else if (poly) {
951 /* we pre-calculated poly_nr */
952 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
953 mul_v2_m3v3(eve.xy, mat_2d, eve.co);
954 }
955 }
956 else {
957 poly = 1;
958
959 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
960 mul_v2_m3v3(eve.xy, mat_2d, eve.co);
961 eve.poly_nr = 0;
962 }
963
964 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
965 eed.poly_nr = 0;
966 }
967 }
968
969 /* STEP 2: remove loose edges and strings of edges */
970 if (flag & BLI_SCANFILL_CALC_LOOSE) {
971 uint toggle = 0;
972 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
973 if ((eed.v1->edge_count++ > 250) || (eed.v2->edge_count++ > 250)) {
974 /* otherwise it's impossible to be sure you can clear vertices */
975#ifndef NDEBUG
976 printf("No vertices with 250 edges allowed!\n");
977#endif
978 return 0;
979 }
980 }
981
982 /* does it only for vertices with (->edge_count == 1) */
983 testvertexnearedge(sf_ctx);
984
985 ok = true;
986 while (ok) {
987 ok = false;
988
989 toggle++;
990
991 ScanFillEdge *eed = (toggle & 1) ? sf_ctx->filledgebase.first() :
992 sf_ctx->filledgebase.last();
993 ScanFillEdge *eed_next;
994 for (; eed; eed = eed_next) {
995 eed_next = (toggle & 1) ? eed->next : eed->prev;
996 if (eed->v1->edge_count == 1) {
997 eed->v2->edge_count--;
998 BLI_remlink(&sf_ctx->fillvertbase, eed->v1);
999 BLI_remlink(&sf_ctx->filledgebase, eed);
1000 ok = true;
1001 }
1002 else if (eed->v2->edge_count == 1) {
1003 eed->v1->edge_count--;
1004 BLI_remlink(&sf_ctx->fillvertbase, eed->v2);
1005 BLI_remlink(&sf_ctx->filledgebase, eed);
1006 ok = true;
1007 }
1008 }
1009 }
1010 if (sf_ctx->filledgebase.is_empty()) {
1011 // printf("All edges removed\n");
1012 return 0;
1013 }
1014 }
1015 else {
1016 /* skip checks for loose edges */
1017 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
1018 eed.v1->edge_count++;
1019 eed.v2->edge_count++;
1020 }
1021#ifndef NDEBUG
1022 /* ensure we're right! */
1023 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
1024 BLI_assert(eed.v1->edge_count != 1);
1025 BLI_assert(eed.v2->edge_count != 1);
1026 }
1027#endif
1028 }
1029
1030 /* CURRENT STATUS:
1031 * - `eve->f`: 1 = available in edges.
1032 * - `eve->poly_nr`: poly-number.
1033 * - `eve->edge_count`: amount of edges connected to vertex.
1034 * - `eve->tmp.v`: store! original vertex number.
1035 *
1036 * - `eed->f`: 1 = boundary edge (optionally set by caller).
1037 * - `eed->poly_nr`: poly number.
1038 */
1039
1040 /* STEP 3: MAKE POLYFILL STRUCT */
1041 pflist = MEM_new_array_uninitialized<PolyFill>(size_t(poly), "edgefill");
1042 pf = pflist;
1043 for (a = 0; a < poly; a++) {
1044 pf->edges = pf->verts = 0;
1045 pf->min_xy[0] = pf->min_xy[1] = 1.0e20f;
1046 pf->max_xy[0] = pf->max_xy[1] = -1.0e20f;
1047 pf->f = SF_POLY_NEW;
1048 pf->nr = a;
1049 pf++;
1050 }
1051 for (ScanFillEdge &eed : sf_ctx->filledgebase) {
1052 pflist[eed.poly_nr].edges++;
1053 }
1054
1055 for (ScanFillVert &eve : sf_ctx->fillvertbase) {
1056 pflist[eve.poly_nr].verts++;
1057 min_xy_p = pflist[eve.poly_nr].min_xy;
1058 max_xy_p = pflist[eve.poly_nr].max_xy;
1059
1060 min_xy_p[0] = (min_xy_p[0]) < (eve.xy[0]) ? (min_xy_p[0]) : (eve.xy[0]);
1061 min_xy_p[1] = (min_xy_p[1]) < (eve.xy[1]) ? (min_xy_p[1]) : (eve.xy[1]);
1062 max_xy_p[0] = (max_xy_p[0]) > (eve.xy[0]) ? (max_xy_p[0]) : (eve.xy[0]);
1063 max_xy_p[1] = (max_xy_p[1]) > (eve.xy[1]) ? (max_xy_p[1]) : (eve.xy[1]);
1064 if (eve.edge_count > 2) {
1065 pflist[eve.poly_nr].f = SF_POLY_VALID;
1066 }
1067 }
1068
1069 /* STEP 4: FIND HOLES OR BOUNDS, JOIN THEM
1070 * ( bounds just to divide it in pieces for optimization,
1071 * the edgefill itself has good auto-hole detection). */
1072
1073 if ((flag & BLI_SCANFILL_CALC_HOLES) && (poly > 1)) {
1074#if 0
1075 pf = pflist;
1076 for (a = 0; a < poly; a++) {
1077 printf("poly:%d edges:%d verts:%d flag: %d\n", a, pf->edges, pf->verts, pf->f);
1078 PRINT2(f, f, pf->min[0], pf->min[1]);
1079 pf++;
1080 }
1081#endif
1082
1083 uint *target_map = MEM_new_array<uint>(poly, "polycache");
1084 array_utils::fill_index_range<uint>({target_map, poly});
1085
1086 for (a = 0; a < poly; a++) {
1087 if (target_map[a] != a) {
1088 continue;
1089 }
1090 fill_target_map_recursive(pflist, poly, a, a, target_map);
1091 }
1092
1093 /* Join polygons. */
1094 for (a = 0; a < poly; a++) {
1095 if (target_map[a] != a) {
1096 PolyFill *pf_src = pflist + a;
1097 PolyFill *pf_dst = pflist + target_map[a];
1098 mergepolysSimp(sf_ctx, pf_dst, pf_src);
1099 }
1100 }
1101
1102 MEM_delete(target_map);
1103 }
1104
1105#if 0
1106 printf("after merge\n");
1107 pf = pflist;
1108 for (a = 0; a < poly; a++) {
1109 printf("poly:%d edges:%d verts:%d flag: %d\n", a, pf->edges, pf->verts, pf->f);
1110 pf++;
1111 }
1112#endif
1113
1114 /* STEP 5: MAKE TRIANGLES */
1115
1116 tempve.first_ = sf_ctx->fillvertbase.first();
1117 tempve.last_ = sf_ctx->fillvertbase.last();
1118 temped.first_ = sf_ctx->filledgebase.first();
1119 temped.last_ = sf_ctx->filledgebase.last();
1120 sf_ctx->fillvertbase.clear_no_delete();
1121 sf_ctx->filledgebase.clear_no_delete();
1122
1123 pf = pflist;
1124 for (a = 0; a < poly; a++) {
1125 if (pf->edges > 1) {
1126 splitlist(sf_ctx, &tempve, &temped, pf->nr);
1127 totfaces += scanfill(sf_ctx, pf, flag);
1128 }
1129 pf++;
1130 }
1131 BLI_movelisttolist(&sf_ctx->fillvertbase, &tempve);
1132 BLI_movelisttolist(&sf_ctx->filledgebase, &temped);
1133
1134 /* FREE */
1135
1136 MEM_delete(pflist);
1137
1138 return totfaces;
1139}
1140
1142{
1143 return BLI_scanfill_calc_ex(sf_ctx, flag, nullptr);
1144}
1145
1146} // namespace blender
#define SF_POLY_UNSET
#define BLI_SCANFILL_ARENA_SIZE
These structs are the foundation for all linked lists in the library system.
Read Blender memory allocation and freeing.
#define pf2(_x, _i)
Prefetch 128.
Definition gim_memory.h:50
#define pf(_x, _i)
Prefetch 64.
Definition gim_memory.h:48
#define FLT_EPSILON
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
void fill_index_range(MutableSpan< T > span, const T start=0)
BMesh Iterators.
MINLINE float min_ff(float a, float b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_scanfill_end(ScanFillContext *sf_ctx)
Definition scanfill.cc:798
unsigned short ushort
Definition BKE_text.h:56
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
@ BLI_SCANFILL_CALC_LOOSE
@ BLI_SCANFILL_CALC_POLYS
@ BLI_SCANFILL_CALC_HOLES
@ BLI_SCANFILL_CALC_REMOVE_DOUBLES
void void void BLI_movelisttolist(ListBase *dst, ListBase *src) ATTR_NONNULL(1
Definition listbase.cc:32
unsigned char uchar
Definition BKE_text.h:58
static uint scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
Definition scanfill.cc:457
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
void BLI_scanfill_begin_arena(ScanFillContext *sf_ctx, struct MemArena *arena)
Definition scanfill.cc:791
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
struct ScanFillVert * BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3])
Definition scanfill.cc:105
static void mergepolysSimp(ScanFillContext *sf_ctx, PolyFill *pf1, PolyFill *pf2)
Definition scanfill.cc:210
void BLI_scanfill_begin(ScanFillContext *sf_ctx)
Definition scanfill.cc:784
float cos_v2v2v2(const float p1[2], const float p2[2], const float p3[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v3(float r[3])
void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1)
Definition listbase.cc:378
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, int flag)
Definition scanfill.cc:1141
struct ScanFillEdge * BLI_scanfill_edge_add(ScanFillContext *sf_ctx, struct ScanFillVert *v1, struct ScanFillVert *v2)
Definition scanfill.cc:127
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
MINLINE float normalize_v3(float n[3])
MINLINE bool compare_v3v3(const float v1[3], const float v2[3], float limit) ATTR_WARN_UNUSED_RESULT
void BLI_scanfill_end_arena(ScanFillContext *sf_ctx, struct MemArena *arena)
Definition scanfill.cc:808
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
static bool boundisect(const PolyFill *pf2, const PolyFill *pf1)
Definition scanfill.cc:162
static ScanFillVertLink * addedgetoscanlist(ScanFillVertLink *scdata, ScanFillEdge *eed, uint len)
Definition scanfill.cc:313
unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, int flag, const float nor_proj[3])
Definition scanfill.cc:818
static int vergscdata(const void *a1, const void *a2)
Definition scanfill.cc:82
float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2])
Definition math_geom.cc:294
static bool testedgeside(const float v1[2], const float v2[2], const float v3[2])
Definition scanfill.cc:241
static bool boundinsideEV(const ScanFillEdge *eed, const ScanFillVert *eve)
Definition scanfill.cc:351
static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed)
Definition scanfill.cc:262
static void addfillface(ScanFillContext *sf_ctx, ScanFillVert *v1, ScanFillVert *v2, ScanFillVert *v3)
Definition scanfill.cc:146
MINLINE void zero_v2(float r[2])
static void fill_target_map_recursive(const PolyFill *__restrict pf_list, const uint pf_len, const uint pf_target, const uint pf_test, uint *__restrict target_map)
Definition scanfill.cc:188
static void splitlist(ScanFillContext *sf_ctx, ListBaseT< ScanFillVert > *tempve, ListBaseT< ScanFillEdge > *temped, ushort nr)
Definition scanfill.cc:433
static void testvertexnearedge(ScanFillContext *sf_ctx)
Definition scanfill.cc:379
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
MINLINE bool compare_v2v2(const float v1[2], const float v2[2], float limit) ATTR_WARN_UNUSED_RESULT
#define SF_POLY_VALID
Definition scanfill.cc:78
#define SF_VERT_NEW
Definition scanfill.cc:65
#define SF_EPSILON
Definition scanfill.cc:61
#define SF_EDGE_NEW
Definition scanfill.cc:72
#define SF_VERT_ZERO_LEN
Definition scanfill.cc:67
#define SF_EDGE_INTERNAL
Definition scanfill.cc:74
#define SF_EPSILON_SQ
Definition scanfill.cc:62
#define SF_POLY_NEW
Definition scanfill.cc:77
#define SF_VERT_AVAILABLE
Definition scanfill.cc:66
ListBaseT< ScanFillFace > fillfacebase
ListBaseT< ScanFillEdge > filledgebase
struct MemArena * arena
ListBaseT< ScanFillVert > fillvertbase
struct ScanFillEdge * prev
unsigned short poly_nr
union blender::ScanFillEdge::@262251053107234334274134243151221246013035300046 tmp
struct ScanFillVert * v2
struct ScanFillEdge * next
struct ScanFillVert * v1
struct ScanFillVert * v2
struct ScanFillVert * v1
struct ScanFillVert * v3
unsigned char edge_count
unsigned short poly_nr
union blender::ScanFillVert::@124355022001164321030006076112165043115032300246 tmp