Blender V2.61 - r43446

scanfill.c

Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN GPL LICENSE BLOCK *****
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License
00006  * as published by the Free Software Foundation; either version 2
00007  * of the License, or (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software Foundation,
00016  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00017  *
00018  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
00019  * All rights reserved.
00020  *
00021  * The Original Code is: all of this file.
00022  *
00023  * Contributor(s): none yet.
00024  *
00025  * ***** END GPL LICENSE BLOCK *****
00026  * (uit traces) maart 95
00027  */
00028 
00034 #include "MEM_guardedalloc.h"
00035 
00036 #include "BLI_callbacks.h"
00037 #include "BLI_editVert.h"
00038 #include "BLI_listbase.h"
00039 #include "BLI_math.h"
00040 #include "BLI_scanfill.h"
00041 
00042 /* callbacks for errors and interrupts and some goo */
00043 static void (*BLI_localErrorCallBack)(const char*) = NULL;
00044 static int (*BLI_localInterruptCallBack)(void) = NULL;
00045 
00046 void BLI_setErrorCallBack(void (*f)(const char *))
00047 {
00048     BLI_localErrorCallBack = f;
00049 }
00050 
00051 void BLI_setInterruptCallBack(int (*f)(void))
00052 {
00053     BLI_localInterruptCallBack = f;
00054 }
00055 
00056 /* just flush the error to /dev/null if the error handler is missing */
00057 void callLocalErrorCallBack(const char* msg)
00058 {
00059     if (BLI_localErrorCallBack) {
00060         BLI_localErrorCallBack(msg);
00061     }
00062 }
00063 
00064 #if 0
00065 /* ignore if the interrupt wasn't set */
00066 static int callLocalInterruptCallBack(void)
00067 {
00068     if (BLI_localInterruptCallBack) {
00069         return BLI_localInterruptCallBack();
00070     } else {
00071         return 0;
00072     }
00073 }
00074 #endif
00075 
00076 /* local types */
00077 typedef struct PolyFill {
00078     int edges,verts;
00079     float min[3],max[3];
00080     short f,nr;
00081 } PolyFill;
00082 
00083 typedef struct ScFillVert {
00084     EditVert *v1;
00085     EditEdge *first,*last;
00086 } ScFillVert;
00087 
00088 
00089 /* local funcs */
00090 
00091 #define COMPLIMIT   0.00003
00092 
00093 static ScFillVert *scdata;
00094 
00095 ListBase fillvertbase = {NULL, NULL};
00096 ListBase filledgebase = {NULL, NULL};
00097 ListBase fillfacebase = {NULL, NULL};
00098 
00099 static int cox, coy;
00100 
00101 /* ****  FUBCTIONS FOR QSORT *************************** */
00102 
00103 
00104 static int vergscdata(const void *a1, const void *a2)
00105 {
00106     const ScFillVert *x1=a1,*x2=a2;
00107     
00108     if( x1->v1->co[coy] < x2->v1->co[coy] ) return 1;
00109     else if( x1->v1->co[coy] > x2->v1->co[coy]) return -1;
00110     else if( x1->v1->co[cox] > x2->v1->co[cox] ) return 1;
00111     else if( x1->v1->co[cox] < x2->v1->co[cox]) return -1;
00112 
00113     return 0;
00114 }
00115 
00116 static int vergpoly(const void *a1, const void *a2)
00117 {
00118     const PolyFill *x1=a1, *x2=a2;
00119 
00120     if( x1->min[cox] > x2->min[cox] ) return 1;
00121     else if( x1->min[cox] < x2->min[cox] ) return -1;
00122     else if( x1->min[coy] > x2->min[coy] ) return 1;
00123     else if( x1->min[coy] < x2->min[coy] ) return -1;
00124     
00125     return 0;
00126 }
00127 
00128 /* ************* MEMORY MANAGEMENT ************* */
00129 
00130 struct mem_elements {
00131     struct mem_elements *next, *prev;
00132     char *data;
00133 };
00134 
00135 
00136 /* simple optimization for allocating thousands of small memory blocks
00137    only to be used within loops, and not by one function at a time
00138    free in the end, with argument '-1'
00139 */
00140 
00141 static void *new_mem_element(int size)
00142 {
00143     int blocksize= 16384;
00144     static int offs= 0;     /* the current free address */
00145     static struct mem_elements *cur= 0;
00146     static ListBase lb= {0, 0};
00147     void *adr;
00148     
00149     if(size>10000 || size==0) {
00150         printf("incorrect use of new_mem_element\n");
00151     }
00152     else if(size== -1) {
00153         cur= lb.first;
00154         while(cur) {
00155             MEM_freeN(cur->data);
00156             cur= cur->next;
00157         }
00158         BLI_freelistN(&lb);
00159         
00160         return NULL;    
00161     }
00162     
00163     size= 4*( (size+3)/4 );
00164     
00165     if(cur) {
00166         if(size+offs < blocksize) {
00167             adr= (void *) (cur->data+offs);
00168             offs+= size;
00169             return adr;
00170         }
00171     }
00172     
00173     cur= MEM_callocN( sizeof(struct mem_elements), "newmem");
00174     cur->data= MEM_callocN(blocksize, "newmem");
00175     BLI_addtail(&lb, cur);
00176     
00177     offs= size;
00178     return cur->data;
00179 }
00180 
00181 void BLI_end_edgefill(void)
00182 {
00183     new_mem_element(-1);
00184     
00185     fillvertbase.first= fillvertbase.last= 0;
00186     filledgebase.first= filledgebase.last= 0;
00187     fillfacebase.first= fillfacebase.last= 0;
00188 }
00189 
00190 /* ****  FILL ROUTINES *************************** */
00191 
00192 EditVert *BLI_addfillvert(float *vec)
00193 {
00194     EditVert *eve;
00195     
00196     eve= new_mem_element(sizeof(EditVert));
00197     BLI_addtail(&fillvertbase, eve);
00198     
00199     eve->co[0] = vec[0];
00200     eve->co[1] = vec[1];
00201     eve->co[2] = vec[2];
00202 
00203     return eve; 
00204 }
00205 
00206 EditEdge *BLI_addfilledge(EditVert *v1, EditVert *v2)
00207 {
00208     EditEdge *newed;
00209 
00210     newed= new_mem_element(sizeof(EditEdge));
00211     BLI_addtail(&filledgebase, newed);
00212     
00213     newed->v1= v1;
00214     newed->v2= v2;
00215 
00216     return newed;
00217 }
00218 
00219 static void addfillface(EditVert *v1, EditVert *v2, EditVert *v3, short mat_nr)
00220 {
00221     /* does not make edges */
00222     EditFace *evl;
00223 
00224     evl= new_mem_element(sizeof(EditFace));
00225     BLI_addtail(&fillfacebase, evl);
00226     
00227     evl->v1= v1;
00228     evl->v2= v2;
00229     evl->v3= v3;
00230     evl->f= 2;
00231     evl->mat_nr= mat_nr;
00232 }
00233 
00234 static int boundisect(PolyFill *pf2, PolyFill *pf1)
00235 {
00236     /* has pf2 been touched (intersected) by pf1 ? with bounding box */
00237     /* test first if polys exist */
00238 
00239     if(pf1->edges==0 || pf2->edges==0) return 0;
00240 
00241     if(pf2->max[cox] < pf1->min[cox] ) return 0;
00242     if(pf2->max[coy] < pf1->min[coy] ) return 0;
00243 
00244     if(pf2->min[cox] > pf1->max[cox] ) return 0;
00245     if(pf2->min[coy] > pf1->max[coy] ) return 0;
00246 
00247     /* join */
00248     if(pf2->max[cox]<pf1->max[cox]) pf2->max[cox]= pf1->max[cox];
00249     if(pf2->max[coy]<pf1->max[coy]) pf2->max[coy]= pf1->max[coy];
00250 
00251     if(pf2->min[cox]>pf1->min[cox]) pf2->min[cox]= pf1->min[cox];
00252     if(pf2->min[coy]>pf1->min[coy]) pf2->min[coy]= pf1->min[coy];
00253 
00254     return 1;
00255 }
00256 
00257 
00258 static void mergepolysSimp(PolyFill *pf1, PolyFill *pf2)    /* add pf2 to pf1 */
00259 {
00260     EditVert *eve;
00261     EditEdge *eed;
00262 
00263     /* replace old poly numbers */
00264     eve= fillvertbase.first;
00265     while(eve) {
00266         if(eve->xs== pf2->nr) eve->xs= pf1->nr;
00267         eve= eve->next;
00268     }
00269     eed= filledgebase.first;
00270     while(eed) {
00271         if(eed->f1== pf2->nr) eed->f1= pf1->nr;
00272         eed= eed->next;
00273     }
00274 
00275     pf1->verts+= pf2->verts;
00276     pf1->edges+= pf2->edges;
00277     pf2->verts= pf2->edges= 0;
00278     pf1->f= (pf1->f | pf2->f);
00279 }
00280 
00281 static short testedgeside(float *v1, float *v2, float *v3)
00282 /* is v3 to the right of v1-v2 ? With exception: v3==v1 || v3==v2 */
00283 {
00284     float inp;
00285 
00286     inp= (v2[cox]-v1[cox])*(v1[coy]-v3[coy])
00287         +(v1[coy]-v2[coy])*(v1[cox]-v3[cox]);
00288 
00289     if(inp < 0.0f) return 0;
00290     else if(inp==0) {
00291         if(v1[cox]==v3[cox] && v1[coy]==v3[coy]) return 0;
00292         if(v2[cox]==v3[cox] && v2[coy]==v3[coy]) return 0;
00293     }
00294     return 1;
00295 }
00296 
00297 static short addedgetoscanvert(ScFillVert *sc, EditEdge *eed)
00298 {
00299     /* find first edge to the right of eed, and insert eed before that */
00300     EditEdge *ed;
00301     float fac,fac1,x,y;
00302 
00303     if(sc->first==0) {
00304         sc->first= sc->last= eed;
00305         eed->prev= eed->next=0;
00306         return 1;
00307     }
00308 
00309     x= eed->v1->co[cox];
00310     y= eed->v1->co[coy];
00311 
00312     fac1= eed->v2->co[coy]-y;
00313     if(fac1==0.0f) {
00314         fac1= 1.0e10f*(eed->v2->co[cox]-x);
00315 
00316     }
00317     else fac1= (x-eed->v2->co[cox])/fac1;
00318 
00319     ed= sc->first;
00320     while(ed) {
00321 
00322         if(ed->v2==eed->v2) return 0;
00323 
00324         fac= ed->v2->co[coy]-y;
00325         if(fac==0.0f) {
00326             fac= 1.0e10f*(ed->v2->co[cox]-x);
00327 
00328         }
00329         else fac= (x-ed->v2->co[cox])/fac;
00330         if(fac>fac1) break;
00331 
00332         ed= ed->next;
00333     }
00334     if(ed) BLI_insertlinkbefore((ListBase *)&(sc->first), ed, eed);
00335     else BLI_addtail((ListBase *)&(sc->first),eed);
00336 
00337     return 1;
00338 }
00339 
00340 
00341 static ScFillVert *addedgetoscanlist(EditEdge *eed, int len)
00342 {
00343     /* inserts edge at correct location in ScFillVert list */
00344     /* returns sc when edge already exists */
00345     ScFillVert *sc,scsearch;
00346     EditVert *eve;
00347 
00348     /* which vert is left-top? */
00349     if(eed->v1->co[coy] == eed->v2->co[coy]) {
00350         if(eed->v1->co[cox] > eed->v2->co[cox]) {
00351             eve= eed->v1;
00352             eed->v1= eed->v2;
00353             eed->v2= eve;
00354         }
00355     }
00356     else if(eed->v1->co[coy] < eed->v2->co[coy]) {
00357         eve= eed->v1;
00358         eed->v1= eed->v2;
00359         eed->v2= eve;
00360     }
00361     /* find location in list */
00362     scsearch.v1= eed->v1;
00363     sc= (ScFillVert *)bsearch(&scsearch,scdata,len,
00364         sizeof(ScFillVert), vergscdata);
00365 
00366     if(sc==0) printf("Error in search edge: %p\n", (void *)eed);
00367     else if(addedgetoscanvert(sc,eed)==0) return sc;
00368 
00369     return 0;
00370 }
00371 
00372 static short boundinsideEV(EditEdge *eed, EditVert *eve)
00373 /* is eve inside boundbox eed */
00374 {
00375     float minx,maxx,miny,maxy;
00376 
00377     if(eed->v1->co[cox]<eed->v2->co[cox]) {
00378         minx= eed->v1->co[cox];
00379         maxx= eed->v2->co[cox];
00380     } else {
00381         minx= eed->v2->co[cox];
00382         maxx= eed->v1->co[cox];
00383     }
00384     if(eve->co[cox]>=minx && eve->co[cox]<=maxx) {
00385         if(eed->v1->co[coy]<eed->v2->co[coy]) {
00386             miny= eed->v1->co[coy];
00387             maxy= eed->v2->co[coy];
00388         } else {
00389             miny= eed->v2->co[coy];
00390             maxy= eed->v1->co[coy];
00391         }
00392         if(eve->co[coy]>=miny && eve->co[coy]<=maxy) return 1;
00393     }
00394     return 0;
00395 }
00396 
00397 
00398 static void testvertexnearedge(void)
00399 {
00400     /* only vertices with ->h==1 are being tested for
00401         being close to an edge, if true insert */
00402 
00403     EditVert *eve;
00404     EditEdge *eed,*ed1;
00405     float dist,vec1[2],vec2[2],vec3[2];
00406 
00407     eve= fillvertbase.first;
00408     while(eve) {
00409         if(eve->h==1) {
00410             vec3[0]= eve->co[cox];
00411             vec3[1]= eve->co[coy];
00412             /* find the edge which has vertex eve */
00413             ed1= filledgebase.first;
00414             while(ed1) {
00415                 if(ed1->v1==eve || ed1->v2==eve) break;
00416                 ed1= ed1->next;
00417             }
00418             if(ed1->v1==eve) {
00419                 ed1->v1= ed1->v2;
00420                 ed1->v2= eve;
00421             }
00422             eed= filledgebase.first;
00423             while(eed) {
00424                 if(eve!=eed->v1 && eve!=eed->v2 && eve->xs==eed->f1) {
00425                     if(compare_v3v3(eve->co,eed->v1->co, COMPLIMIT)) {
00426                         ed1->v2= eed->v1;
00427                         eed->v1->h++;
00428                         eve->h= 0;
00429                         break;
00430                     }
00431                     else if(compare_v3v3(eve->co,eed->v2->co, COMPLIMIT)) {
00432                         ed1->v2= eed->v2;
00433                         eed->v2->h++;
00434                         eve->h= 0;
00435                         break;
00436                     }
00437                     else {
00438                         vec1[0]= eed->v1->co[cox];
00439                         vec1[1]= eed->v1->co[coy];
00440                         vec2[0]= eed->v2->co[cox];
00441                         vec2[1]= eed->v2->co[coy];
00442                         if(boundinsideEV(eed,eve)) {
00443                             dist= dist_to_line_v2(vec1,vec2,vec3);
00444                             if(dist<(float)COMPLIMIT) {
00445                                 /* new edge */
00446                                 ed1= BLI_addfilledge(eed->v1, eve);
00447                                 
00448                                 /* printf("fill: vertex near edge %x\n",eve); */
00449                                 ed1->f= ed1->h= 0;
00450                                 ed1->f1= eed->f1;
00451                                 eed->v1= eve;
00452                                 eve->h= 3;
00453                                 break;
00454                             }
00455                         }
00456                     }
00457                 }
00458                 eed= eed->next;
00459             }
00460         }
00461         eve= eve->next;
00462     }
00463 }
00464 
00465 static void splitlist(ListBase *tempve, ListBase *temped, short nr)
00466 {
00467     /* everything is in templist, write only poly nr to fillist */
00468     EditVert *eve,*nextve;
00469     EditEdge *eed,*nexted;
00470 
00471     BLI_movelisttolist(tempve,&fillvertbase);
00472     BLI_movelisttolist(temped,&filledgebase);
00473 
00474     eve= tempve->first;
00475     while(eve) {
00476         nextve= eve->next;
00477         if(eve->xs==nr) {
00478             BLI_remlink(tempve,eve);
00479             BLI_addtail(&fillvertbase,eve);
00480         }
00481         eve= nextve;
00482     }
00483     eed= temped->first;
00484     while(eed) {
00485         nexted= eed->next;
00486         if(eed->f1==nr) {
00487             BLI_remlink(temped,eed);
00488             BLI_addtail(&filledgebase,eed);
00489         }
00490         eed= nexted;
00491     }
00492 }
00493 
00494 
00495 static int scanfill(PolyFill *pf, short mat_nr)
00496 {
00497     ScFillVert *sc = NULL, *sc1;
00498     EditVert *eve,*v1,*v2,*v3;
00499     EditEdge *eed,*nexted,*ed1,*ed2,*ed3;
00500     float miny = 0.0;
00501     int a,b,verts, maxface, totface;    
00502     short nr, test, twoconnected=0;
00503 
00504     nr= pf->nr;
00505 
00506     /* PRINTS
00507     verts= pf->verts;
00508     eve= fillvertbase.first;
00509     while(eve) {
00510         printf("vert: %x co: %f %f\n",eve,eve->co[cox],eve->co[coy]);
00511         eve= eve->next;
00512     }   
00513     eed= filledgebase.first;
00514     while(eed) {
00515         printf("edge: %x  verts: %x %x\n",eed,eed->v1,eed->v2);
00516         eed= eed->next;
00517     } */
00518 
00519     /* STEP 0: remove zero sized edges */
00520     eed= filledgebase.first;
00521     while(eed) {
00522         if(eed->v1->co[cox]==eed->v2->co[cox]) {
00523             if(eed->v1->co[coy]==eed->v2->co[coy]) {
00524                 if(eed->v1->f==255 && eed->v2->f!=255) {
00525                     eed->v2->f= 255;
00526                     eed->v2->tmp.v= eed->v1->tmp.v;
00527                 }
00528                 else if(eed->v2->f==255 && eed->v1->f!=255) {
00529                     eed->v1->f= 255;
00530                     eed->v1->tmp.v= eed->v2->tmp.v;
00531                 }
00532                 else if(eed->v2->f==255 && eed->v1->f==255) {
00533                     eed->v1->tmp.v= eed->v2->tmp.v;
00534                 }
00535                 else {
00536                     eed->v2->f= 255;
00537                     eed->v2->tmp.v = eed->v1->tmp.v;
00538                 }
00539             }
00540         }
00541         eed= eed->next;
00542     }
00543 
00544     /* STEP 1: make using FillVert and FillEdge lists a sorted
00545         ScFillVert list
00546     */
00547     sc= scdata= (ScFillVert *)MEM_callocN(pf->verts*sizeof(ScFillVert),"Scanfill1");
00548     eve= fillvertbase.first;
00549     verts= 0;
00550     while(eve) {
00551         if(eve->xs==nr) {
00552             if(eve->f!= 255) {
00553                 verts++;
00554                 eve->f= 0;  /* flag for connectedges later on */
00555                 sc->v1= eve;
00556                 sc++;
00557             }
00558         }
00559         eve= eve->next;
00560     }
00561 
00562     qsort(scdata, verts, sizeof(ScFillVert), vergscdata);
00563 
00564     eed= filledgebase.first;
00565     while(eed) {
00566         nexted= eed->next;
00567         eed->f= 0;
00568         BLI_remlink(&filledgebase,eed);
00569 /* commented all of this out, this I have no idea for what it is for, probably from ancient past */
00570 /* it does crash blender, since it uses mixed original and new vertices (ton) */
00571 //      if(eed->v1->f==255) {
00572 //          v1= eed->v1;
00573 //          while((eed->v1->f == 255) && (eed->v1->tmp.v != v1)) 
00574 //              eed->v1 = eed->v1->tmp.v;
00575 //      }
00576 //      if(eed->v2->f==255) {
00577 //          v2= eed->v2;
00578 //          while((eed->v2->f == 255) && (eed->v2->tmp.v != v2))
00579 //              eed->v2 = eed->v2->tmp.v;
00580 //      }
00581         if(eed->v1!=eed->v2) addedgetoscanlist(eed,verts);
00582 
00583         eed= nexted;
00584     }
00585     /*
00586     sc= scdata;
00587     for(a=0;a<verts;a++) {
00588         printf("\nscvert: %x\n",sc->v1);
00589         eed= sc->first;
00590         while(eed) {
00591             printf(" ed %x %x %x\n",eed,eed->v1,eed->v2);
00592             eed= eed->next;
00593         }
00594         sc++;
00595     }*/
00596 
00597 
00598     /* STEP 2: FILL LOOP */
00599 
00600     if(pf->f==0) twoconnected= 1;
00601 
00602     /* (temporal) security: never much more faces than vertices */
00603     totface= 0;
00604     maxface= 2*verts;       /* 2*verts: based at a filled circle within a triangle */
00605 
00606     sc= scdata;
00607     for(a=0;a<verts;a++) {
00608         /* printf("VERTEX %d %x\n",a,sc->v1); */
00609         ed1= sc->first;
00610         while(ed1) {    /* set connectflags  */
00611             nexted= ed1->next;
00612             if(ed1->v1->h==1 || ed1->v2->h==1) {
00613                 BLI_remlink((ListBase *)&(sc->first),ed1);
00614                 BLI_addtail(&filledgebase,ed1);
00615                 if(ed1->v1->h>1) ed1->v1->h--;
00616                 if(ed1->v2->h>1) ed1->v2->h--;
00617             }
00618             else ed1->v2->f= 1;
00619 
00620             ed1= nexted;
00621         }
00622         while(sc->first) {  /* for as long there are edges */
00623             ed1= sc->first;
00624             ed2= ed1->next;
00625             
00626             /* commented out... the ESC here delivers corrupted memory (and doesnt work during grab) */
00627             /* if(callLocalInterruptCallBack()) break; */
00628             if(totface>maxface) {
00629                 /* printf("Fill error: endless loop. Escaped at vert %d,  tot: %d.\n", a, verts); */
00630                 a= verts;
00631                 break;
00632             }
00633             if(ed2==0) {
00634                 sc->first=sc->last= 0;
00635                 /* printf("just 1 edge to vert\n"); */
00636                 BLI_addtail(&filledgebase,ed1);
00637                 ed1->v2->f= 0;
00638                 ed1->v1->h--; 
00639                 ed1->v2->h--;
00640             } else {
00641                 /* test rest of vertices */
00642                 v1= ed1->v2;
00643                 v2= ed1->v1;
00644                 v3= ed2->v2;
00645                 /* this happens with a serial of overlapping edges */
00646                 if(v1==v2 || v2==v3) break;
00647                 /* printf("test verts %x %x %x\n",v1,v2,v3); */
00648                 miny = ( (v1->co[coy])<(v3->co[coy]) ? (v1->co[coy]) : (v3->co[coy]) );
00649                 /*  miny= MIN2(v1->co[coy],v3->co[coy]); */
00650                 sc1= sc+1;
00651                 test= 0;
00652 
00653                 for(b=a+1;b<verts;b++) {
00654                     if(sc1->v1->f==0) {
00655                         if(sc1->v1->co[coy] <= miny) break;
00656 
00657                         if(testedgeside(v1->co,v2->co,sc1->v1->co))
00658                             if(testedgeside(v2->co,v3->co,sc1->v1->co))
00659                                 if(testedgeside(v3->co,v1->co,sc1->v1->co)) {
00660                                     /* point in triangle */
00661                                 
00662                                     test= 1;
00663                                     break;
00664                                 }
00665                     }
00666                     sc1++;
00667                 }
00668                 if(test) {
00669                     /* make new edge, and start over */
00670                     /* printf("add new edge %x %x and start again\n",v2,sc1->v1); */
00671 
00672                     ed3= BLI_addfilledge(v2, sc1->v1);
00673                     BLI_remlink(&filledgebase, ed3);
00674                     BLI_insertlinkbefore((ListBase *)&(sc->first), ed2, ed3);
00675                     ed3->v2->f= 1;
00676                     ed3->f= 2;
00677                     ed3->v1->h++; 
00678                     ed3->v2->h++;
00679                 }
00680                 else {
00681                     /* new triangle */
00682                     /* printf("add face %x %x %x\n",v1,v2,v3); */
00683                     addfillface(v1, v2, v3, mat_nr);
00684                     totface++;
00685                     BLI_remlink((ListBase *)&(sc->first),ed1);
00686                     BLI_addtail(&filledgebase,ed1);
00687                     ed1->v2->f= 0;
00688                     ed1->v1->h--; 
00689                     ed1->v2->h--;
00690                     /* ed2 can be removed when it's an old one */
00691                     if(ed2->f==0 && twoconnected) {
00692                         BLI_remlink((ListBase *)&(sc->first),ed2);
00693                         BLI_addtail(&filledgebase,ed2);
00694                         ed2->v2->f= 0;
00695                         ed2->v1->h--; 
00696                         ed2->v2->h--;
00697                     }
00698 
00699                     /* new edge */
00700                     ed3= BLI_addfilledge(v1, v3);
00701                     BLI_remlink(&filledgebase, ed3);
00702                     ed3->f= 2;
00703                     ed3->v1->h++; 
00704                     ed3->v2->h++;
00705                     
00706                     /* printf("add new edge %x %x\n",v1,v3); */
00707                     sc1= addedgetoscanlist(ed3, verts);
00708                     
00709                     if(sc1) {   /* ed3 already exists: remove */
00710                         /* printf("Edge exists\n"); */
00711                         ed3->v1->h--; 
00712                         ed3->v2->h--;
00713 
00714                         if(twoconnected) ed3= sc1->first;
00715                         else ed3= 0;
00716                         while(ed3) {
00717                             if( (ed3->v1==v1 && ed3->v2==v3) || (ed3->v1==v3 && ed3->v2==v1) ) {
00718                                 BLI_remlink((ListBase *)&(sc1->first),ed3);
00719                                 BLI_addtail(&filledgebase,ed3);
00720                                 ed3->v1->h--; 
00721                                 ed3->v2->h--;
00722                                 break;
00723                             }
00724                             ed3= ed3->next;
00725                         }
00726                     }
00727 
00728                 }
00729             }
00730             /* test for loose edges */
00731             ed1= sc->first;
00732             while(ed1) {
00733                 nexted= ed1->next;
00734                 if(ed1->v1->h<2 || ed1->v2->h<2) {
00735                     BLI_remlink((ListBase *)&(sc->first),ed1);
00736                     BLI_addtail(&filledgebase,ed1);
00737                     if(ed1->v1->h>1) ed1->v1->h--;
00738                     if(ed1->v2->h>1) ed1->v2->h--;
00739                 }
00740 
00741                 ed1= nexted;
00742             }
00743         }
00744         sc++;
00745     }
00746 
00747     MEM_freeN(scdata);
00748 
00749     return totface;
00750 }
00751 
00752 
00753 
00754 int BLI_edgefill(short mat_nr)
00755 {
00756     /*
00757       - fill works with its own lists, so create that first (no faces!)
00758       - for vertices, put in ->tmp.v the old pointer
00759       - struct elements xs en ys are not used here: don't hide stuff in it
00760       - edge flag ->f becomes 2 when it's a new edge
00761       - mode: & 1 is check for crossings, then create edges (TO DO )
00762       - returns number of triangle faces added.
00763     */
00764     ListBase tempve, temped;
00765     EditVert *eve;
00766     EditEdge *eed,*nexted;
00767     PolyFill *pflist,*pf;
00768     float *minp, *maxp, *v1, *v2, norm[3], len;
00769     short a,c,poly=0,ok=0,toggle=0;
00770     int totfaces= 0; /* total faces added */
00771 
00772     /* reset variables */
00773     eve= fillvertbase.first;
00774     while(eve) {
00775         eve->f= 0;
00776         eve->xs= 0;
00777         eve->h= 0;
00778         eve= eve->next;
00779     }
00780 
00781     /* first test vertices if they are in edges */
00782     /* including resetting of flags */
00783     eed= filledgebase.first;
00784     while(eed) {
00785         eed->f= eed->f1= eed->h= 0;
00786         eed->v1->f= 1;
00787         eed->v2->f= 1;
00788 
00789         eed= eed->next;
00790     }
00791 
00792     eve= fillvertbase.first;
00793     while(eve) {
00794         if(eve->f & 1) {
00795             ok=1; 
00796             break;
00797         }
00798         eve= eve->next;
00799     }
00800 
00801     if(ok==0) return 0;
00802 
00803     /* NEW NEW! define projection: with 'best' normal */
00804     /* just use the first three different vertices */
00805     
00806     /* THIS PART STILL IS PRETTY WEAK! (ton) */
00807     
00808     eve= fillvertbase.last;
00809     len= 0.0;
00810     v1= eve->co;
00811     v2= 0;
00812     eve= fillvertbase.first;
00813     while(eve) {
00814         if(v2) {
00815             if( compare_v3v3(v2, eve->co, COMPLIMIT)==0) {
00816                 len= normal_tri_v3( norm,v1, v2, eve->co);
00817                 if(len != 0.0f) break;
00818             }
00819         }
00820         else if(compare_v3v3(v1, eve->co, COMPLIMIT)==0) {
00821             v2= eve->co;
00822         }
00823         eve= eve->next;
00824     }
00825 
00826     if(len==0.0f) return 0; /* no fill possible */
00827 
00828     axis_dominant_v3(&cox, &coy, norm);
00829 
00830     /* STEP 1: COUNT POLYS */
00831     eve= fillvertbase.first;
00832     while(eve) {
00833         /* get first vertex with no poly number */
00834         if(eve->xs==0) {
00835             poly++;
00836             /* now a sortof select connected */
00837             ok= 1;
00838             eve->xs= poly;
00839             
00840             while(ok) {
00841                 
00842                 ok= 0;
00843                 toggle++;
00844                 if(toggle & 1) eed= filledgebase.first;
00845                 else eed= filledgebase.last;
00846 
00847                 while(eed) {
00848                     if(eed->v1->xs==0 && eed->v2->xs==poly) {
00849                         eed->v1->xs= poly;
00850                         eed->f1= poly;
00851                         ok= 1;
00852                     }
00853                     else if(eed->v2->xs==0 && eed->v1->xs==poly) {
00854                         eed->v2->xs= poly;
00855                         eed->f1= poly;
00856                         ok= 1;
00857                     }
00858                     else if(eed->f1==0) {
00859                         if(eed->v1->xs==poly && eed->v2->xs==poly) {
00860                             eed->f1= poly;
00861                             ok= 1;
00862                         }
00863                     }
00864                     if(toggle & 1) eed= eed->next;
00865                     else eed= eed->prev;
00866                 }
00867             }
00868         }
00869         eve= eve->next;
00870     }
00871     /* printf("amount of poly's: %d\n",poly); */
00872 
00873     /* STEP 2: remove loose edges and strings of edges */
00874     eed= filledgebase.first;
00875     while(eed) {
00876         if(eed->v1->h++ >250) break;
00877         if(eed->v2->h++ >250) break;
00878         eed= eed->next;
00879     }
00880     if(eed) {
00881         /* otherwise it's impossible to be sure you can clear vertices */
00882         callLocalErrorCallBack("No vertices with 250 edges allowed!");
00883         return 0;
00884     }
00885     
00886     /* does it only for vertices with ->h==1 */
00887     testvertexnearedge();
00888 
00889     ok= 1;
00890     while(ok) {
00891         ok= 0;
00892         toggle++;
00893         if(toggle & 1) eed= filledgebase.first;
00894         else eed= filledgebase.last;
00895         while(eed) {
00896             if(toggle & 1) nexted= eed->next;
00897             else nexted= eed->prev;
00898             if(eed->v1->h==1) {
00899                 eed->v2->h--;
00900                 BLI_remlink(&fillvertbase,eed->v1); 
00901                 BLI_remlink(&filledgebase,eed); 
00902                 ok= 1;
00903             }
00904             else if(eed->v2->h==1) {
00905                 eed->v1->h--;
00906                 BLI_remlink(&fillvertbase,eed->v2); 
00907                 BLI_remlink(&filledgebase,eed); 
00908                 ok= 1;
00909             }
00910             eed= nexted;
00911         }
00912     }
00913     if(filledgebase.first==0) {
00914         /* printf("All edges removed\n"); */
00915         return 0;
00916     }
00917 
00918 
00919     /* CURRENT STATUS:
00920     - eve->f      :1= availalble in edges
00921     - eve->xs     :polynumber
00922     - eve->h      :amount of edges connected to vertex
00923     - eve->tmp.v  :store! original vertex number
00924 
00925     - eed->f  :
00926     - eed->f1 :poly number
00927     */
00928 
00929 
00930     /* STEP 3: MAKE POLYFILL STRUCT */
00931     pflist= (PolyFill *)MEM_callocN(poly*sizeof(PolyFill),"edgefill");
00932     pf= pflist;
00933     for(a=1;a<=poly;a++) {
00934         pf->nr= a;
00935         pf->min[0]=pf->min[1]=pf->min[2]= 1.0e20;
00936         pf->max[0]=pf->max[1]=pf->max[2]= -1.0e20;
00937         pf++;
00938     }
00939     eed= filledgebase.first;
00940     while(eed) {
00941         pflist[eed->f1-1].edges++;
00942         eed= eed->next;
00943     }
00944 
00945     eve= fillvertbase.first;
00946     while(eve) {
00947         pflist[eve->xs-1].verts++;
00948         minp= pflist[eve->xs-1].min;
00949         maxp= pflist[eve->xs-1].max;
00950 
00951         minp[cox]= (minp[cox])<(eve->co[cox]) ? (minp[cox]) : (eve->co[cox]);
00952         minp[coy]= (minp[coy])<(eve->co[coy]) ? (minp[coy]) : (eve->co[coy]);
00953         maxp[cox]= (maxp[cox])>(eve->co[cox]) ? (maxp[cox]) : (eve->co[cox]);
00954         maxp[coy]= (maxp[coy])>(eve->co[coy]) ? (maxp[coy]) : (eve->co[coy]);
00955         if(eve->h>2) pflist[eve->xs-1].f= 1;
00956 
00957         eve= eve->next;
00958     }
00959 
00960     /* STEP 4: FIND HOLES OR BOUNDS, JOIN THEM
00961      *  ( bounds just to divide it in pieces for optimization, 
00962      *    the edgefill itself has good auto-hole detection)
00963      * WATCH IT: ONLY WORKS WITH SORTED POLYS!!! */
00964     
00965     if(poly>1) {
00966         short *polycache, *pc;
00967 
00968         /* so, sort first */
00969         qsort(pflist, poly, sizeof(PolyFill), vergpoly);
00970         
00971         /*pf= pflist;
00972         for(a=1;a<=poly;a++) {
00973             printf("poly:%d edges:%d verts:%d flag: %d\n",a,pf->edges,pf->verts,pf->f);
00974             PRINT2(f, f, pf->min[0], pf->min[1]);
00975             pf++;
00976         }*/
00977     
00978         polycache= pc= MEM_callocN(sizeof(short)*poly, "polycache");
00979         pf= pflist;
00980         for(a=0; a<poly; a++, pf++) {
00981             for(c=a+1;c<poly;c++) {
00982                 
00983                 /* if 'a' inside 'c': join (bbox too)
00984                  * Careful: 'a' can also be inside another poly.
00985                  */
00986                 if(boundisect(pf, pflist+c)) {
00987                     *pc= c;
00988                     pc++;
00989                 }
00990                 /* only for optimize! */
00991                 /* else if(pf->max[cox] < (pflist+c)->min[cox]) break; */
00992                 
00993             }
00994             while(pc!=polycache) {
00995                 pc--;
00996                 mergepolysSimp(pf, pflist+ *pc);
00997             }
00998         }
00999         MEM_freeN(polycache);
01000     }
01001     
01002     /* printf("after merge\n");
01003     pf= pflist;
01004     for(a=1;a<=poly;a++) {
01005         printf("poly:%d edges:%d verts:%d flag: %d\n",a,pf->edges,pf->verts,pf->f);
01006         pf++;
01007     } */
01008 
01009     /* STEP 5: MAKE TRIANGLES */
01010 
01011     tempve.first= fillvertbase.first;
01012     tempve.last= fillvertbase.last;
01013     temped.first= filledgebase.first;
01014     temped.last= filledgebase.last;
01015     fillvertbase.first=fillvertbase.last= 0;
01016     filledgebase.first=filledgebase.last= 0;
01017 
01018     pf= pflist;
01019     for(a=0;a<poly;a++) {
01020         if(pf->edges>1) {
01021             splitlist(&tempve,&temped,pf->nr);
01022             totfaces += scanfill(pf, mat_nr);
01023         }
01024         pf++;
01025     }
01026     BLI_movelisttolist(&fillvertbase,&tempve);
01027     BLI_movelisttolist(&filledgebase,&temped);
01028 
01029     /* FREE */
01030 
01031     MEM_freeN(pflist);
01032 
01033     return totfaces;
01034 }