From cca66b9ec4e494c1d919bff0f71a820d8afab1fa Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:24:48 +0200 Subject: Adding upstream version 1.2.2. Signed-off-by: Daniel Baumann --- src/livarot/int-line.cpp | 1071 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1071 insertions(+) create mode 100644 src/livarot/int-line.cpp (limited to 'src/livarot/int-line.cpp') diff --git a/src/livarot/int-line.cpp b/src/livarot/int-line.cpp new file mode 100644 index 0000000..ff87475 --- /dev/null +++ b/src/livarot/int-line.cpp @@ -0,0 +1,1071 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** @file + * Implementation of coverage with integer boundaries. + *//* + * Authors: + * see git history + * Fred + * + * Copyright (C) 2018 Authors + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#include +#include +#include +#include +#include +#include +#include "livarot/int-line.h" +#include "livarot/float-line.h" +#include "livarot/BitLigne.h" + +IntLigne::IntLigne() +{ + nbBord = maxBord = 0; + bords = nullptr; + + nbRun = maxRun = 0; + runs = nullptr; + + firstAc = lastAc = -1; +} + + +IntLigne::~IntLigne() +{ + if ( maxBord > 0 ) { + g_free(bords); + nbBord = maxBord = 0; + bords = nullptr; + } + if ( maxRun > 0 ) { + g_free(runs); + nbRun = maxRun = 0; + runs = nullptr; + } +} + +void IntLigne::Reset() +{ + nbBord = 0; + nbRun = 0; + firstAc = lastAc = -1; +} + +int IntLigne::AddBord(int spos, float sval, int epos, float eval) +{ + if ( nbBord + 1 >= maxBord ) { + maxBord = 2 * nbBord + 2; + bords = (int_ligne_bord *) g_realloc(bords, maxBord * sizeof(int_ligne_bord)); + + } + + int n = nbBord++; + bords[n].pos = spos; + bords[n].val = sval; + bords[n].start = true; + bords[n].other = n+1; + bords[n].prev = bords[n].next = -1; + + n = nbBord++; + bords[n].pos = epos; + bords[n].val = eval; + bords[n].start = false; + bords[n].other = n-1; + bords[n].prev = bords[n].next = -1; + + return n - 1; +} + + +float IntLigne::RemainingValAt(int at) +{ + int no = firstAc; + float sum = 0; + while ( no >= 0 ) { + int nn = bords[no].other; + sum += ValAt(at, bords[nn].pos, bords[no].pos, bords[nn].val, bords[no].val); + no = bords[no].next; + } + return sum; +} + +void IntLigne::Flatten() +{ + if ( nbBord <= 1 ) { + Reset(); + return; + } + + nbRun = 0; + firstAc = lastAc = -1; + + for (int i = 0; i < nbBord; i++) { + bords[i].prev = i; + } + + qsort(bords, nbBord, sizeof(int_ligne_bord), IntLigne::CmpBord); + for (int i = 0; i < nbBord; i++) { + bords[bords[i].prev].next = i; + } + + for (int i = 0; i < nbBord; i++) { + bords[i].other = bords[bords[i].other].next; + } + + int lastStart = 0; + float lastVal = 0; + bool startExists = false; + + for (int i = 0; i < nbBord; ) { + int cur = bords[i].pos; + float leftV = 0; + float rightV = 0; + float midV = 0; + while ( i < nbBord && bords[i].pos == cur && bords[i].start == false ) { + Dequeue(i); + leftV += bords[i].val; + i++; + } + midV = RemainingValAt(cur); + while ( i < nbBord && bords[i].pos == cur && bords[i].start ) { + rightV += bords[i].val; + Enqueue(bords[i].other); + i++; + } + + if ( startExists ) { + AddRun(lastStart, cur, lastVal, leftV + midV); + } + if ( firstAc >= 0 ) { + startExists = true; + lastVal = midV + rightV; + lastStart = cur; + } else { + startExists = false; + } + } +} + + +void IntLigne::Affiche() +{ + printf("%i : \n", nbRun); + for (int i = 0; i < nbRun;i++) { + printf("(%i %f -> %i %f) ", runs[i].st, runs[i].vst, runs[i].en, runs[i].ven); // localization ok + } + printf("\n"); +} + +int IntLigne::AddRun(int st, int en, float vst, float ven) +{ + if ( st >= en ) { + return -1; + } + + if ( nbRun >= maxRun ) { + maxRun = 2 * nbRun + 1; + runs = (int_ligne_run *) g_realloc(runs, maxRun * sizeof(int_ligne_run)); + } + + int n = nbRun++; + runs[n].st = st; + runs[n].en = en; + runs[n].vst = vst; + runs[n].ven = ven; + return n; +} + +void IntLigne::Booleen(IntLigne *a, IntLigne *b, BooleanOp mod) +{ + Reset(); + if ( a->nbRun <= 0 && b->nbRun <= 0 ) { + return; + } + + if ( a->nbRun <= 0 ) { + if ( mod == bool_op_union || mod == bool_op_symdiff ) { + Copy(b); + } + return; + } + + if ( b->nbRun <= 0 ) { + if ( mod == bool_op_union || mod == bool_op_diff || mod == bool_op_symdiff ) { + Copy(a); + } + return; + } + + int curA = 0; + int curB = 0; + int curPos = (a->runs[0].st < b->runs[0].st) ? a->runs[0].st : b->runs[0].st; + int nextPos = curPos; + float valA = 0; + float valB = 0; + if ( curPos == a->runs[0].st ) { + valA = a->runs[0].vst; + } + if ( curPos == b->runs[0].st ) { + valB = b->runs[0].vst; + } + + while ( curA < a->nbRun && curB < b->nbRun ) { + int_ligne_run runA = a->runs[curA]; + int_ligne_run runB = b->runs[curB]; + const bool inA = ( curPos >= runA.st && curPos < runA.en ); + const bool inB = ( curPos >= runB.st && curPos < runB.en ); + + bool startA = false; + bool startB = false; + bool endA = false; + bool endB = false; + + if ( curPos < runA.st ) { + if ( curPos < runB.st ) { + startA = runA.st <= runB.st; + startB = runA.st >= runB.st; + nextPos = startA ? runA.st : runB.st; + } else if ( curPos >= runB.st ) { + startA = runA.st <= runB.en; + endB = runA.st >= runB.en; + nextPos = startA ? runA.st : runB.en; + } + } else if ( curPos == runA.st ) { + if ( curPos < runB.st ) { + endA = runA.en <= runB.st; + startB = runA.en >= runB.st; + nextPos = startB ? runB.en : runA.st; + } else if ( curPos == runB.st ) { + endA = runA.en <= runB.en; + endB = runA.en >= runB.en; + nextPos = endA? runA.en : runB.en; + } else { + endA = runA.en <= runB.en; + endB = runA.en >= runB.en; + nextPos = endA ? runA.en : runB.en; + } + } else { + if ( curPos < runB.st ) { + endA = runA.en <= runB.st; + startB = runA.en >= runB.st; + nextPos = startB ? runB.st : runA.en; + } else if ( curPos == runB.st ) { + endA = runA.en <= runB.en; + endB = runA.en >= runB.en; + nextPos = endA ? runA.en : runB.en; + } else { + endA = runA.en <= runB.en; + endB = runA.en >= runB.en; + nextPos = endA ? runA.en : runB.en; + } + } + + float oValA = valA; + float oValB = valB; + valA = inA ? ValAt(nextPos, runA.st, runA.en, runA.vst, runA.ven) : 0; + valB = inB ? ValAt(nextPos, runB.st, runB.en, runB.vst, runB.ven) : 0; + + if ( mod == bool_op_union ) { + + if ( inA || inB ) { + AddRun(curPos, nextPos, oValA + oValB, valA + valB); + } + + } else if ( mod == bool_op_inters ) { + + if ( inA && inB ) { + AddRun(curPos, nextPos, oValA * oValB, valA * valB); + } + + } else if ( mod == bool_op_diff ) { + + if ( inA ) { + AddRun(curPos, nextPos, oValA - oValB, valA - valB); + } + + } else if ( mod == bool_op_symdiff ) { + if ( inA && !(inB) ) { + AddRun(curPos, nextPos, oValA - oValB, valA - valB); + } + if ( !(inA) && inB ) { + AddRun(curPos, nextPos, oValB - oValA, valB - valA); + } + } + + curPos = nextPos; + if ( startA ) { + // inA=true; these are never used + valA = runA.vst; + } + if ( startB ) { + //inB=true; + valB = runB.vst; + } + if ( endA ) { + //inA=false; + valA = 0; + curA++; + if ( curA < a->nbRun && a->runs[curA].st == curPos ) { + valA = a->runs[curA].vst; + } + } + if ( endB ) { + //inB=false; + valB = 0; + curB++; + if ( curB < b->nbRun && b->runs[curB].st == curPos ) { + valB = b->runs[curB].vst; + } + } + } + + while ( curA < a->nbRun ) { + int_ligne_run runA = a->runs[curA]; + const bool inA = ( curPos >= runA.st && curPos < runA.en ); + const bool inB = false; + + bool startA = false; + bool endA = false; + if ( curPos < runA.st ) { + nextPos = runA.st; + startA = true; + } else if ( curPos >= runA.st ) { + nextPos = runA.en; + endA = true; + } + + float oValA = valA; + float oValB = valB; + valA = inA ? ValAt(nextPos,runA.st, runA.en, runA.vst, runA.ven) : 0; + valB = 0; + + if ( mod == bool_op_union ) { + if ( inA || inB ) { + AddRun(curPos, nextPos, oValA + oValB, valA + valB); + } + } else if ( mod == bool_op_inters ) { + if ( inA && inB ) { + AddRun(curPos, nextPos, oValA * oValB, valA * valB); + } + } else if ( mod == bool_op_diff ) { + if ( inA ) { + AddRun(curPos, nextPos, oValA - oValB, valA - valB); + } + } else if ( mod == bool_op_symdiff ) { + if ( inA && !(inB) ) { + AddRun(curPos, nextPos, oValA - oValB, valA - valB); + } + if ( !(inA) && inB ) { + AddRun(curPos,nextPos,oValB-oValA,valB-valA); + } + } + + curPos = nextPos; + if ( startA ) { + //inA=true; + valA = runA.vst; + } + if ( endA ) { + //inA=false; + valA = 0; + curA++; + if ( curA < a->nbRun && a->runs[curA].st == curPos ) { + valA = a->runs[curA].vst; + } + } + } + + while ( curB < b->nbRun ) { + int_ligne_run runB = b->runs[curB]; + const bool inB = ( curPos >= runB.st && curPos < runB.en ); + const bool inA = false; + + bool startB = false; + bool endB = false; + if ( curPos < runB.st ) { + nextPos = runB.st; + startB = true; + } else if ( curPos >= runB.st ) { + nextPos = runB.en; + endB = true; + } + + float oValA = valA; + float oValB = valB; + valB = inB ? ValAt(nextPos, runB.st, runB.en, runB.vst, runB.ven) : 0; + valA = 0; + + if ( mod == bool_op_union ) { + if ( inA || inB ) { + AddRun(curPos, nextPos, oValA + oValB,valA + valB); + } + } else if ( mod == bool_op_inters ) { + if ( inA && inB ) { + AddRun(curPos, nextPos, oValA * oValB, valA * valB); + } + } else if ( mod == bool_op_diff ) { + if ( inA ) { + AddRun(curPos, nextPos, oValA - oValB, valA - valB); + } + } else if ( mod == bool_op_symdiff ) { + if ( inA && !(inB) ) { + AddRun(curPos, nextPos, oValA - oValB,valA - valB); + } + if ( !(inA) && inB ) { + AddRun(curPos, nextPos, oValB - oValA, valB - valA); + } + } + + curPos = nextPos; + if ( startB ) { + //inB=true; + valB = runB.vst; + } + if ( endB ) { + //inB=false; + valB = 0; + curB++; + if ( curB < b->nbRun && b->runs[curB].st == curPos ) { + valB = b->runs[curB].vst; + } + } + } +} + +/** + * Transform a line of bits into pixel coverage values. + * + * This is where you go from supersampled data to alpha values. + * \see IntLigne::Copy(int nbSub,BitLigne* *a). + */ +void IntLigne::Copy(BitLigne* a) +{ + if ( a->curMax <= a->curMin ) { + Reset(); + return; + } + + if ( a->curMin < a->st ) { + a->curMin = a->st; + } + + if ( a->curMax < a->st ) { + Reset(); + return; + } + + if ( a->curMin > a->en ) { + Reset(); + return; + } + + if ( a->curMax > a->en ) { + a->curMax=a->en; + } + + nbBord = 0; + nbRun = 0; + + int lastVal = 0; + int lastStart = 0; + bool startExists = false; + + int masks[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; + + uint32_t c_full = a->fullB[(a->curMin-a->st) >> 3]; + uint32_t c_part = a->partB[(a->curMin-a->st) >> 3]; + c_full <<= 4 * ((a->curMin - a->st) & 0x00000007); + c_part <<= 4 * ((a->curMin - a->st) & 0x00000007); + for (int i = a->curMin; i <= a->curMax; i++) { + int nbBit = masks[c_full >> 28] + masks[c_part >> 28]; + + if ( nbBit > 0 ) { + if ( startExists ) { + if ( lastVal == nbBit ) { + // on continue le run + } else { + AddRun(lastStart, i, ((float) lastVal) / 4, ((float) lastVal) / 4); + lastStart = i; + lastVal = nbBit; + } + } else { + lastStart = i; + lastVal = nbBit; + startExists = true; + } + } else { + if ( startExists ) { + AddRun(lastStart, i, ((float) lastVal) / 4, ((float) lastVal) / 4); + } + startExists = false; + } + int chg = (i + 1 - a->st) & 0x00000007; + if ( chg == 0 ) { + c_full = a->fullB[(i + 1 - a->st) >> 3]; + c_part = a->partB[(i + 1 - a->st) >> 3]; + } else { + c_full <<= 4; + c_part <<= 4; + } + } + if ( startExists ) { + AddRun(lastStart, a->curMax + 1, ((float) lastVal) / 4, ((float) lastVal) / 4); + } +} + +/** + * Transform a line of bits into pixel coverage values. + * + * Alpha values are computed from supersampled data, so we have to scan the + * BitLigne left to right, summing the bits in each pixel. The alpha value + * is then "number of bits"/(nbSub*nbSub)". Full bits and partial bits are + * treated as equals because the method produces ugly results otherwise. + * + * \param nbSub Number of BitLigne in the array "a". + */ +void IntLigne::Copy(int nbSub, BitLigne **as) +{ + if ( nbSub <= 0 ) { + Reset(); + return; + } + + if ( nbSub == 1 ) { + Copy(as[0]); + return; + } + + // compute the min-max of the pixels to be rasterized from the min-max of the inpur bitlignes + int curMin = as[0]->curMin; + int curMax = as[0]->curMax; + for (int i = 1; i < nbSub; i++) { + if ( as[i]->curMin < curMin ) { + curMin = as[i]->curMin; + } + if ( as[i]->curMax > curMax ) { + curMax = as[i]->curMax; + } + } + + if ( curMin < as[0]->st ) { + curMin = as[0]->st; + } + + if ( curMax > as[0]->en ) { + curMax = as[0]->en; + } + + if ( curMax <= curMin ) { + Reset(); + return; + } + + nbBord = 0; + nbRun = 0; + + int lastVal = 0; + int lastStart = 0; + bool startExists = false; + float spA; + int masks[16] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; + + int theSt = as[0]->st; + if ( nbSub == 4 ) { + // special case for 4*4 supersampling, to avoid a few loops + uint32_t c_full[4]; + c_full[0] = as[0]->fullB[(curMin - theSt) >> 3] | as[0]->partB[(curMin - theSt) >> 3]; + c_full[0] <<= 4 * ((curMin - theSt) & 7); + c_full[1] = as[1]->fullB[(curMin - theSt) >> 3] | as[1]->partB[(curMin - theSt) >> 3]; + c_full[1] <<= 4 * ((curMin - theSt) & 7); + c_full[2] = as[2]->fullB[(curMin - theSt) >> 3] | as[2]->partB[(curMin - theSt) >> 3]; + c_full[2] <<= 4* ((curMin - theSt) & 7); + c_full[3] = as[3]->fullB[(curMin - theSt) >> 3] | as[3]->partB[(curMin - theSt) >> 3]; + c_full[3] <<= 4* ((curMin - theSt) & 7); + + spA = 1.0 / (4 * 4); + for (int i = curMin; i <= curMax; i++) { + int nbBit = 0; + + if ( c_full[0] == 0 && c_full[1] == 0 && c_full[2] == 0 && c_full[3] == 0 ) { + + if ( startExists ) { + AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA); + } + startExists = false; + i = theSt + (((i - theSt) & (~7) ) + 7); + + } else if ( c_full[0] == 0xFFFFFFFF && c_full[1] == 0xFFFFFFFF && + c_full[2] == 0xFFFFFFFF && c_full[3] == 0xFFFFFFFF ) { + + if ( startExists ) { + if ( lastVal == 4*4) { + } else { + AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA); + lastStart = i; + } + } else { + lastStart = i; + } + lastVal = 4*4; + startExists = true; + i = theSt + (((i - theSt) & (~7) ) + 7); + + } else { + nbBit += masks[c_full[0] >> 28]; + nbBit += masks[c_full[1] >> 28]; + nbBit += masks[c_full[2] >> 28]; + nbBit += masks[c_full[3] >> 28]; + + if ( nbBit > 0 ) { + if ( startExists ) { + if ( lastVal == nbBit ) { + // on continue le run + } else { + AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA); + lastStart = i; + lastVal = nbBit; + } + } else { + lastStart = i; + lastVal = nbBit; + startExists = true; + } + } else { + if ( startExists ) { + AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA); + } + startExists = false; + } + } + int chg = (i + 1 - theSt) & 7; + if ( chg == 0 ) { + if ( i < curMax ) { + c_full[0] = as[0]->fullB[(i + 1 - theSt) >> 3] | as[0]->partB[(i + 1 - theSt) >> 3]; + c_full[1] = as[1]->fullB[(i + 1 - theSt) >> 3] | as[1]->partB[(i + 1 - theSt) >> 3]; + c_full[2] = as[2]->fullB[(i + 1 - theSt) >> 3] | as[2]->partB[(i + 1 - theSt) >> 3]; + c_full[3] = as[3]->fullB[(i + 1 - theSt) >> 3] | as[3]->partB[(i + 1 - theSt) >> 3]; + } else { + // end of line. byebye + } + } else { + c_full[0] <<= 4; + c_full[1] <<= 4; + c_full[2] <<= 4; + c_full[3] <<= 4; + } + } + + } else { + + uint32_t c_full[16]; // we take nbSub < 16, since 16*16 supersampling makes a 1/256 precision in alpha values + // and that's the max of what 32bit argb can represent + // in fact, we'll treat it as 4*nbSub supersampling, so that's a half truth and a full lazyness from me + // uint32_t c_part[16]; + // start by putting the bits of the nbSub BitLignes in as[] in their respective c_full + + for (int i = 0; i < nbSub; i++) { + // fullB and partB treated equally + c_full[i] = as[i]->fullB[(curMin - theSt) >> 3] | as[i]->partB[(curMin - theSt) >> 3]; + c_full[i] <<= 4 * ((curMin - theSt) & 7); + /* c_part[i]=as[i]->partB[(curMin-theSt)>>3]; + c_part[i]<<=4*((curMin-theSt)&7);*/ + } + + spA = 1.0 / (4 * nbSub); // contribution to the alpha value of a single bit of the supersampled data + for (int i = curMin; i <= curMax;i++) { + int nbBit = 0; + // int nbPartBit=0; + // a little acceleration: if the lines only contain full or empty bits, we can flush + // what's remaining in the c_full at best we flush an entire c_full, ie 32 bits, or 32/4=8 pixels + bool allEmpty = true; + bool allFull = true; + for (int j = 0; j < nbSub; j++) { + if ( c_full[j] != 0 /*|| c_part[j] != 0*/ ) { + allEmpty=false; + break; + } + } + + if ( allEmpty ) { + // the remaining bits in c_full[] are empty: flush + if ( startExists ) { + AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA); + } + startExists = false; + i = theSt + (((i - theSt) & (~7) ) + 7); + } else { + for (int j = 0; j < nbSub; j++) { + if ( c_full[j] != 0xFFFFFFFF ) { + allFull=false; + break; + } + } + + if ( allFull ) { + // the remaining bits in c_full[] are empty: flush + if ( startExists ) { + if ( lastVal == 4 * nbSub) { + } else { + AddRun(lastStart, i, ((float) lastVal) * spA,((float) lastVal) * spA); + lastStart = i; + } + } else { + lastStart = i; + } + lastVal = 4 * nbSub; + startExists = true; + i = theSt + (((i - theSt) & (~7) ) + 7); + } else { + // alpha values will be between 0 and 1, so we have more work to do + // compute how many bit this pixel holds + for (int j = 0; j < nbSub; j++) { + nbBit += masks[c_full[j] >> 28]; +// nbPartBit+=masks[c_part[j]>>28]; + } + // and add a single-pixel run if needed, or extend the current run if the alpha value hasn't changed + if ( nbBit > 0 ) { + if ( startExists ) { + if ( lastVal == nbBit ) { + // alpha value hasn't changed: we continue + } else { + // alpha value did change: put the run that was being done,... + AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA); + // ... and start a new one + lastStart = i; + lastVal = nbBit; + } + } else { + // alpha value was 0, so we "create" a new run with alpha nbBit + lastStart = i; + lastVal = nbBit; + startExists = true; + } + } else { + if ( startExists ) { + AddRun(lastStart, i, ((float) lastVal) * spA,((float) lastVal) * spA); + } + startExists = false; + } + } + } + // move to the right: shift bits in the c_full[], and if we shifted everything, load the next c_full[] + int chg = (i + 1 - theSt) & 7; + if ( chg == 0 ) { + if ( i < curMax ) { + for (int j = 0; j < nbSub; j++) { + c_full[j] = as[j]->fullB[(i + 1 - theSt) >> 3] | as[j]->partB[(i + 1 - theSt) >> 3]; + // c_part[j]=as[j]->partB[(i+1-theSt)>>3]; + } + } else { + // end of line. byebye + } + } else { + for (int j = 0; j < nbSub; j++) { + c_full[j]<<=4; + // c_part[j]<<=4; + } + } + } + } + + if ( startExists ) { + AddRun(lastStart, curMax + 1, ((float) lastVal) * spA,((float) lastVal) * spA); + } +} + +/// Copy another IntLigne +void IntLigne::Copy(IntLigne *a) +{ + if ( a->nbRun <= 0 ) { + Reset(); + return; + } + + nbBord = 0; + nbRun = a->nbRun; + if ( nbRun > maxRun ) { + maxRun = nbRun; + runs = (int_ligne_run*) g_realloc(runs, maxRun * sizeof(int_ligne_run)); + } + memcpy(runs, a->runs, nbRun * sizeof(int_ligne_run)); +} + + +/** + * Copy a FloatLigne's runs. + * + * Compute non-overlapping runs with integer boundaries from a set of runs + * with floating-point boundaries. This involves replacing floating-point + * boundaries that are not integer by single-pixel runs, so this function + * contains plenty of rounding and float->integer conversion (read: + * time-consuming). + * + * \todo + * Optimization Questions: Why is this called so often compared with the + * other Copy() routines? How does AddRun() look for optimization potential? + */ +void IntLigne::Copy(FloatLigne* a) +{ + if ( a->runs.empty() ) { + Reset(); + return; + } + + /* if ( showCopy ) { + printf("\nfloatligne:\n"); + a->Affiche(); + }*/ + + nbBord = 0; + nbRun = 0; + firstAc = lastAc = -1; + bool pixExists = false; + int curPos = (int) floor(a->runs[0].st) - 1; + float lastSurf = 0; + float tolerance = 0.00001; + + // we take each run of the FloatLigne in sequence and make single-pixel runs of its boundaries as needed + // since the float_ligne_runs are non-overlapping, when a single-pixel run intersects with another runs, + // it must intersect with the single-pixel run created for the end of that run. so instead of creating a new + // int_ligne_run, we just add the coverage to that run. + for (auto & run : a->runs) { + float_ligne_run runA = run; + float curStF = floor(runA.st); + float curEnF = floor(runA.en); + int curSt = (int) curStF; + int curEn = (int) curEnF; + + // stEx: start boundary is not integer -> create single-pixel run for it + // enEx: end boundary is not integer -> create single-pixel run for it + // miEx: the runs minus the eventual single-pixel runs is not empty + bool stEx = true; + bool miEx = true; + bool enEx = true; + int miSt = curSt; + float miStF = curStF; + float msv; + float mev; + if ( runA.en - curEnF < tolerance ) { + enEx = false; + } + + // msv and mev are the start and end value of the middle section of the run, that is the run minus the + // single-pixel runs creaed for its boundaries + if ( runA.st-curStF < tolerance /*miSt == runA.st*/ ) { + stEx = false; + msv = runA.vst; + } else { + miSt += 1; + miStF += 1.0; + if ( enEx == false && miSt == curEn ) { + msv = runA.ven; + } else { + // msv=a->ValAt(miSt,runA.st,runA.en,runA.vst,runA.ven); + msv = runA.vst + (miStF-runA.st) * runA.pente; + } + } + + if ( miSt >= curEn ) { + miEx = false; + } + if ( stEx == false && miEx == false /*curEn == runA.st*/ ) { + mev = runA.vst; + } else if ( enEx == false /*curEn == runA.en*/ ) { + mev = runA.ven; + } else { + // mev=a->ValAt(curEn,runA.st,runA.en,runA.vst,runA.ven); + mev = runA.vst + (curEnF-runA.st) * runA.pente; + } + + // check the different cases + if ( stEx && enEx ) { + // stEx && enEx + if ( curEn > curSt ) { + if ( pixExists ) { + if ( curPos < curSt ) { + AddRun(curPos,curPos+1,lastSurf,lastSurf); + lastSurf=0.5*(msv+run.vst)*(miStF-run.st); + AddRun(curSt,curSt+1,lastSurf,lastSurf); + } else { + lastSurf+=0.5*(msv+run.vst)*(miStF-run.st); + AddRun(curSt,curSt+1,lastSurf,lastSurf); + } + pixExists=false; + } else { + lastSurf=0.5*(msv+run.vst)*(miStF-run.st); + AddRun(curSt,curSt+1,lastSurf,lastSurf); + } + } else if ( pixExists ) { + if ( curPos < curSt ) { + AddRun(curPos,curPos+1,lastSurf,lastSurf); + lastSurf=0.5*(run.ven+run.vst)*(run.en-run.st); + curPos=curSt; + } else { + lastSurf += 0.5 * (run.ven+run.vst)*(run.en-run.st); + } + } else { + lastSurf=0.5*(run.ven+run.vst)*(run.en-run.st); + curPos=curSt; + pixExists=true; + } + } else if ( pixExists ) { + if ( curPos < curSt ) { + AddRun(curPos,curPos+1,lastSurf,lastSurf); + lastSurf = 0.5 * (msv+run.vst) * (miStF-run.st); + AddRun(curSt,curSt+1,lastSurf,lastSurf); + } else { + lastSurf += 0.5 * (msv+run.vst) * (miStF-run.st); + AddRun(curSt,curSt+1,lastSurf,lastSurf); + } + pixExists=false; + } else { + lastSurf = 0.5 * (msv+run.vst) * (miStF-run.st); + AddRun(curSt,curSt+1,lastSurf,lastSurf); + } + if ( miEx ) { + if ( pixExists && curPos < miSt ) { + AddRun(curPos,curPos+1,lastSurf,lastSurf); + } + pixExists=false; + AddRun(miSt,curEn,msv,mev); + } + if ( enEx ) { + if ( curEn > curSt ) { + lastSurf=0.5*(mev+run.ven)*(run.en-curEnF); + pixExists=true; + curPos=curEn; + } else if ( ! stEx ) { + if ( pixExists ) { + AddRun(curPos,curPos+1,lastSurf,lastSurf); + } + lastSurf=0.5*(mev+run.ven)*(run.en-curEnF); + pixExists=true; + curPos=curEn; + } + } + } + if ( pixExists ) { + AddRun(curPos,curPos+1,lastSurf,lastSurf); + } + /* if ( showCopy ) { + printf("-> intligne:\n"); + Affiche(); + }*/ +} + + +void IntLigne::Enqueue(int no) +{ + if ( firstAc < 0 ) { + firstAc = lastAc = no; + bords[no].prev = bords[no].next = -1; + } else { + bords[no].next = -1; + bords[no].prev = lastAc; + bords[lastAc].next = no; + lastAc = no; + } +} + + +void IntLigne::Dequeue(int no) +{ + if ( no == firstAc ) { + if ( no == lastAc ) { + firstAc = lastAc = -1; + } else { + firstAc = bords[no].next; + } + } else if ( no == lastAc ) { + lastAc = bords[no].prev; + } else { + } + if ( bords[no].prev >= 0 ) { + bords[bords[no].prev].next = bords[no].next; + } + if ( bords[no].next >= 0 ) { + bords[bords[no].next].prev = bords[no].prev; + } + + bords[no].prev = bords[no].next = -1; +} + +/** + * Rasterization. + * + * The parameters have the same meaning as in the AlphaLigne class. + */ +void IntLigne::Raster(raster_info &dest, void *color, RasterInRunFunc worker) +{ + if ( nbRun <= 0 ) { + return; + } + + int min = runs[0].st; + int max = runs[nbRun-1].en; + if ( dest.endPix <= min || dest.startPix >= max ) { + return; + } + + int curRun = -1; + for (curRun = 0; curRun < nbRun; curRun++) { + if ( runs[curRun].en > dest.startPix ) { + break; + } + } + + if ( curRun >= nbRun ) { + return; + } + + if ( runs[curRun].st < dest.startPix ) { + int nst = runs[curRun].st; + int nen = runs[curRun].en; + float vst = runs[curRun].vst; + float ven = runs[curRun].ven; + float nvst = (vst * (nen - dest.startPix) + ven * (dest.startPix - nst)) / ((float) (nen - nst)); + if ( runs[curRun].en <= dest.endPix ) { + (worker)(dest, color, dest.startPix, nvst, runs[curRun].en, runs[curRun].ven); + } else { + float nven = (vst * (nen - dest.endPix) + ven * (dest.endPix - nst)) / ((float)(nen - nst)); + (worker)(dest, color, dest.startPix, nvst, dest.endPix, nven); + return; + } + curRun++; + } + + for (; (curRun < nbRun && runs[curRun].en <= dest.endPix); curRun++) { + (worker)(dest, color, runs[curRun].st, runs[curRun].vst, runs[curRun].en, runs[curRun].ven); +//Buffer::RasterRun(*dest,color,runs[curRun].st,runs[curRun].vst,runs[curRun].en,runs[curRun].ven); + } + + if ( curRun >= nbRun ) { + return; + } + + if ( runs[curRun].st < dest.endPix && runs[curRun].en > dest.endPix ) { + int const nst = runs[curRun].st; + int const nen = runs[curRun].en; + float const vst = runs[curRun].vst; + float const ven = runs[curRun].ven; + float const nven = (vst * (nen - dest.endPix) + ven * (dest.endPix - nst)) / ((float)(nen - nst)); + + (worker)(dest,color,runs[curRun].st,runs[curRun].vst,dest.endPix,nven); + curRun++; + } +} + + + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 : -- cgit v1.2.3