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