Matt Brubeck

05 Nov 2014

Let's build a browser engine!

Part 7: Painting 101

I’m returning at last to my series on building a simple HTML rendering engine:

In this article, I will add very basic painting code. This code takes the tree of boxes from the layout module and turns them into an array of pixels. This process is also known as “rasterization.”

Browsers usually implement rasterization with the help of graphics APIs and libraries like Skia, Cairo, Direct2D, and so on. These APIs provide functions for painting polygons, lines, curves, gradients, and text. For now, I’m going to write my own rasterizer that can only paint one thing: rectangles.

Eventually I want to implement text rendering. At that point, I may throw away this toy painting code and switch to a “real” 2D graphics library. But for now, rectangles are sufficient to turn the output of my block layout algorithm into pictures.

Catching Up

Since my last post, I’ve made some small changes to the code from previous articles. These includes some minor refactoring, and some updates to keep the code compatible with the latest Rust nightly builds. None of these changes are vital to understanding the code, but if you’re curious, check the commit history.

Building the Display List

Before painting, we will walk through the layout tree and build a display list. This is a list of graphics operations like “draw a circle” or “draw a string of text.” Or in our case, just “draw a rectangle.”

Why put commands into a display list, rather than execute them immediately? The display list is useful for a several reasons. You can search it for items that will be completely covered up by later operations, and remove them to eliminate wasted painting. You can modify and re-use the display list in cases where you know only certain items have changed. And you can use the same display list to generate different types of output: for example, pixels for displaying on a screen, or vector graphics for sending to a printer.

Robinson’s display list is a vector of DisplayCommands. For now there is only one type of DisplayCommand, a solid-color rectangle:

type DisplayList = Vec<DisplayCommand>;

enum DisplayCommand {
    SolidColor(Color, Rect),
    // insert more commands here
}

To build the display list, we walk through the layout tree and generate a series of commands for each box. First we draw the box’s background, then we draw its borders and content on top of the background.

fn build_display_list(layout_root: &LayoutBox) -> DisplayList {
    let mut list = Vec::new();
    render_layout_box(&mut list, layout_root);
    return list;
}

fn render_layout_box(list: &mut DisplayList, layout_box: &LayoutBox) {
    render_background(list, layout_box);
    render_borders(list, layout_box);
    // TODO: render text

    for child in &layout_box.children {
        render_layout_box(list, child);
    }
}

By default, HTML elements are stacked in the order they appear: If two elements overlap, the later one is drawn on top of the earlier one. This is reflected in our display list, which will draw the elements in the same order they appear in the DOM tree. If this code supported the z-index property, then individual elements would be able to override this stacking order, and we’d need to sort the display list accordingly.

The background is easy. It’s just a solid rectangle. If no background color is specified, then the background is transparent and we don’t need to generate a display command.

fn render_background(list: &mut DisplayList, layout_box: &LayoutBox) {
    get_color(layout_box, "background").map(|color|
        list.push(DisplayCommand::SolidColor(color, layout_box.dimensions.border_box())));
}

// Return the specified color for CSS property `name`, or None if no color was specified.
fn get_color(layout_box: &LayoutBox, name: &str) -> Option<Color> {
    match layout_box.box_type {
        BlockNode(style) | InlineNode(style) => match style.value(name) {
            Some(Value::ColorValue(color)) => Some(color),
            _ => None
        },
        AnonymousBlock => None
    }
}

The borders are similar, but instead of a single rectangle we draw four—one for each edge of the box.

fn render_borders(list: &mut DisplayList, layout_box: &LayoutBox) {
    let color = match get_color(layout_box, "border-color") {
        Some(color) => color,
        _ => return // bail out if no border-color is specified
    };

    let d = &layout_box.dimensions;
    let border_box = d.border_box();

    // Left border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y,
        width: d.border.left,
        height: border_box.height,
    }));

    // Right border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x + border_box.width - d.border.right,
        y: border_box.y,
        width: d.border.right,
        height: border_box.height,
    }));

    // Top border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y,
        width: border_box.width,
        height: d.border.top,
    }));

    // Bottom border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y + border_box.height - d.border.bottom,
        width: border_box.width,
        height: d.border.bottom,
    }));
}

Next the rendering function will draw each of the box’s children, until the entire layout tree has been translated into display commands.

Rasterization

Now that we’ve built the display list, we need to turn it into pixels by executing each DisplayCommand. We’ll store the pixels in a Canvas:

struct Canvas {
    pixels: Vec<Color>,
    width: usize,
    height: usize,
}

impl Canvas {
    // Create a blank canvas
    fn new(width: usize, height: usize) -> Canvas {
        let white = Color { r: 255, g: 255, b: 255, a: 255 };
        Canvas {
            pixels: vec![white; width * height],
            width,
            height,
        }
    }
    // ...
}

To paint a rectangle on the canvas, we just loop through its rows and columns, using a helper method to make sure we don’t go outside the bounds of our canvas.

fn paint_item(&mut self, item: &DisplayCommand) {
    match item {
        &DisplayCommand::SolidColor(color, rect) => {
            // Clip the rectangle to the canvas boundaries.
            let x0 = rect.x.clamp(0.0, self.width as f32) as usize;
            let y0 = rect.y.clamp(0.0, self.height as f32) as usize;
            let x1 = (rect.x + rect.width).clamp(0.0, self.width as f32) as usize;
            let y1 = (rect.y + rect.height).clamp(0.0, self.height as f32) as usize;

            for y in (y0 .. y1) {
                for x in (x0 .. x1) {
                    // TODO: alpha compositing with existing pixel
                    self.pixels[x + y * self.width] = color;
                }
            }
        }
    }
}

Note that this code only works with opaque colors. If we added transparency (by reading the opacity property, or adding support for rgba() values in the CSS parser) then it would need to blend each new pixel with whatever it’s drawn on top of.

Now we can put everything together in the paint function, which builds a display list and then rasterizes it to a canvas:

// Paint a tree of LayoutBoxes to an array of pixels.
fn paint(layout_root: &LayoutBox, bounds: Rect) -> Canvas {
    let display_list = build_display_list(layout_root);
    let mut canvas = Canvas::new(bounds.width as usize, bounds.height as usize);
    for item in display_list {
        canvas.paint_item(&item);
    }
    return canvas;
}

Lastly, we can write a few lines of code using the Rust Image library to save the array of pixels as a PNG file.

Pretty Pictures

At last, we’ve reached the end of our rendering pipeline. In under 1000 lines of code, robinson can now parse this HTML file:

<div class="a">
  <div class="b">
    <div class="c">
      <div class="d">
        <div class="e">
          <div class="f">
            <div class="g">
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>

…and this CSS file:

* { display: block; padding: 12px; }
.a { background: #ff0000; }
.b { background: #ffa500; }
.c { background: #ffff00; }
.d { background: #008000; }
.e { background: #0000ff; }
.f { background: #4b0082; }
.g { background: #800080; }

…to produce this:

Yay!

Exercises

If you’re playing along at home, here are some things you might want to try:

  1. Write an alternate painting function that takes a display list and produces vector output (for example, an SVG file) instead of a raster image.

  2. Add support for opacity and alpha blending.

  3. Write a function to optimize the display list by culling items that are completely outside of the canvas bounds.

  4. If you’re familiar with OpenGL, write a hardware-accelerated painting function that uses GL shaders to draw the rectangles.

To Be Continued…

Now that we’ve got basic functionality for each stage in our rendering pipeline, it’s time to go back and fill in some of the missing features—in particular, inline layout and text rendering. Future articles may also add additional stages, like networking and scripting.

I’m going to give a short “Let’s build a browser engine!” talk at this month’s Bay Area Rust Meetup. The meetup is at 7pm tomorrow (Thursday, November 6) at Mozilla’s San Francisco office, and it will also feature talks on Servo by my fellow Servo developers. Video of the talks will be streamed live on Air Mozilla, and recordings will be published there later.

Subscribe