Getting started with DartBox2d

Posted in Web on January 11th, 2012 by dominic – Be the first to comment

The latest Dart library to be released is one that might see a fair bit of use, if the Java and JavaScript versions are anything to go by. DartBox2d is the latest port of the immensely popular 2d physics engine seen in games across the web. It has a very similar interface to the Java version, so getting started shouldn’t be too hard for anyone familiar with that version.

That being said, here’s how to put together a simple application.

Getting the library

Go here and follow the instructions to get a local copy of the code.

The HTML page

Next, you need an HTML page to host the application. A simple boilerplate would look something like:

<html>
  <body>
    <script type="text/javascript" src="tutorial.dart.js"></script>
  </body>
</html>

The Dart code

At the top of the dart file, you need to name your application and import any libraries you want to use:

#library('tutorial');
#import('dart:dom');
#import('[path_to_dartbox2d]/lib/box2d.dart');

Now create a class for your application and a simple main method:

class Tutorial {
  ...
}

void main() {
  Tutorial.main();
}

This simple main method is what will be called when your application starts. It is calling a static method on your class that should now look something like:

class Tutorial {
  static void main() {
    final app = new Tutorial();
    app.run();
  }

  Tutorial() {
    initializeWorld();
    initializeCanvas();
  }
}

All we have left to do is to define the two initialization methods and the run method. First, let’s initialize the world:

class Tutorial {
  ...

  static final int BALL_RADIUS = 1;

  World world;

  void initializeWorld() {
    // Create a world with gravity and allow it to sleep.
    world = new World(new Vector(0, -10), true, new DefaultWorldPool());

    // Create the ground.
    PolygonShape sd = new PolygonShape();
    sd.setAsBox(50.0, 0.4);

    BodyDef bd = new BodyDef();
    bd.position.setCoords(0.0, 0.0);
    Body ground = world.createBody(bd);
    ground.createFixtureFromShape(sd);

    // Create a bouncing ball.
    final bouncingBall = new CircleShape();
    bouncingBall.radius = BALL_RADIUS;

    final ballFixtureDef = new FixtureDef();
    ballFixtureDef.restitution = 0.7;
    ballFixtureDef.density = 0.05;
    ballFixtureDef.shape = bouncingBall;

    final ballBodyDef = new BodyDef();
    ballBodyDef.linearVelocity = new Vector(-2, -20);
    ballBodyDef.position = new Vector(15, 15);
    ballBodyDef.type = BodyType.DYNAMIC;
    ballBodyDef.bullet = true;

    final ballBody = world.createBody(ballBodyDef);
    ballBody.createFixture(ballFixtureDef);
  }
}

And now we’re ready to initialize the canvas:

class Tutorial {
  ...
  static final int CANVAS_WIDTH = 900;
  static final int CANVAS_HEIGHT = 600;
  static final int VIEWPORT_SCALE = 10;

  HTMLCanvasElement canvas;
  CanvasRenderingContext2D ctx;
  IViewportTransform viewport;
  DebugDraw debugDraw;

  void initializeCanvas() {
    // Create a canvas and get the 2d context.
    canvas = document.createElement('canvas');
    canvas.width = CANVAS_WIDTH;
    canvas.height = CANVAS_HEIGHT;
    document.body.appendChild(canvas);
    ctx = canvas.getContext("2d");

    // Create the viewport transform with the center at extents.
    final extents = new Vector(CANVAS_WIDTH / 2, CANVAS_HEIGHT / 2);
    viewport = new CanvasViewportTransform(extents, extents);
    viewport.scale = VIEWPORT_SCALE;

    // Create our canvas drawing tool to give to the world.
    debugDraw = new CanvasDraw(viewport, ctx);

    // Have the world draw itself for debugging purposes.
    world.debugDraw = debugDraw;
  }
}

Now, all that’s left is to start the world running:

class Tutorial {
  ...
  static final num TIME_STEP = 1/60;
  static final int VELOCITY_ITERATIONS = 10;
  static final int POSITION_ITERATIONS = 10;

  void run() {
    window.webkitRequestAnimationFrame((num time) {
      step(time);
    }, canvas);
  }

  void step(num time) {
    // Advance the world.
    world.step(TIME_STEP, VELOCITY_ITERATIONS, POSITION_ITERATIONS);

    // Clear the canvas and draw the frame.
    ctx.clearRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
    world.drawDebugData();

    // Request another animation frame.
    window.webkitRequestAnimationFrame((num t) {
      step(t);
    }, canvas);
  }
}

Once you’ve put all this together, you’re ready to compile it to JavaScript.

I prefer the command-line frog compiler, but DartBox2d also compiles cleanly with dartc with warnings as errors and fatal type errors enabled, so feel free to use either. You can also use the Dart Editor to build your application, and that’s almost certainly the best route to take. Refer to the Dart language site for more details.

Once you’ve compiled to JavaScript, make sure that your html file is referencing the generated file correctly and load it up in a browser. If all went well, you should see a green box with a peach ball bouncing on it.

Porting Colossal Cave Adventure to Native Client

Posted in Web on September 20th, 2011 by dominic – Be the first to comment

Native Client (NaCl) is a new technology built in to Chrome that allows native code (read C++) to be compiled into a form that is then executed within the browser. Several impressive ports have already been completed, including ScummVM, OGRE, and Unity 3D. A host of other open source libraries have also been ported and are available in the naclports repository.

I am really excited about what this could mean for the future of the web as a platform for technology; even old crusty low-level coders like me can get in on this internet thing all the young people are talking about. I had the opportunity recently to take part in a hackathon centred around Native Client and took the opportunity to port a game that should need no introduction: Colossal Cave Adventure.

For those who just want to try it out, you’ll need Chrome 14 as a minimum and you can find it in the Chrome web store right here. If you just want to see the source, which is open of course, you’ll find that here. Please understand that this was written over the course of a few hours so it is not necessarily as elegant a solution as it might be given more time. Perhaps I will return to it and clean it up later.

There were a number of hurdles I had to overcome to complete this port and it might be interesting to others so this post will cover the issues and my approaches to them.

There were three key components to getting the code to work under Native Client:

  • Static data
  • stdin/stdout
  • Synchronous calls

Static data

The problem

The original source contains a utility advent0 that takes the text messages from a set of .txt files and creates look-up tables that match a message with a byte offset. At run-time, these look-up tables are used to seek through the .txt files and read the message out using fseek and fread. This is not feasible under Native Client as this interface to file I/O is not (yet?) supported. Other ports have successfully used forms to allow users to upload files that are required, but that also is not applicable to this app.

The solution

A new utility was created (advtxt_to_c) that converts the .txt files into arrays of c-style strings. These are then statically linked into the executable so that instead of using byte offsets, the run-time can access the message array directly. This does increase the final executable size, but only by about 64kb. For reference, the total executable size is on the order of 4Mb, most of which is library code.

stdin/stdout

The problem

The original source obviously relies heavily on printffputc, etc to write to stdout. Under Native Client these will end up in the console logs rather than appearing on screen. Using fgets and scanf to get input from the user are equally incorrect.

The solution

The solution to this was to write a thin wrapper around any console output. At this point, I also split the output into three:

  • screen printing
  • console printing
  • error printing

All of these functions call through to the Native Client module which then calls through to JavaScript methods.

Screen printing is used whenever the output should go to the, well, screen and in this case is appended to a textarea on the host HTML page. Console output is redirected to the JavaScript console where they can be read using the Developer Tools built in to Chrome, and error messages are added to a special span on the host HTML page that shows up red and fades over time. The game is also restarted whenever an error is produced, which is a far better approach than the original exit(-1).

Input from stdin was fixed by adding a method to the Native Client module that would call a callback when an ‘input’ message was passed from the JavaScript with a string parameter that comes from a text box on the HTML host page. This required some further changes as an synchronous call becomes an asynchronous call. See the next section for more on that.

Synchronous calls

The problem

As well as console output, the original source depended on fgets for reading user input. This is a synchronous call which has no analogue on the Native Client side. In fact, the whole game was originally written with an assumption that the game loop would block waiting for user input which, well, doesn’t work out all that well.

The solution

As mentioned above, fgets has been replaced by a call to the Native Client module that registers a callback to be called when the user submits text through the input control on the HTML page. The places that called fgets and assumed a synchronous return therefore had to be split into two functions. In some cases, they had to take in function pointers to call after the input had been received.

The main gameloop, that was essentially while (true) { turn(); }, has been replaced by a single call to the turn function that contains a single tick of the gameloop. When input is expected and received, a callback is called that once again calls the turn function.

Sub-surface scattering with CDRF

Posted in Rendering on August 25th, 2010 by dominic – 6 Comments

Introduction
In this paper, Kubo, Dobashi and Morishima present a compelling case for using a curvature dependent reflectance function (CRDF) to simulate sub-surface scattering. The basic idea is that smaller objects with higher curvature exhibit more noticeable sub-surface scattering than flatter ones. Using photon mapping with spheres, the authors found a reasonable relationship between the curvature of the sphere (the inverse of the sphere’s radius) and the radiance across the sphere. With the only examples in the paper shown being fairly close to spherical, I wanted to see if I could use their technique, or a variant of it, to get a cheap sub-surface scattering effect on a more complicated mesh. Like, say, the dragon from Stanford’s 3d scanning repository.

The mathematics
First, the authors of the paper attempt to fit their data using the following CDRF:

f_r(\theta, \kappa)=(L_i*g)(\theta)

Where L_i is the incident light energy and g(\theta, \sigma) is a gaussian:

L_i(\theta)=\max(\cos(\theta),0)
g(\theta, \sigma)=\frac{1}{\sqrt{2\pi\sigma(\kappa)^2}}\exp\frac{-\theta^2}{2\sigma(\kappa)^2}

As can be seen from figure 2(c) in the paper, this is not a particularly good fit though it does match the data qualitatively with a Lambert type shape at low curvature which spreads at higher curvatures.

However, a better quantitative fit is given by (thanks to Cedrick Collomb for help with this):
f_r(\theta,\kappa)=\frac{1+\kappa}{4} \frac{\cos\left(\min\left(\frac{(5 + \kappa)\theta}{4}, \pi\right)\right)+1}{1+\left(\frac{\ln\left(1+1.7\kappa\right)\theta}{1.45}\right)^{10}} + 0.075(1-\kappa)

Once you have this, it’s time to move on to measuring the curvature of your mesh.

Mesh curvature
There are a few different techniques out there for determining the local curvature of a mesh, but the two main techniques involve either finding an analytical formula or patch that fits the mesh around the vertex you are interested in, or determining the curvature directly from the vertex and normal information. As this was just a prototype, I went with the more performance friendly, and less work-intensive, option of determining the curvature directly from the mesh.

My first attempt was inspired by this paper where the area of each ring of faces around a vertex is compared to the area of those same faces projected onto a unit sphere. This gives a measure of the Gaussian curvature of a mesh which is an intrinsic property of any surface. When applied to a series of test meshes, the results were less than ideal. The sign of the curvature appears correct, but the magnitude depends heavily on the size of the faces, as you would imagine from the definition.

I did attempt to extend the neighborhood used to calculate the Gaussian curvature to two rings, but this had two negative effects: The local curvature was smoothed out too much in some places, and other places the technique became invalid as it relies on the sign of curvature not changing within a neighborhood.

These limitations led me to a definition of curvature that is not an intrinsic property of a surface, but depends on the space a surface is embedded in. As I can control the ambient space within my test program and ensure it remains Euclidean (side note – has anyone considered making a game set against a non-Euclidean space?) this measure is still valid for my requirements.

This technique, outlined in this paper again compares areas of faces within the neighborhood of a vertex, but as the area of the face appears in both the numerator and the denominator of the ratio, the magnitudes of curvature are more well-behaved both locally and across the mesh. My results from this technique were far more useful.

Putting it all together
So now you have an intimidating formula linking local curvature and incident light angle to outgoing radiance. What happens when you put it together?

First, here’s a baseline. The dragon with a simple Lambert BRDF:

Now replacing this with the CDRF from the original paper:

The diffuse lighting is clearly wrapping around the model more, as expected, however there are some issues. Note in particular the spine of the dragon which, being thinner, should show more transmission. However, as it has flat curvature when compared to the thicker body of the dragon, it transmits less.

To compare, here’s an image of the same mesh, with the same data, but using a more traditional depth-based technique for sub-surface scattering:

Which clearly shows the transmission effect, but where we might expect the scattering effect to be pronounced, around the details in the face, for example, we lose all detail.

While it is true that transmitted light will focus into areas of high curvature, this is an additional effect on top of how far the light has to travel within the model. So perhaps by combining these effects and using the CDRF to add a curvature dependent term to the depth-based sub-surface scattering model, we might get something better than either:

Which has all the benefits of a depth-based technique but with the added benefit of concentrating the transmission where the curvature has a high positive magnitude and darkening the transmission where the curvature is negative.

However, we can combine the curvature with the depth-based sub-surface scattering effect in other ways. We can use the curvature of the model directly to lighten and darken the transmitted light. This should add detail back in without the expense of the CDRF calculations and looks like this:

This, in combination with a Blinn-Phong BRDF and a Fresnel reflectance term, gives us something that starts to approximate jade:

Summary
While the original application of the local curvature of a mesh does not provide a good model of sub-surface scattering for more general cases, it can certainly be applied to existing techniques to add subtlety to the transmission and scattering of light through a model.