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