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