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