Rust Scanline Triangle Rasterizer Algo for tracing pixels with Rust Iterators.

scanline-triangle-iterator.rs

use std::cmp::{max, min};
use std::mem::swap;

#[derive(Debug)]
pub struct Point {
    pub x: f32,
    pub y: f32,
}
impl Point {
    pub fn new(x: f32, y: f32) -> Point {
        Point { x, y }
    }
}
#[derive(Debug)]
struct Range {
    f: usize,
    t: usize,
    i: usize,
}
impl Range {
    pub fn new(f: usize, t: usize) -> Range {
        Range { f, t, i: f }
    }
}
#[derive(Debug)]
enum Mode {
    TopBegin,
    TopStep,
    BottomBegin,
    BottomStep,
    Done,
}

#[derive(Debug)]
pub struct Triangle {
    mode: Mode,
    p0: Point,
    p1: Point,
    p2: Point,
    ix: Range,
    iy: Range,
    h0: f32,
    h1: f32,
}

impl Triangle {
    
    pub fn new(p0: Point, p1: Point, p2: Point) -> Triangle {
        let mode = Mode::TopBegin;
        let h0 = p2.y - p0.y;
        let h1 = 0_f32;
        let ix = Range::new(0, 0);
        let iy = Range::new(0, 0);
        let mut p0 = p0;
        let mut p1 = p1;
        let mut p2 = p2;
        if p0.y > p1.y {
            swap(&mut p0, &mut p1)
        }
        if p1.y > p2.y {
            swap(&mut p1, &mut p2)
        }
        if p0.y > p1.y {
            swap(&mut p0, &mut p1)
        }
        Triangle {
            mode,
            p0,
            p1,
            p2,
            ix,
            iy,
            h0,
            h1,
        }
    }
    #[inline(always)]
    fn set_iy_top(&mut self) {
        self.iy.f = self.p0.y as usize;
        self.iy.t = self.p1.y as usize;
        self.iy.i = self.iy.f;
        self.h1 = self.p1.y - self.p0.y;
    }
    #[inline(always)]
    fn set_ix_top(&mut self) {
        if self.h1 > 0_f32 {
            let y = self.iy.i as f32;
            let sx = (y - self.p0.y) / self.h0;
            let sy = (y - self.p0.y) / self.h1;
            let m0 = (self.p0.x + (self.p2.x - self.p0.x) * sx) as usize;
            let m1 = (self.p0.x + (self.p1.x - self.p0.x) * sy) as usize;
            self.ix.f = min(m0, m1);
            self.ix.t = max(m0, m1);
            self.ix.i = self.ix.f;
        } else {
            self.ix.f = 0;
            self.ix.t = 0;
            self.ix.i = 0;
        }
    }

    #[inline(always)]
    fn set_iy_bottom(&mut self) {
        self.iy.f = self.p1.y as usize;
        self.iy.t = self.p2.y as usize;
        self.iy.i = self.iy.f;
        self.h1 = self.p2.y - self.p1.y;
    }

    #[inline(always)]
    fn set_ix_bottom(&mut self) {
        if self.h1 > 0_f32 {
            let y = self.iy.i as f32;
            let sx = (y - self.p0.y) / self.h0;
            let sy = (y - self.p1.y) / self.h1;
            let m0 = (self.p0.x + (self.p2.x - self.p0.x) * sx) as usize;
            let m1 = (self.p1.x + (self.p2.x - self.p1.x) * sy) as usize;
            self.ix.f = min(m0, m1);
            self.ix.t = max(m0, m1);
            self.ix.i = self.ix.f;
        } else {
            self.ix.f = 0;
            self.ix.t = 0;
            self.ix.i = 0;
        }
    }
    #[inline(always)]
    fn inc_top(&mut self) -> bool {
        self.ix.i += 1;
        if self.ix.i > self.ix.t {
            self.iy.i += 1;
            self.set_ix_top();
            if self.iy.i > self.iy.t {
                return false;
            }
        }
        return true;
    }
    #[inline(always)]
    fn inc_bottom(&mut self) -> bool {
        self.ix.i += 1;
        if self.ix.i > self.ix.t {
            self.iy.i += 1;
            self.set_ix_bottom();
            if self.iy.i > self.iy.t {
                return false;
            }
        }
        return true;
    }
    #[inline(always)]
    fn top_begin(&mut self) -> Option<(usize, usize)> {
        self.mode = Mode::TopStep;
        self.set_iy_top();
        self.set_ix_top();
        self.step()
    }
    #[inline(always)]
    fn top_step(&mut self) -> Option<(usize, usize)> {
        let x = self.ix.i;
        let y = self.iy.i;
        if self.inc_top() {
            Some((x, y))
        } else {
            self.mode = Mode::BottomBegin;
            self.step()
        }
    }
    #[inline(always)]
    fn bottom_begin(&mut self) -> Option<(usize, usize)> {
        self.mode = Mode::BottomStep;
        self.set_iy_bottom();
        self.set_ix_bottom();
        self.step()
    }
    #[inline(always)]
    fn bottom_step(&mut self) -> Option<(usize, usize)> {
        let x = self.ix.i;
        let y = self.iy.i;
        if self.inc_bottom() {
            Some((x, y))
        } else {
            self.mode = Mode::Done;
            self.step()
        }
    }
    #[inline(always)]
    fn step(&mut self) -> Option<(usize, usize)> {
        match self.mode {
            Mode::TopBegin => self.top_begin(),
            Mode::TopStep => self.top_step(),
            Mode::BottomBegin => self.bottom_begin(),
            Mode::BottomStep => self.bottom_step(),
            Mode::Done => None,
        }
    }
}

impl Iterator for Triangle {
    type Item = (usize, usize);
    fn next(&mut self) -> Option<(usize, usize)> {
        self.step()
    }
}

Thanks for sharing. There seems to be at least one edge case. Here's the data that I hit issues with:

#[test]
fn test_small_triangle() {
let p0 = Point::new(132.33862304687500000000000000000000, 0.08926920592784881591796875000000);
let p1 = Point::new(132.50398254394531250000000000000000, 0.25462353229522705078125000000000);
let p2 = Point::new(132.50398254394531250000000000000000, 0.08926920592784881591796875000000);
let t = Triangle::new(p0, p1, p2);
assert_eq!(t.count(), 0);
}

I get:

assertion left == right failed
left: 132
right: 0

@alecrivers Hi,

It's been a very long time since I looked at this code :) (I can't remember writing this) But I am actually still interested in finding a fast, robust, artifact free, scanline triangle rasterization routine. If the above is helpful in some way, that's awesome, but if you do find a better implementation, please consider linking back here :)

All the best!