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