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