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