A Tale of Two Bresenhams
...or How To Draw Thick Bresenham Lines in Rust
I decided last post to construct rivers basically using a bunch of circles. One reason for that is because it would make it easy to have the middle of my rivers be deeper than the edges. Another reason is because properly drawing thick lines has been frustrating me a bit lately and I was eager to just move on. They were both pretty bad reasons. Bad because the zillion circle idea turned out to be really slow (partly because I kept a ring buffer of previous tiles so I could avoid where my circles overlapped), and also bad because where's the fun in being lazy and not figuring something out?
I tried lots of algorithms for thick lines. Lots. Some of them just didn't work, possibly my fault. Some of them were just plain wrong and the line ends weren't perpendicular. I suck at math, so it took me a bit to wrap my head around the problem. At first, I'm thinking to myself: A thick line is just a rectangle...all I need are a couple perpendicular lines to set the corners to, and fill in all the pixels one line at a time. How hard can it be?
Every friggin' site on the internet says that to draw a perpendicular line, just invert the slope. Problem solved! (I mean, except for zero and infinity, but that's easy because at that point we're dealing with vertical or horizontal lines, and even I can add to X or add to Y to get a perpendicular point). But alas, the internet lies. Just blindly inverting a slope will give you a perpendicular slope only some of the time.
I finally found a promising link here: https://github.com/ArminJo/Arduino-BlueDisplay/blob/master/src/LocalGUI/ThickLine.hpp. At first I recoiled in horror at the camelCase variable names, the same exact way I hated Rust's snake_case names at first. Rust got this one right though. I ended up making 3 different versions, all tailored for my specific use, which is why I'm not making (or contributing to) a crate.
get_thick_line_unchecked() will make a proper fat line, even if it overlaps canvas boundaries (which are still only square). I call it unchecked because if any parts of the line go out of bounds, there will be duplicate points. get_thick_line() will also make a proper fat line, account for out of bounds, but also remove duplicates. Option #3 is the scary one, and I'll write about it in a bit. Both of the unchecked versions will produce perfect lines with zero duplicates if no parts of the line rectangle go out of bounds. Here's the code for the first version:
#[inline]
// ported from https://github.com/ArminJo/Arduino-BlueDisplay/blob/master/src/LocalGUI/ThickLine.hpp
pub fn get_thick_line_unchecked(
from: (usize, usize),
to: (usize, usize),
line_width: usize,
thick_mode: ThicknessMode,
map_width: usize,
) -> Vec<(usize, usize)> {
let mut line: Vec<(usize, usize)> = vec![];
let mut x1 = from.0 as isize;
let mut x2 = to.0 as isize;
let mut y1 = from.1 as isize;
let mut y2 = to.1 as isize;
let mut dx: isize;
let mut dy: isize;
let dx2: isize;
let dy2: isize;
let mut err: isize;
let mut step_x: isize;
let mut step_y: isize;
let max_width = (map_width - 1) as isize;
if x1 > max_width {
x1 = max_width;
}
if x2 > max_width {
x2 = max_width;
}
if y1 > max_width {
y1 = max_width;
}
if y2 > max_width {
y2 = max_width;
}
if line_width <= 1 {
return get_line_overlap((x1, y1), (x2, y2), LINE_OVERLAP_NONE, map_width);
}
dy = x2 - x1;
dx = y2 - y1;
let mut swap = true;
if dx < 0 {
dx = -dx;
step_x = -1;
swap = !swap;
} else {
step_x = 1;
}
if dy < 0 {
dy = -dy;
step_y = -1;
swap = !swap;
} else {
step_y = 1;
}
dx2 = dx << 1;
dy2 = dy << 1;
let mut overlap: usize;
let mut draw_start_adjust_count = line_width / 2;
if thick_mode == ThicknessMode::LineThicknessDrawCounterclockwise {
draw_start_adjust_count = line_width - 1;
} else if thick_mode == ThicknessMode::LineThicknessDrawClockwise {
draw_start_adjust_count = 0;
}
if dx >= dy {
if swap {
draw_start_adjust_count = (line_width - 1) - draw_start_adjust_count;
step_y = -step_y;
} else {
step_x = -step_x;
}
err = dy2 - dx;
for _ in (0..draw_start_adjust_count).rev() {
x1 -= step_x;
x2 -= step_x;
if err >= 0 {
y1 -= step_y;
y2 -= step_y;
err -= dx2;
}
err += dy2;
}
line.append(&mut get_line_overlap(
(x1, y1),
(x2, y2),
LINE_OVERLAP_NONE,
map_width,
));
err = dy2 - dx;
for _ in (1..line_width).rev() {
x1 += step_x;
x2 += step_x;
overlap = LINE_OVERLAP_NONE;
if err >= 0 {
y1 += step_y;
y2 += step_y;
err -= dx2;
overlap = LINE_OVERLAP_MAJOR;
}
err += dy2;
line.append(&mut get_line_overlap(
(x1, y1),
(x2, y2),
overlap,
map_width,
))
}
} else {
if swap {
step_x = -step_x;
} else {
draw_start_adjust_count = (line_width - 1) - draw_start_adjust_count;
step_y = -step_y;
}
err = dx2 - dy;
for _ in (0..draw_start_adjust_count).rev() {
y1 -= step_y;
y2 -= step_y;
if err >= 0 {
x1 -= step_x;
x2 -= step_x;
err -= dy2;
}
err += dx2;
}
line.append(&mut get_line_overlap(
(x1, y1),
(x2, y2),
LINE_OVERLAP_NONE,
map_width,
));
err = dx2 - dy;
for _ in (1..line_width).rev() {
y1 += step_y;
y2 += step_y;
overlap = LINE_OVERLAP_NONE;
if err >= 0 {
x1 += step_x;
x2 += step_x;
err -= dy2;
overlap = LINE_OVERLAP_MAJOR;
}
err += dx2;
line.append(&mut get_line_overlap(
(x1, y1),
(x2, y2),
overlap,
map_width,
));
}
}
// these are 2.5x slower than using get_thick_line() to remove dupes:
//line.sort();
//line.dedup();
line
}
and....
const LINE_OVERLAP_NONE: usize = 0; // No line overlap, like in standard Bresenham
const LINE_OVERLAP_MAJOR: usize = 0x01; // Overlap - first go major then minor direction. Pixel is drawn as extension after actual line
const LINE_OVERLAP_MINOR: usize = 0x02; // Overlap - first go minor then major direction. Pixel is drawn as extension before next line
const LINE_OVERLAP_BOTH: usize = 0x03; // Overlap - both
#[derive(PartialEq)]
pub enum ThicknessMode {
LineThicknessMiddle = 0,
LineThicknessDrawClockwise = 1,
LineThicknessDrawCounterclockwise = 2,
}
#[inline]
// ported from https://github.com/ArminJo/Arduino-BlueDisplay/blob/master/src/LocalGUI/ThickLine.hpp
fn get_line_overlap(
from: (isize, isize),
to: (isize, isize),
overlap: usize,
map_width: usize,
) -> Vec<(usize, usize)> {
let mut x1 = from.0;
let x2 = to.0;
let mut y1 = from.1;
let y2 = to.1;
let mut line: Vec<(usize, usize)> = vec![];
let mut dx: isize;
let mut dy: isize;
let dx2: isize;
let dy2: isize;
let mut err: isize;
let step_x: isize;
let step_y: isize;
let max_width = (map_width - 1) as isize;
dx = x2 - x1;
dy = y2 - y1;
if dx < 0 {
dx = -dx;
step_x = -1;
} else {
step_x = 1;
}
if dy < 0 {
dy = -dy;
step_y = -1;
} else {
step_y = 1;
}
dx2 = dx << 1;
dy2 = dy << 1;
line.push((
x1.clamp(0, max_width) as usize,
y1.clamp(0, max_width) as usize,
));
if dx > dy {
err = dy2 - dx;
while x1 != x2 {
x1 += step_x;
if err >= 0 {
if overlap & LINE_OVERLAP_MAJOR != 0 {
line.push((
x1.clamp(0, max_width) as usize,
y1.clamp(0, max_width) as usize,
));
}
y1 += step_y;
if overlap & LINE_OVERLAP_MINOR != 0 {
line.push((
(x1 - step_x).clamp(0, max_width) as usize,
y1.clamp(0, max_width) as usize,
));
}
err -= dx2;
}
err += dy2;
line.push((
x1.clamp(0, max_width) as usize,
y1.clamp(0, max_width) as usize,
));
}
} else {
err = dx2 - dy;
while y1 != y2 {
y1 += step_y;
if err >= 0 {
if overlap & LINE_OVERLAP_MAJOR != 0 {
line.push((
x1.clamp(0, max_width) as usize,
y1.clamp(0, max_width) as usize,
));
}
x1 += step_x;
if overlap & LINE_OVERLAP_MINOR != 0 {
line.push((
x1.clamp(0, max_width) as usize,
(y1 - step_y).clamp(0, max_width) as usize,
));
}
err -= dy2;
}
err += dx2;
line.push((
x1.clamp(0, max_width) as usize,
y1.clamp(0, max_width) as usize,
));
}
}
line
}
Okay, that's the first version. It works, but possibly includes duplicate points. If you're actually trying to rasterize a rectangle pixel by pixel in 2023, then dupes might not matter.
Here's the guaranteed dupe free version, with an option for an unsafe unchecked version:
#[inline]
// ported from https://github.com/ArminJo/Arduino-BlueDisplay/blob/master/src/LocalGUI/ThickLine.hpp
// i strongly discourage use of the unsafe_unchecked version unless you're 100% sure of what you're doing
pub fn get_thick_line(
from: (usize, usize),
to: (usize, usize),
line_width: usize,
thick_mode: ThicknessMode,
map_width: usize,
unsafe_unchecked: bool,
) -> Vec<(usize, usize)> {
let mut line: Vec<(isize, isize)> = vec![];
let mut x1 = from.0 as isize;
let mut x2 = to.0 as isize;
let mut y1 = from.1 as isize;
let mut y2 = to.1 as isize;
let mut dx: isize;
let mut dy: isize;
let dx2: isize;
let dy2: isize;
let mut err: isize;
let mut step_x: isize;
let mut step_y: isize;
let max_width = (map_width - 1) as isize;
if x1 > max_width {
x1 = max_width;
}
if x2 > max_width {
x2 = max_width;
}
if y1 > max_width {
y1 = max_width;
}
if y2 > max_width {
y2 = max_width;
}
fn convert(input: &Vec<(isize, isize)>, max_width: isize) -> Vec<(usize, usize)> {
let mut retval: Vec<(usize, usize)> = Vec::with_capacity(input.len());
for x in 0..input.len() {
if input[x].0 >= 0
&& input[x].0 <= max_width
&& input[x].1 >= 0
&& input[x].1 <= max_width
{
retval.push((input[x].0 as usize, input[x].1 as usize));
}
}
retval
}
unsafe fn fast_convert(input: Vec<(isize, isize)>) -> Vec<(usize, usize)> {
let mut v = std::mem::ManuallyDrop::new(input);
Vec::from_raw_parts(v.as_mut_ptr() as *mut (usize, usize), v.len(), v.capacity())
}
if line_width <= 1 {
line = get_line_overlap2((x1, y1), (x2, y2), LINE_OVERLAP_NONE);
return convert(&line, max_width);
}
dy = x2 - x1;
dx = y2 - y1;
let mut swap = true;
if dx < 0 {
dx = -dx;
step_x = -1;
swap = !swap;
} else {
step_x = 1;
}
if dy < 0 {
dy = -dy;
step_y = -1;
swap = !swap;
} else {
step_y = 1;
}
dx2 = dx << 1;
dy2 = dy << 1;
let mut overlap: usize;
let mut draw_start_adjust_count = line_width / 2;
if thick_mode == ThicknessMode::LineThicknessDrawCounterclockwise {
draw_start_adjust_count = line_width - 1;
} else if thick_mode == ThicknessMode::LineThicknessDrawClockwise {
draw_start_adjust_count = 0;
}
if dx >= dy {
if swap {
draw_start_adjust_count = (line_width - 1) - draw_start_adjust_count;
step_y = -step_y;
} else {
step_x = -step_x;
}
err = dy2 - dx;
for _ in (0..draw_start_adjust_count).rev() {
x1 -= step_x;
x2 -= step_x;
if err >= 0 {
y1 -= step_y;
y2 -= step_y;
err -= dx2;
}
err += dy2;
}
line.append(&mut get_line_overlap2(
(x1, y1),
(x2, y2),
LINE_OVERLAP_NONE,
));
err = dy2 - dx;
for _ in (1..line_width).rev() {
x1 += step_x;
x2 += step_x;
overlap = LINE_OVERLAP_NONE;
if err >= 0 {
y1 += step_y;
y2 += step_y;
err -= dx2;
overlap = LINE_OVERLAP_MAJOR;
}
err += dy2;
line.append(&mut get_line_overlap2((x1, y1), (x2, y2), overlap));
}
} else {
if swap {
step_x = -step_x;
} else {
draw_start_adjust_count = (line_width - 1) - draw_start_adjust_count;
step_y = -step_y;
}
err = dx2 - dy;
for _ in (0..draw_start_adjust_count).rev() {
y1 -= step_y;
y2 -= step_y;
if err >= 0 {
x1 -= step_x;
x2 -= step_x;
err -= dy2;
}
err += dx2;
}
line.append(&mut get_line_overlap2(
(x1, y1),
(x2, y2),
LINE_OVERLAP_NONE,
));
err = dx2 - dy;
for _ in (1..line_width).rev() {
y1 += step_y;
y2 += step_y;
overlap = LINE_OVERLAP_NONE;
if err >= 0 {
x1 += step_x;
x2 += step_x;
err -= dy2;
overlap = LINE_OVERLAP_MAJOR;
}
err += dx2;
line.append(&mut get_line_overlap2((x1, y1), (x2, y2), overlap));
}
}
if unsafe_unchecked {
unsafe { fast_convert(line) }
} else {
convert(&line, max_width)
}
}
and...
#[inline]
// ported from https://github.com/ArminJo/Arduino-BlueDisplay/blob/master/src/LocalGUI/ThickLine.hpp
fn get_line_overlap2(
from: (isize, isize),
to: (isize, isize),
overlap: usize,
) -> Vec<(isize, isize)> {
let mut x1 = from.0;
let x2 = to.0;
let mut y1 = from.1;
let y2 = to.1;
let mut line: Vec<(isize, isize)> = vec![];
let mut dx: isize;
let mut dy: isize;
let dx2: isize;
let dy2: isize;
let mut err: isize;
let step_x: isize;
let step_y: isize;
dx = x2 - x1;
dy = y2 - y1;
if dx < 0 {
dx = -dx;
step_x = -1;
} else {
step_x = 1;
}
if dy < 0 {
dy = -dy;
step_y = -1;
} else {
step_y = 1;
}
dx2 = dx << 1;
dy2 = dy << 1;
line.push((x1, y1));
if dx > dy {
err = dy2 - dx;
while x1 != x2 {
x1 += step_x;
if err >= 0 {
if overlap & LINE_OVERLAP_MAJOR != 0 {
line.push((x1, y1));
}
y1 += step_y;
if overlap & LINE_OVERLAP_MINOR != 0 {
line.push((x1 - step_x, y1));
}
err -= dx2;
}
err += dy2;
line.push((x1, y1));
}
} else {
err = dx2 - dy;
while y1 != y2 {
y1 += step_y;
if err >= 0 {
if overlap & LINE_OVERLAP_MAJOR != 0 {
line.push((x1, y1));
}
x1 += step_x;
if overlap & LINE_OVERLAP_MINOR != 0 {
line.push((x1, y1 - step_y));
}
err -= dy2;
}
err += dx2;
line.push((x1, y1));
}
}
line
}
Above I talked about scary Option #3. That's calling get_thick_line() with unsafe_unchecked = true. The unsafe version just directly casts an (isize, isize) vec into a (usize, usize) vec. If you are 100% damn sure that the entirety of your thick line lies within the canvas boundaries, you'll get a thick line with no duplicates and no crashing.
If, however, you cast negative signed coordinates into unsigned ones, and actually attempt to use them without checking them...Bad Things Will Happen™ (and if you have overflow checks enabled, the app will crash before you can even attempt to crash the app in a different way)
Here are some example images produced using the code, showing proper handling of out of bounds coordinates:
I'll have a crude little benchmark further below. First though, a little tidbit about a problem I had testing the code originally. Thick lines in the middle of the canvas were like the ones above, perfectly fine. But as parts of the line got further out of bounds, the line would take on a trapezoid shape, or sometimes sort of "bounce" off the boundary of the canvas.
Here's an example of the trapezoid anomaly (notice the starting points in yellow are off-center as well):
I eventually tracked it down to the beginning of the drawLineOverlap function here. So I snipped out my version of this code:
if (aXStart >= LOCAL_DISPLAY_WIDTH) {
aXStart = LOCAL_DISPLAY_WIDTH - 1;
}
if (aXEnd >= LOCAL_DISPLAY_WIDTH) {
aXEnd = LOCAL_DISPLAY_WIDTH - 1;
}
if (aYStart >= LOCAL_DISPLAY_HEIGHT) {
aYStart = LOCAL_DISPLAY_HEIGHT - 1;
}
if (aYEnd >= LOCAL_DISPLAY_HEIGHT) {
aYEnd = LOCAL_DISPLAY_HEIGHT - 1;
}
...and the issue disappeared. I'm not sure if it's actually a bug in the implementation I copied, or if it was my fault in how I ported the code. All I know is that it's fixed now in my code =)
Crude benchmark code:
fn test_fat_lines(tests: usize, map_width: usize, line_width: usize) {
println!("----------------------- [ test begin ] -----------------------");
let mut rng = nanorand::tls_rng();
let mut points1: Vec<(usize, usize)> = vec![];
let mut points2: Vec<(usize, usize)> = vec![];
let mut line: Vec<(usize, usize)>;
let mut len: usize = 0;
for _ in 0..tests {
points1.push((rng.generate_range(0..map_width), rng.generate_range(0..map_width)));
points2.push((rng.generate_range(0..map_width), rng.generate_range(0..map_width)));
}
let start = Instant::now();
for x in 0..tests {
line = utils::get_thick_line_unchecked(
points1[x],
points2[x],
line_width,
utils::ThicknessMode::LineThicknessMiddle,
map_width,
);
len += line.len();
}
let duration = start.elapsed();
println!(
"{} iterations for get_thick_line_unchecked() took: {:?}",
tests, duration
);
println!(
"total pixels = {}, line width = {}, canvas size = {}x{}\n",
len, line_width, map_width, map_width
);
len = 0;
let start = Instant::now();
for x in 0..tests {
line = utils::get_thick_line(
points1[x],
points2[x],
line_width,
utils::ThicknessMode::LineThicknessMiddle,
map_width,
false,
);
len += line.len();
}
let duration = start.elapsed();
println!(
"{} iterations for get_thick_line() took: {:?}",
tests, duration
);
println!(
"total pixels = {}, line width = {}, canvas size = {}x{}\n",
len, line_width, map_width, map_width
);
len = 0;
let start = Instant::now();
for x in 0..tests {
line = utils::get_thick_line(
points1[x],
points2[x],
line_width,
utils::ThicknessMode::LineThicknessMiddle,
map_width,
true,
);
len += line.len();
}
let duration = start.elapsed();
println!(
"{} iterations for get_thick_line(unsafe unchecked) took: {:?}",
tests, duration
);
println!(
"total pixels = {}, line width = {}, canvas size = {}x{}\n",
len, line_width, map_width, map_width
);
}
And the results of a few tests with different parameters:
----------------------- [ test begin ] -----------------------
5000 iterations for get_thick_line_unchecked() took: 16.8303775s
total pixels = 1470765496, line width = 500, canvas size = 1000x1000
5000 iterations for get_thick_line() took: 22.3055861s
total pixels = 1348434370, line width = 500, canvas size = 1000x1000
5000 iterations for get_thick_line(unsafe unchecked) took: 16.1727516s
total pixels = 1470765496, line width = 500, canvas size = 1000x1000
----------------------- [ test begin ] -----------------------
5000 iterations for get_thick_line_unchecked() took: 5.7484512s
total pixels = 589019150, line width = 200, canvas size = 1000x1000
5000 iterations for get_thick_line() took: 7.6234731s
total pixels = 578641650, line width = 200, canvas size = 1000x1000
5000 iterations for get_thick_line(unsafe unchecked) took: 5.1384081s
total pixels = 589019150, line width = 200, canvas size = 1000x1000
----------------------- [ test begin ] -----------------------
10000 iterations for get_thick_line_unchecked() took: 1.8566417s
total pixels = 294929612, line width = 50, canvas size = 1000x1000
10000 iterations for get_thick_line() took: 2.2578805s
total pixels = 294517820, line width = 50, canvas size = 1000x1000
10000 iterations for get_thick_line(unsafe unchecked) took: 1.6420243s
total pixels = 294929612, line width = 50, canvas size = 1000x1000
----------------------- [ test begin ] -----------------------
50000 iterations for get_thick_line_unchecked() took: 1.5864814s
total pixels = 288522185, line width = 10, canvas size = 1000x1000
50000 iterations for get_thick_line() took: 1.854512s
total pixels = 288501000, line width = 10, canvas size = 1000x1000
50000 iterations for get_thick_line(unsafe unchecked) took: 1.4808243s
total pixels = 288522185, line width = 10, canvas size = 1000x1000
The unsafe code is always fastest of course, but it's not that far behind the version with potential duplicates. In the pixel counts you can see how many pixels were removed by the version of the function which removes dupes. get_thick_line(unsafe unchecked) will ONLY have duplicates if it has been abused (like in my above tests).
That's all for today, code for this post and the previous one can be found here: https://github.com/0xDEADFED5/dwarf_dreams/tree/main/thick_bresenham.
Kudos and respect to ArminJo, without their code I'd probably still be scratching my head.
quick edit:
I ran the tests again, this time with coordinates firmly within the canvas, but with the same parameters as the previous tests. As expected, each function call returned the same number of pixels, but with differing performance. Here are the results:
----------------------- [ test begin ] -----------------------
5000 iterations for get_thick_line_unchecked() took: 22.2698107s
total pixels = 2500000000, line width = 500, canvas size = 1000x1000
5000 iterations for get_thick_line() took: 30.3468048s
total pixels = 2500000000, line width = 500, canvas size = 1000x1000
5000 iterations for get_thick_line(unsafe unchecked) took: 19.8017243s
total pixels = 2500000000, line width = 500, canvas size = 1000x1000
----------------------- [ test begin ] -----------------------
5000 iterations for get_thick_line_unchecked() took: 8.2815981s
total pixels = 1000000000, line width = 200, canvas size = 1000x1000
5000 iterations for get_thick_line() took: 11.9877238s
total pixels = 1000000000, line width = 200, canvas size = 1000x1000
5000 iterations for get_thick_line(unsafe unchecked) took: 7.7751189s
total pixels = 1000000000, line width = 200, canvas size = 1000x1000
----------------------- [ test begin ] -----------------------
10000 iterations for get_thick_line_unchecked() took: 3.6693278s
total pixels = 500000000, line width = 50, canvas size = 1000x1000
10000 iterations for get_thick_line() took: 6.2115697s
total pixels = 500000000, line width = 50, canvas size = 1000x1000
10000 iterations for get_thick_line(unsafe unchecked) took: 3.3808899s
total pixels = 500000000, line width = 50, canvas size = 1000x1000
----------------------- [ test begin ] -----------------------
50000 iterations for get_thick_line_unchecked() took: 1.749504s
total pixels = 500000000, line width = 10, canvas size = 1000x1000
50000 iterations for get_thick_line() took: 2.2008861s
total pixels = 500000000, line width = 10, canvas size = 1000x1000
50000 iterations for get_thick_line(unsafe unchecked) took: 1.4769065s
total pixels = 500000000, line width = 10, canvas size = 1000x1000