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