source/blender/blenlib/intern/scanfill.c

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