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