Matt Brubeck: Planet Matt

Bookmarks: The Metaphysics of Causation (Stanford Encyclopedia of Philosophy)

Posted in Bookmarks on July 31, 2016 05:23 AM

"What must a world be like, to host causal relations? When the cue ball knocks the nine ball into the corner pocket, in virtue of what is this a case of causation?"

Bookmarks: Art Ludique - Le Musée

Posted in Bookmarks on February 05, 2016 11:50 PM

Paris museum with exhibits of Pixar, Ghibli, comic book, and video game art.

Bookmarks: Chess Tempo

Posted in Bookmarks on February 04, 2016 01:16 AM

“A website dedicated to helping chess players improve their game.” Extensive database of tactics/endgame problems with analysis.

Bookmarks: Computer Science Field Guide — Computer Science Field Guide Beta

Posted in Bookmarks on February 04, 2016 12:24 AM

“The ‘Computer Science Field Guide’ is an online interactive resource for high school students learning about computer science, developed at the University of Canterbury in New Zealand.”

Bookmarks: MHz Choice

Posted in Bookmarks on January 20, 2016 07:56 PM

"MHz choice is a brand new subscription-based streaming service featuring new and exclusive international mysteries, dramas and comedies—most presented in HD and all unedited with easy-to-read English subtitles."

Bookmarks: A Matter Of Electric Sheep

Posted in Bookmarks on October 29, 2015 12:15 AM

"Deckard is Gaff. If you think about it, it makes complete sense. Who is Gaff anyway? I propose that he was the best Blade Runner in the business before he got injured and acquired his limp, possibly even going after the replicants in the film."

Journal: So Gurgeh took his

Posted in Journal on August 17, 2015 12:26 AM (comments)

Iain Banks, in 1988 (!), correctly predicting the problems of suspense writing in the age of smart phones:

Stories set in the Culture in which Things Went Wrong tended to start with humans losing or forgetting or deliberately leaving behind their terminal. It was a conventional opening, the equivalent of straying off the path in the wild woods in one age, or a car breaking down at night on a lonely road in another. A terminal, in the shape of a ring, button, bracelet or pen or whatever, was your link with everybody and everything else in the Culture. With a terminal, you were never more than a question or a shout away from almost anything you wanted to know, or almost any help you could possibly need.

The Player of Games

Bookmarks: Understanding Hydroplane Races for the New Seattleite

Posted in Bookmarks on August 06, 2015 10:59 PM

"Before Microsoft, Amazon, Starbucks, etc., there were basically three major Seattle industries: (1) logging and lumber based industries like paper manufacturing; (2) maritime industries like fishing, shipbuilding, shipping, and the navy; (3) aerospace (i.e., Boeing). Vintage hydroplane racing represented the Seattle trifecta: Wooden boats with airplane engines!"

Journal: Let It Go, as sung by Taylor Swift

Posted in Journal on January 31, 2015 08:29 PM (comments)

(To the tune of Shake it Off. I blame cortex for inspiring me.)

My ice magic is a curse.
I think it's getting worse.
At least, that's what people say, mmm.
That's what people say, mmm.

My power's getting strong.
Father said that it was wrong.
That's why I conceal, mmm.
That's why I don't feel, mmm.

I froze a fountain, ran to the North Mountain.
It's like I've got this pounding, in my mind, saying it's gonna be alright.

'Cause Anna's gonna wed wed wed wed wed
Some guy that she just met met met met met.
Baby, I just wanna let let let let let,
Let it go, let it go.

Ice breakers gonna sled sled sled sled sled,
And reindeer gonna shed shed shed shed shed.
I'm just gonna let let let let let,
Let it go, let it go.

I'm sick of being nice.
I built a castle made of ice.
And that's what they don't know, mmm.
That's what they don't know, mmm.

I'm alone but now I'm free.
No right or wrong for me.
And that's what they don't see.
That's what they don't see.

I froze a fountain, ran to the North Mountain.
It's like I've got this pounding, in my mind, saying it's gonna be alright.

'Cause Anna's still in bed bed bed bed bed.
And Olaf lost his head head head.
Baby I'm just gonna let let let let let,
Let it go, let it go.

Trolls are gonna troll troll troll troll troll,
Snow men are made of snow snow snow snow snow.
I'm just gonna go go go go go,
Let it go, let it go.

Hey, hey, hey. While you've been getting down about the liars,
And the dirty dirty weasels of the world,
You could have been getting down to this. sick. beat.

My little sis brought her new boyfriend.
He's like "oh my god," so I'm just gonna shake.
And to the duke over there with the hella weird hair,
Won't you come on over baby, we can shake, shake, shake.

'Cause trolls are gonna troll troll troll troll troll,
Snow men are made of snow snow snow snow snow.
I'm just gonna go go go go go,
Let it go, let it go.

Ice breakers gonna sled sled sled sled sled,
And reindeer gonna shed shed shed shed shed.
I'm just gonna let let let let let,
Let it go, let it go.

I let it go, I let it go, oh.
I let it go, I let it go, oh.
I let it go, I let it go, oh.
I let it go, I let it go, oh.

Journal: A chip off the old block

Posted in Journal on November 30, 2014 06:18 AM (comments)

When E.’s new friend from school comes over to our house, the two of them like to spend half their time playing, and the other half sitting and reading books. Which is awesome.

Weblog: Let's build a browser engine! Part 7: Painting 101

Posted in Weblog on November 05, 2014 05:55 PM

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 }; return Canvas { pixels: repeat(white).take(width * height).collect(), width: width, height: 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.

Weblog: A little randomness for Hacker News

Posted in Weblog on October 22, 2014 10:00 PM

In systems that rely heavily on “most popular” lists, like Reddit or Hacker News, the rich get richer while the poor stay poor. Since most people only look at the top of the charts, anything that’s not already listed has a much harder time being seen. You need visibility to get ratings, and you need ratings to get visibility.

Aggregators try to address this problem by promoting new items as well as popular ones. But this is hard to do effectively. For example, the “new” page at Hacker News gets only a fraction of the front page’s traffic. Most users want to see the best content, not wade through an unfiltered stream of links. Thus, very little input is available to decide which links get promoted to the front page.

As an experiment, I wrote a userscript that uses the Hacker News API to search for new or low-ranked links and randomly insert just one or two of them into the front page. It’s also available as a bookmarklet for those who can’t or don’t want to install the user script.

Install user script (may require a browser extension)

Randomize HN (drag to bookmark bar, or right-click to bookmark)

This gives readers a chance to see and vote on links that they otherwise wouldn’t, without altering their habits or wading through a ton of unfiltered content. Each user will see just one or two links per visit, but thanks to randomness a much larger number of links will be seen by the overall user population. My belief, though I can’t prove it, is that widespread use of this feature would improve the quality of the selection process.

The script isn’t perfect (search for FIXME in the source code for some known issues), but it works well enough to try out the idea. Unfortunately, the HN API doesn’t give access to all the data I’d like, and sometimes the script won’t find any suitable links to insert. (You can look at your browser’s console to see which which items were randomly inserted.) Ideally, this feature would be built in to Hacker News—and any other service that recommends “popular” items.