nxsaken / clipline

Efficient rasterization of line segments with pixel-perfect clipping.

clipline

Efficient rasterization of line segments with pixel-perfect clipping.

Overview

• Provides iterators for clipped and unclipped rasterized line segments.
  • Eliminates bounds checking: clipped line segments are guaranteed to be within the region.
  • Guarantees clipped line segments match the unclipped versions of themselves.
• Supports signed and unsigned integer coordinates of most sizes.
  • Uses integer arithmetic only.
  • Prevents overflow and division by zero, forbids clippy::arithmetic_side_effects.
  • Defines the iterators on the entire domains of the underlying numeric types.
• Usable in const contexts and #![no_std] environments.

Usage

Add clipline to Cargo.toml:

[dependencies]
clipline = "0.3.0"

Feature flags

• octant_64
  • Enables Octant and AnyOctant over i64/u64 for all targets, and over isize/usize for 64-bit targets.
  • Use this only if you need the full 64-bit range, as Octant will use u128 and i128 for some calculations.
• try_fold, is_empty (nightly-only)
  • Enable optimized Iterator::try_fold and ExactSizeIterator::is_empty implementations.

Example

use clipline::{AnyOctant, Clip, Diagonal0, Point};

/// Width of the pixel buffer.
const WIDTH: usize = 64;
/// Height of the pixel buffer.
const HEIGHT: usize = 48;

/// Pixel color value.
const RGBA: u32 = 0xFFFFFFFF;

/// A function that operates on a single pixel in a pixel buffer.
///
/// ## Safety
/// `(x, y)` must be inside the `buffer`.
unsafe fn draw(buffer: &mut [u32], (x, y): Point<i8>, rgba: u32) {
    let index = y as usize * WIDTH + x as usize;
    debug_assert!(index < buffer.len());
    *buffer.get_unchecked_mut(index) = rgba;
}

fn main() {
    let mut buffer = [0_u32; WIDTH * HEIGHT];

    // The clipping region is closed/inclusive, thus 1 needs to be subtracted from the size.
    let clip = Clip::<i8>::new((0, 0), (WIDTH as i8 - 1, HEIGHT as i8 - 1)).unwrap();

    // `Clip` has convenience methods for the general iterators.
    clip.any_octant((-128, -100), (100, 80))
        // None if the line segment is completely invisible.
        // You might want to handle that case differently.
        .unwrap()
        // clipped to [(0, 1), ..., (58, 47)]
        .for_each(|xy| {
            // SAFETY: (x, y) has been clipped to the buffer.
            unsafe { draw(&mut buffer, xy, RGBA) }
        });

    // Alternatively, use the iterator constructors.
    AnyOctant::<i8>::clip((12, 0), (87, 23), &clip)
        .into_iter()
        .flatten()
        // clipped to [(12, 0), ..., (63, 16)]
        .for_each(|xy| {
            // SAFETY: (x, y) has been clipped to the buffer.
            unsafe { draw(&mut buffer, xy, RGBA) }
        });

    // Horizontal and vertical line segments.
    clip.axis_0(32, 76, -23)
        .unwrap()
        // clipped to [(63, 32), ..., (0, 32)]
        .for_each(|xy| {
            // SAFETY: (x, y) has been clipped to the buffer.
            unsafe { draw(&mut buffer, xy, RGBA) }
        });

    clip.axis_1(32, -23, 76)
        .unwrap()
        // clipped to [(32, 0), ..., (32, 47)]
        .for_each(|xy| {
            // SAFETY: (x, y) has been clipped to the buffer.
            unsafe { draw(&mut buffer, xy, RGBA) }
        });

    // Unclipped iterators are also available.
    // (-2, -2) -> (12, 12) is covered by Diagonal0, we can construct it directly.
    Diagonal0::<i8>::new((-2, -2), (12, 12))
        .unwrap()
        // Need to check every pixel to avoid going out of bounds.
        .filter(|&xy| clip.point(xy))
        .for_each(|xy| {
            // SAFETY: (x, y) is inside the buffer.
            unsafe { draw(&mut buffer, xy, RGBA) }
        });
}

Limitations

• To support usage in const contexts, types must have an inherent implementation for every supported numeric type instead of relying on a trait. This and Rust's lack of support for function overloading means that the numeric type parameter must always be specified.
• Currently, only half-open line segments can be iterated. This allows ExactSizeIterator to be implemented for all types. Inclusive iterators are tracked in #1.

References

clipline is inspired by the following papers:

• A fast two-dimensional line clipping algorithm via line encoding, Mark S. Sobkow, Paul Pospisil, Yee-Hong Yang, 1987.
• A new approach to parametric line clipping, Michael Dörr, 1990.
• Bresenham's Line Generation Algorithm with Built-in Clipping, Yevgeny P. Kuzmin, 1995.

clipline's Issues

Benchmark 0.3.0

Support all integral numeric types

Implement all clipline types and functions for all primitive integral numeric types.

Forbid `arithmetic_side_effects`

Make all arithmetic operations explicit regarding their side effects, preventing unexpected overflow or panics.

Clipline iterator

• Add a way to traverse the line with an Iterator.
• #4

motivation: parasyte/pixels#381 (comment)

Line inconsistencies

• clipline draws lines slightly differently from line_drawing
• lines drawn from p1 -> p2 are different from lines drawn from p2 -> p1 (line_drawing does the same, but maybe this should be explicit)

line (3, 8) -> (0, 0)
cl: (3, 8), ld: (3, 8)  
cl: (3, 7), ld: (3, 7)  
cl: (2, 6), ld: (3, 6) X
cl: (2, 5), ld: (2, 5)  
cl: (1, 4), ld: (2, 4) X
cl: (1, 3), ld: (2, 3) X
cl: (1, 2), ld: (1, 2)  
cl: (0, 1), ld: (1, 1) X
cl: (0, 0), ld: (0, 0)  

line (0, 0) -> (3, 8)
cl: (0, 0), ld: (0, 0)  
cl: (0, 1), ld: (0, 1)  
cl: (1, 2), ld: (0, 2) X
cl: (1, 3), ld: (1, 3)  
cl: (2, 4), ld: (1, 4) X
cl: (2, 5), ld: (1, 5) X
cl: (2, 6), ld: (2, 6)  
cl: (3, 7), ld: (2, 7) X
cl: (3, 8), ld: (3, 8) 
 
line (0, 0) -> (6, 8)
cl: (0, 0), ld: (0, 0)  
cl: (1, 1), ld: (0, 1) X
cl: (2, 2), ld: (1, 2) X
cl: (2, 3), ld: (2, 3)  
cl: (3, 4), ld: (3, 4)  
cl: (4, 5), ld: (3, 5) X
cl: (5, 6), ld: (4, 6) X
cl: (5, 7), ld: (5, 7)  
cl: (6, 8), ld: (6, 8)  

line (6, 8) -> (0, 0)
cl: (6, 8), ld: (6, 8)  
cl: (5, 7), ld: (6, 7) X
cl: (4, 6), ld: (5, 6) X
cl: (4, 5), ld: (4, 5)  
cl: (3, 4), ld: (3, 4)  
cl: (2, 3), ld: (3, 3) X
cl: (1, 2), ld: (2, 2) X
cl: (1, 1), ld: (1, 1)  
cl: (0, 0), ld: (0, 0)  

Closed/inclusive line segment iterators

Provide a way to construct end-point exclusive and inclusive line segment iterators.

Break down Kuzmin's algorithm into const generic octants

The current implementation of Kuzmin's clipping algorithm performs unnecessary operations, e.g. when standardizing and destandardizing the line segment. This can be improved using const generics.

Implement `DoubleEndedIterator` for `Bresenham`

Make the Bresenham iterator reversible. This requires storing both end_x and end_y coordinates instead of just one of them, as it currently is.

Add run-length slice Bresenham iterator

Add an iterator for the faster (with Iterator::fold) run-length slice version of Bresenham's algorithm.

Mixed-integer clipping operations

Clipping windows are often defined to be ((0, 0), (w - 1, h - 1)), where (w, h) is the unsigned resolution of an image or a screen (generally, a 2D array). Usually, these windows are much smaller than the coordinate space.

Currently, clipping windows use the same type as the coordinate space. It would be nice to have mixed-integer operations where any window type W0 can be used with any coordinate type C0. Something like:

let clipped: AnyOctant<u8> = Clip::<u8>::new((0, 0), (255, 255))?
    .any_octant::<i16>((-1280, -64), (127, 630))?;

This can't be combined with const in this form today, since there is no way to implement the method for each type parameter inherently. However, some other API could be possible.

Benchmarks

Line segment generators

It would be nice to have a line segment generator producing lines with certain properties (lines that satisfy a certain clipping case, for example). This could be very useful for tests and benchmarks.

I tried implementing one, but realized it's essentially a constraint satisfaction problem.