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