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