Josh On Design

How can you draw a filled rectangle fast? By making it not slow! Great if you are using a GPU to accelerate rectangle drawing for you, but what if you are doing it oldskool with an in memory frame-buffer? You'd probably write some code like this:

// assume width is the width of your frame buffer
// assume color is a u32 of ARGB 
let ry = rect.y as usize;
let rx = rect.x as usize;
let rh = rect.h as usize;
let rw = rect.w as usize;
for y in 0..rh {
    for x in 0..rw {
        self.buffer[((ry + y) * width) + rx + x] = color
    }
}

Now, this will work of course, It's in fact the simplest thing to do, but if that's a lot of calculations we are doing for every pixel even though they are getting the same value. Really we are just copying a 32 bit integer over and over to the same adjecent memory. If this was in C we'd use memcpy() but we are using Rust and want to be safe, so what can we do?

Safely Modifying Vectors in Rust

In Rust, you can represent a memory buffer by a Vector of u8 or u32 numbers. Since my project is for an ARGB display, I'm using Vec<u32>. While you can set values individually with indexes, this is slower than in C because it has to do runtime bounds checking to make sure the you don't off the end of the allocated memory.

For the same reason Rust really doesn't want you to copy only parts of one vector to another because that also needs bounds checking. Instead Rust provides functions like copy_from_slice which let you copy only the entire vector at once, which is fast and only checks bounds once. That's fine if we want to manipulate the entire vector, but what if we only want to work with just a part of the vector?

Vector has a few other interesting methods like split and chunks, which give you access to subsections of the vector as mutable slices. Want to copy into just the half the vector? Split it! Need to chop it up into a bunch of uniform sized chunks, Chunk it!

The Plan

We are going to compose our solution for drawing rectangles in sections. First we will divide the buffer up into rows for each scan line, and then figure out the part of the rect inside that row. Then we can finally fill it in. Let's go.

First, let's calculate how big the buffer is in buffer_bounds and what part of the rectangle will be drawn in fill_bounds. In case the rectangle isn't fully inside the buffer we must calculate the intersection first.

let buffer_bounds = Rect::from_ints(0, 0, width as i32, height as i32);
let fill_bounds = buffer_bounds.intersect(rect);

Now let's create a vector representing a single row of the rectangle. Think of it as a rubber stamp that we can use over and over. Let's fill it with the color.

let mut row = vec![0; fill_bounds.w as usize];
row.fill(color);

Now we need to access each row of the buffer as a separate slice. We can do this with chunks_exact_mut. All the chunks methods return an iterator over the slices. The exact version ensures we only get chunks of the exact size we want (any remainder will be ignored), and mut means the slices will be mutable. For each row_slice we first check if it intersects with the rectangle we want to fill. If not then just continue.

for (j, row_slice) in self.buffer.chunks_exact_mut(width).enumerate() {
    let j = j as i32;
    if j < fill_bounds.y {
         continue;
    }
    if j >= fill_bounds.y + fill_bounds.h {
        continue;
    }

Now we can split the row of the buffer into three parts, before, after, and the middle part. The middle is the only part we want to draw. We can pull these parts out using split_at_mut. Now we can finally copy from our row to the current slice, just the part we need.

    let (_, after) = row_slice.split_at_mut((fill_bounds.x) as usize);
    let (middle, _) = after.split_at_mut((fill_bounds.w) as usize);
    middle.copy_from_slice(&row);
}

That's it. Now you can draw a rectangle or other shapes faster than setting each pixel individually. You can see this code in action as part of the next release of IdealOS Clogwench here.