Expand description
§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
- Unclipped iterators are created using constructors:
AnyOctant::<i8>::new
. - For clipped iterators:
- Define a rectangular clipping region using the
Clip
type. - Construct the desired iterator, e.g.
AnyOctant::<i8>
:- Builder style: using one of the methods on
Clip
, e.g.Clip::<i8>::any_octant
. Should be preferred, as it avoids specifying the numeric type again. - Constructor style:
AnyOctant::<i8>::clip
.
- Builder style: using one of the methods on
- Define a rectangular clipping region using the
§Octant iterators
For an arbitrary line segment, use the AnyOctant
iterator,
which determines the type of the line segment at runtime
and handles it with a specialized iterator.
If you know more about the line segment, you can use an iterator
from the axis-aligned or diagonal families (more below),
or the generic Octant
backed by one of the eight cases of Bresenham’s algorithm:
Octant0
:x
andy
both increase,x
changes faster thany
.Octant1
:x
increases andy
decreases,y
changes faster thanx
.Octant2
:x
decreases andy
increases,x
changes faster thany
.Octant3
:x
andy
both decrease,y
changes faster thanx
.Octant4
:x
andy
both increase,x
changes faster thany
.Octant5
:x
increases andy
decreases,y
changes faster thanx
.Octant6
:x
decreases andy
increases,x
changes faster thany
.Octant7
:x
andy
both decrease,y
changes faster thanx
.
§Axis-aligned iterators
For an arbitrary axis-aligned line segment, use the AnyAxis
iterator,
which determines both the axis-alignment and direction at runtime.
If you know the axis-alignment of the line segment but not the direction,
use the generic Axis
iterator, or one of its type aliases:
If you also know the direction, use the generic SignedAxis
iterator,
or one of its type aliases:
PositiveAxis
/NegativeAxis
: fixed direction, generic orientation.SignedAxis0
/SignedAxis1
: fixed orientation, generic direction.PositiveAxis0
/NegativeAxis0
/PositiveAxis1
/NegativeAxis1
: both fixed.
§Diagonal iterators
For an arbitrary diagonal line segment, use the AnyDiagonal
iterator,
which determines the orientation at runtime.
If you know the orientation, use the generic Diagonal
iterator,
or one of its type aliases:
Diagonal0
:x
andy
both increase.Diagonal1
:x
increases andy
decreases.Diagonal2
:x
decreases andy
increases.Diagonal3
:x
andy
both decrease.
§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.
§Feature flags
octant_64
try_fold
,is_empty
(nightly-only)- Enable optimized
Iterator::try_fold
andExactSizeIterator::is_empty
implementations.
- Enable optimized
§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.
Structs§
- A rectangular region defined by its minimum and maximum corners.
- Iterator over a diagonal line segment in the given quadrant.
- Iterator over a line segment in the given octant, backed by one of the eight cases of Bresenham’s algorithm.
- Iterator over a line segment aligned to the given signed axis.
Enums§
- Iterator over a horizontal or vertical line segment, with the axis-alignment and direction determined at runtime.
- Iterator over any diagonal line segment, with the orientation determined at runtime.
- Iterator over an arbitrary line segment.
- Iterator over a line segment aligned to the given axis, with the direction determined at runtime.
Type Aliases§
- Iterator over a line segment aligned to the horizontal axis, with the direction determined at runtime.
- Iterator over a line segment aligned to the vertical axis, with the direction determined at runtime.
- Iterator over a line segment aligned to the given negative signed axis.
- Iterator over a line segment aligned to the negative horizontal signed axis.
- Iterator over a line segment aligned to the negative vertical signed axis.
- Iterator over a line segment in the octant where
x
andy
both increase, withx
changing faster thany
(gentle slope). - Iterator over a line segment in the octant where
x
andy
both increase, withy
changing faster thanx
(steep slope). - Iterator over a line segment in the octant where
x
increases andy
decreases, withx
changing faster thany
(gentle slope). - Iterator over a line segment in the octant where
x
increases andy
decreases, withy
changing faster thanx
(steep slope). - Iterator over a line segment in the octant where
x
decreases andy
increases, withx
changing faster thany
(gentle slope). - Iterator over a line segment in the octant where
x
decreases andy
increases, withy
changing faster thanx
(steep slope). - Iterator over a line segment in the octant where
x
andy
both decrease, withx
changing faster thany
(gentle slope). - Iterator over a line segment in the octant where
x
andy
both decrease, withy
changing faster thanx
(steep slope). - A generic 2D point.
- Iterator over a line segment aligned to the given positive signed axis.
- Iterator over a line segment aligned to the positive horizontal signed axis.
- Iterator over a line segment aligned to the positive vertical signed axis.
- Iterator over a line segment aligned to the given horizontal signed axis.
- Iterator over a line segment aligned to the given vertical signed axis.