Writing your own Canvas Scene Graph

Writing a scene-what? The HTML5 Canvas api provides primitive methods to express shapes, strokes and fills, which is all fine and dandy, but in a lot of situations we tend to think of drawing as composed of objects. E.g. to draw what I see from my window I need to draw a tree, a house and some grass, not a sequence of paths.

This is true even more when we start animating, typically objects that are part of another object move when the parent object moves.

One way to abstract this is to have a graph of objects where some objects are contained in other objects and each object takes care of drawing itself. This is called scene graph rendering.

In this article I will show how to build your very own scene graph renderer for the HTML5 canvas. If you are simply looking for a full-featured, pre-built solution, I recommend checking out CAAT. But sometimes you need something easily customizable/lightweight. We will build a single CoffeeScript class that implements everything necessary.

The basics

The first thing that any computer graphics program has to deal with are coordinate systems. We want each object to have it’s own independent coordinate system and itself be defined in terms of it’s parents. In general this indepence is one of the best reasons for using a scene-graph solution, since canvas tends to have a lot of global state, and you might often face the situation that changing one part of your composition affects a very different part. We wish to avoid that.

The simplest way to solve this is to have each object be it’s own canvas. So let’s start coding:

class Entity
  width: 0
  height: 0

  constructor: (@width, @height) ->
    # Create the canvas we will be rendering the object to
    @canvas = document.createElement('canvas')
    @canvas.width = @width
    @canvas.height = @height

  # Call this function to render out the object, returns a Canvas instance
  render: ->
    ctx = @canvas.getContext('2d')
    # Clear the canvas, important for animation
    ctx.clearRect(0, 0, @width, @height)
    @draw(ctx)
    @canvas # return the canvas

  # This function should be overriden in subclasses  
  draw: (ctx) ->

Now each subclass has to only implement the draw method with it’s own set of drawing primitives.

Composition

We hover are still not a graph, there is no way in which objects can have no children. First we need to add a few more properties to our class:

x: 0
y: 0
children: []
parent: null

x and y are numbers that determine where will the object be drawn in the parent’s coordinate system. Let’s implement a default draw method, that will render the children:

draw: (ctx) ->
  for child in @children
    ctx.drawImage(child.render(), child.x, child.y)
  false # return some value, otherwise CoffeeScript will return an array

The drawImage method takes an Image, Canvas or Video object and draws it at specified coordinates. Since render returns a canvas instance with the object drawn in it, we can now render it in the parent canvas. A simple demo of this class:

Rotations

To make this even more worth it, we would like to support rotating any object and having all it’s children be rotated as well. Again we need to add a rotation attribute:

rotation: 0

and tweak our draw function:

draw: (ctx) ->
  for child in @children
    if child.rotation isnt 0
      ctx.save()
      ctx.translate(child.x, child.y)
      ctx.rotate(child.rotation)
      ctx.drawImage(child.render(), 0, 0)
      ctx.restore()
    else
      ctx.drawImage(child.render(), child.x, child.y)
  false

Canvas provides us with all the magic we need. We save the current context, then shift our origin point to the child’s coordinates (NB: we are going to be rotating children around their origin point, perhaps you would like to implement rotation around center point). Then we do the rotation and drawing and then we simply restore our context to it’s original point of origin.

Shaping up the API

First of all since most entity objects will want to override draw in one way or another we might simply use a Kestrel in the constructor and allow the user to optionally provide it when initiating the class:

constructor: (@width, @height, @draw = @draw) ->
    @canvas = document.createElement('canvas')
    @canvas.width = @width
    @canvas.height = @height

The @draw = @draw might look a bit awkward at first glance, but it assigns as a default our own implementation of draw if the user hasn’t provided one. The js looks like this:

function(draw) {
  this.draw = (draw != null ? draw : this.draw);
}

Next let’s have a single function for instantiating new Entities and simultaneously adding them as children:

add_child: (width, height, draw) ->
  child = new Entity width, height, draw
  @children.push child
  child.parent = @
  child # return `child` so that we can do stuff like `collection = scene.add_child 30, 30`

You might want to create another class that wraps up some common functionality as creating the top level Entity (typically called Scene) and setting its canvas as the one actually displayed in the document and setting up animation loops and so on. I’ll leave that as an exercise for the reader (hint: look at the fiddles, there you have the basics).

Caching

If you draw expensive things in your objects (and some things in canvas are pretty expensive like shapes with multiple gradients/shadows), you might not want to redraw them 60 times per second. Our architecture allows us to prevent that rather easily.

Again we add two more attributes:

# This is what the user sets
perform_caching: no
# This tracks whether or not we should render
is_cached: no

Now let’s modify our render function:

render: ->
  return @canvas if @perform_caching and @is_cached
  ctx = @canvas.getContext('2d')
  ctx.clearRect(0,0,@width, @height)
  @draw(ctx)
  @is_cached = true
  @canvas

We skip all the work when caching is enabled, since the canvas still contains all that was drawn into it.

Wrapping up

And that’s basically all there is to it. There are a myriad of features you can add like more transformations apart from rotations, primitive entity subclasses (think something like Sprite entity), etc. The complete class is here:

What bothers me about ACTA, SOPA, etc.

There is a significant problem with these laws (acts, agreements, whatever) even if you don’t care about IP legislation at all.

The current entertainment industry arose under a certain set of conditions. These condition have changed and the industry is failing to keep pace¹. So instead of transforming into something modern they attempt to change the conditions back to their outdated state via the law.

Let me make an analogy: imagine that Catholic priests started lobbying for the state to ban atheism because they were losing their jobs. The current legislation is the same thing for the entertainment industry.

Many people view the current protests as some sort of hippie free-lunch² absurdity. What is in fact at stake is however a core value of capitalism: if you can’t make a profit with your product, you don’t make the government protect your market, you make your product better or you shrivel up and die.

1. Actually it’s not even doing so bad, but that’s a separate issue.

2. The Pirate culture tends to elicit such views with slogans such as “Sharing is caring” .

Zdeněk Miler
1921-2011

Jesus’ Game

A question I’ve often thought about is why is it that people that don’t believe in God are often not dramatically evil or immoral. I’ll take a look at one of the famous parts of the New Testament, Jesus’ Sermon on the Mountain. Many smart people have written much about it. However, some aspects of it are still very hard to understand and even harder to implement in your own life.

The passage I would like to discuss is Mathew 6, 38-48:

“You have heard that it was said, ‘An eye for an eye and a tooth for a tooth.’

But I say to you, Do not resist one who is evil. But if any one strikes you on the right cheek, turn to him the other also; and if any one would sue you and take your coat, let him have your cloak as well; and if any one forces you to go one mile, go with him two miles. Give to him who begs from you, and do not refuse him who would borrow from you.

“You have heard that it was said, ‘You shall love your neighbor and hate your enemy.’

But I say to you, Love your enemies and pray for those who persecute you, so that you may be sons of your Father who is in heaven; for he makes his sun rise on the evil and on the good, and sends rain on the just and on the unjust. For if you love those who love you, what reward have you? Do not even the tax collectors do the same? And if you salute only your brethren, what more are you doing than others? Do not even the Gentiles do the same?

You, therefore, must be perfect, as your heavenly Father is perfect.

Before I get to the text itself allow me to take a bit of an excursion to another famous and well discussed problem: the Prisoner’s Dilemma. This is one of the fundamental problems of Game Theory. Here is Wikipedia’s take:

Two suspects are arrested by the police. The police have insufficient evidence for a conviction, and, having separated the prisoners, visit each of them to offer the same deal. If one testifies for the prosecution against the other (defects) and the other remains silent (cooperates), the defector goes free and the silent accomplice receives the full 10-year sentence. If both remain silent, both prisoners are sentenced to only six months in jail for a minor charge. If each betrays the other, each receives a five-year sentence. Each prisoner must choose to betray the other or to remain silent. Each one is assured that the other would not know about the betrayal before the end of the investigation. How should the prisoners act?

Imagine you were one of these suspects. I presume you would be facing a tough moral decision. Ten years spent in prison is a big chunk of your life, and you can’t be sure how your accomplice will react?

It is well established that the rational¹ thing to do in a Prisoner’s Dilemma situation is to defect. In fact it is a strictly dominant strategy. For some time, this result turned out to be quite a wrench in the wheels of theories on why and how people cooperate with each other. It seems inconsistent with the notion that people are (mostly²) rational beings.

Take a moment to consider how you feel about the fact that human cooperation is irrational - that in fact, by helping others you are making your own life worse. Not exactly cool, is it?

Thankfully, Keneth Binmore comes to our rescue:

A whole generation of scholars swallowed the line that the Prisoner’s Dilemma embodies the essence of human cooperation… Rational players don’t cooperate in the Prisoner’s Dilemma because the conditions necessary for rational cooperation are absent³.

Doesn’t look that bad for the human race after all. But it answers the question I’ve started this essay with: Why don’t atheists sin a lot more? Why do we know pretty decent people who don’t believe in God? Why aren’t even satanists epically evil? If you are absolutely convinced that there is nothing greater than us, there seems to be no reason to adhere to basic morality, is there?

In a lot of situations behaving morally is rational. Or in other words, being good to others is in fact good for us (in a very materialistic sense). Jesus refers to this when he says: “For if you love those who love you, what reward have you? Do not even the tax collectors⁴ do the same?”

What I’m trying to get at with this digression into Game Theory is that Jesus tries to tell us that as Christians we need not be always rational - or specifically, not always rational in game-theoretic terms.

If you look at how this would turn out in the Prisoner’s dilemma then yes, at first you would get the sucker’s payoff. But now imagine a world where most people would try their best to turn the other cheek and when in a prisoner’s dilemma you would know that the other person will cooperate with say a 60% probability. Then defecting loses its strict dominance and you would be more likely to choose the option that maximizes social welfare, that is an option that’s better for every player taken together. Hence I believe that not only does choosing this “irrational” lifestyle make sense morally but also it in fact may affect other people’s lives and actually contribute to make the world a better place.

Also:

My thanks to Joachim Veselý for proofreading this essay.

1. What exactly constitutes rational behavior is of course debatable; in Game Theory it generally means to maximize one’s payoff.

2. Whether or not you consider humans as rational depends on which psychological theory you subscribe to and what notions of rationality you hold, but I would argue that humans are more or less rational in decisions that matter.

3. Imagine that in the prisoner’s situation if they both cooperate then they will be set free for lack of evidence and if only one defects he will get minor jail-time, then cooperation is the dominant strategy. Binmore argues that this type of situation is far more common in real life then Prisoner’s Dilemmas and this fact is why we cooperate in most situations.

4. Tax collectors were considered the scumbags of Jesus’ time.

Popular passwords in 2010

A long story short: I got my hands on a data-dump of 184 550 hacked usernames and passwords from Gawker. With a bit of data-analysis magick I did a bit of research.

20 most popular passwords

Now the first entry is rather shocking: the most used password is also the most obvious password possible. A full 1% (and 0.11% of the full DB; see bellow) used this password! What didn’t exactly fit on the list was that another 111 people used ‘Password’ and 129 people used the slightly better ‘passw0rd’.

“lifehack” and “gizmodo” are both names of the sites these passwords were retrieved from. Not very secure. ‘qwerty’ and ‘abc123’ are also extremely obvious passwords. 15 of the remaining passwords are single words contained in any dictionary.

Password Strength

Next I marked the passwords with these simple rules:

• +1 point for each of: uppercase characters, lowercase characters, numerals, punctuation
• +1 point for passwords longer then 7 letters
• 0 points if they were part of the username

The following table shows the distribution of these strengths.

Now a score of 1 is very bad - it is the default unless you use the same password as your name. However a staggering amount of people use these very unsafe passwords.

A new year’s (a bit early, but well) promise should be a bit more online safety for all of us.

A few notes

1. The dataset is available here and the details of how it was obtained are here.

2. The full db contained ~1.5M records out of which the attackers obtained ~1.2M (presumably randomly). They proceeded to crack the week encryption algorithm of ~200K accounts. This I do not assume was completely random. Out of this I got a total number of 184 550 records.

3. The site apparently stored only the first 8 characters (sic!) of the password. This suggests caution with passwords of length 8 because these were possibly truncated. I set those shorter then 8 characters in an italicized font. However apart from “lifehack” which would be probably “lifehacker” all other passwords in the top 20 seem as complete words or phrases. As an aside a strong password is generally considered to be at least 16 characters long.

4. I would like to perform more research into password sharing with this dataset but I don’t have the time for that right now. I’d be interested if someone will investigate.

Designing a departures board with CSS3

Warning: Technical article ahead. Beware.

As I’ve written before, CSS3 is very good for designing things. Today we’re going to use it to do some fun pixel pushing. Behold our inspiration.

This article contains features and examples that do no work properly in the dashboard. Please follow to the version on my site.

Markup

Simple. Use any thing you like. We will be using a div called .board.

The basics

We’ll start with designing for Webkit for now. First the basic shape and color.

.board {
    padding:  5px 10px;
    display: inline-block;
    background: rgb(30, 30, 30);
    -webkit-border-radius: 3px;
    text-transform: uppercase;
    color: white;
}

yields:

Shadows

Now let’s make the dark shadow effects from the top and sides of the box. For this we’ll use multiple inset box shadow declarations:

-webkit-box-shadow:  
  inset 2px 0px 4px rgba(0,0,0,0.9), 
  inset -2px 0px 4px rgba(0,0,0,0.9);

Gives:

Spinner

These sort’s of displays use a spinner and thin boards to display different strings. When you go to a train station or airport (that still use this magnificently old tech) you can see the dividing line between the two halves. We’ll recreate that here.

How? Using a pseudo element with thin boarders.

.board:before {
    border-top: 1px solid rgba(0,0,0,0.4);
    /* this line will be barely visible, but that's how we want it */
    border-bottom: 1px solid rgba(255,255,255,0.08);
    height: 0px;
    position: relative;
    /* you might need to ajust these positions to your layout */
    width: 110%;
    left: -9px;
    top: 11px;
    content: " "; /* we have to set this, otherwise it won't be visible */
    display: block;
}

This is how it looks:

Border

To make the spinner look realistic we have to also pay attention to the bottom border. It has to have a 3D effect an look plastic enough. We’d also like to see the board bellow it. So we modify our shadows definition and add a border.

border-bottom: 1px solid rgba(0,0,0,0.7);
-webkit-box-shadow: 
  inset 0 -1px 0 rgba(50,50,50,0.7), 
  inset 0 -2px 0 rgba(0,0,0,0.7), 
  inset 2px 0px 4px rgba(0,0,0,0.9), 
  inset -2px 0px 4px rgba(0,0,0,0.9);

Lighting

Light’s and shadows are a crucial part of any visualization. So as a finishing touch we add a few light effects (with a subtle gradient and a few more shadows):

-webkit-box-shadow: 
  inset 0 -1px 0 rgba(50,50,50,0.7), 
  inset 0 -2px 0 rgba(0,0,0,0.7), 
  inset 2px 0px 4px rgba(0,0,0,0.9), 
  inset -2px 0px 4px rgba(0,0,0,0.9), 
  /* This one is new and adds a light edge on the bottom*/
  0 1px 0px rgba(255,255,255,0.2); 
background: -webkit-gradient(linear, center top, center bottom, 
  color-stop(0.0, rgba(0,0,0, 1)), 
  color-stop(0.05, rgba(30,30,30, 1)),  
  color-stop(1.0, rgba(50, 50, 60, 1)));

Which yields:

Conclusion

As you can see, CSS3 enables us to do with a few lines of code some incredible pixel-pushing. So here’s the complete code with syntax for other browsers and fallbacks for graceful degradation:

Let me know if you’d like more articles like this.

Edit: For an animated version see this project by Paul Cuthbertson.