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