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