153d24aaf994de2e529920709b61d9ee87f3604e
[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 bij 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 binnen 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 /* ****  FUNKTIES VOOR 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 void *new_mem_element(int size)
178 {
179         /* Alleen als gedurende het werken duizenden elementen worden aangemaakt en
180          * nooit (tussendoor) vrijgegeven. Op eind is vrijgeven nodig (-1).
181          */
182         int blocksize= 16384;
183         static int offs= 0;             /* het huidige vrije adres */
184         static struct mem_elements *cur= 0;
185         static ListBase lb= {0, 0};
186         void *adr;
187         
188         if(size>10000 || size==0) {
189                 printf("incorrect use of new_mem_element\n");
190         }
191         else if(size== -1) {
192                 cur= lb.first;
193                 while(cur) {
194                         MEM_freeN(cur->data);
195                         cur= cur->next;
196                 }
197                 BLI_freelistN(&lb);
198                 
199                 return NULL;    
200         }
201         
202         size= 4*( (size+3)/4 );
203         
204         if(cur) {
205                 if(size+offs < blocksize) {
206                         adr= (void *) (cur->data+offs);
207                         offs+= size;
208                         return adr;
209                 }
210         }
211         
212         cur= MEM_callocN( sizeof(struct mem_elements), "newmem");
213         cur->data= MEM_callocN(blocksize, "newmem");
214         BLI_addtail(&lb, cur);
215         
216         offs= size;
217         return cur->data;
218 }
219
220 void BLI_end_edgefill(void)
221 {
222         new_mem_element(-1);
223         
224         fillvertbase.first= fillvertbase.last= 0;
225         filledgebase.first= filledgebase.last= 0;
226         fillvlakbase.first= fillvlakbase.last= 0;
227 }
228
229 /* ****  FILL ROUTINES *************************** */
230
231 EditVert *BLI_addfillvert(float *vec)
232 {
233         EditVert *eve;
234         
235         eve= new_mem_element(sizeof(EditVert));
236         BLI_addtail(&fillvertbase, eve);
237         
238         if(vec) {
239                 *(eve->co)     = *(vec);
240                 *(eve->co + 1) = *(vec + 1);
241                 *(eve->co + 2) = *(vec + 2);
242         }
243 /*      VECCOPY(eve->co, vec); */
244
245         return eve;     
246 }
247
248 EditEdge *BLI_addfilledge(EditVert *v1, EditVert *v2)
249 {
250         EditEdge *newed;
251
252         newed= new_mem_element(sizeof(EditEdge));
253         BLI_addtail(&filledgebase, newed);
254         
255         newed->v1= v1;
256         newed->v2= v2;
257
258         return newed;
259 }
260
261 void addfillvlak(EditVert *v1, EditVert *v2, EditVert *v3)
262 {
263         /* maakt geen edges aan */
264         EditVlak *evl;
265
266         evl= new_mem_element(sizeof(EditVlak));
267         BLI_addtail(&fillvlakbase, evl);
268         
269         evl->v1= v1;
270         evl->v2= v2;
271         evl->v3= v3;
272         evl->f= 2;
273         /* G.obedit is Object*, actcol is char */
274 /*      if(G.obedit && G.obedit->actcol) evl->mat_nr= G.obedit->actcol-1; */
275         if (objectref && colourref && *colourref) {
276                 evl->mat_nr = *colourref - 1;
277         } else {
278                 evl->mat_nr = 0;
279         }
280 }
281
282
283 int boundinside(PolyFill *pf1, PolyFill *pf2)
284 {
285         /* is pf2 INSIDE pf1 ? met boundingbox */
286         /* eerst testen of poly's bestaan */
287
288         if(pf1->edges==0 || pf2->edges==0) return 0;
289
290         if(pf2->max[cox]<pf1->max[cox])
291                 if(pf2->max[coy]<pf1->max[coy])
292                         if(pf2->min[cox]>pf1->min[cox])
293                                 if(pf2->min[coy]>pf1->min[coy]) return 1;
294         return 0;
295 }
296
297 int boundisect(PolyFill *pf2, PolyFill *pf1)
298 {
299         /* is pf2 aangeraakt door pf1 ? met boundingbox */
300         /* eerst testen of poly's bestaan */
301
302         if(pf1->edges==0 || pf2->edges==0) return 0;
303
304         if(pf2->max[cox] < pf1->min[cox] ) return 0;
305         if(pf2->max[coy] < pf1->min[coy] ) return 0;
306
307         if(pf2->min[cox] > pf1->max[cox] ) return 0;
308         if(pf2->min[coy] > pf1->max[coy] ) return 0;
309
310         /* samenvoegen */
311         if(pf2->max[cox]<pf1->max[cox]) pf2->max[cox]= pf1->max[cox];
312         if(pf2->max[coy]<pf1->max[coy]) pf2->max[coy]= pf1->max[coy];
313
314         if(pf2->min[cox]>pf1->min[cox]) pf2->min[cox]= pf1->min[cox];
315         if(pf2->min[coy]>pf1->min[coy]) pf2->min[coy]= pf1->min[coy];
316
317         return 1;
318 }
319
320
321
322
323
324 void mergepolysSimp(PolyFill *pf1, PolyFill *pf2)       /* pf2 bij pf1 */
325 /*  PolyFill *pf1,*pf2; */
326 {
327         EditVert *eve;
328         EditEdge *eed;
329
330         /* alle oude polynummers vervangen */
331         eve= fillvertbase.first;
332         while(eve) {
333                 if(eve->xs== pf2->nr) eve->xs= pf1->nr;
334                 eve= eve->next;
335         }
336         eed= filledgebase.first;
337         while(eed) {
338                 if(eed->f1== pf2->nr) eed->f1= pf1->nr;
339                 eed= eed->next;
340         }
341
342         pf1->verts+= pf2->verts;
343         pf1->edges+= pf2->edges;
344         pf2->verts= pf2->edges= 0;
345         pf1->f= (pf1->f | pf2->f);
346 }
347
348
349
350 EditEdge *existfilledge(EditVert *v1, EditVert *v2)
351 /*  EditVert *v1,*v2; */
352 {
353         EditEdge *eed;
354
355         eed= filledgebase.first;
356         while(eed) {
357                 if(eed->v1==v1 && eed->v2==v2) return eed;
358                 if(eed->v2==v1 && eed->v1==v2) return eed;
359                 eed= eed->next;
360         }
361         return 0;
362 }
363
364
365 short testedgeside(float *v1, float *v2, float *v3) /* is v3 rechts van v1-v2 ? Met uizondering: v3==v1 || v3==v2*/
366 /*  float *v1,*v2,*v3; */
367 {
368         float inp;
369
370         inp= (v2[cox]-v1[cox])*(v1[coy]-v3[coy])
371             +(v1[coy]-v2[coy])*(v1[cox]-v3[cox]);
372
373         if(inp<0.0) return 0;
374         else if(inp==0) {
375                 if(v1[cox]==v3[cox] && v1[coy]==v3[coy]) return 0;
376                 if(v2[cox]==v3[cox] && v2[coy]==v3[coy]) return 0;
377         }
378         return 1;
379 }
380
381 short testedgeside2(float *v1, float *v2, float *v3) /* is v3 rechts van v1-v2 ? niet doorsnijden! */
382 /*  float *v1,*v2,*v3; */
383 {
384         float inp;
385
386         inp= (v2[cox]-v1[cox])*(v1[coy]-v3[coy])
387             +(v1[coy]-v2[coy])*(v1[cox]-v3[cox]);
388
389         if(inp<=0.0) return 0;
390         return 1;
391 }
392
393 short addedgetoscanvert(ScFillVert *sc, EditEdge *eed)
394 /*  ScFillVert *sc; */
395 /*  EditEdge *eed; */
396 {
397         /* zoek eerste edge die rechts van eed ligt en stop eed daarvoor */
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 /*  EditEdge *eed; */
441 /*  int len; */
442 {
443         /* voegt edge op juiste plek in ScFillVert list */
444         /* geeft sc terug als edge al bestaat */
445         ScFillVert *sc,scsearch;
446         EditVert *eve;
447
448         /* welke vert is linksboven */
449         if(eed->v1->co[coy] == eed->v2->co[coy]) {
450                 if(eed->v1->co[cox] > eed->v2->co[cox]) {
451                         eve= eed->v1;
452                         eed->v1= eed->v2;
453                         eed->v2= eve;
454                 }
455         }
456         else if(eed->v1->co[coy] < eed->v2->co[coy]) {
457                 eve= eed->v1;
458                 eed->v1= eed->v2;
459                 eed->v2= eve;
460         }
461         /* zoek plek in lijst */
462         scsearch.v1= eed->v1;
463         sc= (ScFillVert *)bsearch(&scsearch,scdata,len,
464             sizeof(ScFillVert), vergscdata);
465
466         if(sc==0) printf("Error in search edge: %x\n",eed);
467         else if(addedgetoscanvert(sc,eed)==0) return sc;
468
469         return 0;
470 }
471
472 short boundinsideEV(EditEdge *eed, EditVert *eve)       /* is eve binnen boundbox eed */
473 /*  EditEdge *eed; */
474 /*  EditVert *eve; */
475 {
476         float minx,maxx,miny,maxy;
477
478         if(eed->v1->co[cox]<eed->v2->co[cox]) {
479                 minx= eed->v1->co[cox];
480                 maxx= eed->v2->co[cox];
481         } else {
482                 minx= eed->v2->co[cox];
483                 maxx= eed->v1->co[cox];
484         }
485         if(eve->co[cox]>=minx && eve->co[cox]<=maxx) {
486                 if(eed->v1->co[coy]<eed->v2->co[coy]) {
487                         miny= eed->v1->co[coy];
488                         maxy= eed->v2->co[coy];
489                 } else {
490                         miny= eed->v2->co[coy];
491                         maxy= eed->v1->co[coy];
492                 }
493                 if(eve->co[coy]>=miny && eve->co[coy]<=maxy) return 1;
494         }
495         return 0;
496 }
497
498
499 void testvertexnearedge(void)
500 {
501         /* alleen de vertices met ->h==1 worden getest op
502                 nabijheid van edge, zo ja invoegen */
503
504         EditVert *eve;
505         EditEdge *eed,*ed1;
506         float dist,vec1[2],vec2[2],vec3[2];
507
508         eve= fillvertbase.first;
509         while(eve) {
510                 if(eve->h==1) {
511                         vec3[0]= eve->co[cox];
512                         vec3[1]= eve->co[coy];
513                         /* de bewuste edge vinden waar eve aan zit */
514                         ed1= filledgebase.first;
515                         while(ed1) {
516                                 if(ed1->v1==eve || ed1->v2==eve) break;
517                                 ed1= ed1->next;
518                         }
519                         if(ed1->v1==eve) {
520                                 ed1->v1= ed1->v2;
521                                 ed1->v2= eve;
522                         }
523                         eed= filledgebase.first;
524                         while(eed) {
525                                 if(eve!=eed->v1 && eve!=eed->v2 && eve->xs==eed->f1) {
526                                         if(FloatCompare(eve->co,eed->v1->co, COMPLIMIT)) {
527                                                 ed1->v2= eed->v1;
528                                                 eed->v1->h++;
529                                                 eve->h= 0;
530                                                 break;
531                                         }
532                                         else if(FloatCompare(eve->co,eed->v2->co, COMPLIMIT)) {
533                                                 ed1->v2= eed->v2;
534                                                 eed->v2->h++;
535                                                 eve->h= 0;
536                                                 break;
537                                         }
538                                         else {
539                                                 vec1[0]= eed->v1->co[cox];
540                                                 vec1[1]= eed->v1->co[coy];
541                                                 vec2[0]= eed->v2->co[cox];
542                                                 vec2[1]= eed->v2->co[coy];
543                                                 if(boundinsideEV(eed,eve)) {
544                                                         dist= DistVL2Dfl(vec1,vec2,vec3);
545                                                         if(dist<COMPLIMIT) {
546                                                                 /* nieuwe edge */
547                                                                 ed1= BLI_addfilledge(eed->v1, eve);
548                                                                 
549                                                                 /* printf("fill: vertex near edge %x\n",eve); */
550                                                                 ed1->f= ed1->h= 0;
551                                                                 ed1->f1= eed->f1;
552                                                                 eed->v1= eve;
553                                                                 eve->h= 3;
554                                                                 break;
555                                                         }
556                                                 }
557                                         }
558                                 }
559                                 eed= eed->next;
560                         }
561                 }
562                 eve= eve->next;
563         }
564 }
565
566 void splitlist(ListBase *tempve, ListBase *temped, short nr)
567 /*  ListBase *tempve,*temped; */
568 /*  short nr; */
569 {
570         /* alles zit in de templist, alleen poly nr naar fillist schrijven */
571         EditVert *eve,*nextve;
572         EditEdge *eed,*nexted;
573
574         addlisttolist(tempve,&fillvertbase);
575         addlisttolist(temped,&filledgebase);
576
577         eve= tempve->first;
578         while(eve) {
579                 nextve= eve->next;
580                 if(eve->xs==nr) {
581                         BLI_remlink(tempve,eve);
582                         BLI_addtail(&fillvertbase,eve);
583                 }
584                 eve= nextve;
585         }
586         eed= temped->first;
587         while(eed) {
588                 nexted= eed->next;
589                 if(eed->f1==nr) {
590                         BLI_remlink(temped,eed);
591                         BLI_addtail(&filledgebase,eed);
592                 }
593                 eed= nexted;
594         }
595 }
596
597
598 void scanfill(PolyFill *pf)
599 {
600         ScFillVert *sc = NULL, *sc1;
601         EditVert *eve,*v1,*v2,*v3;
602         EditEdge *eed,*nexted,*ed1,*ed2,*ed3;
603         float miny = 0.0;
604         int a,b,verts, maxvlak, totvlak;
605         short nr, test, twoconnected=0;
606
607         nr= pf->nr;
608         verts= pf->verts;
609
610         /* PRINTS
611         eve= fillvertbase.first;
612         while(eve) {
613                 printf("vert: %x co: %f %f\n",eve,eve->co[cox],eve->co[coy]);
614                 eve= eve->next;
615         }       
616         eed= filledgebase.first;
617         while(eed) {
618                 printf("edge: %x  verts: %x %x\n",eed,eed->v1,eed->v2);
619                 eed= eed->next;
620         } */
621
622         /* STAP 0: alle nul lange edges eruit */
623         eed= filledgebase.first;
624         while(eed) {
625                 if(eed->v1->co[cox]==eed->v2->co[cox]) {
626                         if(eed->v1->co[coy]==eed->v2->co[coy]) {
627                                 if(eed->v1->f==255 && eed->v2->f!=255) {
628                                         eed->v2->f= 255;
629                                         eed->v2->vn= eed->v1->vn;
630                                 }
631                                 else if(eed->v2->f==255 && eed->v1->f!=255) {
632                                         eed->v1->f= 255;
633                                         eed->v1->vn= eed->v2->vn;
634                                 }
635                                 else if(eed->v2->f==255 && eed->v1->f==255) {
636                                         eed->v1->vn= eed->v2->vn;
637                                 }
638                                 else {
639                                         eed->v2->f= 255;
640                                         eed->v2->vn= eed->v1;
641                                 }
642                         }
643                 }
644                 eed= eed->next;
645         }
646
647         /* STAP 1: maak ahv van FillVert en FillEdge lijsten een gesorteerde
648                 ScFillVert lijst
649         */
650         sc= scdata= (ScFillVert *)MEM_callocN(pf->verts*sizeof(ScFillVert),"Scanfill1");
651         eve= fillvertbase.first;
652         verts= 0;
653         while(eve) {
654                 if(eve->xs==nr) {
655                         if(eve->f!= 255) {
656                                 verts++;
657                                 eve->f= 0;      /* vlag later voor connectedges */
658                                 sc->v1= eve;
659                                 sc++;
660                         }
661                 }
662                 eve= eve->next;
663         }
664
665         qsort(scdata, verts, sizeof(ScFillVert), vergscdata);
666
667         sc= scdata;
668         eed= filledgebase.first;
669         while(eed) {
670                 nexted= eed->next;
671                 eed->f= 0;
672                 BLI_remlink(&filledgebase,eed);
673                 if(eed->v1->f==255) {
674                         v1= eed->v1;
675                         while(eed->v1->f==255 && eed->v1->vn!=v1) eed->v1= eed->v1->vn;
676                 }
677                 if(eed->v2->f==255) {
678                         v2= eed->v2;
679                         while(eed->v2->f==255 && eed->v2->vn!=v2) eed->v2= eed->v2->vn;
680                 }
681                 if(eed->v1!=eed->v2) addedgetoscanlist(eed,verts);
682
683                 eed= nexted;
684         }
685         /*
686         sc= scdata;
687         for(a=0;a<verts;a++) {
688                 printf("\nscvert: %x\n",sc->v1);
689                 eed= sc->first;
690                 while(eed) {
691                         printf(" ed %x %x %x\n",eed,eed->v1,eed->v2);
692                         eed= eed->next;
693                 }
694                 sc++;
695         }*/
696
697
698         /* STAP 2: FILL LUS */
699
700         if(pf->f==0) twoconnected= 1;
701
702         /* (tijdelijke) beveiliging: nooit veel meer vlakken dan vertices */
703         totvlak= 0;
704         maxvlak= 2*verts;               /* 2*verts: cirkel in driehoek, beide gevuld */
705
706         sc= scdata;
707         for(a=0;a<verts;a++) {
708                 /* printf("VERTEX %d %x\n",a,sc->v1); */
709                 ed1= sc->first;
710                 while(ed1) {    /* connectflags zetten */
711                         nexted= ed1->next;
712                         if(ed1->v1->h==1 || ed1->v2->h==1) {
713                                 BLI_remlink((ListBase *)&(sc->first),ed1);
714                                 BLI_addtail(&filledgebase,ed1);
715                                 if(ed1->v1->h>1) ed1->v1->h--;
716                                 if(ed1->v2->h>1) ed1->v2->h--;
717                         }
718                         else ed1->v2->f= 1;
719
720                         ed1= nexted;
721                 }
722                 while(sc->first) {      /* zolang er edges zijn */
723                         ed1= sc->first;
724                         ed2= ed1->next;
725
726                         if(callLocalInterruptCallBack()) break;
727                         if(totvlak>maxvlak) {
728                                 /* printf("Fill error: endless loop. Escaped at vert %d,  tot: %d.\n", a, verts); */
729                                 a= verts;
730                                 break;
731                         }
732                         if(ed2==0) {
733                                 sc->first=sc->last= 0;
734                                 /* printf("maar 1 edge aan vert\n"); */
735                                 BLI_addtail(&filledgebase,ed1);
736                                 ed1->v2->f= 0;
737                                 ed1->v1->h--; 
738                                 ed1->v2->h--;
739                         } else {
740                                 /* test rest vertices */
741                                 v1= ed1->v2;
742                                 v2= ed1->v1;
743                                 v3= ed2->v2;
744                                 /* hieronder komt voor bij serie overlappende edges */
745                                 if(v1==v2 || v2==v3) break;
746                                 /* printf("test verts %x %x %x\n",v1,v2,v3); */
747                                 miny = ( (v1->co[coy])<(v3->co[coy]) ? (v1->co[coy]) : (v3->co[coy]) );
748 /*                              miny= MIN2(v1->co[coy],v3->co[coy]); */
749                                 sc1= sc+1;
750                                 test= 0;
751
752                                 for(b=a+1;b<verts;b++) {
753                                         if(sc1->v1->f==0) {
754                                                 if(sc1->v1->co[coy] <= miny) break;
755
756                                                 if(testedgeside(v1->co,v2->co,sc1->v1->co))
757                                                         if(testedgeside(v2->co,v3->co,sc1->v1->co))
758                                                                 if(testedgeside(v3->co,v1->co,sc1->v1->co)) {
759                                                                         /* punt in driehoek */
760                                                                 
761                                                                         test= 1;
762                                                                         break;
763                                                                 }
764                                         }
765                                         sc1++;
766                                 }
767                                 if(test) {
768                                         /* nieuwe edge maken en overnieuw beginnen */
769                                         /* printf("add new edge %x %x and start again\n",v2,sc1->v1); */
770
771                                         ed3= BLI_addfilledge(v2, sc1->v1);
772                                         BLI_remlink(&filledgebase, ed3);
773                                         BLI_insertlinkbefore((ListBase *)&(sc->first), ed2, ed3);
774                                         ed3->v2->f= 1;
775                                         ed3->f= 2;
776                                         ed3->v1->h++; 
777                                         ed3->v2->h++;
778                                 }
779                                 else {
780                                         /* nieuwe driehoek */
781                                         /* printf("add vlak %x %x %x\n",v1,v2,v3); */
782                                         addfillvlak(v1, v2, v3);
783                                         totvlak++;
784                                         BLI_remlink((ListBase *)&(sc->first),ed1);
785                                         BLI_addtail(&filledgebase,ed1);
786                                         ed1->v2->f= 0;
787                                         ed1->v1->h--; 
788                                         ed1->v2->h--;
789                                         /* ed2 mag ook weg als het een oude is */
790                                         if(ed2->f==0 && twoconnected) {
791                                                 BLI_remlink((ListBase *)&(sc->first),ed2);
792                                                 BLI_addtail(&filledgebase,ed2);
793                                                 ed2->v2->f= 0;
794                                                 ed2->v1->h--; 
795                                                 ed2->v2->h--;
796                                         }
797
798                                         /* nieuwe edge */
799                                         ed3= BLI_addfilledge(v1, v3);
800                                         BLI_remlink(&filledgebase, ed3);
801                                         ed3->f= 2;
802                                         ed3->v1->h++; 
803                                         ed3->v2->h++;
804                                         
805                                         /* printf("add new edge %x %x\n",v1,v3); */
806                                         sc1= addedgetoscanlist(ed3, verts);
807                                         
808                                         if(sc1) {       /* ed3 bestaat al: verwijderen*/
809                                                 /* printf("Edge bestaat al\n"); */
810                                                 ed3->v1->h--; 
811                                                 ed3->v2->h--;
812
813                                                 if(twoconnected) ed3= sc1->first;
814                                                 else ed3= 0;
815                                                 while(ed3) {
816                                                         if( (ed3->v1==v1 && ed3->v2==v3) || (ed3->v1==v3 && ed3->v2==v1) ) {
817                                                                 BLI_remlink((ListBase *)&(sc1->first),ed3);
818                                                                 BLI_addtail(&filledgebase,ed3);
819                                                                 ed3->v1->h--; 
820                                                                 ed3->v2->h--;
821                                                                 break;
822                                                         }
823                                                         ed3= ed3->next;
824                                                 }
825                                         }
826
827                                 }
828                         }
829                         /* test op loze edges */
830                         ed1= sc->first;
831                         while(ed1) {
832                                 nexted= ed1->next;
833                                 if(ed1->v1->h<2 || ed1->v2->h<2) {
834                                         BLI_remlink((ListBase *)&(sc->first),ed1);
835                                         BLI_addtail(&filledgebase,ed1);
836                                         if(ed1->v1->h>1) ed1->v1->h--;
837                                         if(ed1->v2->h>1) ed1->v2->h--;
838                                 }
839
840                                 ed1= nexted;
841                         }
842                 }
843                 sc++;
844         }
845
846         MEM_freeN(scdata);
847 }
848
849
850
851 int BLI_edgefill(int mode)  /* DE HOOFD FILL ROUTINE */
852 {
853         /*
854           - fill werkt met eigen lijsten, eerst aanmaken dus (geen vlakken)
855           - geef vertices in ->vn de oude pointer mee
856           - alleen xs en ys worden hier niet gebruikt: daar kan je iets in verstoppen
857           - edge flag ->f wordt 2 als het nieuwe edge betreft
858           - mode: & 1 is kruispunten testen, edges maken  (NOG DOEN )
859         */
860         ListBase tempve, temped;
861         EditVert *eve;
862         EditEdge *eed,*nexted;
863         PolyFill *pflist,*pf;
864         float *minp, *maxp, *v1, *v2, norm[3], len;
865         short a,c,poly=0,ok=0,toggle=0;
866
867         /* variabelen resetten*/
868         eve= fillvertbase.first;
869         while(eve) {
870                 eve->f= 0;
871                 eve->xs= 0;
872                 eve->h= 0;
873                 eve= eve->next;
874         }
875
876         /* eerst de vertices testen op aanwezigheid in edges */
877         /* plus flaggen resetten */
878         eed= filledgebase.first;
879         while(eed) {
880                 eed->f= eed->f1= eed->h= 0;
881                 eed->v1->f= 1;
882                 eed->v2->f= 1;
883
884                 eed= eed->next;
885         }
886
887         eve= fillvertbase.first;
888         while(eve) {
889                 if(eve->f & 1) {
890                         ok=1; 
891                         break;
892                 }
893                 eve= eve->next;
894         }
895
896         if(ok==0) return 0;
897
898         /* NEW NEW! projektie bepalen: met beste normaal */
899         /* pak de eerste drie verschillende verts */
900         
901         /* DIT STUK IS NOG STEEDS TAMELIJK ZWAK! */
902         
903         eve= fillvertbase.last;
904         len= 0.0;
905         v1= eve->co;
906         v2= 0;
907         eve= fillvertbase.first;
908         while(eve) {
909                 if(v2) {
910                         if( FloatCompare(v2, eve->co,  0.0003)==0) {
911                                 len= CalcNormFloat(v1, v2, eve->co, norm);
912                                 if(len != 0.0) break;
913                         }
914                 }
915                 else if(FloatCompare(v1, eve->co,  0.0003)==0) {
916                         v2= eve->co;
917                 }
918                 eve= eve->next;
919         }
920
921         if(len==0.0) return 0;  /* geen fill mogelijk */
922
923         norm[0]= fabs(norm[0]);
924         norm[1]= fabs(norm[1]);
925         norm[2]= fabs(norm[2]);
926         
927         if(norm[2]>=norm[0] && norm[2]>=norm[1]) {
928                 cox= 0; coy= 1;
929         }
930         else if(norm[1]>=norm[0] && norm[1]>=norm[2]) {
931                 cox= 0; coy= 2;
932         }
933         else {
934                 cox= 1; coy= 2;
935         }
936
937         /* STAP 1: AANTAL POLY'S TELLEN */
938         eve= fillvertbase.first;
939         while(eve) {
940                 /* pak eerste vertex zonder polynummer */
941                 if(eve->xs==0) {
942                         poly++;
943                         /* nu een soort select connected */
944                         ok= 1;
945                         eve->xs= poly;
946                         
947                         while(ok) {
948                                 
949                                 ok= 0;
950                                 toggle++;
951                                 if(toggle & 1) eed= filledgebase.first;
952                                 else eed= filledgebase.last;
953
954                                 while(eed) {
955                                         if(eed->v1->xs==0 && eed->v2->xs==poly) {
956                                                 eed->v1->xs= poly;
957                                                 eed->f1= poly;
958                                                 ok= 1;
959                                         }
960                                         else if(eed->v2->xs==0 && eed->v1->xs==poly) {
961                                                 eed->v2->xs= poly;
962                                                 eed->f1= poly;
963                                                 ok= 1;
964                                         }
965                                         else if(eed->f1==0) {
966                                                 if(eed->v1->xs==poly && eed->v2->xs==poly) {
967                                                         eed->f1= poly;
968                                                         ok= 1;
969                                                 }
970                                         }
971                                         if(toggle & 1) eed= eed->next;
972                                         else eed= eed->prev;
973                                 }
974                         }
975                 }
976                 eve= eve->next;
977         }
978         /* printf("aantal poly's: %d\n",poly); */
979
980         /* STAP 2: LOSSE EDGES EN SLIERTEN VERWIJDEREN */
981         eed= filledgebase.first;
982         while(eed) {
983                 if(eed->v1->h++ >250) break;
984                 if(eed->v2->h++ >250) break;
985                 eed= eed->next;
986         }
987         if(eed) {
988                 /* anders kan hierna niet met zekerheid vertices worden gewist */
989                 callLocalErrorCallBack("No vertices with 250 edges allowed!");
990                 return 0;
991         }
992         
993         /* doet alleen vertices met ->h==1 */
994         testvertexnearedge();
995
996         ok= 1;
997         while(ok) {
998                 ok= 0;
999                 toggle++;
1000                 if(toggle & 1) eed= filledgebase.first;
1001                 else eed= filledgebase.last;
1002                 while(eed) {
1003                         if(toggle & 1) nexted= eed->next;
1004                         else nexted= eed->prev;
1005                         if(eed->v1->h==1) {
1006                                 eed->v2->h--;
1007                                 BLI_remlink(&fillvertbase,eed->v1); 
1008                                 BLI_remlink(&filledgebase,eed); 
1009                                 ok= 1;
1010                         }
1011                         else if(eed->v2->h==1) {
1012                                 eed->v1->h--;
1013                                 BLI_remlink(&fillvertbase,eed->v2); 
1014                                 BLI_remlink(&filledgebase,eed); 
1015                                 ok= 1;
1016                         }
1017                         eed= nexted;
1018                 }
1019         }
1020         if(filledgebase.first==0) {
1021                 /* printf("All edges removed\n"); */
1022                 return 0;
1023         }
1024
1025
1026         /* STAND VAN ZAKEN:
1027         - eve->f  :1= aanwezig in edges
1028         - eve->xs :polynummer
1029         - eve->h  :aantal edges aan vertex
1030         - eve->vn :bewaren! oorspronkelijke vertexnummer
1031
1032         - eed->f  :
1033         - eed->f1 :polynummer
1034 */
1035
1036
1037         /* STAP 3: POLYFILL STRUCT MAKEN */
1038         pflist= (PolyFill *)MEM_callocN(poly*sizeof(PolyFill),"edgefill");
1039         pf= pflist;
1040         for(a=1;a<=poly;a++) {
1041                 pf->nr= a;
1042                 pf->min[0]=pf->min[1]=pf->min[2]= 1.0e20;
1043                 pf->max[0]=pf->max[1]=pf->max[2]= -1.0e20;
1044                 pf++;
1045         }
1046         eed= filledgebase.first;
1047         while(eed) {
1048                 pflist[eed->f1-1].edges++;
1049                 eed= eed->next;
1050         }
1051
1052         eve= fillvertbase.first;
1053         while(eve) {
1054                 pflist[eve->xs-1].verts++;
1055                 minp= pflist[eve->xs-1].min;
1056                 maxp= pflist[eve->xs-1].max;
1057
1058                 minp[cox]= (minp[cox])<(eve->co[cox]) ? (minp[cox]) : (eve->co[cox]);
1059                 minp[coy]= (minp[coy])<(eve->co[coy]) ? (minp[coy]) : (eve->co[coy]);
1060                 maxp[cox]= (maxp[cox])>(eve->co[cox]) ? (maxp[cox]) : (eve->co[cox]);
1061                 maxp[coy]= (maxp[coy])>(eve->co[coy]) ? (maxp[coy]) : (eve->co[coy]);
1062                 if(eve->h>2) pflist[eve->xs-1].f= 1;
1063
1064                 eve= eve->next;
1065         }
1066
1067         /* STAP 4: GATEN OF BOUNDS VINDEN EN SAMENVOEGEN
1068          *  ( bounds alleen om grote hoeveelheden een beetje in stukjes te verdelen, 
1069          *    de edgefill heeft van zichzelf een adequate autogat!!!
1070          * LET OP: WERKT ALLEEN ALS POLY'S GESORTEERD ZIJN!!! */
1071         
1072         if(poly>1) {
1073                 short *polycache, *pc;
1074
1075                 /* dus: eerst sorteren */
1076                 qsort(pflist, poly, sizeof(PolyFill), vergpoly);
1077                 
1078                 /*pf= pflist;
1079                 for(a=1;a<=poly;a++) {
1080                         printf("poly:%d edges:%d verts:%d flag: %d\n",a,pf->edges,pf->verts,pf->f);
1081                         PRINT2(f, f, pf->min[0], pf->min[1]);
1082                         pf++;
1083                 }*/
1084         
1085                 polycache= pc= MEM_callocN(sizeof(short)*poly, "polycache");
1086                 pf= pflist;
1087                 for(a=0; a<poly; a++, pf++) {
1088                         for(c=a+1;c<poly;c++) {
1089                                 
1090                                 /* als 'a' inside 'c': samenvoegen (ook bbox)
1091                                  * Pas Op: 'a' kan ook inside andere poly zijn.
1092                                  */
1093                                 if(boundisect(pf, pflist+c)) {
1094                                         *pc= c;
1095                                         pc++;
1096                                 }
1097                                 /* alleen voor opt! */
1098                                 /* else if(pf->max[cox] < (pflist+c)->min[cox]) break; */
1099                                 
1100                         }
1101                         while(pc!=polycache) {
1102                                 pc--;
1103                                 mergepolysSimp(pf, pflist+ *pc);
1104                         }
1105                 }
1106                 MEM_freeN(polycache);
1107         }
1108         
1109         pf= pflist;
1110         /* printf("na merge\n");
1111         for(a=1;a<=poly;a++) {
1112                 printf("poly:%d edges:%d verts:%d flag: %d\n",a,pf->edges,pf->verts,pf->f);
1113                 pf++;
1114         } */
1115
1116         /* STAP 5: DRIEHOEKEN MAKEN */
1117
1118         tempve.first= fillvertbase.first;
1119         tempve.last= fillvertbase.last;
1120         temped.first= filledgebase.first;
1121         temped.last= filledgebase.last;
1122         fillvertbase.first=fillvertbase.last= 0;
1123         filledgebase.first=filledgebase.last= 0;
1124
1125         pf= pflist;
1126         for(a=0;a<poly;a++) {
1127                 if(pf->edges>1) {
1128                         splitlist(&tempve,&temped,pf->nr);
1129                         scanfill(pf);
1130                 }
1131                 pf++;
1132         }
1133         addlisttolist(&fillvertbase,&tempve);
1134         addlisttolist(&filledgebase,&temped);
1135
1136         /* evl= fillvlakbase.first;     
1137         while(evl) {
1138                 printf("nieuw vlak %x %x %x\n",evl->v1,evl->v2,evl->v3);
1139                 evl= evl->next;
1140         }*/
1141
1142
1143         /*  VRIJGEVEN */
1144
1145         MEM_freeN(pflist);
1146         return 1;
1147
1148 }
1149
1150 /*
1151   MOVED TO EDITMESH.C since it's really bad to leave it here
1152   
1153 void fill_mesh(void)
1154 {
1155         EditVert *eve,*v1;
1156         EditEdge *eed,*e1,*nexted;
1157         EditVlak *evl,*nextvl;
1158         short ok;
1159
1160         if(G.obedit==0 || (G.obedit->type!=OB_MESH)) return;
1161
1162         waitcursor(1);
1163
1164         / * alle selected vertices kopieeren * /
1165         eve= G.edve.first;
1166         while(eve) {
1167                 if(eve->f & 1) {
1168                         v1= addfillvert(eve->co);
1169                         eve->vn= v1;
1170                         v1->vn= eve;
1171                         v1->h= 0;
1172                 }
1173                 eve= eve->next;
1174         }
1175         / * alle selected edges kopieeren * /
1176         eed= G.eded.first;
1177         while(eed) {
1178                 if( (eed->v1->f & 1) && (eed->v2->f & 1) ) {
1179                         e1= addfilledge(eed->v1->vn, eed->v2->vn);
1180                         e1->v1->h++; 
1181                         e1->v2->h++;
1182                 }
1183                 eed= eed->next;
1184         }
1185         / * van alle selected vlakken vertices en edges verwijderen om dubbels te voorkomen * /
1186         / * alle edges tellen punten op, vlakken trekken af,
1187            edges met vertices ->h<2 verwijderen * /
1188         evl= G.edvl.first;
1189         ok= 0;
1190         while(evl) {
1191                 nextvl= evl->next;
1192                 if( vlakselectedAND(evl, 1) ) {
1193                         evl->v1->vn->h--;
1194                         evl->v2->vn->h--;
1195                         evl->v3->vn->h--;
1196                         if(evl->v4) evl->v4->vn->h--;
1197                         ok= 1;
1198                         
1199                 }
1200                 evl= nextvl;
1201         }
1202         if(ok) {        / * er zijn vlakken geselecteerd * /
1203                 eed= filledgebase.first;
1204                 while(eed) {
1205                         nexted= eed->next;
1206                         if(eed->v1->h<2 || eed->v2->h<2) {
1207                                 remlink(&filledgebase,eed);
1208                         }
1209                         eed= nexted;
1210                 }
1211         }
1212
1213         / * tijd=clock(); * /
1214
1215         ok= edgefill(0);
1216
1217         / * printf("time: %d\n",(clock()-tijd)/1000); * /
1218
1219         if(ok) {
1220                 evl= fillvlakbase.first;
1221                 while(evl) {
1222                         addvlaklist(evl->v1->vn, evl->v2->vn, evl->v3->vn, 0, evl);
1223                         evl= evl->next;
1224                 }
1225         }
1226         / * else printf("fill error\n"); * /
1227
1228         end_edgefill();
1229
1230         waitcursor(0);
1231
1232         countall();
1233         allqueue(REDRAWVIEW3D, 0);
1234 }
1235
1236 MOVED TO editmesh.c !!!!! (you bastards!)
1237
1238  */