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