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 <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"
22 IntLigne::IntLigne()
23 {
24 nbBord = maxBord = 0;
25 bords = NULL;
27 nbRun = maxRun = 0;
28 runs = NULL;
30 firstAc = lastAc = -1;
31 }
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 }
48 void IntLigne::Reset()
49 {
50 nbBord = 0;
51 nbRun = 0;
52 firstAc = lastAc = -1;
53 }
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));
61 }
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;
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;
77 return n - 1;
78 }
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 }
93 void IntLigne::Flatten()
94 {
95 if ( nbBord <= 1 ) {
96 Reset();
97 return;
98 }
100 nbRun = 0;
101 firstAc = lastAc = -1;
103 for (int i = 0; i < nbBord; i++) {
104 bords[i].prev = i;
105 }
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 }
112 for (int i = 0; i < nbBord; i++) {
113 bords[i].other = bords[bords[i].other].next;
114 }
116 int lastStart = 0;
117 float lastVal = 0;
118 bool startExists = false;
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 }
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 }
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 }
160 int IntLigne::AddRun(int st, int en, float vst, float ven)
161 {
162 if ( st >= en ) {
163 return -1;
164 }
166 if ( nbRun >= maxRun ) {
167 maxRun = 2 * nbRun + 1;
168 runs = (int_ligne_run *) g_realloc(runs, maxRun * sizeof(int_ligne_run));
169 }
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 }
179 void IntLigne::Booleen(IntLigne *a, IntLigne *b, BooleanOp mod)
180 {
181 Reset();
182 if ( a->nbRun <= 0 && b->nbRun <= 0 ) {
183 return;
184 }
186 if ( a->nbRun <= 0 ) {
187 if ( mod == bool_op_union || mod == bool_op_symdiff ) {
188 Copy(b);
189 }
190 return;
191 }
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 }
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 }
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 );
219 bool startA = false;
220 bool startB = false;
221 bool endA = false;
222 bool endB = false;
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 }
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;
269 if ( mod == bool_op_union ) {
271 if ( inA || inB ) {
272 AddRun(curPos, nextPos, oValA + oValB, valA + valB);
273 }
275 } else if ( mod == bool_op_inters ) {
277 if ( inA && inB ) {
278 AddRun(curPos, nextPos, oValA * oValB, valA * valB);
279 }
281 } else if ( mod == bool_op_diff ) {
283 if ( inA ) {
284 AddRun(curPos, nextPos, oValA - oValB, valA - valB);
285 }
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 }
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 }
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;
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 }
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;
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 }
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 }
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;
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 }
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;
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 }
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 }
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 }
449 if ( a->curMin < a->st ) {
450 a->curMin = a->st;
451 }
453 if ( a->curMax < a->st ) {
454 Reset();
455 return;
456 }
458 if ( a->curMin > a->en ) {
459 Reset();
460 return;
461 }
463 if ( a->curMax > a->en ) {
464 a->curMax=a->en;
465 }
467 nbBord = 0;
468 nbRun = 0;
470 int lastVal = 0;
471 int lastStart = 0;
472 bool startExists = false;
474 int masks[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
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];
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 }
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 }
534 if ( nbSub == 1 ) {
535 Copy(as[0]);
536 return;
537 }
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 }
551 if ( curMin < as[0]->st ) {
552 curMin = as[0]->st;
553 }
555 if ( curMax > as[0]->en ) {
556 curMax = as[0]->en;
557 }
559 if ( curMax <= curMin ) {
560 Reset();
561 return;
562 }
564 nbBord = 0;
565 nbRun = 0;
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};
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);
586 spA = 1.0 / (4 * 4);
587 for (int i = curMin; i <= curMax; i++) {
588 int nbBit = 0;
590 if ( c_full[0] == 0 && c_full[1] == 0 && c_full[2] == 0 && c_full[3] == 0 ) {
592 if ( startExists ) {
593 AddRun(lastStart, i, ((float) lastVal) * spA, ((float) lastVal) * spA);
594 }
595 startExists = false;
596 i = theSt + (((i - theSt) & (~7) ) + 7);
598 } else if ( c_full[0] == 0xFFFFFFFF && c_full[1] == 0xFFFFFFFF &&
599 c_full[2] == 0xFFFFFFFF && c_full[3] == 0xFFFFFFFF ) {
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);
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];
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 }
659 } else {
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
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 }
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 }
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 }
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 }
772 if ( startExists ) {
773 AddRun(lastStart, curMax + 1, ((float) lastVal) * spA,((float) lastVal) * spA);
774 }
775 }
777 /// Copy another IntLigne
778 void IntLigne::Copy(IntLigne *a)
779 {
780 if ( a->nbRun <= 0 ) {
781 Reset();
782 return;
783 }
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 }
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 }
815 /* if ( showCopy ) {
816 printf("\nfloatligne:\n");
817 a->Affiche();
818 }*/
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;
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;
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 }
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 }
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 }
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 }
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 }
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 }
991 bords[no].prev = bords[no].next = -1;
992 }
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 }
1005 int min = runs[0].st;
1006 int max = runs[nbRun-1].en;
1007 if ( dest.endPix <= min || dest.startPix >= max ) {
1008 return;
1009 }
1011 int curRun = -1;
1012 for (curRun = 0; curRun < nbRun; curRun++) {
1013 if ( runs[curRun].en > dest.startPix ) {
1014 break;
1015 }
1016 }
1018 if ( curRun >= nbRun ) {
1019 return;
1020 }
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 }
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 }
1043 if ( curRun >= nbRun ) {
1044 return;
1045 }
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));
1054 (worker)(dest,color,runs[curRun].st,runs[curRun].vst,dest.endPix,nven);
1055 curRun++;
1056 }
1057 }
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 :