source/blender/blenlib/intern/scanfill.c

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