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