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 */
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"
18 IntLigne::IntLigne()
19 {
20 nbBord = maxBord = 0;
21 bords = NULL;
23 nbRun = maxRun = 0;
24 runs = NULL;
26 firstAc = lastAc = -1;
27 }
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 }
44 void IntLigne::Reset()
45 {
46 nbBord = 0;
47 nbRun = 0;
48 firstAc = lastAc = -1;
49 }
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));
57 }
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;
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;
73 return n - 1;
74 }
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 }
89 void IntLigne::Flatten()
90 {
91 if ( nbBord <= 1 ) {
92 Reset();
93 return;
94 }
96 nbRun = 0;
97 firstAc = lastAc = -1;
99 for (int i = 0; i < nbBord; i++) {
100 bords[i].prev = i;
101 }
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 }
108 for (int i = 0; i < nbBord; i++) {
109 bords[i].other = bords[bords[i].other].next;
110 }
112 int lastStart = 0;
113 float lastVal = 0;
114 bool startExists = false;
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 }
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 }
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 }
156 int IntLigne::AddRun(int st, int en, float vst, float ven)
157 {
158 if ( st >= en ) {
159 return -1;
160 }
162 if ( nbRun >= maxRun ) {
163 maxRun = 2 * nbRun + 1;
164 runs = (int_ligne_run *) g_realloc(runs, maxRun * sizeof(int_ligne_run));
165 }
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 }
175 void IntLigne::Booleen(IntLigne *a, IntLigne *b, BooleanOp mod)
176 {
177 Reset();
178 if ( a->nbRun <= 0 && b->nbRun <= 0 ) {
179 return;
180 }
182 if ( a->nbRun <= 0 ) {
183 if ( mod == bool_op_union || mod == bool_op_symdiff ) {
184 Copy(b);
185 }
186 return;
187 }
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 }
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 }
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 );
215 bool startA = false;
216 bool startB = false;
217 bool endA = false;
218 bool endB = false;
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 }
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;
265 if ( mod == bool_op_union ) {
267 if ( inA || inB ) {
268 AddRun(curPos, nextPos, oValA + oValB, valA + valB);
269 }
271 } else if ( mod == bool_op_inters ) {
273 if ( inA && inB ) {
274 AddRun(curPos, nextPos, oValA * oValB, valA * valB);
275 }
277 } else if ( mod == bool_op_diff ) {
279 if ( inA ) {
280 AddRun(curPos, nextPos, oValA - oValB, valA - valB);
281 }
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 }
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 }
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;
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 }
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;
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 }
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 }
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;
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 }
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;
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 }
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 }
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 }
445 if ( a->curMin < a->st ) {
446 a->curMin = a->st;
447 }
449 if ( a->curMax < a->st ) {
450 Reset();
451 return;
452 }
454 if ( a->curMin > a->en ) {
455 Reset();
456 return;
457 }
459 if ( a->curMax > a->en ) {
460 a->curMax=a->en;
461 }
463 nbBord = 0;
464 nbRun = 0;
466 int lastVal = 0;
467 int lastStart = 0;
468 bool startExists = false;
470 int masks[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
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];
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 }
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 }
530 if ( nbSub == 1 ) {
531 Copy(as[0]);
532 return;
533 }
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 }
547 if ( curMin < as[0]->st ) {
548 curMin = as[0]->st;
549 }
551 if ( curMax > as[0]->en ) {
552 curMax = as[0]->en;
553 }
555 if ( curMax <= curMin ) {
556 Reset();
557 return;
558 }
560 nbBord = 0;
561 nbRun = 0;
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};
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);
582 spA = 1.0 / (4 * 4);
583 for (int i = curMin; i <= curMax; i++) {
584 int nbBit = 0;
586 if ( c_full[0] == 0 && c_full[1] == 0 && c_full[2] == 0 && c_full[3] == 0 ) {
588 if ( startExists ) {
589 AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
590 }
591 startExists = false;
592 i = theSt + (((i - theSt) & (~7) ) + 7);
594 } else if ( c_full[0] == 0xFFFFFFFF && c_full[1] == 0xFFFFFFFF &&
595 c_full[2] == 0xFFFFFFFF && c_full[3] == 0xFFFFFFFF ) {
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);
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];
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 }
655 } else {
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
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 }
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 }
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 }
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 }
768 if ( startExists ) {
769 AddRun(lastStart, curMax + 1, ((float) lastVal) * spA,((float) lastVal) * spA);
770 }
771 }
773 /// Copy another IntLigne
774 void IntLigne::Copy(IntLigne *a)
775 {
776 if ( a->nbRun <= 0 ) {
777 Reset();
778 return;
779 }
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 }
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 }
811 /* if ( showCopy ) {
812 printf("\nfloatligne:\n");
813 a->Affiche();
814 }*/
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;
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;
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 }
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 }
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 }
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 }
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 }
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 }
987 bords[no].prev = bords[no].next = -1;
988 }
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 }
1001 int min = runs[0].st;
1002 int max = runs[nbRun-1].en;
1003 if ( dest.endPix <= min || dest.startPix >= max ) {
1004 return;
1005 }
1007 int curRun = -1;
1008 for (curRun = 0; curRun < nbRun; curRun++) {
1009 if ( runs[curRun].en > dest.startPix ) {
1010 break;
1011 }
1012 }
1014 if ( curRun >= nbRun ) {
1015 return;
1016 }
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 }
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 }
1039 if ( curRun >= nbRun ) {
1040 return;
1041 }
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));
1050 (worker)(dest,color,runs[curRun].st,runs[curRun].vst,dest.endPix,nven);
1051 curRun++;
1052 }
1053 }
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 :