src/livarot/int-line.cpp

   1 /**
   2  *  \file livarot/int-line.cpp
   3  *
   4  * Implementation of coverage with integer boundaries.
   5  *
   6  *  \author Fred
   7  *
   8  *  public domain
   9  *
  10  */
  11
  12 #include <glib/gmem.h>
  13 #include <cmath>
  14 #include "livarot/int-line.h"
  15 #include "livarot/float-line.h"
  16 #include "livarot/BitLigne.h"
  17
  18 IntLigne::IntLigne()
  19 {
  20     nbBord = maxBord = 0;
  21     bords = NULL;
  22
  23     nbRun = maxRun = 0;
  24     runs = NULL;
  25
  26     firstAc = lastAc = -1;
  27 }
  28
  29
  30 IntLigne::~IntLigne()
  31 {
  32     if ( maxBord > 0 ) {
  33         g_free(bords);
  34         nbBord = maxBord = 0;
  35         bords = NULL;
  36     }
  37     if ( maxRun > 0 ) {
  38         g_free(runs);
  39         nbRun = maxRun = 0;
  40         runs = NULL;
  41     }
  42 }
  43
  44 void IntLigne::Reset()
  45 {
  46     nbBord = 0;
  47     nbRun = 0;
  48     firstAc = lastAc = -1;
  49 }
  50
  51 int IntLigne::AddBord(int spos, float sval, int epos, float eval)
  52 {
  53     if ( nbBord + 1 >= maxBord ) {
  54         maxBord = 2 * nbBord + 2;
  55         bords = (int_ligne_bord *) g_realloc(bords, maxBord * sizeof(int_ligne_bord));
  56
  57     }
  58
  59     int n = nbBord++;
  60     bords[n].pos = spos;
  61     bords[n].val = sval;
  62     bords[n].start = true;
  63     bords[n].other = n+1;
  64     bords[n].prev = bords[n].next = -1;
  65
  66     n = nbBord++;
  67     bords[n].pos = epos;
  68     bords[n].val = eval;
  69     bords[n].start = false;
  70     bords[n].other = n-1;
  71     bords[n].prev = bords[n].next = -1;
  72
  73     return n - 1;
  74 }
  75
  76
  77 float IntLigne::RemainingValAt(int at)
  78 {
  79     int no = firstAc;
  80     float sum = 0;
  81     while ( no >= 0 ) {
  82         int nn = bords[no].other;
  83         sum += ValAt(at, bords[nn].pos, bords[no].pos, bords[nn].val, bords[no].val);
  84         no = bords[no].next;
  85     }
  86     return sum;
  87 }
  88
  89 void IntLigne::Flatten()
  90 {
  91     if ( nbBord <= 1 ) {
  92         Reset();
  93         return;
  94     }
  95
  96     nbRun = 0;
  97     firstAc = lastAc = -1;
  98
  99     for (int i = 0; i < nbBord; i++) {
 100         bords[i].prev = i;
 101     }
 102
 103     qsort(bords, nbBord, sizeof(int_ligne_bord), IntLigne::CmpBord);
 104     for (int i = 0; i < nbBord; i++) {
 105         bords[bords[i].prev].next = i;
 106     }
 107
 108     for (int i = 0; i < nbBord; i++) {
 109         bords[i].other = bords[bords[i].other].next;
 110     }
 111
 112     int lastStart = 0;
 113     float lastVal = 0;
 114     bool startExists = false;
 115
 116     for (int i = 0; i < nbBord; ) {
 117         int cur = bords[i].pos;
 118         float leftV = 0;
 119         float rightV = 0;
 120         float midV = 0;
 121         while ( i < nbBord && bords[i].pos == cur && bords[i].start == false ) {
 122             Dequeue(i);
 123             leftV += bords[i].val;
 124             i++;
 125         }
 126         midV = RemainingValAt(cur);
 127         while ( i < nbBord && bords[i].pos == cur && bords[i].start == true ) {
 128             rightV += bords[i].val;
 129             Enqueue(bords[i].other);
 130             i++;
 131         }
 132
 133         if ( startExists ) {
 134             AddRun(lastStart, cur, lastVal, leftV + midV);
 135         }
 136         if ( firstAc >= 0 ) {
 137             startExists = true;
 138             lastVal = midV + rightV;
 139             lastStart = cur;
 140         } else {
 141             startExists = false;
 142         }
 143     }
 144 }
 145
 146
 147 void IntLigne::Affiche()
 148 {
 149     printf("%i : \n", nbRun);
 150     for (int i = 0; i < nbRun;i++) {
 151         printf("(%i %f -> %i %f) ", runs[i].st, runs[i].vst, runs[i].en, runs[i].ven); // localization ok
 152     }
 153     printf("\n");
 154 }
 155
 156 int IntLigne::AddRun(int st, int en, float vst, float ven)
 157 {
 158     if ( st >= en ) {
 159         return -1;
 160     }
 161
 162     if ( nbRun >= maxRun ) {
 163         maxRun = 2 * nbRun + 1;
 164         runs = (int_ligne_run *) g_realloc(runs, maxRun * sizeof(int_ligne_run));
 165     }
 166
 167     int n = nbRun++;
 168     runs[n].st = st;
 169     runs[n].en = en;
 170     runs[n].vst = vst;
 171     runs[n].ven = ven;
 172     return n;
 173 }
 174
 175 void IntLigne::Booleen(IntLigne *a, IntLigne *b, BooleanOp mod)
 176 {
 177     Reset();
 178     if ( a->nbRun <= 0 && b->nbRun <= 0 ) {
 179         return;
 180     }
 181
 182     if ( a->nbRun <= 0 ) {
 183         if ( mod == bool_op_union || mod == bool_op_symdiff ) {
 184             Copy(b);
 185         }
 186         return;
 187     }
 188
 189     if ( b->nbRun <= 0 ) {
 190         if ( mod == bool_op_union || mod == bool_op_diff || mod == bool_op_symdiff ) {
 191             Copy(a);
 192         }
 193         return;
 194     }
 195
 196     int curA = 0;
 197     int curB = 0;
 198     int curPos = (a->runs[0].st < b->runs[0].st) ? a->runs[0].st : b->runs[0].st;
 199     int nextPos = curPos;
 200     float valA = 0;
 201     float valB = 0;
 202     if ( curPos == a->runs[0].st ) {
 203         valA = a->runs[0].vst;
 204     }
 205     if ( curPos == b->runs[0].st ) {
 206         valB = b->runs[0].vst;
 207     }
 208
 209     while ( curA < a->nbRun && curB < b->nbRun ) {
 210         int_ligne_run runA = a->runs[curA];
 211         int_ligne_run runB = b->runs[curB];
 212         const bool inA = ( curPos >= runA.st && curPos < runA.en );
 213         const bool inB = ( curPos >= runB.st && curPos < runB.en );
 214
 215         bool startA = false;
 216         bool startB = false;
 217         bool endA = false;
 218         bool endB = false;
 219
 220         if ( curPos < runA.st ) {
 221             if ( curPos < runB.st ) {
 222                 startA = runA.st <= runB.st;
 223                 startB = runA.st >= runB.st;
 224                 nextPos = startA ? runA.st : runB.st;
 225             } else if ( curPos >= runB.st ) {
 226                 startA = runA.st <= runB.en;
 227                 endB = runA.st >= runB.en;
 228                 nextPos = startA ? runA.st : runB.en;
 229             }
 230         } else if ( curPos == runA.st ) {
 231             if ( curPos < runB.st ) {
 232                 endA = runA.en <= runB.st;
 233                 startB = runA.en >= runB.st;
 234                 nextPos = startB ? runB.en : runA.st;
 235             } else if ( curPos == runB.st ) {
 236                 endA = runA.en <= runB.en;
 237                 endB = runA.en >= runB.en;
 238                 nextPos = endA? runA.en : runB.en;
 239             } else {
 240                 endA = runA.en <= runB.en;
 241                 endB = runA.en >= runB.en;
 242                 nextPos = endA ? runA.en : runB.en;
 243             }
 244         } else {
 245             if ( curPos < runB.st ) {
 246                 endA = runA.en <= runB.st;
 247                 startB = runA.en >= runB.st;
 248                 nextPos = startB ? runB.st : runA.en;
 249             } else if ( curPos == runB.st ) {
 250                 endA = runA.en <= runB.en;
 251                 endB = runA.en >= runB.en;
 252                 nextPos = endA ? runA.en : runB.en;
 253             } else {
 254                 endA = runA.en <= runB.en;
 255                 endB = runA.en >= runB.en;
 256                 nextPos = endA ? runA.en : runB.en;
 257             }
 258         }
 259
 260         float oValA = valA;
 261         float oValB = valB;
 262         valA = inA ? ValAt(nextPos, runA.st, runA.en, runA.vst, runA.ven) : 0;
 263         valB = inB ? ValAt(nextPos, runB.st, runB.en, runB.vst, runB.ven) : 0;
 264
 265         if ( mod == bool_op_union ) {
 266
 267             if ( inA || inB ) {
 268                 AddRun(curPos, nextPos, oValA + oValB, valA + valB);
 269             }
 270
 271         } else if ( mod == bool_op_inters ) {
 272
 273             if ( inA && inB ) {
 274                 AddRun(curPos, nextPos, oValA * oValB, valA * valB);
 275             }
 276
 277         } else if ( mod == bool_op_diff ) {
 278
 279             if ( inA ) {
 280                 AddRun(curPos, nextPos, oValA - oValB, valA - valB);
 281             }
 282
 283         } else if ( mod == bool_op_symdiff ) {
 284             if ( inA && !(inB) ) {
 285                 AddRun(curPos, nextPos, oValA - oValB, valA - valB);
 286             }
 287             if ( !(inA) && inB ) {
 288                 AddRun(curPos, nextPos, oValB - oValA, valB - valA);
 289             }
 290         }
 291
 292         curPos = nextPos;
 293         if ( startA ) {
 294             // inA=true; these are never used
 295             valA = runA.vst;
 296         }
 297         if ( startB ) {
 298             //inB=true;
 299             valB = runB.vst;
 300         }
 301         if ( endA ) {
 302             //inA=false;
 303             valA = 0;
 304             curA++;
 305             if ( curA < a->nbRun && a->runs[curA].st == curPos ) {
 306                 valA = a->runs[curA].vst;
 307             }
 308         }
 309         if ( endB ) {
 310             //inB=false;
 311             valB = 0;
 312             curB++;
 313             if ( curB < b->nbRun && b->runs[curB].st == curPos ) {
 314                 valB = b->runs[curB].vst;
 315             }
 316         }
 317     }
 318
 319     while ( curA < a->nbRun ) {
 320         int_ligne_run runA = a->runs[curA];
 321         const bool inA = ( curPos >= runA.st && curPos < runA.en );
 322         const bool inB = false;
 323
 324         bool startA = false;
 325         bool endA = false;
 326         if ( curPos < runA.st ) {
 327             nextPos = runA.st;
 328             startA = true;
 329         } else if ( curPos >= runA.st ) {
 330             nextPos = runA.en;
 331             endA = true;
 332         }
 333
 334         float oValA = valA;
 335         float oValB = valB;
 336         valA = inA ? ValAt(nextPos,runA.st, runA.en, runA.vst, runA.ven) : 0;
 337         valB = 0;
 338
 339         if ( mod == bool_op_union ) {
 340             if ( inA || inB ) {
 341                 AddRun(curPos, nextPos, oValA + oValB, valA + valB);
 342             }
 343         } else if ( mod == bool_op_inters ) {
 344             if ( inA && inB ) {
 345                 AddRun(curPos, nextPos, oValA * oValB, valA * valB);
 346             }
 347         } else if ( mod == bool_op_diff ) {
 348             if ( inA ) {
 349                 AddRun(curPos, nextPos, oValA - oValB, valA - valB);
 350             }
 351         } else if ( mod == bool_op_symdiff ) {
 352             if ( inA && !(inB) ) {
 353                 AddRun(curPos, nextPos, oValA - oValB, valA - valB);
 354             }
 355             if ( !(inA) && inB ) {
 356                 AddRun(curPos,nextPos,oValB-oValA,valB-valA);
 357             }
 358         }
 359
 360         curPos = nextPos;
 361         if ( startA ) {
 362             //inA=true;
 363             valA = runA.vst;
 364         }
 365         if ( endA ) {
 366             //inA=false;
 367             valA = 0;
 368             curA++;
 369             if ( curA < a->nbRun && a->runs[curA].st == curPos ) {
 370                 valA = a->runs[curA].vst;
 371             }
 372         }
 373     }
 374
 375     while ( curB < b->nbRun ) {
 376         int_ligne_run runB = b->runs[curB];
 377         const bool inB = ( curPos >= runB.st && curPos < runB.en );
 378         const bool inA = false;
 379
 380         bool startB = false;
 381         bool endB = false;
 382         if ( curPos < runB.st ) {
 383             nextPos = runB.st;
 384             startB = true;
 385         } else if ( curPos >= runB.st ) {
 386             nextPos = runB.en;
 387             endB = true;
 388         }
 389
 390         float oValA = valA;
 391         float oValB = valB;
 392         valB = inB ? ValAt(nextPos, runB.st, runB.en, runB.vst, runB.ven) : 0;
 393         valA = 0;
 394
 395         if ( mod == bool_op_union ) {
 396             if ( inA || inB ) {
 397                 AddRun(curPos, nextPos, oValA + oValB,valA + valB);
 398             }
 399         } else if ( mod == bool_op_inters ) {
 400             if ( inA && inB ) {
 401                 AddRun(curPos, nextPos, oValA * oValB, valA * valB);
 402             }
 403         } else if ( mod == bool_op_diff ) {
 404             if ( inA ) {
 405                 AddRun(curPos, nextPos, oValA - oValB, valA - valB);
 406             }
 407         } else if ( mod == bool_op_symdiff ) {
 408             if ( inA && !(inB) ) {
 409                 AddRun(curPos, nextPos, oValA - oValB,valA - valB);
 410             }
 411             if ( !(inA) && inB ) {
 412                 AddRun(curPos, nextPos, oValB - oValA, valB - valA);
 413             }
 414         }
 415
 416         curPos = nextPos;
 417         if ( startB ) {
 418             //inB=true;
 419             valB = runB.vst;
 420         }
 421         if ( endB ) {
 422             //inB=false;
 423             valB = 0;
 424             curB++;
 425             if ( curB < b->nbRun && b->runs[curB].st == curPos ) {
 426                 valB = b->runs[curB].vst;
 427             }
 428         }
 429     }
 430 }
 431
 432 /**
 433  * Transform a line of bits into pixel coverage values.
 434  *
 435  * This is where you go from supersampled data to alpha values.
 436  * \see IntLigne::Copy(int nbSub,BitLigne* *a).
 437  */
 438 void IntLigne::Copy(BitLigne* a)
 439 {
 440     if ( a->curMax <= a->curMin ) {
 441         Reset();
 442         return;
 443     }
 444
 445     if ( a->curMin < a->st ) {
 446         a->curMin = a->st;
 447     }
 448
 449     if ( a->curMax < a->st ) {
 450         Reset();
 451         return;
 452     }
 453
 454     if ( a->curMin > a->en ) {
 455         Reset();
 456         return;
 457     }
 458
 459     if ( a->curMax > a->en ) {
 460         a->curMax=a->en;
 461     }
 462
 463     nbBord = 0;
 464     nbRun = 0;
 465
 466     int lastVal = 0;
 467     int lastStart = 0;
 468     bool startExists = false;
 469
 470     int masks[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
 471
 472     uint32_t c_full = a->fullB[(a->curMin-a->st) >> 3];
 473     uint32_t c_part = a->partB[(a->curMin-a->st) >> 3];
 474     c_full <<= 4 * ((a->curMin - a->st) & 0x00000007);
 475     c_part <<= 4 * ((a->curMin - a->st) & 0x00000007);
 476     for (int i = a->curMin; i <= a->curMax; i++) {
 477         int nbBit = masks[c_full >> 28] + masks[c_part >> 28];
 478
 479         if ( nbBit > 0 ) {
 480             if ( startExists ) {
 481                 if ( lastVal == nbBit ) {
 482                     // on continue le run
 483                 } else {
 484                     AddRun(lastStart, i, ((float) lastVal) / 4, ((float) lastVal) / 4);
 485                     lastStart = i;
 486                     lastVal = nbBit;
 487                 }
 488             } else {
 489                 lastStart = i;
 490                 lastVal = nbBit;
 491                 startExists = true;
 492             }
 493         } else {
 494             if ( startExists ) {
 495                 AddRun(lastStart, i, ((float) lastVal) / 4, ((float) lastVal) / 4);
 496             }
 497             startExists = false;
 498         }
 499         int chg = (i + 1 - a->st) & 0x00000007;
 500         if ( chg == 0 ) {
 501             c_full = a->fullB[(i + 1 - a->st) >> 3];
 502             c_part = a->partB[(i + 1 - a->st) >> 3];
 503         } else {
 504             c_full <<= 4;
 505             c_part <<= 4;
 506         }
 507     }
 508     if ( startExists ) {
 509         AddRun(lastStart, a->curMax + 1, ((float) lastVal) / 4, ((float) lastVal) / 4);
 510     }
 511 }
 512
 513 /**
 514  * Transform a line of bits into pixel coverage values.
 515  *
 516  * Alpha values are computed from supersampled data, so we have to scan the
 517  * BitLigne left to right, summing the bits in each pixel. The alpha value
 518  * is then "number of bits"/(nbSub*nbSub)". Full bits and partial bits are
 519  * treated as equals because the method produces ugly results otherwise.
 520  *
 521  * \param nbSub Number of BitLigne in the array "a".
 522  */
 523 void IntLigne::Copy(int nbSub, BitLigne **as)
 524 {
 525     if ( nbSub <= 0 ) {
 526         Reset();
 527         return;
 528     }
 529
 530     if ( nbSub == 1 ) {
 531         Copy(as[0]);
 532         return;
 533     }
 534
 535     // compute the min-max of the pixels to be rasterized from the min-max of the  inpur bitlignes
 536     int curMin = as[0]->curMin;
 537     int curMax = as[0]->curMax;
 538     for (int i = 1; i < nbSub; i++) {
 539         if ( as[i]->curMin < curMin ) {
 540             curMin = as[i]->curMin;
 541         }
 542         if ( as[i]->curMax > curMax ) {
 543             curMax = as[i]->curMax;
 544         }
 545     }
 546
 547     if ( curMin < as[0]->st ) {
 548         curMin = as[0]->st;
 549     }
 550
 551     if ( curMax > as[0]->en ) {
 552         curMax = as[0]->en;
 553     }
 554
 555     if ( curMax <= curMin ) {
 556         Reset();
 557         return;
 558     }
 559
 560     nbBord = 0;
 561     nbRun = 0;
 562
 563     int lastVal = 0;
 564     int lastStart = 0;
 565     bool startExists = false;
 566     float spA;
 567     int masks[16] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
 568
 569     int  theSt = as[0]->st;
 570     if ( nbSub == 4 ) {
 571         // special case for 4*4 supersampling, to avoid a few loops
 572         uint32_t c_full[4];
 573         c_full[0] = as[0]->fullB[(curMin - theSt) >> 3] | as[0]->partB[(curMin - theSt) >> 3];
 574         c_full[0] <<= 4 * ((curMin - theSt) & 7);
 575         c_full[1] = as[1]->fullB[(curMin - theSt) >> 3] | as[1]->partB[(curMin - theSt) >> 3];
 576         c_full[1] <<= 4 * ((curMin - theSt) & 7);
 577         c_full[2] = as[2]->fullB[(curMin - theSt) >> 3] | as[2]->partB[(curMin - theSt) >> 3];
 578         c_full[2] <<= 4* ((curMin - theSt) & 7);
 579         c_full[3] = as[3]->fullB[(curMin - theSt) >> 3] | as[3]->partB[(curMin - theSt) >> 3];
 580         c_full[3] <<= 4* ((curMin - theSt) & 7);
 581
 582         spA = 1.0 / (4 * 4);
 583         for (int i = curMin; i <= curMax; i++) {
 584             int nbBit = 0;
 585
 586             if ( c_full[0] == 0 && c_full[1] == 0 && c_full[2] == 0 && c_full[3] == 0 ) {
 587
 588                 if ( startExists ) {
 589                     AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
 590                 }
 591                 startExists = false;
 592                 i = theSt + (((i - theSt) & (~7) ) + 7);
 593
 594             } else if ( c_full[0] == 0xFFFFFFFF && c_full[1] == 0xFFFFFFFF &&
 595                         c_full[2] == 0xFFFFFFFF && c_full[3] == 0xFFFFFFFF ) {
 596
 597                 if ( startExists ) {
 598                     if ( lastVal == 4*4) {
 599                     } else {
 600                         AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
 601                         lastStart = i;
 602                     }
 603                 } else {
 604                     lastStart = i;
 605                 }
 606                 lastVal = 4*4;
 607                 startExists = true;
 608                 i = theSt + (((i - theSt) & (~7) ) + 7);
 609
 610             } else {
 611                 nbBit += masks[c_full[0] >> 28];
 612                 nbBit += masks[c_full[1] >> 28];
 613                 nbBit += masks[c_full[2] >> 28];
 614                 nbBit += masks[c_full[3] >> 28];
 615
 616                 if ( nbBit > 0 ) {
 617                     if ( startExists ) {
 618                         if ( lastVal == nbBit ) {
 619                             // on continue le run
 620                         } else {
 621                             AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
 622                             lastStart = i;
 623                             lastVal = nbBit;
 624                         }
 625                     } else {
 626                         lastStart = i;
 627                         lastVal = nbBit;
 628                         startExists = true;
 629                     }
 630                 } else {
 631                     if ( startExists ) {
 632                         AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
 633                     }
 634                     startExists = false;
 635                 }
 636             }
 637             int chg = (i + 1 - theSt) & 7;
 638             if ( chg == 0 ) {
 639                 if ( i < curMax ) {
 640                     c_full[0] = as[0]->fullB[(i + 1 - theSt) >> 3] | as[0]->partB[(i + 1 - theSt) >> 3];
 641                     c_full[1] = as[1]->fullB[(i + 1 - theSt) >> 3] | as[1]->partB[(i + 1 - theSt) >> 3];
 642                     c_full[2] = as[2]->fullB[(i + 1 - theSt) >> 3] | as[2]->partB[(i + 1 - theSt) >> 3];
 643                     c_full[3] = as[3]->fullB[(i + 1 - theSt) >> 3] | as[3]->partB[(i + 1 - theSt) >> 3];
 644                 } else {
 645                     // end of line. byebye
 646                 }
 647             } else {
 648                 c_full[0] <<= 4;
 649                 c_full[1] <<= 4;
 650                 c_full[2] <<= 4;
 651                 c_full[3] <<= 4;
 652             }
 653         }
 654
 655     } else {
 656
 657         uint32_t c_full[16]; // we take nbSub < 16, since 16*16 supersampling makes a 1/256 precision in alpha values
 658         // and that's the max of what 32bit argb can represent
 659         // in fact, we'll treat it as 4*nbSub supersampling, so that's a half truth and a full lazyness from me
 660         //      uint32_t  c_part[16];
 661         // start by putting the bits of the nbSub BitLignes in as[] in their respective c_full
 662
 663         for (int i = 0; i < nbSub; i++) {
 664             // fullB and partB treated equally
 665             c_full[i] = as[i]->fullB[(curMin - theSt) >> 3] | as[i]->partB[(curMin - theSt) >> 3];
 666             c_full[i] <<= 4 * ((curMin - theSt) & 7);
 667             /*          c_part[i]=as[i]->partB[(curMin-theSt)>>3];
 668                         c_part[i]<<=4*((curMin-theSt)&7);*/
 669         }
 670
 671         spA = 1.0 / (4 * nbSub); // contribution to the alpha value of a single bit of the supersampled data
 672         for (int i = curMin; i <= curMax;i++) {
 673             int  nbBit = 0;
 674             //                  int nbPartBit=0;
 675             // a little acceleration: if the lines only contain full or empty bits, we can flush
 676             // what's remaining in the c_full at best we flush an entire c_full, ie 32 bits, or 32/4=8 pixels
 677             bool allEmpty = true;
 678             bool allFull = true;
 679             for (int j = 0; j < nbSub; j++) {
 680                 if ( c_full[j] != 0 /*|| c_part[j] != 0*/ ) {
 681                     allEmpty=false;
 682                     break;
 683                 }
 684             }
 685
 686             if ( allEmpty ) {
 687                 // the remaining bits in c_full[] are empty: flush
 688                 if ( startExists ) {
 689                     AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
 690                 }
 691                 startExists = false;
 692                 i = theSt + (((i - theSt) & (~7) ) + 7);
 693             } else {
 694                 for (int j = 0; j < nbSub; j++) {
 695                     if ( c_full[j] != 0xFFFFFFFF ) {
 696                         allFull=false;
 697                         break;
 698                     }
 699                 }
 700
 701                 if ( allFull ) {
 702                     // the remaining bits in c_full[] are empty: flush
 703                     if ( startExists ) {
 704                         if ( lastVal == 4 * nbSub) {
 705                         } else {
 706                             AddRun(lastStart, i, ((float) lastVal) * spA,((float) lastVal) * spA);
 707                             lastStart = i;
 708                         }
 709                     } else {
 710                         lastStart = i;
 711                     }
 712                     lastVal = 4 * nbSub;
 713                     startExists = true;
 714                     i = theSt + (((i - theSt) & (~7) ) + 7);
 715                 } else {
 716                     // alpha values will be between 0 and 1, so we have more work to do
 717                     // compute how many bit this pixel holds
 718                     for (int j = 0; j < nbSub; j++) {
 719                         nbBit += masks[c_full[j] >> 28];
 720 //                                              nbPartBit+=masks[c_part[j]>>28];
 721                     }
 722                     // and add a single-pixel run if needed, or extend the current run if the alpha value hasn't changed
 723                     if ( nbBit > 0 ) {
 724                         if ( startExists ) {
 725                             if ( lastVal == nbBit ) {
 726                                 // alpha value hasn't changed: we continue
 727                             } else {
 728                                 // alpha value did change: put the run that was being done,...
 729                                 AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
 730                                 // ... and start a new one
 731                                 lastStart = i;
 732                                 lastVal = nbBit;
 733                             }
 734                         } else {
 735                             // alpha value was 0, so we "create" a new run with alpha nbBit
 736                             lastStart = i;
 737                             lastVal = nbBit;
 738                             startExists = true;
 739                         }
 740                     } else {
 741                         if ( startExists ) {
 742                             AddRun(lastStart, i, ((float) lastVal) * spA,((float) lastVal) * spA);
 743                         }
 744                         startExists = false;
 745                     }
 746                 }
 747             }
 748             // move to the right: shift bits in the c_full[], and if we shifted everything, load the next c_full[]
 749             int chg = (i + 1 - theSt) & 7;
 750             if ( chg == 0 ) {
 751                 if ( i < curMax ) {
 752                     for (int j = 0; j < nbSub; j++) {
 753                         c_full[j] = as[j]->fullB[(i + 1 - theSt) >> 3] | as[j]->partB[(i + 1 - theSt) >> 3];
 754                         //                      c_part[j]=as[j]->partB[(i+1-theSt)>>3];
 755                     }
 756                 } else {
 757                     // end of line. byebye
 758                 }
 759             } else {
 760                 for (int j = 0; j < nbSub; j++) {
 761                     c_full[j]<<=4;
 762                     //                  c_part[j]<<=4;
 763                 }
 764             }
 765         }
 766     }
 767
 768     if ( startExists ) {
 769         AddRun(lastStart, curMax + 1, ((float) lastVal) * spA,((float) lastVal) * spA);
 770     }
 771 }
 772
 773 /// Copy another IntLigne
 774 void IntLigne::Copy(IntLigne *a)
 775 {
 776     if ( a->nbRun <= 0 ) {
 777         Reset();
 778         return;
 779     }
 780
 781     nbBord = 0;
 782     nbRun = a->nbRun;
 783     if ( nbRun > maxRun ) {
 784         maxRun = nbRun;
 785         runs = (int_ligne_run*) g_realloc(runs, maxRun * sizeof(int_ligne_run));
 786     }
 787     memcpy(runs, a->runs, nbRun * sizeof(int_ligne_run));
 788 }
 789
 790
 791 /**
 792  * Copy a FloatLigne's runs.
 793  *
 794  * Compute non-overlapping runs with integer boundaries from a set of runs
 795  * with floating-point boundaries. This involves replacing floating-point
 796  * boundaries that are not integer by single-pixel runs, so this function
 797  * contains plenty of rounding and float->integer conversion (read:
 798  * time-consuming).
 799  *
 800  * \todo
 801  * Optimization Questions: Why is this called so often compared with the
 802  * other Copy() routines? How does AddRun() look for optimization potential?
 803  */
 804 void IntLigne::Copy(FloatLigne* a)
 805 {
 806     if ( a->runs.empty() ) {
 807         Reset();
 808         return;
 809     }
 810
 811     /*  if ( showCopy ) {
 812         printf("\nfloatligne:\n");
 813         a->Affiche();
 814         }*/
 815
 816     nbBord = 0;
 817     nbRun = 0;
 818     firstAc = lastAc = -1;
 819     bool pixExists = false;
 820     int curPos = (int) floor(a->runs[0].st) - 1;
 821     float lastSurf = 0;
 822     float tolerance = 0.00001;
 823
 824     // we take each run of the FloatLigne in sequence and make single-pixel runs of its boundaries as needed
 825     // since the float_ligne_runs are non-overlapping, when a single-pixel run intersects with another runs,
 826     // it must intersect with the single-pixel run created for the end of that run. so instead of creating a new
 827     // int_ligne_run, we just add the coverage to that run.
 828     for (int i = 0; i < int(a->runs.size()); i++) {
 829         float_ligne_run runA = a->runs[i];
 830         float curStF = floor(runA.st);
 831         float curEnF = floor(runA.en);
 832         int   curSt  = (int) curStF;
 833         int   curEn  = (int) curEnF;
 834
 835         // stEx: start boundary is not integer -> create single-pixel run for it
 836         // enEx: end boundary is not integer -> create single-pixel run for it
 837         // miEx: the runs minus the eventual single-pixel runs is not empty
 838         bool  stEx  = true;
 839         bool  miEx  = true;
 840         bool  enEx  = true;
 841         int   miSt  = curSt;
 842         float miStF = curStF;
 843         float msv;
 844         float mev;
 845         if ( runA.en - curEnF < tolerance ) {
 846             enEx = false;
 847         }
 848
 849         // msv and mev are the start and end value of the middle section of the run, that is the run minus the
 850         // single-pixel runs creaed for its boundaries
 851         if ( runA.st-curStF < tolerance /*miSt == runA.st*/ ) {
 852             stEx = false;
 853             msv = runA.vst;
 854         } else {
 855             miSt  += 1;
 856             miStF += 1.0;
 857             if ( enEx == false && miSt == curEn ) {
 858                 msv = runA.ven;
 859             } else {
 860                 //                      msv=a->ValAt(miSt,runA.st,runA.en,runA.vst,runA.ven);
 861                 msv = runA.vst + (miStF-runA.st) * runA.pente;
 862             }
 863         }
 864
 865         if ( miSt >= curEn ) {
 866             miEx = false;
 867         }
 868         if ( stEx == false && miEx == false /*curEn == runA.st*/ ) {
 869             mev = runA.vst;
 870         } else if ( enEx == false /*curEn == runA.en*/ ) {
 871             mev = runA.ven;
 872         } else {
 873             //                  mev=a->ValAt(curEn,runA.st,runA.en,runA.vst,runA.ven);
 874             mev = runA.vst + (curEnF-runA.st) * runA.pente;
 875         }
 876
 877         // check the different cases
 878         if ( stEx && enEx ) {
 879             // stEx && enEx
 880             if ( curEn > curSt ) {
 881                 if ( pixExists ) {
 882                     if ( curPos < curSt ) {
 883                         AddRun(curPos,curPos+1,lastSurf,lastSurf);
 884                         lastSurf=0.5*(msv+a->runs[i].vst)*(miStF-a->runs[i].st);
 885                         AddRun(curSt,curSt+1,lastSurf,lastSurf);
 886                     } else {
 887                         lastSurf+=0.5*(msv+a->runs[i].vst)*(miStF-a->runs[i].st);
 888                         AddRun(curSt,curSt+1,lastSurf,lastSurf);
 889                     }
 890                     pixExists=false;
 891                 } else {
 892                     lastSurf=0.5*(msv+a->runs[i].vst)*(miStF-a->runs[i].st);
 893                     AddRun(curSt,curSt+1,lastSurf,lastSurf);
 894                 }
 895             } else if ( pixExists ) {
 896                 if ( curPos < curSt ) {
 897                     AddRun(curPos,curPos+1,lastSurf,lastSurf);
 898                     lastSurf=0.5*(a->runs[i].ven+a->runs[i].vst)*(a->runs[i].en-a->runs[i].st);
 899                     curPos=curSt;
 900                 } else {
 901                     lastSurf += 0.5 * (a->runs[i].ven+a->runs[i].vst)*(a->runs[i].en-a->runs[i].st);
 902                 }
 903             } else {
 904                 lastSurf=0.5*(a->runs[i].ven+a->runs[i].vst)*(a->runs[i].en-a->runs[i].st);
 905                 curPos=curSt;
 906                 pixExists=true;
 907             }
 908         } else if ( pixExists ) {
 909             if ( curPos < curSt ) {
 910                 AddRun(curPos,curPos+1,lastSurf,lastSurf);
 911                 lastSurf = 0.5 * (msv+a->runs[i].vst) * (miStF-a->runs[i].st);
 912                 AddRun(curSt,curSt+1,lastSurf,lastSurf);
 913             } else {
 914                 lastSurf += 0.5 * (msv+a->runs[i].vst) * (miStF-a->runs[i].st);
 915                 AddRun(curSt,curSt+1,lastSurf,lastSurf);
 916             }
 917             pixExists=false;
 918         } else {
 919             lastSurf = 0.5 * (msv+a->runs[i].vst) * (miStF-a->runs[i].st);
 920             AddRun(curSt,curSt+1,lastSurf,lastSurf);
 921         }
 922         if ( miEx ) {
 923             if ( pixExists && curPos < miSt ) {
 924                 AddRun(curPos,curPos+1,lastSurf,lastSurf);
 925             }
 926             pixExists=false;
 927             AddRun(miSt,curEn,msv,mev);
 928         }
 929         if ( enEx ) {
 930             if ( curEn > curSt ) {
 931                 lastSurf=0.5*(mev+a->runs[i].ven)*(a->runs[i].en-curEnF);
 932                 pixExists=true;
 933                 curPos=curEn;
 934             } else if ( ! stEx ) {
 935                 if ( pixExists ) {
 936                     AddRun(curPos,curPos+1,lastSurf,lastSurf);
 937                 }
 938                 lastSurf=0.5*(mev+a->runs[i].ven)*(a->runs[i].en-curEnF);
 939                 pixExists=true;
 940                 curPos=curEn;
 941             }
 942         }
 943     }
 944     if ( pixExists ) {
 945         AddRun(curPos,curPos+1,lastSurf,lastSurf);
 946     }
 947     /*  if ( showCopy ) {
 948         printf("-> intligne:\n");
 949         Affiche();
 950         }*/
 951 }
 952
 953
 954 void IntLigne::Enqueue(int no)
 955 {
 956     if ( firstAc < 0 ) {
 957         firstAc = lastAc = no;
 958         bords[no].prev = bords[no].next = -1;
 959     } else {
 960         bords[no].next = -1;
 961         bords[no].prev = lastAc;
 962         bords[lastAc].next = no;
 963         lastAc = no;
 964     }
 965 }
 966
 967
 968 void IntLigne::Dequeue(int no)
 969 {
 970     if ( no == firstAc ) {
 971         if ( no == lastAc ) {
 972             firstAc = lastAc = -1;
 973         } else {
 974             firstAc = bords[no].next;
 975         }
 976     } else if ( no == lastAc ) {
 977         lastAc = bords[no].prev;
 978     } else {
 979     }
 980     if ( bords[no].prev >= 0 ) {
 981         bords[bords[no].prev].next = bords[no].next;
 982     }
 983     if ( bords[no].next >= 0 ) {
 984         bords[bords[no].next].prev = bords[no].prev;
 985     }
 986
 987     bords[no].prev = bords[no].next = -1;
 988 }
 989
 990 /**
 991  * Rasterization.
 992  *
 993  * The parameters have the same meaning as in the AlphaLigne class.
 994  */
 995 void IntLigne::Raster(raster_info &dest, void *color, RasterInRunFunc worker)
 996 {
 997     if ( nbRun <= 0 ) {
 998         return;
 999     }
1000
1001     int min = runs[0].st;
1002     int max = runs[nbRun-1].en;
1003     if ( dest.endPix <= min || dest.startPix >= max ) {
1004         return;
1005     }
1006
1007     int curRun = -1;
1008     for (curRun = 0; curRun < nbRun; curRun++) {
1009         if ( runs[curRun].en > dest.startPix ) {
1010             break;
1011         }
1012     }
1013
1014     if ( curRun >= nbRun ) {
1015         return;
1016     }
1017
1018     if ( runs[curRun].st < dest.startPix ) {
1019         int nst = runs[curRun].st;
1020         int nen = runs[curRun].en;
1021         float vst = runs[curRun].vst;
1022         float ven = runs[curRun].ven;
1023         float nvst = (vst * (nen - dest.startPix) + ven * (dest.startPix - nst)) / ((float) (nen - nst));
1024         if ( runs[curRun].en <= dest.endPix ) {
1025             (worker)(dest, color, dest.startPix, nvst, runs[curRun].en, runs[curRun].ven);
1026         } else {
1027             float nven = (vst * (nen - dest.endPix) + ven * (dest.endPix - nst)) / ((float)(nen - nst));
1028             (worker)(dest, color, dest.startPix, nvst, dest.endPix, nven);
1029             return;
1030         }
1031         curRun++;
1032     }
1033
1034     for (; (curRun < nbRun && runs[curRun].en <= dest.endPix); curRun++) {
1035         (worker)(dest, color, runs[curRun].st, runs[curRun].vst, runs[curRun].en, runs[curRun].ven);
1036 //Buffer::RasterRun(*dest,color,runs[curRun].st,runs[curRun].vst,runs[curRun].en,runs[curRun].ven);
1037     }
1038
1039     if ( curRun >= nbRun ) {
1040         return;
1041     }
1042
1043     if ( runs[curRun].st < dest.endPix && runs[curRun].en > dest.endPix ) {
1044         int const nst = runs[curRun].st;
1045         int const nen = runs[curRun].en;
1046         float const vst = runs[curRun].vst;
1047         float const ven = runs[curRun].ven;
1048         float const nven = (vst * (nen - dest.endPix) + ven * (dest.endPix - nst)) / ((float)(nen - nst));
1049
1050         (worker)(dest,color,runs[curRun].st,runs[curRun].vst,dest.endPix,nven);
1051         curRun++;
1052     }
1053 }
1054
1055
1056
1057 /*
1058   Local Variables:
1059   mode:c++
1060   c-file-style:"stroustrup"
1061   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1062   indent-tabs-mode:nil
1063   fill-column:99
1064   End:
1065 */
1066 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :