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