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