agg_rust/
rasterizer_cells_aa.rs

1//! Anti-aliased cell rasterizer engine.
2//!
3//! Port of `agg_rasterizer_cells_aa.h` — converts edges (line segments in
4//! 24.8 fixed-point coordinates) into cells with coverage and area values.
5//! This is the core computational engine used by `RasterizerScanlineAa`.
6//!
7//! Also ports the `cell_aa` struct from `agg_rasterizer_scanline_aa_nogamma.h`.
8
9use crate::basics::{POLY_SUBPIXEL_MASK, POLY_SUBPIXEL_SCALE, POLY_SUBPIXEL_SHIFT};
10
11// ============================================================================
12// CellAa — a single pixel cell with coverage data
13// ============================================================================
14
15/// A pixel cell storing accumulated coverage and area from edges.
16///
17/// Port of C++ `cell_aa` from `agg_rasterizer_scanline_aa_nogamma.h`.
18/// - `cover`: net winding contribution (sum of dy across this cell)
19/// - `area`: twice the signed area of edge fragments within this cell,
20///   used to compute the partial-pixel coverage at cell boundaries
21#[derive(Debug, Clone, Copy)]
22pub struct CellAa {
23    pub x: i32,
24    pub y: i32,
25    pub cover: i32,
26    pub area: i32,
27}
28
29impl CellAa {
30    /// Reset to the "initial" sentinel state (matches C++ `cell_aa::initial`).
31    #[inline]
32    pub fn initial(&mut self) {
33        self.x = i32::MAX;
34        self.y = i32::MAX;
35        self.cover = 0;
36        self.area = 0;
37    }
38
39    /// Style comparison (no-op for basic cell_aa — only meaningful for
40    /// compound rasterizer cells). Matches C++ `cell_aa::style`.
41    #[inline]
42    pub fn style(&mut self, _other: &CellAa) {}
43
44    /// Returns non-zero if this cell differs from position (ex, ey).
45    /// Matches C++ `cell_aa::not_equal` — uses unsigned subtraction trick.
46    #[inline]
47    pub fn not_equal(&self, ex: i32, ey: i32, _style: &CellAa) -> bool {
48        (ex as u32).wrapping_sub(self.x as u32) | (ey as u32).wrapping_sub(self.y as u32) != 0
49    }
50}
51
52impl Default for CellAa {
53    fn default() -> Self {
54        Self {
55            x: i32::MAX,
56            y: i32::MAX,
57            cover: 0,
58            area: 0,
59        }
60    }
61}
62
63// ============================================================================
64// SortedY — per-scanline index into sorted cell array
65// ============================================================================
66
67#[derive(Debug, Clone, Copy, Default)]
68struct SortedY {
69    start: u32,
70    num: u32,
71}
72
73// ============================================================================
74// RasterizerCellsAa — the edge-to-cell conversion engine
75// ============================================================================
76
77/// The main rasterization engine that converts line segments (edges) into
78/// anti-aliased pixel cells.
79///
80/// Port of C++ `rasterizer_cells_aa<Cell>` from `agg_rasterizer_cells_aa.h`.
81///
82/// Instead of the C++ block-based allocator, we use a flat `Vec<CellAa>`.
83/// Sorted cell access uses indices into this vec rather than raw pointers.
84pub struct RasterizerCellsAa {
85    cells: Vec<CellAa>,
86    sorted_cells: Vec<u32>,
87    sorted_y: Vec<SortedY>,
88    curr_cell: CellAa,
89    style_cell: CellAa,
90    min_x: i32,
91    min_y: i32,
92    max_x: i32,
93    max_y: i32,
94    sorted: bool,
95}
96
97/// Limit for dx magnitude before recursive subdivision in `line()`.
98const DX_LIMIT: i64 = 16384 << POLY_SUBPIXEL_SHIFT;
99
100impl RasterizerCellsAa {
101    /// Create a new empty cell rasterizer.
102    pub fn new() -> Self {
103        Self {
104            cells: Vec::new(),
105            sorted_cells: Vec::new(),
106            sorted_y: Vec::new(),
107            curr_cell: CellAa::default(),
108            style_cell: CellAa::default(),
109            min_x: i32::MAX,
110            min_y: i32::MAX,
111            max_x: i32::MIN,
112            max_y: i32::MIN,
113            sorted: false,
114        }
115    }
116
117    /// Reset the rasterizer, discarding all cells.
118    pub fn reset(&mut self) {
119        self.cells.clear();
120        self.sorted_cells.clear();
121        self.sorted_y.clear();
122        self.curr_cell.initial();
123        self.style_cell.initial();
124        self.min_x = i32::MAX;
125        self.min_y = i32::MAX;
126        self.max_x = i32::MIN;
127        self.max_y = i32::MIN;
128        self.sorted = false;
129    }
130
131    /// Set the current style cell (used by compound rasterizer; no-op for basic usage).
132    #[inline]
133    pub fn style(&mut self, style_cell: &CellAa) {
134        self.style_cell.style(style_cell);
135    }
136
137    #[inline]
138    pub fn min_x(&self) -> i32 {
139        self.min_x
140    }
141    #[inline]
142    pub fn min_y(&self) -> i32 {
143        self.min_y
144    }
145    #[inline]
146    pub fn max_x(&self) -> i32 {
147        self.max_x
148    }
149    #[inline]
150    pub fn max_y(&self) -> i32 {
151        self.max_y
152    }
153
154    /// Total number of accumulated cells.
155    #[inline]
156    pub fn total_cells(&self) -> u32 {
157        self.cells.len() as u32
158    }
159
160    /// Whether cells have been sorted.
161    #[inline]
162    pub fn sorted(&self) -> bool {
163        self.sorted
164    }
165
166    /// Number of cells on scanline `y` (only valid after `sort_cells()`).
167    #[inline]
168    pub fn scanline_num_cells(&self, y: u32) -> u32 {
169        self.sorted_y[(y as i32 - self.min_y) as usize].num
170    }
171
172    /// Get a slice of cell indices for scanline `y` (only valid after `sort_cells()`).
173    /// Returns indices into the internal cells array.
174    #[inline]
175    pub fn scanline_cells(&self, y: u32) -> &[u32] {
176        let sy = &self.sorted_y[(y as i32 - self.min_y) as usize];
177        &self.sorted_cells[sy.start as usize..(sy.start + sy.num) as usize]
178    }
179
180    /// Get a reference to the cell at the given index.
181    #[inline]
182    pub fn cell(&self, idx: u32) -> &CellAa {
183        &self.cells[idx as usize]
184    }
185
186    /// Get a reference to all cells.
187    #[inline]
188    pub fn cells(&self) -> &[CellAa] {
189        &self.cells
190    }
191
192    // ========================================================================
193    // Private helpers
194    // ========================================================================
195
196    /// Flush the current cell into the cells array if it has non-zero data.
197    #[inline]
198    pub(crate) fn add_curr_cell(&mut self) {
199        if self.curr_cell.area | self.curr_cell.cover != 0 {
200            self.cells.push(self.curr_cell);
201        }
202    }
203
204    /// Import pre-computed cells with a pixel offset, bypassing path conversion.
205    ///
206    /// The cells must have been generated at position (0, 0) — i.e., with the
207    /// path origin at pixel (0, 0). The `(dx, dy)` offset is added to each
208    /// cell's `(x, y)` before insertion.
209    ///
210    /// **Caller responsibility**: the shifted cells must remain within the
211    /// rasterizer's configured clip region. This bypasses the clipper entirely,
212    /// so out-of-bounds cells will produce incorrect rendering near clip edges.
213    ///
214    /// Call `sort_cells()` (via the rasterizer's `rewind_scanlines()`) after
215    /// all cells have been inserted.
216    pub fn add_cells_offset(&mut self, src: &[CellAa], dx: i32, dy: i32) {
217        self.sorted = false;
218        self.cells.reserve(src.len());
219        for c in src {
220            let x = c.x + dx;
221            let y = c.y + dy;
222            if x < self.min_x {
223                self.min_x = x;
224            }
225            if x > self.max_x {
226                self.max_x = x;
227            }
228            if y < self.min_y {
229                self.min_y = y;
230            }
231            if y > self.max_y {
232                self.max_y = y;
233            }
234            self.cells.push(CellAa {
235                x,
236                y,
237                cover: c.cover,
238                area: c.area,
239            });
240        }
241    }
242
243    /// Move to a new cell position, flushing the previous cell if needed.
244    #[inline]
245    fn set_curr_cell(&mut self, x: i32, y: i32) {
246        if self.curr_cell.not_equal(x, y, &self.style_cell) {
247            self.add_curr_cell();
248            self.curr_cell.style(&self.style_cell);
249            self.curr_cell.x = x;
250            self.curr_cell.y = y;
251            self.curr_cell.cover = 0;
252            self.curr_cell.area = 0;
253        }
254    }
255
256    /// Render a horizontal line segment within a single scanline row `ey`.
257    ///
258    /// `x1`, `x2` are in 24.8 fixed-point; `y1`, `y2` are fractional y within
259    /// the scanline (0..POLY_SUBPIXEL_SCALE).
260    ///
261    /// This is the most performance-critical helper. Matches C++ `render_hline`
262    /// exactly, including the `i64` arithmetic for large dx values.
263    fn render_hline(&mut self, ey: i32, x1: i32, y1: i32, x2: i32, y2: i32) {
264        let ex1 = x1 >> POLY_SUBPIXEL_SHIFT;
265        let ex2 = x2 >> POLY_SUBPIXEL_SHIFT;
266        let fx1 = x1 & POLY_SUBPIXEL_MASK as i32;
267        let fx2 = x2 & POLY_SUBPIXEL_MASK as i32;
268
269        // Trivial case: horizontal line (y1 == y2) — just move to target cell
270        if y1 == y2 {
271            self.set_curr_cell(ex2, ey);
272            return;
273        }
274
275        // Everything in a single cell
276        if ex1 == ex2 {
277            let delta = y2 - y1;
278            self.curr_cell.cover += delta;
279            self.curr_cell.area += (fx1 + fx2) * delta;
280            return;
281        }
282
283        // Run of adjacent cells on the same hline
284        let mut p = (POLY_SUBPIXEL_SCALE as i64 - fx1 as i64) * (y2 - y1) as i64;
285        let mut first = POLY_SUBPIXEL_SCALE as i32;
286        let mut incr = 1_i32;
287
288        let mut dx = x2 as i64 - x1 as i64;
289
290        if dx < 0 {
291            p = fx1 as i64 * (y2 - y1) as i64;
292            first = 0;
293            incr = -1;
294            dx = -dx;
295        }
296
297        let mut delta = (p / dx) as i32;
298        let mut modulo = p % dx;
299
300        if modulo < 0 {
301            delta -= 1;
302            modulo += dx;
303        }
304
305        self.curr_cell.cover += delta;
306        self.curr_cell.area += (fx1 + first) * delta;
307
308        let mut ex1 = ex1 + incr;
309        self.set_curr_cell(ex1, ey);
310        let mut y1 = y1 + delta;
311
312        if ex1 != ex2 {
313            p = POLY_SUBPIXEL_SCALE as i64 * (y2 - y1 + delta) as i64;
314            let mut lift = (p / dx) as i32;
315            let mut rem = p % dx;
316
317            if rem < 0 {
318                lift -= 1;
319                rem += dx;
320            }
321
322            modulo -= dx;
323
324            while ex1 != ex2 {
325                delta = lift;
326                modulo += rem;
327                if modulo >= 0 {
328                    modulo -= dx;
329                    delta += 1;
330                }
331
332                self.curr_cell.cover += delta;
333                self.curr_cell.area += POLY_SUBPIXEL_SCALE as i32 * delta;
334                y1 += delta;
335                ex1 += incr;
336                self.set_curr_cell(ex1, ey);
337            }
338        }
339        delta = y2 - y1;
340        self.curr_cell.cover += delta;
341        self.curr_cell.area += (fx2 + POLY_SUBPIXEL_SCALE as i32 - first) * delta;
342    }
343
344    /// Add a line segment in 24.8 fixed-point coordinates.
345    ///
346    /// This is the primary entry point for the rasterizer. Large dx values
347    /// are handled by recursive subdivision (matching the C++ implementation).
348    pub fn line(&mut self, x1: i32, y1: i32, x2: i32, y2: i32) {
349        let dx = x2 as i64 - x1 as i64;
350
351        if dx >= DX_LIMIT || dx <= -DX_LIMIT {
352            let cx = ((x1 as i64 + x2 as i64) >> 1) as i32;
353            let cy = ((y1 as i64 + y2 as i64) >> 1) as i32;
354            self.line(x1, y1, cx, cy);
355            self.line(cx, cy, x2, y2);
356            return;
357        }
358
359        let dy = y2 as i64 - y1 as i64;
360        let ex1 = x1 >> POLY_SUBPIXEL_SHIFT;
361        let ex2 = x2 >> POLY_SUBPIXEL_SHIFT;
362        let ey1_orig = y1 >> POLY_SUBPIXEL_SHIFT;
363        let ey2 = y2 >> POLY_SUBPIXEL_SHIFT;
364        let fy1 = y1 & POLY_SUBPIXEL_MASK as i32;
365        let fy2 = y2 & POLY_SUBPIXEL_MASK as i32;
366
367        // Update bounding box
368        if ex1 < self.min_x {
369            self.min_x = ex1;
370        }
371        if ex1 > self.max_x {
372            self.max_x = ex1;
373        }
374        if ey1_orig < self.min_y {
375            self.min_y = ey1_orig;
376        }
377        if ey1_orig > self.max_y {
378            self.max_y = ey1_orig;
379        }
380        if ex2 < self.min_x {
381            self.min_x = ex2;
382        }
383        if ex2 > self.max_x {
384            self.max_x = ex2;
385        }
386        if ey2 < self.min_y {
387            self.min_y = ey2;
388        }
389        if ey2 > self.max_y {
390            self.max_y = ey2;
391        }
392
393        let mut ey1 = ey1_orig;
394
395        self.set_curr_cell(ex1, ey1);
396
397        // Everything on a single hline
398        if ey1 == ey2 {
399            self.render_hline(ey1, x1, fy1, x2, fy2);
400            return;
401        }
402
403        // Vertical line — optimized path without render_hline calls
404        let mut incr = 1_i32;
405        if dx == 0 {
406            let ex = x1 >> POLY_SUBPIXEL_SHIFT;
407            let two_fx = (x1 - (ex << POLY_SUBPIXEL_SHIFT)) << 1;
408
409            let mut first = POLY_SUBPIXEL_SCALE as i32;
410            if dy < 0 {
411                first = 0;
412                incr = -1;
413            }
414
415            let x_from = x1;
416            let _ = x_from; // keep name for clarity matching C++
417
418            let mut delta = first - fy1;
419            self.curr_cell.cover += delta;
420            self.curr_cell.area += two_fx * delta;
421
422            ey1 += incr;
423            self.set_curr_cell(ex, ey1);
424
425            delta = first + first - POLY_SUBPIXEL_SCALE as i32;
426            let area = two_fx * delta;
427            while ey1 != ey2 {
428                self.curr_cell.cover = delta;
429                self.curr_cell.area = area;
430                ey1 += incr;
431                self.set_curr_cell(ex, ey1);
432            }
433            delta = fy2 - POLY_SUBPIXEL_SCALE as i32 + first;
434            self.curr_cell.cover += delta;
435            self.curr_cell.area += two_fx * delta;
436            return;
437        }
438
439        // General case: multiple hlines
440        let mut p = (POLY_SUBPIXEL_SCALE as i64 - fy1 as i64) * dx;
441        let mut first = POLY_SUBPIXEL_SCALE as i32;
442
443        let mut dy_abs = dy;
444        if dy < 0 {
445            p = fy1 as i64 * dx;
446            first = 0;
447            incr = -1;
448            dy_abs = -dy;
449        }
450
451        let mut delta = (p / dy_abs) as i32;
452        let mut modulo = p % dy_abs;
453
454        if modulo < 0 {
455            delta -= 1;
456            modulo += dy_abs;
457        }
458
459        let mut x_from = x1 + delta;
460        self.render_hline(ey1, x1, fy1, x_from, first);
461
462        ey1 += incr;
463        self.set_curr_cell(x_from >> POLY_SUBPIXEL_SHIFT, ey1);
464
465        if ey1 != ey2 {
466            p = POLY_SUBPIXEL_SCALE as i64 * dx;
467            let mut lift = (p / dy_abs) as i32;
468            let mut rem = p % dy_abs;
469
470            if rem < 0 {
471                lift -= 1;
472                rem += dy_abs;
473            }
474            modulo -= dy_abs;
475
476            while ey1 != ey2 {
477                delta = lift;
478                modulo += rem;
479                if modulo >= 0 {
480                    modulo -= dy_abs;
481                    delta += 1;
482                }
483
484                let x_to = x_from + delta;
485                self.render_hline(ey1, x_from, POLY_SUBPIXEL_SCALE as i32 - first, x_to, first);
486                x_from = x_to;
487
488                ey1 += incr;
489                self.set_curr_cell(x_from >> POLY_SUBPIXEL_SHIFT, ey1);
490            }
491        }
492        self.render_hline(ey1, x_from, POLY_SUBPIXEL_SCALE as i32 - first, x2, fy2);
493    }
494
495    /// Sort all accumulated cells by Y then X.
496    ///
497    /// After sorting, cells can be queried per-scanline via
498    /// `scanline_num_cells()` and `scanline_cells()`.
499    pub fn sort_cells(&mut self) {
500        if self.sorted {
501            return;
502        }
503
504        self.add_curr_cell();
505        self.curr_cell.x = i32::MAX;
506        self.curr_cell.y = i32::MAX;
507        self.curr_cell.cover = 0;
508        self.curr_cell.area = 0;
509
510        if self.cells.is_empty() {
511            return;
512        }
513
514        // Allocate sorted_cells (indices) and sorted_y (histogram)
515        let num_cells = self.cells.len();
516        self.sorted_cells.clear();
517        self.sorted_cells.resize(num_cells, 0);
518
519        let y_range = (self.max_y - self.min_y + 1) as usize;
520        self.sorted_y.clear();
521        self.sorted_y.resize(y_range, SortedY::default());
522
523        // Pass 1: Build Y-histogram (count cells per scanline)
524        for cell in &self.cells {
525            let yi = (cell.y - self.min_y) as usize;
526            self.sorted_y[yi].start += 1;
527        }
528
529        // Convert histogram to starting indices
530        let mut start = 0u32;
531        for sy in &mut self.sorted_y {
532            let count = sy.start;
533            sy.start = start;
534            start += count;
535        }
536
537        // Pass 2: Fill sorted_cells with cell indices, sorted by Y
538        for (i, cell) in self.cells.iter().enumerate() {
539            let yi = (cell.y - self.min_y) as usize;
540            let sy = &mut self.sorted_y[yi];
541            self.sorted_cells[(sy.start + sy.num) as usize] = i as u32;
542            sy.num += 1;
543        }
544
545        // Pass 3: Sort each scanline's cells by X
546        for sy in &self.sorted_y {
547            if sy.num > 0 {
548                let start = sy.start as usize;
549                let end = (sy.start + sy.num) as usize;
550                let slice = &mut self.sorted_cells[start..end];
551                let cells = &self.cells;
552                slice.sort_unstable_by_key(|&idx| cells[idx as usize].x);
553            }
554        }
555
556        self.sorted = true;
557    }
558}
559
560impl Default for RasterizerCellsAa {
561    fn default() -> Self {
562        Self::new()
563    }
564}
565
566// ============================================================================
567// ScanlineHitTest — simple scanline that tests if a specific X is covered
568// ============================================================================
569
570/// A minimal "scanline" that only checks whether a specific X coordinate
571/// is covered by the rasterized polygon.
572///
573/// Port of C++ `scanline_hit_test` from `agg_rasterizer_cells_aa.h`.
574pub struct ScanlineHitTest {
575    x: i32,
576    hit: bool,
577}
578
579impl ScanlineHitTest {
580    pub fn new(x: i32) -> Self {
581        Self { x, hit: false }
582    }
583
584    #[inline]
585    pub fn reset_spans(&mut self) {}
586
587    #[inline]
588    pub fn finalize(&mut self, _y: i32) {}
589
590    #[inline]
591    pub fn add_cell(&mut self, x: i32, _cover: u32) {
592        if self.x == x {
593            self.hit = true;
594        }
595    }
596
597    #[inline]
598    pub fn add_span(&mut self, x: i32, len: u32, _cover: u32) {
599        if self.x >= x && self.x < x + len as i32 {
600            self.hit = true;
601        }
602    }
603
604    #[inline]
605    pub fn num_spans(&self) -> u32 {
606        1
607    }
608
609    #[inline]
610    pub fn hit(&self) -> bool {
611        self.hit
612    }
613}
614
615// ============================================================================
616// Tests
617// ============================================================================
618
619#[cfg(test)]
620mod tests {
621    use super::*;
622
623    // ------------------------------------------------------------------
624    // CellAa tests
625    // ------------------------------------------------------------------
626
627    #[test]
628    fn test_cell_aa_default() {
629        let cell = CellAa::default();
630        assert_eq!(cell.x, i32::MAX);
631        assert_eq!(cell.y, i32::MAX);
632        assert_eq!(cell.cover, 0);
633        assert_eq!(cell.area, 0);
634    }
635
636    #[test]
637    fn test_cell_aa_initial() {
638        let mut cell = CellAa {
639            x: 10,
640            y: 20,
641            cover: 5,
642            area: 100,
643        };
644        cell.initial();
645        assert_eq!(cell.x, i32::MAX);
646        assert_eq!(cell.y, i32::MAX);
647        assert_eq!(cell.cover, 0);
648        assert_eq!(cell.area, 0);
649    }
650
651    #[test]
652    fn test_cell_aa_not_equal() {
653        let cell = CellAa {
654            x: 10,
655            y: 20,
656            cover: 0,
657            area: 0,
658        };
659        let style = CellAa::default();
660        assert!(!cell.not_equal(10, 20, &style));
661        assert!(cell.not_equal(11, 20, &style));
662        assert!(cell.not_equal(10, 21, &style));
663        assert!(cell.not_equal(11, 21, &style));
664    }
665
666    // ------------------------------------------------------------------
667    // RasterizerCellsAa basic tests
668    // ------------------------------------------------------------------
669
670    #[test]
671    fn test_new_rasterizer_is_empty() {
672        let ras = RasterizerCellsAa::new();
673        assert_eq!(ras.total_cells(), 0);
674        assert!(!ras.sorted());
675        assert_eq!(ras.min_x(), i32::MAX);
676        assert_eq!(ras.min_y(), i32::MAX);
677        assert_eq!(ras.max_x(), i32::MIN);
678        assert_eq!(ras.max_y(), i32::MIN);
679    }
680
681    #[test]
682    fn test_reset() {
683        let mut ras = RasterizerCellsAa::new();
684        // Add a line to generate some cells
685        ras.line(0, 0, 256, 256);
686        assert!(ras.total_cells() > 0 || true); // line may not add cells until sort
687        ras.reset();
688        assert_eq!(ras.total_cells(), 0);
689        assert!(!ras.sorted());
690    }
691
692    // ------------------------------------------------------------------
693    // Horizontal line tests
694    // ------------------------------------------------------------------
695
696    #[test]
697    fn test_horizontal_line_no_cells() {
698        let mut ras = RasterizerCellsAa::new();
699        // Horizontal line: y1 == y2 in pixel space, same fractional y
700        let y = 10 << POLY_SUBPIXEL_SHIFT;
701        ras.line(0, y, 512, y);
702        ras.sort_cells();
703        // A perfectly horizontal line generates no coverage (dy=0 at subpixel level)
704        // The cells may have zero area/cover, so they might not be stored
705    }
706
707    // ------------------------------------------------------------------
708    // Vertical line tests
709    // ------------------------------------------------------------------
710
711    #[test]
712    fn test_vertical_line_generates_cells() {
713        let mut ras = RasterizerCellsAa::new();
714        let x = 10 << POLY_SUBPIXEL_SHIFT;
715        let y1 = 5 << POLY_SUBPIXEL_SHIFT;
716        let y2 = 15 << POLY_SUBPIXEL_SHIFT;
717        ras.line(x, y1, x, y2);
718        ras.sort_cells();
719        assert!(ras.total_cells() > 0);
720        // Should span from y=5 to y=14 (10 scanlines)
721        assert_eq!(ras.min_y(), 5);
722        assert_eq!(ras.max_y(), 15);
723    }
724
725    #[test]
726    fn test_vertical_line_cover_sum() {
727        let mut ras = RasterizerCellsAa::new();
728        // Vertical line from pixel (10, 5) to (10, 8) — 3 pixel rows
729        let x = (10 << POLY_SUBPIXEL_SHIFT) + 128; // at x=10.5 subpixel
730        let y1 = 5 << POLY_SUBPIXEL_SHIFT;
731        let y2 = 8 << POLY_SUBPIXEL_SHIFT;
732        ras.line(x, y1, x, y2);
733        ras.sort_cells();
734
735        // Total cover across all cells should equal dy in subpixel units
736        let total_cover: i32 = ras.cells.iter().map(|c| c.cover).sum();
737        assert_eq!(total_cover, (y2 - y1) >> 0); // dy in subpixel = 3*256 = 768
738                                                 // Actually, cover is accumulated in subpixel units within each cell row
739                                                 // The total should be 3 * POLY_SUBPIXEL_SCALE = 768
740        assert_eq!(total_cover, 3 * POLY_SUBPIXEL_SCALE as i32);
741    }
742
743    // ------------------------------------------------------------------
744    // Diagonal line tests
745    // ------------------------------------------------------------------
746
747    #[test]
748    fn test_diagonal_line_generates_cells() {
749        let mut ras = RasterizerCellsAa::new();
750        let x1 = 0;
751        let y1 = 0;
752        let x2 = 10 << POLY_SUBPIXEL_SHIFT;
753        let y2 = 10 << POLY_SUBPIXEL_SHIFT;
754        ras.line(x1, y1, x2, y2);
755        ras.sort_cells();
756        assert!(ras.total_cells() > 0);
757        assert_eq!(ras.min_x(), 0);
758        assert_eq!(ras.min_y(), 0);
759        assert_eq!(ras.max_x(), 10);
760        assert_eq!(ras.max_y(), 10);
761    }
762
763    #[test]
764    fn test_diagonal_line_cover_sum() {
765        let mut ras = RasterizerCellsAa::new();
766        let x1 = 0;
767        let y1 = 0;
768        let x2 = 5 << POLY_SUBPIXEL_SHIFT;
769        let y2 = 5 << POLY_SUBPIXEL_SHIFT;
770        ras.line(x1, y1, x2, y2);
771        ras.sort_cells();
772
773        // Total cover should equal total dy in subpixel units
774        let total_cover: i32 = ras.cells.iter().map(|c| c.cover).sum();
775        assert_eq!(total_cover, 5 * POLY_SUBPIXEL_SCALE as i32);
776    }
777
778    // ------------------------------------------------------------------
779    // Sort and query tests
780    // ------------------------------------------------------------------
781
782    #[test]
783    fn test_sort_cells_idempotent() {
784        let mut ras = RasterizerCellsAa::new();
785        let x = 5 << POLY_SUBPIXEL_SHIFT;
786        ras.line(x, 0, x, 3 << POLY_SUBPIXEL_SHIFT);
787        ras.sort_cells();
788        let count1 = ras.total_cells();
789        ras.sort_cells(); // second call should be a no-op
790        assert_eq!(ras.total_cells(), count1);
791    }
792
793    #[test]
794    fn test_sort_empty_rasterizer() {
795        let mut ras = RasterizerCellsAa::new();
796        ras.sort_cells();
797        assert_eq!(ras.total_cells(), 0);
798    }
799
800    #[test]
801    fn test_scanline_query() {
802        let mut ras = RasterizerCellsAa::new();
803        let x = 5 << POLY_SUBPIXEL_SHIFT;
804        ras.line(x, 2 << POLY_SUBPIXEL_SHIFT, x, 5 << POLY_SUBPIXEL_SHIFT);
805        ras.sort_cells();
806
807        // Check that each scanline in range has cells
808        for y in ras.min_y()..=ras.max_y() {
809            let num = ras.scanline_num_cells(y as u32);
810            let indices = ras.scanline_cells(y as u32);
811            assert_eq!(indices.len(), num as usize);
812            // Each cell should be on the correct scanline
813            for &idx in indices {
814                assert_eq!(ras.cell(idx).y, y);
815            }
816        }
817    }
818
819    #[test]
820    fn test_cells_sorted_by_x_within_scanline() {
821        let mut ras = RasterizerCellsAa::new();
822        // Draw a diagonal that crosses multiple X cells on the same scanline
823        ras.line(0, 0, 10 << POLY_SUBPIXEL_SHIFT, 1 << POLY_SUBPIXEL_SHIFT);
824        ras.sort_cells();
825
826        for y in ras.min_y()..=ras.max_y() {
827            let indices = ras.scanline_cells(y as u32);
828            for window in indices.windows(2) {
829                let x_a = ras.cell(window[0]).x;
830                let x_b = ras.cell(window[1]).x;
831                assert!(x_a <= x_b, "Cells not sorted by X: {} > {}", x_a, x_b);
832            }
833        }
834    }
835
836    // ------------------------------------------------------------------
837    // Triangle (closed polygon) test
838    // ------------------------------------------------------------------
839
840    #[test]
841    fn test_triangle_closed_polygon() {
842        let mut ras = RasterizerCellsAa::new();
843        let s = POLY_SUBPIXEL_SCALE as i32;
844        // Triangle: (10,10) -> (20,10) -> (15,20) -> (10,10)
845        ras.line(10 * s, 10 * s, 20 * s, 10 * s); // top edge (horizontal)
846        ras.line(20 * s, 10 * s, 15 * s, 20 * s); // right edge
847        ras.line(15 * s, 20 * s, 10 * s, 10 * s); // left edge
848        ras.sort_cells();
849
850        assert!(ras.total_cells() > 0);
851        assert_eq!(ras.min_y(), 10);
852        assert_eq!(ras.max_y(), 20);
853    }
854
855    // ------------------------------------------------------------------
856    // Large dx subdivision test
857    // ------------------------------------------------------------------
858
859    #[test]
860    fn test_large_dx_subdivision() {
861        let mut ras = RasterizerCellsAa::new();
862        // Very large dx should trigger recursive subdivision
863        let x1 = 0;
864        let y1 = 0;
865        let x2 = 20000 << POLY_SUBPIXEL_SHIFT;
866        let y2 = 1 << POLY_SUBPIXEL_SHIFT;
867        ras.line(x1, y1, x2, y2);
868        ras.sort_cells();
869        // Should not panic, and should produce cells
870        assert!(ras.total_cells() > 0);
871    }
872
873    // ------------------------------------------------------------------
874    // ScanlineHitTest tests
875    // ------------------------------------------------------------------
876
877    #[test]
878    fn test_scanline_hit_test_add_cell() {
879        let mut ht = ScanlineHitTest::new(42);
880        assert!(!ht.hit());
881        ht.add_cell(41, 255);
882        assert!(!ht.hit());
883        ht.add_cell(42, 255);
884        assert!(ht.hit());
885    }
886
887    #[test]
888    fn test_scanline_hit_test_add_span() {
889        let mut ht = ScanlineHitTest::new(15);
890        assert!(!ht.hit());
891        ht.add_span(10, 4, 255); // covers [10, 13]
892        assert!(!ht.hit());
893        ht.add_span(10, 6, 255); // covers [10, 15]
894        assert!(ht.hit());
895    }
896
897    #[test]
898    fn test_scanline_hit_test_num_spans() {
899        let ht = ScanlineHitTest::new(0);
900        assert_eq!(ht.num_spans(), 1);
901    }
902}
agg_rust/rasterizer_cells_aa.rs

agg_rust/
rasterizer_cells_aa.rs
