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