← Back to branch summary

~valavanisalex/ubuntu/precise/inkscape/fix-943984

« back to all changes in this revision

Viewing changes to inkscape-0.47pre1/src/livarot/int-line.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Bryce Harrington
  • Date: 2009-07-02 17:09:45 UTC
  • mfrom: (1.1.9 upstream)
  • Revision ID: james.westby@ubuntu.com-20090702170945-nn6d6zswovbwju1t
Tags: 0.47~pre1-0ubuntu1
https://launchpad.net/bugs/348842
https://launchpad.net/bugs/391149
* New upstream release.
  - Don't constrain maximization on small resolution devices (pre0)
    (LP: #348842)
  - Fixes segfault on startup (pre0)
    (LP: #391149)

Show diffs side-by-side

added added

removed removed

Lines of Context:
inkscape-0.47pre1/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 :