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