Line algorithm benchmark

line.rs

// Bresenham average time: 30.9531ms
// DDA average time: 54.9077ms
// Xiaolin Wu average time: 58.1189ms
// Midpoint average time: 22.2429ms
// Gupta-Sproull average time: 121.9053ms
// Bresenham (flat buffer) avg time: 92.995ms
// DDA (flat buffer) avg time: 127.3775ms
// Xiaolin Wu (flat buffer) avg time: 144.9308ms
// Midpoint (flat buffer) avg time: 77.1491ms
// Gupta-Sproull (flat buffer) avg time: 252.5661ms
use std::time::{Duration, Instant};

// Bresenham's Line Algorithm
fn bresenham_line(x1: isize, y1: isize, x2: isize, y2: isize) -> Vec<(isize, isize)> {
    let mut points = Vec::new();
    let (mut x, mut y) = (x1, y1);
    let dx = (x2 - x1).abs();
    let dy = (y2 - y1).abs();
    let sx = if x1 < x2 { 1 } else { -1 };
    let sy = if y1 < y2 { 1 } else { -1 };
    let mut err = dx - dy;

    loop {
        points.push((x, y));
        if x == x2 && y == y2 { break; }
        let e2 = 2 * err;
        if e2 > -dy {
            err -= dy;
            x += sx;
        }
        if e2 < dx {
            err += dx;
            y += sy;
        }
    }
    points
}

// Digital Differential Analyzer (DDA) Algorithm
fn dda_line(x1: f32, y1: f32, x2: f32, y2: f32) -> Vec<(isize, isize)> {
    let mut points = Vec::new();
    let dx = x2 - x1;
    let dy = y2 - y1;
    let steps = dx.abs().max(dy.abs()) as usize;
    let x_inc = dx / steps as f32;
    let y_inc = dy / steps as f32;
    let (mut x, mut y) = (x1, y1);

    for _ in 0..=steps {
        points.push((x.round() as isize, y.round() as isize));
        x += x_inc;
        y += y_inc;
    }
    points
}

// Xiaolin Wu's Line Algorithm
fn xiaolin_wu_line(x1: f32, y1: f32, x2: f32, y2: f32) -> Vec<((isize, isize), f32)> {
    let mut points = Vec::new();
    // Determine if the line is steep.
    let steep = (y2 - y1).abs() > (x2 - x1).abs();
    // Swap coordinates if steep.
    let (x1, y1, x2, y2) = if steep {
        (y1, x1, y2, x2)
    } else {
        (x1, y1, x2, y2)
    };
    // Ensure drawing from left-to-right.
    let (x1, y1, x2, y2) = if x1 > x2 {
        (x2, y2, x1, y1)
    } else {
        (x1, y1, x2, y2)
    };

    let dx = x2 - x1;
    let dy = y2 - y1;
    let gradient = if dx == 0.0 { 1.0 } else { dy / dx };

    // First endpoint
    let x_end = x1.round();
    let y_end = y1 + gradient * (x_end - x1);
    let x_gap = 1.0 - (x1 + 0.5).fract();
    let x_pixel1 = x_end as isize;
    let y_pixel1 = y_end.floor() as isize;
    if steep {
        points.push(((y_pixel1, x_pixel1), (1.0 - (y_end - y_pixel1 as f32)) * x_gap));
        points.push(((y_pixel1 + 1, x_pixel1), (y_end - y_pixel1 as f32) * x_gap));
    } else {
        points.push(((x_pixel1, y_pixel1), (1.0 - (y_end - y_pixel1 as f32)) * x_gap));
        points.push(((x_pixel1, y_pixel1 + 1), (y_end - y_pixel1 as f32) * x_gap));
    }
    let mut intery = y_end + gradient;

    // Second endpoint
    let x_end = x2.round();
    let y_end = y2 + gradient * (x_end - x2);
    let x_gap = (x2 + 0.5).fract();
    let x_pixel2 = x_end as isize;
    let y_pixel2 = y_end.floor() as isize;
    if steep {
        points.push(((y_pixel2, x_pixel2), (1.0 - (y_end - y_pixel2 as f32)) * x_gap));
        points.push(((y_pixel2 + 1, x_pixel2), (y_end - y_pixel2 as f32) * x_gap));
    } else {
        points.push(((x_pixel2, y_pixel2), (1.0 - (y_end - y_pixel2 as f32)) * x_gap));
        points.push(((x_pixel2, y_pixel2 + 1), (y_end - y_pixel2 as f32) * x_gap));
    }

    // Main loop
    for x in (x_pixel1 + 1)..x_pixel2 {
        if steep {
            let y_pixel = intery.floor() as isize;
            points.push(((y_pixel, x), 1.0 - (intery - y_pixel as f32)));
            points.push(((y_pixel + 1, x), intery - y_pixel as f32));
        } else {
            let y_pixel = intery.floor() as isize;
            points.push(((x, y_pixel), 1.0 - (intery - y_pixel as f32)));
            points.push(((x, y_pixel + 1), intery - y_pixel as f32));
        }
        intery += gradient;
    }
    points
}

// Midpoint Line Algorithm (simple integer version)
fn midpoint_line(x1: isize, y1: isize, x2: isize, y2: isize) -> Vec<(isize, isize)> {
    let mut points = Vec::new();
    let (mut x, mut y) = (x1, y1);
    let dx = x2 - x1;
    let dy = y2 - y1;
    let mut d = dy - (dx / 2);
    points.push((x, y));

    while x < x2 {
        x += 1;
        if d < 0 {
            d += dy;
        } else {
            y += 1;
            d += dy - dx;
        }
        points.push((x, y));
    }
    points
}

// Gupta-Sproull Algorithm (simplified version)
// This version uses a quadratic falloff for weights to mimic anti-aliasing.
fn gupta_sproull_line(x1: isize, y1: isize, x2: isize, y2: isize) -> Vec<((isize, isize), f32)> {
    let mut points = Vec::new();
    let steep = (y2 - y1).abs() > (x2 - x1).abs();
    let (x1, y1, x2, y2) = if steep { (y1, x1, y2, x2) } else { (x1, y1, x2, y2) };
    let (x1, y1, x2, y2) = if x1 > x2 { (x2, y2, x1, y1) } else { (x1, y1, x2, y2) };

    let dx = (x2 - x1) as f32;
    let dy = (y2 - y1) as f32;
    let gradient = if dx == 0.0 { 1.0 } else { dy / dx };

    for x in x1..=x2 {
        let y = y1 as f32 + gradient * ((x - x1) as f32);
        let y_floor = y.floor();
        let t = y - y_floor;
        // Quadratic weighting for anti-aliasing (a simplified approximation)
        let w_lower = (1.0 - t).powi(2);
        let w_upper = t.powi(2);
        if steep {
            points.push(((y_floor as isize, x), w_lower));
            points.push((((y_floor as isize) + 1, x), w_upper));
        } else {
            points.push(((x, y_floor as isize), w_lower));
            points.push(((x, (y_floor as isize) + 1), w_upper));
        }
    }
    points
}

// Bresenham's Line Algorithm on flat buffer.
fn bresenham_line_flat(
    buffer: &mut [f32],
    width: usize,
    height: usize,
    x1: isize,
    y1: isize,
    x2: isize,
    y2: isize,
    value: f32,
) {
    let mut x = x1;
    let mut y = y1;
    let dx = (x2 - x1).abs();
    let dy = (y2 - y1).abs();
    let sx = if x1 < x2 { 1 } else { -1 };
    let sy = if y1 < y2 { 1 } else { -1 };
    let mut err = dx - dy;
    loop {
        if x >= 0 && x < width as isize && y >= 0 && y < height as isize {
            let idx = y as usize * width + x as usize;
            buffer[idx] = value;
        }
        if x == x2 && y == y2 {
            break;
        }
        let e2 = 2 * err;
        if e2 > -dy {
            err -= dy;
            x += sx;
        }
        if e2 < dx {
            err += dx;
            y += sy;
        }
    }
}

// Digital Differential Analyzer (DDA) Algorithm on flat buffer.
fn dda_line_flat(
    buffer: &mut [f32],
    width: usize,
    height: usize,
    x1: f32,
    y1: f32,
    x2: f32,
    y2: f32,
    value: f32,
) {
    let dx = x2 - x1;
    let dy = y2 - y1;
    let steps = dx.abs().max(dy.abs()) as usize;
    let x_inc = dx / steps as f32;
    let y_inc = dy / steps as f32;
    let (mut x, mut y) = (x1, y1);
    for _ in 0..=steps {
        let ix = x.round() as isize;
        let iy = y.round() as isize;
        if ix >= 0 && ix < width as isize && iy >= 0 && iy < height as isize {
            let idx = iy as usize * width + ix as usize;
            buffer[idx] = value;
        }
        x += x_inc;
        y += y_inc;
    }
}

// Xiaolin Wu's Line Algorithm on flat buffer (anti-aliased).
fn xiaolin_wu_line_flat(
    buffer: &mut [f32],
    width: usize,
    height: usize,
    x1: f32,
    y1: f32,
    x2: f32,
    y2: f32,
    value: f32,
) {
    let steep = (y2 - y1).abs() > (x2 - x1).abs();
    let (mut x1, mut y1, mut x2, mut y2) = if steep {
        (y1, x1, y2, x2)
    } else {
        (x1, y1, x2, y2)
    };
    if x1 > x2 {
        std::mem::swap(&mut x1, &mut x2);
        std::mem::swap(&mut y1, &mut y2);
    }
    let dx = x2 - x1;
    let dy = y2 - y1;
    let gradient = if dx == 0.0 { 1.0 } else { dy / dx };

    // First endpoint.
    let x_end = x1.round();
    let y_end = y1 + gradient * (x_end - x1);
    let x_gap = 1.0 - (x1 + 0.5).fract();
    let x_pixel = x_end as isize;
    let y_pixel = y_end.floor() as isize;
    if steep {
        if x_pixel >= 0 && x_pixel < height as isize && y_pixel >= 0 && y_pixel < width as isize {
            let idx = x_pixel as usize * width + y_pixel as usize;
            buffer[idx] = value * (1.0 - (y_end - y_pixel as f32)) * x_gap;
        }
        if x_pixel + 1 >= 0 && x_pixel + 1 < height as isize && y_pixel >= 0 && y_pixel < width as isize {
            let idx = (x_pixel + 1) as usize * width + y_pixel as usize;
            buffer[idx] = value * (y_end - y_pixel as f32) * x_gap;
        }
    } else {
        if x_pixel >= 0 && x_pixel < width as isize && y_pixel >= 0 && y_pixel < height as isize {
            let idx = y_pixel as usize * width + x_pixel as usize;
            buffer[idx] = value * (1.0 - (y_end - y_pixel as f32)) * x_gap;
        }
        if x_pixel >= 0 && x_pixel < width as isize && y_pixel + 1 >= 0 && y_pixel + 1 < height as isize {
            let idx = (y_pixel + 1) as usize * width + x_pixel as usize;
            buffer[idx] = value * (y_end - y_pixel as f32) * x_gap;
        }
    }
    let mut intery = y_end + gradient;

    // Second endpoint.
    let x_end = x2.round();
    let y_end = y2 + gradient * (x_end - x2);
    let x_gap = (x2 + 0.5).fract();
    let x_pixel2 = x_end as isize;
    let y_pixel2 = y_end.floor() as isize;
    if steep {
        if x_pixel2 >= 0 && x_pixel2 < height as isize && y_pixel2 >= 0 && y_pixel2 < width as isize {
            let idx = x_pixel2 as usize * width + y_pixel2 as usize;
            buffer[idx] = value * (1.0 - (y_end - y_pixel2 as f32)) * x_gap;
        }
        if x_pixel2 + 1 >= 0 && x_pixel2 + 1 < height as isize && y_pixel2 >= 0 && y_pixel2 < width as isize {
            let idx = (x_pixel2 + 1) as usize * width + y_pixel2 as usize;
            buffer[idx] = value * (y_end - y_pixel2 as f32) * x_gap;
        }
    } else {
        if x_pixel2 >= 0 && x_pixel2 < width as isize && y_pixel2 >= 0 && y_pixel2 < height as isize {
            let idx = y_pixel2 as usize * width + x_pixel2 as usize;
            buffer[idx] = value * (1.0 - (y_end - y_pixel2 as f32)) * x_gap;
        }
        if x_pixel2 >= 0 && x_pixel2 < width as isize && y_pixel2 + 1 >= 0 && y_pixel2 + 1 < height as isize {
            let idx = (y_pixel2 + 1) as usize * width + x_pixel2 as usize;
            buffer[idx] = value * (y_end - y_pixel2 as f32) * x_gap;
        }
    }

    // Main loop.
    for x in (x1.round() as isize + 1)..(x2.round() as isize) {
        let y = intery;
        let y_floor = y.floor() as isize;
        let t = y - y.floor();
        if steep {
            if x >= 0 && x < height as isize && y_floor >= 0 && y_floor < width as isize {
                let idx = x as usize * width + y_floor as usize;
                buffer[idx] = value * (1.0 - t);
            }
            if x >= 0 && x < height as isize && y_floor + 1 >= 0 && y_floor + 1 < width as isize {
                let idx = x as usize * width + (y_floor + 1) as usize;
                buffer[idx] = value * t;
            }
        } else {
            if x >= 0 && x < width as isize && y_floor >= 0 && y_floor < height as isize {
                let idx = y_floor as usize * width + x as usize;
                buffer[idx] = value * (1.0 - t);
            }
            if x >= 0 && x < width as isize && y_floor + 1 >= 0 && y_floor + 1 < height as isize {
                let idx = (y_floor + 1) as usize * width + x as usize;
                buffer[idx] = value * t;
            }
        }
        intery += gradient;
    }
}

// Midpoint Line Algorithm on flat buffer.
fn midpoint_line_flat(
    buffer: &mut [f32],
    width: usize,
    height: usize,
    x1: isize,
    y1: isize,
    x2: isize,
    y2: isize,
    value: f32,
) {
    let mut x = x1;
    let mut y = y1;
    let dx = x2 - x1;
    let dy = y2 - y1;
    let mut d = dy - (dx / 2);
    if x >= 0 && x < width as isize && y >= 0 && y < height as isize {
        let idx = y as usize * width + x as usize;
        buffer[idx] = value;
    }
    while x < x2 {
        x += 1;
        if d < 0 {
            d += dy;
        } else {
            y += 1;
            d += dy - dx;
        }
        if x >= 0 && x < width as isize && y >= 0 && y < height as isize {
            let idx = y as usize * width + x as usize;
            buffer[idx] = value;
        }
    }
}

// Gupta-Sproull Algorithm on flat buffer (simplified anti-aliased version).
fn gupta_sproull_line_flat(
    buffer: &mut [f32],
    width: usize,
    height: usize,
    x1: isize,
    y1: isize,
    x2: isize,
    y2: isize,
    value: f32,
) {
    let steep = (y2 - y1).abs() > (x2 - x1).abs();
    let (x1, y1, x2, y2) = if steep {
        (y1, x1, y2, x2)
    } else {
        (x1, y1, x2, y2)
    };
    let (x1, y1, x2, y2) = if x1 > x2 {
        (x2, y2, x1, y1)
    } else {
        (x1, y1, x2, y2)
    };

    let dx = (x2 - x1) as f32;
    let dy = (y2 - y1) as f32;
    let gradient = if dx == 0.0 { 1.0 } else { dy / dx };

    for x in x1..=x2 {
        let y = y1 as f32 + gradient * ((x - x1) as f32);
        let y_floor = y.floor() as isize;
        let t = y - y.floor();
        let w_lower = (1.0 - t).powi(2);
        let w_upper = t.powi(2);
        if steep {
            if x >= 0 && x < height as isize && y_floor >= 0 && y_floor < width as isize {
                let idx = x as usize * width + y_floor as usize;
                buffer[idx] = value * w_lower;
            }
            if x >= 0 && x < height as isize && (y_floor + 1) >= 0 && (y_floor + 1) < width as isize {
                let idx = x as usize * width + (y_floor + 1) as usize;
                buffer[idx] = value * w_upper;
            }
        } else {
            if x >= 0 && x < width as isize && y_floor >= 0 && y_floor < height as isize {
                let idx = y_floor as usize * width + x as usize;
                buffer[idx] = value * w_lower;
            }
            if x >= 0 && x < width as isize && (y_floor + 1) >= 0 && (y_floor + 1) < height as isize {
                let idx = (y_floor + 1) as usize * width + x as usize;
                buffer[idx] = value * w_upper;
            }
        }
    }
}

// Benchmark helper: runs a closure `iterations` times and returns average time (ns).
fn benchmark<F>(func: F, iterations: usize) -> Duration
where
    F: Fn() -> (),
{
    let start = Instant::now();
    for _ in 0..iterations {
        func();
    }
    start.elapsed()
}


fn bench_vec() {
    let iterations = 10_000;
    // Define endpoints for integer algorithms.
    let (x1, y1, x2, y2) = (0, 0, 100, 100);
    // And for floating-point algorithms.
    let (fx1, fy1, fx2, fy2) = (0.0, 0.0, 100.0, 100.0);

    let time_bresenham = benchmark(|| {
        let _ = bresenham_line(x1, y1, x2, y2);
    }, iterations);
    println!("Bresenham average time: {:?}", time_bresenham);

    let time_dda = benchmark(|| {
        let _ = dda_line(fx1, fy1, fx2, fy2);
    }, iterations);
    println!("DDA average time: {:?}", time_dda);

    let time_wu = benchmark(|| {
        let _ = xiaolin_wu_line(fx1, fy1, fx2, fy2);
    }, iterations);
    println!("Xiaolin Wu average time: {:?}", time_wu);

    let time_midpoint = benchmark(|| {
        let _ = midpoint_line(x1, y1, x2, y2);
    }, iterations);
    println!("Midpoint average time: {:?}", time_midpoint);

    let time_gupta = benchmark(|| {
        let _ = gupta_sproull_line(x1, y1, x2, y2);
    }, iterations);
    println!("Gupta-Sproull average time: {:?}", time_gupta);
}

fn bench_flat() {
    let iterations = 10_000;
    let width = 200;
    let height = 200;
    let buffer_size = width * height;
    // Endpoints for integer algorithms.
    let (x1, y1, x2, y2) = (10, 10, 190, 190);
    // Endpoints for floating-point algorithms.
    let (fx1, fy1, fx2, fy2) = (10.0, 10.0, 190.0, 190.0);
    let value = 1.0;

    // Benchmark Bresenham.
    let time_bresenham = benchmark(|| {
        let mut buffer = vec![0.0f32; buffer_size];
        bresenham_line_flat(&mut buffer, width, height, x1, y1, x2, y2, value);
    }, iterations);
    println!("Bresenham (flat buffer) avg time: {:?}", time_bresenham);

    // Benchmark DDA.
    let time_dda = benchmark(|| {
        let mut buffer = vec![0.0f32; buffer_size];
        dda_line_flat(&mut buffer, width, height, fx1, fy1, fx2, fy2, value);
    }, iterations);
    println!("DDA (flat buffer) avg time: {:?}", time_dda);

    // Benchmark Xiaolin Wu.
    let time_wu = benchmark(|| {
        let mut buffer = vec![0.0f32; buffer_size];
        xiaolin_wu_line_flat(&mut buffer, width, height, fx1, fy1, fx2, fy2, value);
    }, iterations);
    println!("Xiaolin Wu (flat buffer) avg time: {:?}", time_wu);

    // Benchmark Midpoint.
    let time_midpoint = benchmark(|| {
        let mut buffer = vec![0.0f32; buffer_size];
        midpoint_line_flat(&mut buffer, width, height, x1, y1, x2, y2, value);
    }, iterations);
    println!("Midpoint (flat buffer) avg time: {:?}", time_midpoint);

    // Benchmark Gupta-Sproull.
    let time_gupta = benchmark(|| {
        let mut buffer = vec![0.0f32; buffer_size];
        gupta_sproull_line_flat(&mut buffer, width, height, x1, y1, x2, y2, value);
    }, iterations);
    println!("Gupta-Sproull (flat buffer) avg time: {:?}", time_gupta);
}

fn main() {
    bench_vec();
    bench_flat()
}