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