Ming's Coding Blog

Egit and Github: Pulling from a Master Repository and Pushing into Your Own Forked Repository

2012-01-21T14:13:00.000-05:00

So I'm new to the world of git and Github, so I'm trying to figure out how all this stuff works. Making things more complicated is the fact that I'm using Eclipse and its egit plugin, but most of the documentation on working with Github assumes that you're working with the command-line version of git. Although there is some documentation on how to use egit with Github, it mostly assumes that you created your own repository in git for your own projects. Github encourages people to take an existing project, fork it, and then work with your own copy of the repository though. This then makes things difficult when you need to pull in changes from the original master repository and stick them in your own repository.

Again, there is documentation on how to do get your forked repository in-sync with the master repository, but I'm still trying to feel my way about how to do this in Eclipse with egit. So far, here are some sets of instructions that seem to work with Eclipse Indigo 3.7 (but I'm still feeling my way around though, so I could be wrong).

So I'm assuming that you've forked a repository on Github, and you've successfully used the egit defaults to make a local repository based on your fork. So in the Git Repository Exploring perspective of Eclipse, you go into your repository.

In the Remotes section, right-click and choose "Create Remote"

Set the name to "upstream" and configure it for fetch
the URI should be set to the git URI of the original master repository on Github that you forked
"Add" a RefSpec
the source should be master, and the destination should then be automatically filled in to refs/remotes/upstream/master
Save your changes

In the Remotes section, expand the upstream configuration, right-click the green incoming arrow, and choose Fetch
After fetching, I think the latest changes are now available in your local repository, so now you want to apply those changes to your local branch, and then push them out to your forked repository
So make sure you have your local master checked out or whatever
Right-click your repository and choose Merge...
Merge in from upstream/master
And then you can push everything back into your forked repository on Github with a simple Right-click on your repository and Push.

It looks like egit might also support some sort of special Upstream configuration or something, so that egit will automatically track the master version of a fork, but it looks like the forked repository needs to be configured a special way, and I don't know how to get Github to do this. I imagine if you dig into egit's property files, there'll be some way to enable it, but I can't figure it out yet.

Thinking about Diagrams and Figures with Constraints

2012-01-16T15:53:00.002-05:00

I have a small website for teaching kids to program, and I've long wanted to translate it into French and other languages. Being a website geared towards kids, the website has lots of diagrams and figures. Many of these diagrams contain text, so I would need to new versions of about 100 diagrams for each additional language I wanted to support with my website. Obviously, sitting around redrawing the diagrams for each new language would be impractical, especially for languages that I'm personally not familiar with. So I need some system that will let me define my diagrams in a generic way, substitute in different translations for the text, and then generate different versions of the diagrams for different languages.

The crux of the problem is that text might be different sizes in different languages. In English, you might use one word to describe something, but another language might use 5 words to describe the same thing. As a result, the diagrams need to lay themselves out differently depending on the size of the text. I've been trying to find a tool to do that, but I've been having problems figuring out what terms to use in the search. Right now, I'm just trying to understand what sort of tools are available in the space or, given that I probably have to write a chunk of code to substitute in the text translations anyway, how hard it would be to write a simple one from scratch.

Internationalization is a common problem in user interfaces, so coders commonly use a constraint-based layout scheme for their user interfaces in order to avoid this problem. Basically, you have some simple patterns or templates that define how UI elements should be arranged with respect to one another, and then you stick UI widgets into those templates. So you might have a row of widgets, or a grid of widgets, etc. This doesn't necessarily work too well for diagrams because the layouts tend not to be as rigid as in UIs. I was thinking that I could build a more complex version of the system where the diagram designer simply inputs arbitrary layout constraints (e.g. the right side of this element should touch the left side of this other element), and then everything would be fed into a solver of a linear system of equations to get the final layout.

I'm a little concerned though that it might get tedious describing all of the constraints needed to solve a full system. Plus, these constraints might be too rigid in that you can't say, "I need a circle as big as possible to fill that space between the elements" or "make the font size as big as possible as long as the width isn't too big." Of course, doing something like that might require a system that uses linear programming or some other mathematical optimization technique underneath, and it might be tricky to translate constraints from a diagram design into the proper set of inequalities and objective functions without totally confusing the diagram designer.

There are various "constraint-based diagram editors" available, but most of these tools are designed from drawing large graphs (e.g. org charts). Given a bunch of inter-connected diagram elements, these tools will use spring systems or other techniques to find a good planar embedding of the graph. Some of my diagrams could be laid out this way, but I'm not sure if this approach is simultaneously too heavy and too underpowered for the types of diagrams I want. My diagrams don't really fit into those graph models, so I'd be worried that the mismatch of diagram types would make it difficult to get the results I wanted.

I also looked at some constraint solver systems that I could maybe build up into a diagram tool since that would give me the most flexibility in terms of how constraints could be expressed. Unfortunately, constraint solvers are actually a technical term used to refer to specific AI-like problems like SAT, etc. They specialize in solving binary constraints. Although they can also work with real numbers, it seems that some of them solve the problem by discretizing the real number line and then using standard binary constraints to solve things.

Perhaps what I need is some sort of symbolic computation engine that can work with intervals. Does that even exist? Perhaps I'm going overboard with this whole diagramming thing.

WebGL Pre-Tutorial, Part 2: Drawing a 2d Triangle

2011-11-10T17:51:00.001-05:00

This part of the pre-tutorial will show you how to write a very basic WebGL program that draws a 2d triangle on the screen.

Unfortunately, even the simplest WebGL program is somewhat long and involved. Below is the complete code for the program followed by more detailed explanations of the different parts of that code.

<!doctype html> <canvas width="500" height="500" id="mainCanvas"></canvas> <script> function main() { // Configure the canvas to use WebGL // var gl; var canvas = document.getElementById('mainCanvas'); try { gl = canvas.getContext('experimental-webgl'); } catch (e) { throw new Error('no WebGL found'); } // Copy an array of data points forming a triangle to the
// graphics hardware // var vertices = [ 0.0, 0.5, 0.5, -0.5, -0.5, -0.5, ]; var buffer = gl.createBuffer(); gl.bindBuffer(gl.ARRAY_BUFFER, buffer); gl.bufferData(gl.ARRAY_BUFFER, new Float32Array(vertices), gl.STATIC_DRAW); // Create a simple vertex shader // var vertCode = 'attribute vec2 coordinates;' + 'void main(void) {' + ' gl_Position = vec4(coordinates, 0.0, 1.0);' + '}'; var vertShader = gl.createShader(gl.VERTEX_SHADER); gl.shaderSource(vertShader, vertCode); gl.compileShader(vertShader); if (!gl.getShaderParameter(vertShader, gl.COMPILE_STATUS)) throw new Error(gl.getShaderInfoLog(vertShader)); // Create a simple fragment shader // var fragCode = 'void main(void) {' + ' gl_FragColor = vec4(1.0, 1.0, 1.0, 1.0);' + '}'; var fragShader = gl.createShader(gl.FRAGMENT_SHADER); gl.shaderSource(fragShader, fragCode); gl.compileShader(fragShader); if (!gl.getShaderParameter(fragShader, gl.COMPILE_STATUS)) throw new Error(gl.getShaderInfoLog(fragShader)); // Put the vertex shader and fragment shader together into // a complete program // var shaderProgram = gl.createProgram(); gl.attachShader(shaderProgram, vertShader); gl.attachShader(shaderProgram, fragShader); gl.linkProgram(shaderProgram); if (!gl.getProgramParameter(shaderProgram, gl.LINK_STATUS)) throw new Error(gl.getProgramInfoLog(shaderProgram)); // Everything we need has now been copied to the graphics // hardware, so we can start drawing // Clear the drawing surface // gl.clearColor(0.0, 0.0, 0.0, 1.0); gl.clear(gl.COLOR_BUFFER_BIT); // Tell WebGL which shader program to use // gl.useProgram(shaderProgram); // Tell WebGL that the data from the array of triangle
// coordinates that we've already copied to the graphics
// hardware should be fed to the vertex shader as the
// parameter "coordinates" // var coordinatesVar = gl.getAttribLocation(shaderProgram, "coordinates"); gl.enableVertexAttribArray(coordinatesVar); gl.bindBuffer(gl.ARRAY_BUFFER, buffer); gl.vertexAttribPointer(coordinatesVar, 2, gl.FLOAT, false, 0, 0); // Now we can tell WebGL to draw the 3 points that make
// up the triangle // gl.drawArrays(gl.TRIANGLES, 0, 3); } window.onload = main; </script>

The first part of the HTML page creates the HTML element where the actual 3d drawing will occur. WebGL uses the canvas element to define its drawing surface, which can also used in HTML5 for doing 2d drawing.

<canvas width="500" height="500" id="mainCanvas"></canvas>

Then, we get into the actual code. First, we need to configure the canvas for use with WebGL instead of for 2d drawing by grabbing a WebGL context object that lets us invoke WebGL commands on the canvas.

var gl; var canvas = document.getElementById('mainCanvas'); try { gl = canvas.getContext('experimental-webgl'); } catch (e) { throw new Error('no WebGL found'); }

Next, we have an array holding the coordinates of the three points that make up a triangle.

As mentioned in part 1, we need to copy this triangle data to the graphics hardware before we can draw it. This is done by using createBuffer() to tell WebGL to that we want to set aside some memory at the graphics hardware for our data, bindBuffer() to select this buffer as something we want to manipulate, and then bufferData() to actually copy the triangle data to the currently selected buffer in the graphics hardware.

var vertices = [ 0.0, 0.5, 0.5, -0.5, -0.5, -0.5, ]; var buffer = gl.createBuffer(); gl.bindBuffer(gl.ARRAY_BUFFER, buffer); gl.bufferData(gl.ARRAY_BUFFER, new Float32Array(vertices), gl.STATIC_DRAW);

The “vertices” array that holds the triangle data is put inside a Float32Array object before being sent to the bufferData() call. This Float32Array object specifies how the array data should be laid out in memory. JavaScript is purposely vague about the exact memory layout of objects, but these details are important when working with graphics hardware. In this case, we specify that the triangle data should be stored as consecutive 32-bit floating point numbers.

As mentioned in part 1, the WebGL graphics pipeline requires us to define vertex shader and fragment shader programs in order to draw anything on the screen. We first define the vertex shader program.

var vertCode = 'attribute vec2 coordinates;' + 'void main(void) {' + ' gl_Position = vec4(coordinates, 0.0, 1.0);' + '}'; var vertShader = gl.createShader(gl.VERTEX_SHADER); gl.shaderSource(vertShader, vertCode); gl.compileShader(vertShader); if (!gl.getShaderParameter(vertShader, gl.COMPILE_STATUS)) throw new Error(gl.getShaderInfoLog(vertShader));

The actual code for the vertex shader is held in a string. The vertex shader allows us to move the points of a triangle or other small transformations before they are displayed. Each point that makes up a triangle is given to the vertex shader, and the vertex shader program returns the final position of the point, plus additional data that it may want to specify. In our case, we don't need to move the points around, but we need to put the data in a proper form for WebGL. WebGL displays the parts of triangles that fit inside the 3d cube between (-1,-1,-1) and (1,1,1). Our triangle coordinates are only (x,y) values, so we need to specify an extra z value so that WebGL can determine where the triangle is in 3d space. We just use 0 for this z coordinate. In fact, WebGL needs us to specify four values: x, y, z, and a fourth value that is normally always 1. So our vertex shader will take the 2d (x,y) coordinates for a point in the triangle and transform it to (x,y,0,1).

attribute vec2 coordinates; void main(void) { gl_Position = vec4(coordinates, 0.0, 1.0); }

Next we define the fragment shader.

var fragCode = 'void main(void) {' + ' gl_FragColor = vec4(1.0, 1.0, 1.0, 1.0);' + '}'; var fragShader = gl.createShader(gl.FRAGMENT_SHADER); gl.shaderSource(fragShader, fragCode); gl.compileShader(fragShader); if (!gl.getShaderParameter(fragShader, gl.COMPILE_STATUS)) throw new Error(gl.getShaderInfoLog(fragShader));

A fragment shader controls the color of each pixel making up the triangle. For each pixel, a fragment shader should return four numbers describing the color: the amount of red, the amount of green, the amount of blue, and the amount of transparency. If we look at the code for the fragment shader, we can see that the fragment shader is fairly simple. It simply uses the same color for every pixel: an opaque white color.

void main(void) { gl_FragColor = vec4(1.0, 1.0, 1.0, 1.0); }

After defining a vertex shader and fragment shader, we need to put these two shaders together in a single program for drawing things.

var shaderProgram = gl.createProgram(); gl.attachShader(shaderProgram, vertShader); gl.attachShader(shaderProgram, fragShader); gl.linkProgram(shaderProgram); if (!gl.getProgramParameter(shaderProgram, gl.LINK_STATUS)) throw new Error(gl.getProgramInfoLog(shaderProgram));

Now that we've copied the triangle data and shader programs over to the graphics hardware, we're finally ready to do some drawing. First, we clear the drawing surface to black so that the white triangle we're drawing will show up.

gl.clearColor(0.0, 0.0, 0.0, 1.0); gl.clear(gl.COLOR_BUFFER_BIT);

Then we specify which shader program to use for drawing.

gl.useProgram(shaderProgram);

We then tell WebGL to feed our buffer of triangle data through this shader program. To do this, we need to specify how the values in this array of points should be given to the program. We want our point data to be given to the vertex shader as the “coordinates” variable. So we get a handle for this variable and configure the variable. We then select our buffer of data, and use vertexAttribPointer() to specify that the buffer should be divided into groups of two floating-point numbers, and these numbers should be fed into the shader program as the “coordinates” variable.

var coordinatesVar = gl.getAttribLocation(shaderProgram, "coordinates"); gl.enableVertexAttribArray(coordinatesVar); gl.bindBuffer(gl.ARRAY_BUFFER, buffer); gl.vertexAttribPointer(coordinatesVar, 2, gl.FLOAT, false, 0, 0);

Finally, now that we've properly configured everything, we can now instruct WebGL to actually draw something. We tell it to take the three (x,y) points in our array, feed them through the shader program, and draw the result as a triangle.

gl.drawArrays(gl.TRIANGLES, 0, 3);

So this is the end of the pre-tutorial. To include anything more would turn this into an actual tutorial.

Here is part 1 of the pre-tutorial in case you missed it.

WebGL Pre-Tutorial, Part 1

2011-11-06T21:16:00.000-05:00

I've recently tried to learn WebGL, and it turns out that it's pretty complicated. Most of the tutorials that I've found on the web have been geared towards getting the learner doing 3d as quickly as possible by skipping over a lot of details. This is probably what most learners want, but I find that this approach doesn't suit my learning style. I, personally, want to understand the details so that I can write my own 3d code instead of haphazardly cutting and pasting together code snippets that I've found on the Internet. People who just want to do 3d as quickly as possible would probably be better served by using a higher-level 3d graphics engine. The purpose of this pre-tutorial is to fill in some of the details that are left out of other WebGL tutorials. This should make it easier to understand what the code in those tutorials is trying to do. I will try my best to keep the explanations of this pre-tutorial as simple as possible, but WebGL is inherently a pretty low-level API, so it helps if people have some limited systems and 3d programming experience first.

WebGL is the JavaScript version of the 3d library OpenGL ES 2.0. OpenGL ES 2.0 is targeted as a low-level 3d API for phones and other mobile devices. Unlike the full OpenGL for desktop computers, OpenGL ES 2.0 leaves out support for high-precision numbers, which are mostly needed for scientific computation or engineering design, and it leaves out support for a lot of older library calls that aren't used in modern 3d programs. Despite this missing functionality, OpenGL ES 2.0 and WebGL are still great for games, and they are designed to provide good performance on modern 3d graphics hardware.

WebGL is designed for a hardware architecture like that shown below:

The architecture assumes that a machine's graphics hardware is separated from its CPU. The graphics hardware likely has separate memory from the CPU. The graphics processing unit (GPU) specializes in running multiple copies of a single program at the same time. Unlike a normal CPU, these programs must be small and simple, but a GPU can run many, many copies of these programs simultaneously, making it faster than a normal CPU for graphics tasks. With this sort of hardware architecture, one of the biggest bottlenecks for fast 3d programs is the communication between the CPU and GPU.

The general design philosophy of WebGL is based on the idea that this communication between CPU and GPU should be minimized. Instead of repeatedly sending instructions and graphics resources from the CPU to the GPU, all of this data should be copied over only once and kept on the GPU. This minimizes the communication that needs to happen between the CPU and GPU. The communication that does happen is batched together into clumps so that the GPU can work independently from the CPU.

WebGL Graphics Model

WebGL presents a certain abstract model of how the graphics hardware works to the programmer. In the WebGL graphics model, the window or area where 3d graphics are displayed is modeled as a cube. The (x,y,z) values of one corner of the cube is (-1,-1,-1), and the values of the opposite corner are (1,1,1).

An x value of -1 refers to the left side of the window while an x value of 1 refers to the right side of the window. Similarly, a y value of -1 refers to the bottom of the window while a y value of 1 refers to the top of the window. Different z values refer to how close or how far an object is.

You create graphics by drawing triangles in this cube. If you provide the 3d coordinates of the three corners of a triangle, WebGL will draw them on the window. Since the sides of the cube refer to the sides of the window, WebGL will chop off any parts of the triangle that fall outside of the cube.

Triangles are a little limiting, and it takes a lot of communication overhead to transfer all the triangle coordinates from the CPU to the GPU. To overcome this problem, WebGL offers two mechanisms for programming how these triangles are displayed.

The first mechanism is called the fragment shader. When drawing the pixels that make up a triangle, WebGL runs a little program for each pixel that says what color the pixel should be. You can have the triangle be a single color, rainbow-colored, or even a complex pattern.

The second mechanism is called the vertex shader. The main purpose behind the vertex shader is to reduce the amount of communication between the CPU and GPU. Suppose you have a complex 3d model made up of lots of triangles, and you send all of these triangles to the GPU to draw them. If you then want to move the model over to the left a little bit, you would normally need to change the positions of all the points of all the triangles and then send all those new coordinates from the CPU to the GPU. This is a bit wasteful because the coordinates of all those triangles are already stored at the GPU. You just wanted to move them a bit, but you had to send all the coordinates a second time. With a vertex shader, you can send a program to the GPU that will enable the GPU to rewrite the coordinates of all the triangles itself. This means you only have to send the triangles of the 3d model once, plus a little program for moving the coordinates of the triangles.

So the WebGL graphics model can be thought of as a pipeline that processes triangles through different stages. You initially provide WebGL with some triangles to draw. The triangles can be moved around and shifted by vertex shader programs. Any triangles that fit within the cube at (-1,-1,-1) and (1,1,1) will be drawn. WebGL does this by running a fragment shader program for each pixel of the triangle to determine which color to draw there.

Part 2 of the pre-tutorial demonstrates some code for a very basic WebGL program.

Arabic Support in Java

2011-09-24T21:07:00.001-04:00

So a few months back, I started working on an Arabic version of JavaScript, which required me to figure out how to write an Arabic Java program. To my surprise, Java actually has pretty lousy support for BIDI and Arabic.

Now, I always suspected that the old Sun severely understaffed its Java UI group and I always had this odd feeling that their UI programmers never actually programmed any real applications using their UI frameworks. The fact that Java, the major enterprise programming language of the last decade, still doesn't properly support Arabic even after all these years of development just tells you everything you need to know right there. IBM/eclipse, with its SWT UI framework for Java, has had proper Arabic support for a long time now. Instead of doing everything alone, why didn't Sun get help from others when developing Java? Why? Mind you, they rely heavily on proper OS support for Arabic while Java's Swing framework is designed in such a way that they have to reimplement Arabic support from scratch. And the Unicode character encoding was specifically designed so that text processing of Unicode is easy but the handling Unicode in a GUI is the most awfully complicated piece of code possible. But still, we're at Java 7 now, and they should have been able to get this basic piece of infrastructure supported by now.

It makes me wonder which programming languages computer science students are taught in the Arab world. It can't be Java. What's the point of learning a programming language that can't properly handle the input and display of your native language? I guess it must be C# or something.

Anyway, this is what I found. I was working in Windows in Java 6, so my observations may be specific to this combination.

In AWT, I tried setting the text direction using applyComponentOrientation(), but I could never get that thing to work. The text always stayed left-to-right using AWT widgets. In both AWT and Swing, there's a setLocale() method, but I have yet to figure out whether that method actually does anything. I suspect it doesn't do anything. So basically, I don't think there's any BIDI support in AWT. This is somewhat annoying because Windows has reasonable BIDI and Arabic support, so if Java simply passed on this text orientation information from AWT to Windows, then we could simply use AWT for our UIs, and everyone would be happy. Unfortunately, it doesn't.

In Swing, the applyComponentOrientation() method did seem to properly set the text orientation, so there's some good support for bi-directional text there. Unfortunately, for Arabic text, you also need support for text numeric shaping. Although some Arab nations use western number symbols (which, as you probably know, are called Arabic numerals, which makes things nice and confusing for everybody), most Arab nations have their own number symbols. Unicode, in its infinite wisdom, decided that these symbols will actually be encoded in character streams as western digits 0-9, but the UI will be responsible for automatically substituting in different number shapes when the characters are actually displayed. The Java graphics libraries actually have some support for numeric shaping when displaying text, but it's sort of broken. Java doesn't automatically extract region and locale information from the OS, so it defaults to guessing which numeric shapes it should use. If the string you're displaying starts with numbers, there's no initial context for the numeric shaper to use in guessing which number forms to use, so it will default to Western shapes. Also, the Java numeric shaper only reshapes numbers and forgets to reshape the decimal point and thousand separator. I tried a release candidate for Java 7, and this problem was still there. Does anybody at Sun/Oracle actually use their UI framework in real applications? Anyway, even this broken support for numeric shaping isn't actually enabled in Swing, so you can't display numbers in Arabic. In the Java 7 release candidate, programmers could manually enable Arabic numeric shaping in rich text widgets (i.e. JTextArea), but it wasn't clear whether that support was also added to other widgets like JButton or JLabel, etc. In any case, given the brokenness of Java numeric shaping, that isn't exactly a big win.

So in the end, if you want to build an Arabic GUI in Java, use SWT. Eclipse now has a free GUI builder available called Window Builder, and even though I didn't actually know any SWT, I was able to throw together a SWT GUI in a couple of hours with almost no work. GUI builders are awesome. Previously, I was always concerned that I would lose some flexibility in the code I could write, but the one in Eclipse is a real dream and saves a lot of time. I really should have paid money to buy one years ago.

Getting Type 1 Postscript Fonts from pdflatex

2011-08-13T00:36:00.000-04:00

For the past several years, I've been using pdflatex to generate PDFs from my LaTeX, and it usually works like a charm. All modern versions of pdflatex correctly use type 1 (vector) postscript fonts and not type 3 (bitmap) fonts.

Just today, I was generating a PDF for a camera-ready, but whenever I looked at the list of fonts in the document, I kept seeing type 3 fonts there. I couldn't figure out where those type 3 fonts were coming from. I initially thought they might be from some figures, but that ended up not being the case. After playing with my document for a while, I discovered that the problem was that I was using some non-English characters, which was causing problems for LaTeX. Apparently my default installation of LaTeX had type 1 fonts that only covered the standard English character set (plus some accents). When I used characters like French guillemets quotation marks, LaTeX would need to use type 3 fonts because those were the only versions of the fonts with those characters. Using \usepackage[T1]{fontenc} did nothing since my LaTeX installation simply didn't have the necessary fonts.

Fortunately, there is a package called cm-super that seemed to contain the necessary fonts. I couldn't figure out how to coax my Fedora TexLive distribution to download this package, so I tried to grab it in Windows using MiKTeX. Unfortunately, the package is fairly large, and MiKTeX kept killing my computer while trying to download it. The download would start quickly, but gradually slow down to a crawl while my cpu utilization would go upwards. I suspected MiKTeX was doing something silly like storing the file in memory, but in a linearly expanding buffer of some sort. My Thinkpad X61t has always had heat problems, and running with high cpu usage for such long periods kept causing my laptop to overheat and die before the download would finish. Fortunately, I was able to download the packages plus some index files directly from a mirror, and get MiKTeX to load the package locally instead of from the Internet. Some people also needed to do the usual MiKTeX oddness to get things to work right afterwards.

But everything seemed to work ok once I had cm-super installed. My PDFs contained only type 1 fonts. I really don't have a strong understanding of why cm-super isn't included in my default LaTeX installation. Are the fonts too big? Is the quality of the fonts not as good as the default ones? I have no idea. But it looked ok to me, so I'm going with it.

How to Use Constructors and Do Inheritance Properly in JavaScript

2011-05-08T15:53:00.000-04:00

With all my complaints about how difficult it is to find good documentation about how to do inheritance properly in JavaScript, I thought it might be useful to write a blog post about it, so then it would be easier (for me, at least) to find information about the topic.

Constructors

So, let's suppose you have a program, and you need to have a Student object. Students have a name and an array of courses that they are taking. The quickest way to create a Student object is to use the object literal syntax:

var student = { 
   name: 'Joe', 
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};

If you need to create many Student objects, you can simply create a function that creates them for you:

function makeStudent(student_name) {
   return {
         name: student_name, 
         courses: [],
         addCourse: function(course) { courses.push(course); } 
      };
}
var student = makeStudent('Joe');

You can also use a constructor function, which essentially does the same thing:

function Student(student_name) {
   this.name = student_name;
   this.courses = [];
   this.addCourse = function(course) { courses.push(course); };
}
var joe = new Student('Joe');
var ann = new Student('Ann');
var sue = new Student('Sue');

There is a small problem with using constructors in this way. When you create many Student objects, the same name, courses, and addCourse properties show up in each Student. Everything still works, but it's not as efficient as it could be.

To make things more efficient, we need all the Student objects to share some properties instead of having separate, identical properties in each Student. For objects to share properties, we need to make use of JavaScript prototypes. In JavaScript, every object has a prototype object. When you read a property, JavaScript first looks if the property exists in the current object, if it doesn't, JavaScript then looks to see if the property exists in the chain of prototype objects. When you write to a property, the property is changed in the current object and not the prototype. Different Student objects can share the same prototype. Initially, all the properties of the prototype will appear as properties of the Student. As the Student objects change, they will get their own versions of the properties.

What all this amounts to is that prototypes are useful for describing the initial, "prototypical" view of what a certain type of object should look like. Over time, objects will change and stray from looking like the prototype, but that's fine.

For our Student example, let's first create a generic Student object that can serve as a prototype.

var studentPrototype = {
   name: 'Generic Name',
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};

Now, in order to create objects that have this object as a prototype, you need to set the prototype field of a constructor function. When you create an object using the constructor, the constructor will set the prototype of the object to whatever its prototype field is set to. It can be a bit confusing. Setting the prototype field of a function does not change the prototype of that Function object. In general, JavaScript does not provide a variable where you can set or get the prototype of an object. You have to do it all indirectly by using these constructor functions.

var studentPrototype = {
   name: 'Generic Name',
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};
function Student() {
}
Student.prototype = studentPrototype;

Now, when you create Student objects using the constructor, you will get objects that share a lot of fields.

var joe = new Student();
var ann = new Student();
var sue = new Student();

As you set the names of the Student objects, the prototype remains the same, but the name property of the individual Student objects will be set. This name property in the individual objects essentially "overrides" the name property of the prototype.

joe.name = 'Joe';
sue.name = 'Sue';

You can also set the name inside the constructor function, which will give the same result:

var studentPrototype = {
   name: 'Generic Name',
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};
function Student(student_name) {
   this.name = student_name;
}
Student.prototype = studentPrototype;

var joe = new Student('Joe');
var sue = new Student('Sue');

Unfortunately, a problem happens though when you start dealing with courses.

joe.addCourse('math');
alert(sue.courses);

Somehow, Sue ends up enrolled in the math course, even though the course was only added to Joe. It seems that when modifying the courses property, the property of the prototype gets modified and not of the Joe object. Since all the Student objects share the same courses property of the prototype, it looks like Sue is taking math.

The problem is that the courses property of Joe is never written to. When addCourse is called, the method reads the courses property and gets an array. The "math" course is then added to this array. The array is modified, but the courses property is never written to, so Joe ends up modifying the prototype's array of courses instead of creating its own copy that isn't shared. To get around this problem, we should create a new array of courses for each Student, and assign it to the courses property in the Student constructor function.

Constructors Summary

When you want to create many objects with the same structure, you should use constructors and prototypes. You should take all the properties of these objects and divide them up into

properties that are constant and that can be shared between different instances of an object (i.e. methods)
properties that are unique to each object and that can be different in each object (i.e. data fields and pretty much everything that isn't a method)

Constant properties should be put into the prototype of the objects while the other properties should be set in the constructor function.

So suppose we want to be able to make multiple Student objects:

student = { 
   name: 'Joe', 
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};

The method addCourse is the same between all Student objects, so it should appear in the prototype. The other properties will be set in the constructor.

var studentPrototype = {
   addCourse: function(course) { courses.push(course); } 
};
function Student(student_name) {
   this.name = student_name;
   this.courses = [];
}
Student.prototype = studentPrototype;

var joe = new Student('Joe');

Inheritance

Inheritance in JavaScript is less useful than in class-based object-oriented languages. JavaScript has a dynamic type system, so inheritance is not used to indicate which objects share the same interfaces. Inheritance is only used in JavaScript for code reuse. If you have many different objects that all have the same interface (e.g. in a graphics system, you might have objects for different shapes like lines and circles, and these shapes all understand a draw command), these objects do NOT need to inherit from the same base object unless these objects share code for implementing these interfaces.

The easiest way to think about inheritance hierarchies in JavaScript is to ignore it and to simply focus on the concept of prototypes.

Suppose we have a program that makes use of Student objects, which have the fields name and courses in addition to a method called addCoruse, as in the previous section:

function Student(student_name) {
   this.name = student_name;
   this.courses = [];
}
Student.prototype.addCourse = function(course) {
   courses.push(course);
};

Some of the students are special because take their courses via the Internet. For these students, we not only need to know their name and the courses they are taking, but also their e-mail information so that lectures and homework can be e-mailed to them. We'll use an InternetStudent object to represent these types of students.

function makeInternetStudent(student_name, student_mail) {
   return {
      name: student_name,
      courses: [],
      addCourse: function(course) { courses.push(course); },
      email: student_email,
      sendEmail: function(subject, body) { ... }
   };
}

To make a constructor for an InternetStudent, we need a prototype that serves as a good initial template for what an InternetStudent object looks like. Since an InternetStudent shares most of the properties of a Student object, we can use a Student as the prototype.

function InternetStudent() {
}
InternetStudent.prototype = new Student('GenericName');

There are two new properties in an InternetStudent that aren't in a Student: an emailfield that varies from student to student and a constant sendEmail method. The field should go in the constructor function while the method should be added to the prototype.

function InternetStudent(student_name, student_email) {
   this.name = student_name;
   this.email = student_email;
}
InternetStudent.prototype = new Student('GenericName');
InternetStudent.prototype.sendEmail = function(subject, body) { ... };

As in the section on constructors, you have to be careful when dealing with prototypes that you don't accidentally share data structures between different objects. In the above example, the courses array is shared between all InternetStudent objects because they all use the version in the prototype even though each InternetStudent should get their own separate array.

If you recall, the prototype contains all the properties of an object that shouldn't change between different objects while the constructor function initializes the properties that do change from object to object. The constructor function for Student objects creates new name and courses properties for each Student object. We can use that function to create new versions of these properties in the InternetStudent through constructor chaining:

function InternetStudent(student_name, student_email) {
   // Chain the constructor
   Student.call(this, student_name);

   // Initialize the fields that are unique to InternetStudent objects
   this.email = student_email;
}
InternetStudent.prototype = new Student('GenericName');
InternetStudent.prototype.sendEmail = function(subject, body) { ... };

var john = new InternetStudent('John', 'john@example.com');

And we're done.

Inheritance Summary

Inheritance is used for code reuse in JavaScript. In JavaScript inheritance, instead of using a plain Object as a prototype in a constructor, you create some other type of object to use as a prototype base instead.

As always with prototypes, you have to be careful not to accidentally share data structures in your objects. This is especially important when inheriting from something other than a plain Object because you may not know all of the internal data structures of the object you are inheriting from. If you are careful to initialize all non-constant data fields in your constructor functions, you can use constructor chaining to properly initialize these inherited internal data structures.

JavaScript Constructors Were a Mistake and Should Be Removed

2011-04-04T14:33:00.000-04:00

For a long time now, I've been uncomfortable with JavaScript's syntax for constructors, but I could never quite figure out what was wrong with them. They always seemed sort of cumbersome and rigid. In fact, for most of my code, I created my objects almost exclusively using the object literal syntax instead of using constructors. The object literal syntax for creating objects simply seems so natural and spontaneous in comparison to using constructors.

JavaScript constructors simply feel like a weird hack. They're normal functions except you call them with new. In fact, all functions have extra fields for tracking prototypes that are only used when you use functions as a constructor. It also seems incongruent that JavaScript objects are not class-based and can be dynamically changed at any time, yet you're expected to put all your object construction code in one place in a single function. I would personally avoid using JavaScript constructors in all situations, but you can only make use of inheritance and reuse if you use constructors.

But constructors just end up feeling even more cumbersome once you start using them for inheritance. Theoretically, the inheritance model of JavaScript is very simple. Every object has a prototype object. When you use a property, JavaScript first looks if the property exists in the current object, if it doesn't, JavaScript then looks to see if the property exists in the chain of prototype objects. But when you actually go about trying to use inheritance in JavaScript, everything suddenly becomes really complicated. Every time I want to use inheritance, I always end up having to search on the Internet for tutorials about how to do it because it simply never sticks in my mind. There's something with the way constructors and inheritance are implemented in JavaScript that somehow makes the simple concept of prototype inheritance completely confusing to me. If you search for "JavaScript inheritance," you end up with all sorts of weird frameworks for abstracting away the inheritance process. It's actually somewhat hard to find good documentation on how to do inheritance (actually, the Mozilla docs that I linked to are very confusing as well because their description of constructor chaining is hard to grasp). I think that part of the problem is that the using constructors to create objects simply doesn't fit well with the prototype model of objects. If I'm creating an abstract base object that other things will inherit from, why do I need to create a constructor for allowing anybody to create multiple instances of that object, then use that constructor to make a single instance, and then inherit from that one instance? It just seems weird that if I want a single Employee base object that other objects will inherit from, I need to create an Employee constructor object, create the Employee, and then use this instance as a prototype in other constructor functions.

After many years of having these JavaScript issues gnaw at me, I've recently started to realize that my unease with constructors and inheritance wasn't a problem with me but a problem with JavaScript. Constructors are simply a mistake in the language and should be removed. It is, of course, impractical to literally remove constructors from the JavaScript language, but they should be deprecated, and all documentation should cease to mention them in reference to objects. JavaScript constructors attempt to impose a class-based object model onto JavaScript, but JavaScript is prototype-based, so it simply doesn't work. Because JavaScript is somewhat inspired by Java, there was an attempt to bring in some Java's object syntax into the language, but Java's constructors simply don't work in JavaScript. And I know that people really want class-based inheritance in JavaScript as evidenced by the fact that people keep trying to add class-based inheritance into JavaScript, but class-based inheritance doesn't exist in JavaScript now, so there's no point in trying to fit a square peg in a round hole. Fortunately, ECMAScript 5 has a new Object.create method that offers a reasonable alternative syntax for creating objects. This method can also be retrofitted into older versions of JavaScript as well (albeit with a performance penalty).

When using Object.create() to create objects, the code for creating an inheritance hierarchy then ends up closely matching the inheritance hierarchy itself:

Employee = {
      department : '',
      giveBonus : function(bonus) {...},
      handleVacation : function() {...},
   }

WageEmployee = Object.create(Employee, {
      wagePerHour : 10 
   });

SalaryEmployee = Object.create(Employee, {
      salaryPerYear : 50000 
   });

When you need to create multiple instances of the same type of object, you can still create a function to do that, instead of an explicit constructor.

function createSalariedEmployee(name, salary) {
   var emp = Object.create(SalaryEmployee);
   emp.name = name;
   emp.salaryPerYear = salary;
   return emp;
}

Sometimes you need to do constructor chaining in order to handle state that cannot be safely be stored in a prototype. For these situations, I would suggest having an initialization method in each object that can be chained (similar to Smalltalk conventions).

Employee = {
   __init__ : function(name) { this.name = name; },
   department : '',
   giveBonus : function(bonus) {...},
   handleVacation : function() {...},
}

WageEmployee = Object.create(Employee, {
      __init__ : function(name, wage) {
         Employee.__init__.call(this, name);
         this.wagePerHour = wage;
      } 
   });

var newEmployee = Object.create(WageEmployee);
newEmployee.__init__('John', 10);

I think this approach for creating objects is less confusing than using constructors. It's definitely a lot cleaner for singleton objects and for abstract objects. It may not be that great for flat hierarchies, where programmers want to create many instances of the same object, but it's not a big loss there either.

Scaling Up the Transitway

2011-04-01T00:30:00.000-04:00

I was recently late for a train and had to rush across Ottawa from the west-end to the train station.Unfortunately, what is normally a quick dash across downtown on the Transitway turned into a grueling crawl. Most of the pain is entirely self-inflicted though. The Transitway buses ran on dedicated bus lanes through downtown, so the buses didn't have to weave through waves of cars. No, the problem was that there were just too many buses. The Transitway is used above its capacity, so during rush hour, the Transitway becomes a long line of bumper to bumper buses. The Transitway in downtown is just a single lane, so there's no passing of other buses, and every bus needs to stop at the bus stops, and then stop at the traffic lights, so you have to wait ages for every bus in front of yours to move forward a bit, load and unload passengers, wait at the light, and move on. If there are five buses in front of yours, you have to wait in turn for each bus to stop, board passengers, and then move on. It's brutal.

Given these capacity problems, it's clear to me that the current model for how to run buses along the Transitway through downtown just isn't very efficient any more. Ideally, more bus lanes would be provided downtown, but that isn't going to happen. The LRT through downtown will solve the capacity problems, but it'll be many years before that gets built, if ever. Until then, it would be nice if we could find some way to scale up the capacity of the Transitway a bit so that it can be used more efficiently.

I think it's time to remove the express buses from the Transitway in downtown. I know that one of the main advantages of a Bus Rapid Transit system like the Transitway is that people can take one bus from downtown and have it zip along a transit corridor, leave the corridor, and then deliver people directly to their houses. Transit users don't have to transfer, and they can time their arrivals at bus stops so that they don't have to wait around much. Unfortunately, insufficient capacity on the Transitway through downtown makes this model extremely inefficient. Traveling through downtown takes much too long, and all the traffic makes the arrival times of buses unpredictable. Previously, I've complained that Larry O'Brien's plan for having an underground downtown train line to be silly because it eliminates the advantage of express buses (i.e. no transfers) and makes it impossible for transit users to cross the city efficiently. But I'm now thinking that he might have been on to something. The capacity problems in downtown are so bad that the amount of time needed to get through downtown is beginning to outweigh the advantages of being able to take a single bus home from downtown. Having 20 different express buses all lined up with each one having to stop to let a few people on board, delaying all the buses behind it, just doesn't work. Instead, there should be single bus crossing downtown that moves people to a bus station/terminal where people can then transfer to their express buses. If there's only a single cross-downtown bus available, it would be more efficient because bus users would all simply board onto the first bus that arrives, and they'll fill the bus to capacity. There'll be no need to have a long line of somewhat full express buses inching across downtown. These cross-downtown buses could then deposit passengers off at large bus stations with bus loops where there's space for buses to stop and wait for large numbers of people to board buses. Hurdman and Bayview probably make the most sense as these bus transfer points. This proposal is similar to the initial phase of the current LRT plan in that there'll be a high capacity transit system just for downtown which focuses only on moving people to transfer points outside of downtown where people can transfer to buses for the rest of their journeys home.

It might also be possible to improve the efficiency of the downtown portions of the Transitway by having some sort of preboarding system. Other BRT systems do this, where they treat their bus systems like a subway. People have to pay before boarding a bus, and go through a turnstile into a loading/unloading zone. Then, when the bus comes, people can just jam themselves into the bus from whatever door is available since everyone in the loading/unloading zone has already paid. As a result, the loading and unloading of buses can be done faster.

HTML5 Audio is Still Too Immature to Use in Games

2011-02-18T16:19:00.000-05:00

I made a little HTML game a year and a half ago that made some basic use of HTML5 audio, and it worked well enough, but it was very finicky, but I could see HTML5 audio eventually being useful once it matured.

Recently, I reprogrammed an old XNA game I wrote into HTML5 (I never want to go near XNA coding or the XNA community ever again), and I was hoping to program a much more extensive audio engine for the game. Unfortunately, I found HTML5 audio support to be just as finicky as before. Apparently the iPhone/iPad can't play more than one audio stream at once, meaning you can't play music and sound effects at the same time, so it's not possible to make HTML5 games that work well on the iPhone and iPad (basically, all of Apple's talk about HTML5 being superior to Flash on the iPhone and iPad was just propaganda and not reality). Firefox doesn't play short audio files, so the bips, clicks, and other sounds for button presses won't play. Chrome (and possibly Safari too) will not let you play an audio file more than once unless you serve the file from certain types of web servers. The audio in Chrome just sort of dies out after a while anyway, so you don't get any sound after a while. The Internet Explorer 9 Release Candidate seems to only support mp3 files for audio, and using mp3 files in games requires the payment of a licensing fee of $2500 to the mp3 licensing guys. So basically, it's not possible to build a very basic, reliable sound engine for HTML5 games right now.

This struck me as strange though because there are plenty of HTML5 demos and games that have extensive sound support. How can they pull off reliable sound while I can't?

They cheat, of course. All of these games make use of one of these common JavaScript sound libraries like SoundManager2. The dirty little secret is that these libraries will always use Flash for their sound unless Flash support isn't available. Flash is able to offer reliable, solid sound support across many platforms, so developers are able to build solid sound engines for their HTML5 games on top of it. If you try using pure HTML5 audio, things just fall apart.

Perhaps by this time next year, it will be possible to build a pure HTML5 game with good sound and graphics. I haven't used Firefox 4 yet, but I have high hopes for it. Until then, I think Flash is still the only viable platform for online games.

GWT Isn't a Good Environment for HTML5 Games

2011-01-31T01:48:00.000-05:00

Last year, I made a small game in XNA. No one played it, so I've started porting it to be a web HTML5 game. Since the game was originally written in C#, I decided that the easiest way to webify it would be to rewrite the code in Java and then use GWT to translate the code into JavaScript. GWT is a set of tools from Google that let you write web code in statically typed Java. It then translates this code into cross-browser JavaScript for you.

After quickly discarding the GWT UI framework, I found GWT experience to be much smoother and much nicer than I had originally expected. Unfortunately, I've found that the current incarnation of GWT (GWT 2) doesn't work well for HTML5 games. The problem is that in development mode, GWT doesn't actually translate any of your code into JavaScript. It runs all of your code as regular Java, and then uses an intermediary layer to transfer manipulations of JavaScript objects or the DOM to a browser where the manipulation is done and the result transferred back to the Java world. Initially, I thought this wasn't a big deal because it only causes problems if you make an outrageous number of DOM API calls or decide to store a lot of things in JavaScript objects for some reason. Unfortunately, I found I was doing this alot in my HTML5 game. I was drawing lots of things to the HTML5 canvas, which requires lots of API calls. I was also using JSON for my save game data, which means you have to store a lot of data in the form of JavaScript objects.

As a result, my game code ran really sluggishly when run in development mode. This was especially true of Chrome whose sandbox design means that the Chrome GWT development plugin is particularly slow in transferring data between the browser and Java code. Doing my development with Firefox made things bearable, but I still found that I was optimizing things incorrectly. Things that seemed to be slow when running in development mode (e.g. the JSON game saving code appeared so slow that it would timeout the browser) were actually instantaneous when the code was properly compiled down to JavaScript. The overhead of interfacing Java code with a brower's JavaScript engine simply distorts performance information so much that it's hard for a developer to get a good feel for how a game behaves.

I understand why GWT is designed in this way. Most browsers don't expose JavaScript debugger APIs that would let a tool like GWT map lines and variables in JavaScript code to the original Java code that a programmer has written. Fortunately, browsers like Firefox are becoming mature enough platforms to have such APIs, so I'm hopeful that in the future, someone might reprogram GWT to actually translate Java code into JavaScript when in development mode and still let you properly debug it.

In the meantime, I'm going to finish coding up my game in GWT, and then go back to pure JavaScript games. I find the complete freeform, unstructured nature of JavaScript to be unproductive, but I'm wondering whether the static typing of Java is the best way to solve the problem. When I used to code in Smalltalk, everything was also dynamically typed, but it was a fairly productive environment to code in. Smalltalk organizes your code in a very structured way though, so it was easy to navigate the code and find things in it. Currently, the style of JavaScript code that I write is too freeform that even Eclipse with JDST can't analyze it too well and can only provide me simple ways to browse it. Perhaps I'll try writing my code in a more structured style to see if a proper code editor can extract useful structure from it, thereby allowing me to navigate and code JavaScript code more productively.

Rhino JavaScript security

2011-01-05T16:29:00.002-05:00

My programming website programmingbasics.org contains a Java applet with a code interpreter for running user code. Users will not only run their own code, but possibly code from other people as well, meaning that they might be exposed to malicious code. The user is kept safe though because the code interpreter runs as part of an applet, meaning everything runs within the Java security sandbox.

For many years, I've been planning on making a standalone-version of my applet that can be easily downloaded and run as an application, but I've been concerned about security issues. I want user's to be able to run random code that they've found on the Internet without having to worry about the code infecting their systems with something. Without Java's applet security sandbox, my application would have to create its own sandbox. I always assumed that with Java's multiple layers of security, that I would be able to cobble something together. In the end, due to a convoluted API design, it seems that Java's security system is much less flexible than I had originally thought, meaning it's not really possible to do something like lower your own security permissions or to chroot yourself. I think the actual security mechanism in the VM could support this, but the APIs that Java exposes don't let you access such functionality.

The main security issue that I'm trying to protect against is that I want to let users run potentially malicious code in the interpreter. This interpreter has to call into my own code to access certain features. I'm too lazy to properly secure all of my own code, so I want to sandbox the interpreter code from my own code so that potentially malicious code can't muck around with the public fields of my objects and play with my inner classes to trick my code into doing something unsafe. So basically, I need a mechanism that allows me to take part of my own code, declare that I don't trust myself, and lower my permissions for that portion of code.

Based on what I can understand from the security documentation I've read, there are two primary mechanisms that Java uses to secure itself. The first is a namespace mechanism where different threads can be given access to only certain classes (or different versions of classes). This initially sounded like a great way of separating out my code from the interpreter code. My code would simply not be visible to the interpreter code, meaning that I wouldn't have to bother securing my own code. I would only have to create a hardened API for interfacing the interpreter with my own code. The second mechanism is a permissions mechanism where every class has an associated set of permissions. Whenever a potentially dangerous operation is being performed, the permission framework will go through the stack, find the class/code on the stack with the lowest set of permissions, and only allow the operation to proceed if the permissions are sufficiently high to allow it. So for my interpreter thread, as long as I could create a class with no permissions and then slip this class at the base of the interpreter thread's stack frame, then the interpreter wouldn't be able to do malicious things.

So with these two mechanisms, I could use permissions to prevent the interpreter from doing anything bad and use namespaces to prevent the interpreter from tricking my own code into doing bad things. Unfortunately, although this sounds theoretically great, I couldn't quite make the Java APIs do this for me. It seems like the API was mainly designed so that the Java VM and library could secure itself in applets. If programmers want to use the same mechanisms to secure their own code, you have to jump through a lot of hoops. The main problem seems to be that the Java VM loads the application's code with the system class loader. This means that the application code is basically considered to be as trusted and as secure as Java library code. You can't easily create a new thread with a new namespace with fewer classes and where existing classes are relabeled with lower permissions. It's probably possible to do some crazy classloader voodoo where my code is packaged in a separate jar and the interpreter is in its own jar and then a special bootstrap jar will piece together the other jars in some sort of secure way, but it's messy, hard to debug, and hard to distribute all these jars to end-users (I think this is how Java application servers do their security though).

If I spent enough time thinking about class loaders, I might be able to figure out a way to solve it, but I was able to put together a solution that presumably has similar security but doesn't require so much mental gymnastics. The interpreter I use for programmingbasics.org is the Mozilla Rhino JavaScript engine. The interpreter has a ClassShutter which restricts which Java classes that user scripts can have access to. Assuming that the Rhino interpreter is properly secured, then setting the ClassShutter to prevent access to any Java classes should prevent user code from accessing my own insecure code except through well-defined and secured APIs. This should provide equivalent security to namespaces. I still made use of the Java permissions security mechanism, but that only required me to find a way to use class loaders to load a single class with reduced security. Basically, I created a class that implemented a proxy for java.lang.Runnable and compiled it by hand. I renamed the resulting .class file to a .bin so that the system class loader wouldn't prevent my class loader from seeing the file. I then created a classloader that would intercept attempts to create that class and create a version from the .bin file instead with lower permissions. In order to make sure you use the version of the class loaded by the custom class loader (the one with reduced permissions) and not the system class loader (the one with full permissions), you have to carefully use reflection to get the class loader to load its version though. When creating the interpreter thread, I start the thread off by running this class, thereby inserting these lower permissions at the base of the interpreter's stack frame.

Getting the Rehearsal Timings for Multiple Slides in PowerPoint

2010-11-15T12:11:00.003-05:00

When practicing a presentation, you can have PowerPoint record how much time each slide takes using rehearsal mode. Although PowerPoint shows the time for each slide in the slide sorter and in the transition information, I couldn't figure out how to get the total time for multiple slides. This is useful when you want to find out how long different sections of the presentation are so that you know if you are spending too long on certain parts. In the end, I just wrote up a quick PowerPoint macro to do it (just select some slides in the slide sorter and then run the macro to tell you the total time needed for the selected slides):


Sub TotalSlideTiming()
  Dim pres As Presentation
  Set pres = ActivePresentation

  Dim slides As SlideRange
  Set slides = ActiveWindow.Selection.SlideRange
  TotalTime = 0
  For Each s In slides
      TotalTime = TotalTime + s.SlideShowTransition.AdvanceTime
  Next s

  minutes = TotalTime \ 60
  seconds = TotalTime Mod 60

  msg = Str(minutes) + "m " + Str(seconds) + "s"

  MsgBox msg

End Sub

Public Transit in Ottawa in the Age of Cars

2010-11-10T13:18:00.013-05:00

This blog is supposed to be mainly about coding, but for engineering-types, the efficient movement of people around a city is always an interesting puzzle, so though this blog post is off-topic, I don't think it's uninteresting (note: I'm not a transit expert; I'm just a transit fan who likes shouting out like a blowhard).

Well, anyway, now that there's a new(ish) mayor of Ottawa, there's been a lot of newspaper articles about whether the old mayor's light rail (LRT) plans should be continued or scrapped. Personally, I always thought that the old mayor was pretty dumb (or at least naive) regarding transit. It takes decades to put together transit plans and get contracts signed, so for the old mayor to cancel the original light rail contracts when he got elected was stupid. The plans may not have been perfect, but it was better than nothing, and by canceling the contracts, the mayor left the city with nothing for at least another decade (the electric light rail line proposed by the old plan sure would have been useful when gas prices went through the roof!). I always assumed that the new light rail plans proposed by the old mayor would be impractical, and everything I heard about it seemed to confirm that. But with all the talk in the newspapers, I finally took a glance at Ottawa's 2008 transportation master plan, and I can now definitively say that it's a bad plan. It's a boondoggle that will cost a fortune but not actually improve public transit at all. It was obviously designed by a car driver who took a look at some other cities, became impressed with the shiny trains and subways, and decided that Ottawa should get them too, without any thought about money, efficiency, or political realities.

The reality is that this is the age of the car. In the age of the car, trains only make sense in certain limited situations. It does not make sense to copy the transit systems of Europe because those cities were built before the age of the car. It does not make sense to copy the transit system of large North American cities because those cities are larger than Ottawa, and those cities evolved before the age of the car. Ottawa grew big during the age of the car, and it built a transit system appropriate for the age of the car with its Bus Rapid Transit (BRT) Transitway. As a result, Ottawa is now a leader in designing transit systems for the age of the car, and Ottawa can't really look to other cities for patterns to copy because most other comparable cities to Ottawa are behind it, not ahead of it. Ottawa must innovate in order to come up with appropriate solutions to its transit problems.

Cities that developed during the age of the car are notable because people live all throughout the city, and they might work all throughout the city. It's the urban sprawl model of urban development. It is true that cities in the age of the car still have a downtown core where a large minority of the population work, but it's definitely not New York where masses of people commute from the suburbs into downtown. In the age of the car, people on the east side will work in an industrial park on the west side, people in downtown will work at a shop in the south, or people in the south-end will work in the south-west. To be useful, public transit shouldn't take everyone to a central hub or to simply move people between two points--it has to be able to take a person from anywhere and move them to anywhere in a reasonable amount of time. The hub and spoke model doesn't work in the age of the car, public transit needs to provide a network or lattice that can move people from anywhere to anywhere. Buses are the most appropriate transit option in the age of the car because they can easily go anywhere in the city, and they can use dedicated busways to go long distances quite quickly. LRT is an obvious choice if you already have a bunch of unused rail lines sitting around (Ottawa dug up its rail lines a long time ago) or if you have a lot of extra money that you can splurge on indulgent infrastructure (Canada hasn't had extra money for decades). If those conditions don't hold, then you have to be a lot more strategic in when you build LRTs.

So although I love trains, you can't let the romanticism of trains influence your decisions. In reality, trains are expensive. In modern medium-sized cities, it almost always makes more sense to use buses for public transit than trains. As far as I can tell, these are the factors that must be considered in evaluating new transit projects:

Do the proposed lines go anywhere interesting? In particular, they should go among high density residential, commercial, and industrial districts containing people who are too poor to own cars. Some rail advocates argue that a train station magically makes a place an interesting destination. I think this is false. In the age of the car, a train station can add to the attractiveness of an area, but you can't build something from nothing. If a real estate developer has a choice between building a condominium tower in a place with good amenities and car access (which is good for the 70% of a city's population who are car drivers) or building a condominium tower in a place with nothing except for a train station (which is only good for the 30% of the population who are either prefer a lifestyle where they are within walking distance to amenities or who are too poor to own a car let alone a condo), I think they'll skip over the train station. They may build a slightly taller apartment building in a place if there's a train station there though. It's also important that transit lines go through as many interesting places as possible due to the network effect. A line going from point A to B can carry people from A to B or from B to A. A line going from A to B to C can carry people from A to B or C; or from B to A or C; or from C to a or B (that's six combinations vs. two). A line going between more locations allow for a lot more possible journey combinations, making the line a lot more useful.
How long is the waiting time? I think the rule of thumb is that transit riders feel that waiting for transit feels twice as long as it actually takes. So if you have to wait 10 minutes for a bus, then need to waiting another 5 minutes for a bus transfer, you'll feel like you wasted 30 minutes of your life even though you spent only 15 minutes waiting. As a result, a good transit line should minimize transfers and have vehicles that come often.
Capacity: a line should have enough capacity to handle the expected ridership. Trains can potentially carry more people than buses, and they can board passengers more efficiently than buses. Ottawa does have a capacity problem in the downtown area in that the roads cannot handle the number of buses that pass through the area.
Cost of construction: The cheaper the better. Also, exotic technology should be avoided at all costs. When you build any piece of infrastructure, you end up having to rebuild it every few decades as part of the maintenance. If you use standardized technology, you benefit from lower costs due to mass production since everyone else in the world is using the same technology. If you use exotic stuff, you have to pay elevated prices to rebuild the same custom, exotic stuff every few decades.
Cost of operation: the most successful transit lines are the ones that make money (in reality, I don't think any transit line in world supports themselves without subsidies or financial wizardry--though they probably pay for themselves indirectly by improving the efficiency of the economy and reducing the need to build highways). Electric trains have a lower operating costs than buses because they require fewer drivers and can hold more people. There's a bit of a trade-off needed to get this lower operating cost for a train though--you save money by running fewer trains than buses, but that means that people have to wait around longer for trains than for buses. It's not clear to me how mostly empty trains or diesel trains compare to buses in terms of costs. Again, exotic technology like hybrid buses, diesel-electric trains, etc. often end up costing more money in the long run.
Speed: I think the speed hierarchy is bus/streetcar, bus/tram with dedicated lanes, bus/lrt with dedicated lanes and traffic priority, busway/dedicated rail line, bus/lrt with grade separation (i.e. tunnel, trench, or elevated line), automated underground trains. As far as I can tell, trains do not go any faster than buses. The main determining factors in the speed of transit are whether a line is separated from car traffic and how many stops there are on a line.
Risk minimization through diversification: things go wrong, so it's useful to have a backup plan. With trains, people are always throwing themselves onto the line or whatnot, and that leads to the whole line being backed up. Buses are often useful in that you can reroute them around traffic incidents. With multiple possible routes serving an area, a transit system can more easily withstand problems such as accidents, long construction projects, blackouts, demonstrations, etc.
Every phase of the project must provide an incremental benefit: The reality of big infrastructure projects is that they often get canceled due to lack of money or a change of politicians. Although politicians can make 10-20 year plans, the plan usually only survives for 3-5 years. If that first phase provides significant benefits, then if you're lucky, the other phases might get funded. So each phase must be nicely self-contained and provide a benefit in and of itself.

So given these criteria, this is why I think the 2008 transit master plan for Ottawa is a waste of money:

Do the proposed lines go anywhere interesting? No. The proposed LRT will follow the existing Transitway line, so it won't provide access to anywhere new.
How long is the waiting time? Wait times will be longer, especially during its construction. Anyone crossing the city will need to make two additional transfers.
Capacity: the LRT should solve the capacity problems on the downtown portion of the Transitway.
Cost of construction: Any sort of grade separation like a tunnel will cost a fortune
Cost of operation: I imagine the number of passengers will be high enough that the cost of operation will be lower than running buses along the Transitway.
Speed: As far as I can tell, there's no reason to believe that LRTs will be faster than buses along the Transitway. Any speed-ups will be solely due to the tunnel through downtown. This tunnel will probably save about 5-10 minutes per trip that goes through downtown.
Risk minimization through diversification: the LRT means Ottawa is actually increasing its risks of unusual disruptions. With buses, you can reroute buses around problems. Although a tunnel will mean fewer disruptions due to traffic, the use of trains means that every time someone throws themselves onto the tracks (I imagine it'll happen once every month or two), the whole system will grind to a halt.
Every phase of the project must provide an incremental benefit: This is the big weakness of the plan. The proposed new LRT system only works if the whole thing gets built. If you only build the first phase, you actually end up with a worse system than you started out with. Let's say you build the LRT tunnel and then you run out of money. You've then spent a billion dollars building a train that doesn't go anywhere. Basically, you'll end up with a train that crosses downtown. Ottawa is not Toronto. There isn't enough density in downtown Ottawa to support a train that only goes from one of the downtown to the other. For people in the suburbs, you have to catch a bus for one part of your journey anyway, so it simply makes sense to stay on the bus and ride all the way to or across downtown. The only way to get them to ride the train would be to force them--bus journeys would purposely have to halt at the edge of downtown and everyone would be forced to transfer to a train. People going from the west end to the east end would have to make two transfers if not more. It's just a disaster. The LRT only works if it's long enough to stretch across the city, but I seriously doubt the funding will last that long.

So in my opinion, the proposed LRT plan involves spending two billion dollars to build a train that doesn't go anywhere new but simply cuts travel times by 5-10 minutes. Of course, if a problem develops in the plan and it isn't completed, Ottawa will instead end up with a train that increases everyone's travel times by 5-10 minutes due to increased transfers. This plan just seems like a huge risk and a huge cost with only a small possible benefit. If the risks or the costs were small, then it might be worthwhile. If the possible benefits were huge, it would also be worth it. But this plan has too many negatives. The old mayor used to claim that making transit faster would get more people to use it. This is one of those delusions by car drivers that they would switch to using transit if it could be made faster than driving. This is, of course, totally ridiculous. It's pretty much impossible to make transit faster than driving, and most people still wouldn't switch.

Of course, I have to admit that solving this transit problem is tricky. The most pragmatic plans aren't necessarily the ones that are politically feasible. I also don't have the numbers about costs and ridership, so I can't really make well-informed proposals. But in the interests of being constructive, I'll throw out some completely uninformed suggestions.

The primary transit problem that needs to be addressed by Ottawa is that the city has reached the capacity for buses in downtown. Any transit plan needs to address this problem. It would be nice if a proposed transit plan also provides other benefits, but the current system will run fine for another decade or so as long as the downtown problem is resolved. Although everyone wants to get rid of the Transitway through downtown, this is simply not an option in the next few decades. BRT is the fundamental backbone of the Ottawa transit system. If you mess with it, you might break the entire system, and that's too risky. So all planning decisions must start with the assumption that the Transitway will continue to go through downtown for the foreseeable future. Starting from that assumption quickly narrows down the number of feasible plans for solving the downtown capacity problem:

A grade separated busway through downtown (it doesn't have to be a tunnel--a trench or elevated line might be cheaper and less risky) should probably be enough to solve the capacity problems because you can have really long bus platforms without having to be limited by the size of city blocks and traffic lights. Travel times through downtown would also probably decrease by 5-10 minutes. This plan would be expensive though and not very glamorous, so I'm not sure that it's politically feasible to go this route.
A supplemental bus transit line through downtown to pull traffic off of the Transitway. Expanding the downtown portion of the Transitway into a four-lane bus highway would probably work but would never get political support. Having a second bus rapid transit line would probably also work (it would be something like buses that eventually go north or south will run along Laurier while east-west buses will continue to use Albert and Slater), but I don't think it would work politically either.
Any supplemental downtown transit line would have to be light rail to be politically viable. One advantage of LRT is that it's easier to drum up support for them. Car drivers would rise up in arms if you converted part of a busy road into dedicated bus lanes. But if you convert part of a busy road into a dedicated LRT, people will often grudgingly agree (though they'll mutter about Toronto streetcars the whole time). A surface light rail line would probably be sufficient because it's cheaper and the LRT only needs to serve enough capacity to bring down the Transitway bus traffic to reasonable levels. Unfortunately, a short LRT will hardly have any traffic at all--though riders might save 3-5 minutes by taking the LRT through downtown instead of riding the bus, they'll lose all that time by needing to transfer to a bus later for the rest of their journey. You need to have a long LRT to have any hope of getting reasonable ridership. There's a problem with placement of the line though. Running an LRT along the Transitway probably makes the most sense, but is probably politically infeasible because Ottawa was originally going to do this back in 2006 but it was canceled out by the old mayor. It would look bad to simply revive the old plan. One possibility is to run a LRT along Carling and then through south downtown or centretown, and then somehow possibly down Montreal road. This LRT configuration would serve underserved neighbourhoods that are good candidates for densification, which will help drum up political support for the plan. It'll be comparatively cheap as a surface rail line. It would hopefully pull traffic from the Transitway though I admit that there's no guarantee about that. It also provides a nice diversity of transportation options for people in downtown. It wouldn't be very fast though.
Some percentage of the traffic on the Transitway through downtown is caused by people traveling through downtown but not actually stopping there. It might be possible to pull some of the traffic off of the Transitway by developing the O-train into a proper diesel commuter train. The O-train can be extended both south past the greenbelt and north into Hull (not that anyone expects much ridership to/from Gatineau with only a single station, but until there's an actual train station on the other side of the river, no one in Gatineau is going to make appropriate transit plans that incorporate that possibility. Plus, responsibility for the O-Train can then be dumped on the NCC and outsourced). There's a bit of a risk that a commuter train will lead to more urban sprawl, making transit problems worse, but these sorts of risks are impossible to predict. It might also be worthwhile to build an experimental commuter train line that runs from Orleans, to the Via train station, to Billings Bridge, and then up to Bayview. I'm not sure if the O-train line has the capacity and signaling to handle the traffic though.
It might be possible to gamble that the future development of the city will lead to a change in traffic patterns as jobs and housing start distributing themselves more evenly around the city instead of having the jobs mostly be in downtown and housing mostly be in the suburbs. In that case, it makes sense to ignore the problem in downtown and focus on making sure that there is a sufficient lattice of BRT lines crisscrossing the city to allow for the efficient movement of people from anywhere in the city to anywhere. If that is the case, it might make sense to create a Transitway ring around the city (possibly two--one inside the Greenbelt and one outside).

MVC is not Elegant, It's the Only Thing that Works

2010-10-30T16:35:00.001-04:00

I was doing some Swing programming over the summer. Although I've long been familiar with MVC concepts and although I've been doing Swing programming almost since Swing first came out, it was only this summer when I *really* started understanding MVC.

In the past, I always understood MVC in terms of "elegance." Designing UI frameworks using MVC concepts supposedly resulted in a more elegant design. One could easily change the look of a component and reuse behaviours in different widgets. Separation of presentation from data and control logic led to a cleaner design where orthogonal issues would be stored in different places in the code instead of all grouped together.

In fact, this is all wrong. People don't use MVC because it is elegant. People use MVC because for certain user interfaces, MVC is the only design that works. As such, you don't have much choice. If you have a UI design that allows for two views on the same piece of data, you need MVC (for example, if you have two word processing windows open on the same document--so when you type things in one window, these changes should be reflected in the other window as well). Once you need to support this situation in a UI, then MVC just naturally falls out.

If you have two windows for editing the same data, you need code to let the user edit data: that's the controller.
You need to store the data in one spot (not separately in each window) or else it will get out of sync in the two windows: there's your data model
Finally, whenever the data changes, it needs to update both windows to reflect the changes: that's the view

Once you want to support two views of the same piece of data, the reasoning behind MVC becomes obvious. MVC is not elegant. In fact, for simple UIs that only need to support a single view on a piece of data, MVC is unnecessarily complicated. MVC exists because it is the only design that works for complicated UIs. They really should state this outright in documentation instead of rambling on about this elegance nonsense.

Double-Click Detection in IE and Other Browsers

2010-10-11T17:58:00.003-04:00

Several months ago, I wrote some code for cross-browser support for double-click detection. It was sort of tricky to put together, so I should I have posted it, but I forgot. But here it is:

function hookIEDblClickToClickCatcher(object, handler)
{
   var isDown = false;
   var isMismatchedUp = false;
   object.onmousedown = function() { isDown = true; isMismatchedUp = false; };
   object.onmouseup = function() { if (isDown) isDown = false; else isMismatchedUp = true; };
   object.ondblclick = function() { if (isMismatchedUp) { handler.call(this); isMismatchedUp = false; } };
   object = null;
}

The general idea of this code is this. You might add an onclick handler to some HTML element in JavaScript. But then you notice that, in IE, if people click an object repeatedly (like in a game), every 2nd click counts as a double-click and is ignored. So you want to register a double-click handler and have that also trigger a click event.

The problem is that this results in too many clicks for non-IE browsers. Other browsers trigger both a click event and a double-click event on the second click of a double-click, so in total your click handler ends up triggering three times. So what you want is a way to trigger a click handler on a dblclick for IE only (but you don't want IE specific code in case IE changes its behavior in the future).

Fortunately, IE has a distinctive sequence of mouse down and mouse up events that lets you detect an IE double-click vs. the double-click of other browsers (there is no mouse-down event before the double-click event).

Data URI Test

2010-10-11T11:19:00.003-04:00

In games, I want to use data URLs for images, but IE only supported this type of URL starting with IE8. Here is some code for testing for URI support. You supply a callback function, and it will be given a true or false value depending on whether data URIs are supported or not (the data URI used is a 1x1 transparent GIF--I couldn't really find anything smaller).

function testDataURLSupport(callbackfn)
{
  var img = new Image();
  img.onload = function() { callbackfn(true); callbackfn = null; };
  img.onerror = function() { callbackfn(false); callbackfn = null; };
  img.onabort = function() { callbackfn(false); callbackfn = null; };
  img.src = 'data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==';
}

Scrolling Games in JavaScript

2010-10-10T18:47:00.007-04:00

So I'd previously tried to program a game in JavaScript with a scrolling background, and repeatedly encountered performance problems. In the background of the game was about 100 images, positioned absolutely, that had to scroll as the player moved. These images were part of a larger map involving thousands of image tiles, so not all of the images could be created in advance--images that were not visible had to be removed and new images had to be created as for map tiles coming into view.

All the benchmark information available at the time talked a lot about how innerHTML to create new objects was much faster than manipulating the DOM by hand in JavaScript. This makes sense. JavaScript is slow, but in most browsers, DOM objects are separated from JavaScript by heavy COM or XPCOM abstraction layers, so if you can minimize the number of DOM calls you make, that should make your JavaScript faster. Based on this reasoning, I initially wrote my scrolling code by erasing all my objects and creating replacements with a single innerHTML call. Unfortunately, this was really slow (too slow for most games), but I was too busy to work out a better approach.

I recently found some time to take a second look at this, and I found that the performance issues were more comlex than that. In fact, there is an overhead for manipulating the DOM, but it's actually not too bad. Creating (and to a lesser extent deleting) DOM objects involves a much larger overhead. Also strange is that IE8 is much slower than IE6 for a lot of this DOM manipulation (probably because it's properly synchronized etc.).

So the correct way to create a scrolling background is not to restrict oneself to a single DOM call. Instead, to scroll a bunch of images, it's fastest to go through each image and move each one by an appropriate amount (by using divElement.style.left = '?px'). It results in hundreds of DOM calls, but it's much faster than creating new images. I was thinking of creating some sort of complicated DOM hierarchy, so that I could move multiple images with a single DOM call, but that wasn't necessary--moving each image individually was sufficiently fast. Of course, you need to create new images and remove old ones as new areas come into view or move out of view, but the performance saved by creating fewer new HTML elements counteracts the cost of the extra DOM calls.

So some quicky benchmarks reveal that when 100 moves of around 25 tiles, 128x128 in size, in 5 pixel increments take this amount of time (in milliseconds) :

IE8 with innerHTML complete refresh of all objects	14563
Chrome with innerHTML complete refresh of all objects	5843
FF3.5 with innerHTML complete refresh of all objects	10918
IE8 with simple move elements around	1919
Chrome with simple move elements around	605
FF3.5 with simple move elements around	1691
IE8 with simple move elements and reusing old elements	1641

This means that it's probably possible to do simple games in IE8, so there's no immediate need to switch to using canvas and restricting oneself to non-IE browsers. I'm hoping that developers won't program their HTML5 games using only the canvas element because I think more traditional methods are sufficiently fast and more compatible. In fact, if I do move to use HTML5 features, I'm vaguely thinking of going with SVG, but I'll have to see how the performance evolves.

Miscellaneous Java Swing stuff

2010-07-08T15:47:00.008-04:00

I was doing some Java Swing coding over the summer, and I found that there were a few issues that took a lot of time to figure out due to insufficient documentation, so I thought I would dicuss the solutions that I eventually found here. (Note: I started writing this post in July, but I only finished writing this post at the end of October)

One thing that has bugged me about clipboard operations is how to efficiently support an Edit menu in the menu bar with cut/copy/paste menu items. If a user selects cut, how is the UI supposed to know where to cut from? Do you need to write some sort of crazy handler that tracks which UI widget last had input focus, and then if that widget supports cut operations, perform the cut there? In fact, Swing has classes to do this. If you only support cut&paste operations in text widgets, then there's a TextAction class you can use. I think if you want to support more than text widgets, you might be able to use TransferHandler.getCutAction()---though I haven't investigated this second option too deeply, but I think it automatically performs a cut operation on the last widget that supports clipboard operations through a TransferHandler interface.

Another thing that bugged me with Swing is that in the Windows Look and Feel, the JTextArea defaults to using a fixed size font. This is a little bizarre because the AWT TextArea doesn't use a fixed size font, and the JTextArea using the default look and feel doesn't use a fixed size font. I would normally just set the font of a JTextArea to something else, but I couldn't find sufficient information in Swing about how to do this properly. In order to change the font, you need to specify a font size, but what size is appropriate? You can't use a "reasonable" value like 12pt, because the user might have configured their OS to use extra large fonts. Operating systems usually provide an area where you can look up information about which default font should be used in user interfaces, but it seemed like Swing didn't provide access to such information. In the end, the best compromise I could find was to grab the font used in JTextField widgets and apply them to the JTextArea. Presumably, Swing will configure JTextField widgets to use an appropriate font based on a user's settings, so applying this information to a JTextArea will give you a reasonable default. It's not a great solution, but it will have to do until this bizarre JTextArea problem is fixed (it's been there for many, many Java versions though, so I doubt it will be fixed any time soon) or until Java comes with a default look & feel that isn't so confusing and disorienting (even I have problems using the file dialogs in the default metal l&f).

Another thing that I had a hard time finding in the Java documentation is how newlines/linebreaks are handled in a JTextArea. Do they use the platform defaults? If you save the contents of a JTextArea to a file, do you have to manually convert between CR, CR/LF, and LF in order to get things in a neutral format? This is all nicely documented, but it is stored in an unusual spot.

Finally, the last Swing issue that took me a long time to figure out was how to support a JTextArea that you can resize horizontally, but which will grow vertically as you type into it. So for the purposes of word-wrapping, it behaves like it has a fixed width, but you should still be able to change that width by resizing the window. A normal understanding of the Java UI layout model suggests that this isn't possible. The preferredSize()/size()/minimumSize()/maximumSize() model can't handle things that sometimes have a fixed width but expand downwards, but sometimes lets you change the width, resulting in a different height for the widget. In fact, if you code up a JTextArea with no scroll bars but with a layout manager that can control the width of the widget, it works fine. Apparently, Java has various hacks for supporting this sort of setup, so it just works.

Upgrading from Windows Vista to Windows 7

2010-06-12T15:39:00.003-04:00

I recently did an upgrade from Windows Vista to Windows 7, and I encountered a few difficulties with the install process, which I documented here.

Windows Mail is Missing

In Windows 7, they removed Windows Mail. Although Windows 7 can still run the Windows Mail program, the upgrade process will uninstall Windows Mail, which is somewhat annoying (I'm not sure where the Windows dev team started having the great idea of uninstalling functionality that was working fine before the upgrade, but I think the new Windows team has some weird priorities that previous Windows teams didn't seem to have).

During the upgrade process, Windows 7 will tell you that it will keep your old Windows Mail settings around, and it will be easy to install Windows Live Mail Desktop later. This is untrue. Windows Live Mail Desktop will automatically import your old Windows Mail settings only if it detects that you have Windows Mail. Of course, Windows 7 uninstalls Windows Mail, so Windows Live Mail Desktop will not automatically import your old settings. So if you use Windows Mail in Vista, you should install Windows Live Mail Desktop FIRST, have it pick up all your old settings, and then upgrade to Windows 7 SECOND.

If you didn't do this, then you have to manually re-enter your account settings, then import your old mail from C:\Users\[userid]\AppData\Local\Microsoft\Windows Mail, and then go into contacts to import your old contact list from Windows Contacts.

East Asian Handwriting Recognition

The whole reason I upgraded to Windows 7 was because the Chinese Handwriting Recognition was a little flaky. It didn't integrate properly with Internet Explorer and Google (it kept losing focus and changing its language), and it was hard to resize the input panel, etc (it, oddly, seemed to work fine in Firefox though). I was hoping that they finally fixed this problem in Windows 7. And they did. They removed East-Asian Handwriting Recognition support from Windows 7. Instead, they want me to shell out an extra $150 for Ultimate in order to get access to this feature, which they removed during my upgrade to Windows 7. To the product manager who earned a nice bonus for thinking of this way to increase Microsoft's revenue: "Thanks a lot, asshole." I remember a time when Microsoft was mean and dangerous, but at least they would try to do right for their customers. Nowadays, their main areas of innovation seem to be finding fiendish ways to increase revenue.

Fortunately, Windows 7 still includes limited East Asian handwriting recognition in the IMEPad (to be removed in Windows 8, no doubt). And it seems to work more reliably than in Windows XP or Windows Vista. The instructions for enabling the Chinese handwriting recognition in IMEPad are the same as for Vista.

No Going Back

I was so annoyed with losing all this functionality during the upgrade that I was going to revert my upgrade back to Windows Vista. Windows has a long history of allowing you to undo even really invasive Windows upgrades (e.g. you can uninstall Windows XP and revert back to Windows 95 after such an upgrade). But, apparently, they stopped providing this functionality ever since Sinofsky took over the Windows Vista team (it might also be related to Windows Activation). So I'm stuck with it. I'm starting to think this will be the last Windows upgrade that I will ever do though, so I'm not too annoyed.

PowerPoint 2007 VBA Macro for Expanding Custom Animation into Multiple Slides (for Export to .PDF)

2010-04-11T12:36:00.006-04:00

When I make presentation slides, I like using a lot of diagrams to explain algorithms, and often I use animations to show the different processing stages of these algorithms. In the past, I would just make a different slide for each stage in an animation sequence, but this gets tedious when I have to make lots of edits to a slide (I then have to go back and change all the slides in the animation sequence). So I started using the custom animation feature of PowerPoint, but when PowerPoint exports a presentation or prints notes, it sticks all of the animation elements on a single slide, so it's not possible to follow the animations in an exported presentation. This is especially important when exporting to PDF so that I can put my presentation online or so that I can have a backup copy of the presentation around in case there are portability problems with PowerPoint.

There were a couple of scripts online for doing this (here and here), but I wanted to write my own because one of them came with an installer, which I don't like, and the other one seemed too limited. Figuring out how to write my script ended up being more difficult than I expected though. I've programmed a few things in Visual Basic for Applications (VBA) before--the standard way to write macros for Office--but I vaguely remembered that when designing Office 2007, Microsoft said that it would be phasing out VBA in subsequent versions in preference for Visual Studio .Net. In fact, the record VBA macro feature (a common technique people use to program initial macros) wasn't even included in PowerPoint 2007. Programming things in .Net is a bit of overkill when you just want to write a little macro that's easy to distribute, so that wasn't feasible either. I thought about writing a little VBScript or JavaScript/JScript script that would do what I wanted, but then I found out that Microsoft was deprecating the whole ActiveScripting framework as well. Since the new Office file format OOXML is supposedly XML, I thought about just reading in and modifying the files directly, but after playing with the files a bit, I found that OOXML is very much an XML dump of the legacy Office file formats. There are all sorts of crazy cross-links between the different sub-files inside an OOXML zip file that it's impossible to read and modify a small part of the file without breaking it. In order to modify it properly, you really need to read and parse the whole thing into an intermediate form, modify it there, and then write a new file from scratch, but this is clearly too much work for a little script. I briefly considered making my presentation in OpenOffice instead, and I actually would have if the OpenOffice people had bothered to add in a couple of extra features into their application instead of simply making a brain-dead clone of Office (e.g. like being able to animate the color changes of individual words of text instead of being restricted to paragraphs only), but I was beginning to like the automatic text sizing and animation number indicators of PowerPoint 2007.

After much digging around though, I found out that Microsoft had changed their mind and decided not to deprecate VBA after all. Starting with Office 14 / Office 2010, Microsoft has renewed their commitment to maintaining VBA. So I wrote a little VBA script to split up an animation into multiple slides. I believe my script handles all entrance and exit animations, but I haven't really tested this. It makes use of Office 2007's new API for exposing the different sub-parts of an animation, which should allow a script to handle new animations in a more uniform way. Unfortunately, this new API is still somewhat broken, so it needs various error-handling code to handle anomalies like SetEffect objects without any properties etc.

To use the script, go into PowerPoint 2007, go to View...Macros, create a new macro called "ExpandAnimations", replace the macro code with the code below, and then run it.


Private AnimVisibilityTag As String


Sub ExpandAnimations()
AnimVisibilityTag = "AnimationExpandVisibility"

Dim pres As Presentation
Dim Slidenum As Integer

Set pres = ActivePresentation
Slidenum = 1
Do While Slidenum <= pres.Slides.Count
Dim s As Slide
Dim animationCount As Integer
Set s = pres.Slides.Item(Slidenum)

If s.TimeLine.MainSequence.Count > 0 Then
    Set s = pres.Slides.Item(Slidenum)
    PrepareSlideForAnimationExpansion s
    animationCount = expandAnimationsForSlide(pres, s)
Else
    animationCount = 1
End If
Slidenum = Slidenum + animationCount
Loop
End Sub

Private Sub PrepareSlideForAnimationExpansion(s As Slide)
' Set visibility tags on all shapes
For Each oShape In s.Shapes
oShape.Tags.Add AnimVisibilityTag, "true"
Next oShape

' Find initial visibility of each shape
For animIdx = s.TimeLine.MainSequence.Count To 1 Step -1
Dim seq As Effect
Set seq = s.TimeLine.MainSequence.Item(animIdx)
On Error GoTo UnknownEffect
For behaviourIdx = seq.Behaviors.Count To 1 Step -1
    Dim behavior As AnimationBehavior
    Set behavior = seq.Behaviors.Item(behaviourIdx)
    If behavior.Type = msoAnimTypeSet Then
        If behavior.SetEffect.Property = msoAnimVisibility Then
            If behavior.SetEffect.To <> 0 Then
                seq.Shape.Tags.Delete AnimVisibilityTag
                seq.Shape.Tags.Add AnimVisibilityTag, "false"
            Else
                seq.Shape.Tags.Delete AnimVisibilityTag
                seq.Shape.Tags.Add AnimVisibilityTag, "true"
            End If
        End If
    End If
Next behaviourIdx
NextSequence:
On Error GoTo 0
Next animIdx
Exit Sub

UnknownEffect:
MsgBox ("Encountered an error while calculating object visibility: " + Err.Description)
Resume NextSequence
End Sub


Private Function expandAnimationsForSlide(pres As Presentation, s As Slide) As Integer
Dim numSlides As Integer
numSlides = 1

' Play the animation back to determine visibility
Do While True
' Stop when animation is over or we hit a click trigger
If s.TimeLine.MainSequence.Count <= 0 Then Exit Do
Dim fx As Effect
Set fx = s.TimeLine.MainSequence.Item(1)
If fx.Timing.TriggerType = msoAnimTriggerOnPageClick Then Exit Do

' Play the animation
PlayAnimationEffect fx
fx.Delete
Loop

' Make a copy of the slide and recurse
If s.TimeLine.MainSequence.Count > 0 Then
s.TimeLine.MainSequence.Item(1).Timing.TriggerType = msoAnimTriggerWithPrevious
Dim nextSlide As Slide
Set nextSlide = s.Duplicate.Item(1)
numSlides = 1 + expandAnimationsForSlide(pres, nextSlide)
End If

' Apply visibility
rescan = True
While rescan
rescan = False
For n = 1 To s.Shapes.Count
    If s.Shapes.Item(n).Tags.Item(AnimVisibilityTag) = "false" Then
        s.Shapes.Item(n).Delete
        rescan = True
        Exit For
    End If
Next n
Wend

' Clear all tags
For Each oShape In s.Shapes
oShape.Tags.Delete AnimVisibilityTag
Next oShape

' Remove animation (since they've been expanded now)
While s.TimeLine.MainSequence.Count > 0
s.TimeLine.MainSequence.Item(1).Delete
Wend

expandAnimationsForSlide = numSlides
End Function


Private Sub assignColor(ByRef varColor As ColorFormat, valueColor As ColorFormat)
If valueColor.Type = msoColorTypeScheme Then
varColor.SchemeColor = valueColor.SchemeColor
Else
varColor.RGB = valueColor.RGB
End If
End Sub


Private Sub PlayAnimationEffect(fx As Effect)
On Error GoTo UnknownEffect
For n = 1 To fx.Behaviors.Count
Dim behavior As AnimationBehavior
Set behavior = fx.Behaviors.Item(n)
Select Case behavior.Type
    Case msoAnimTypeSet
        ' Appear or disappear
        If behavior.SetEffect.Property = msoAnimVisibility Then
            If behavior.SetEffect.To <> 0 Then
                fx.Shape.Tags.Delete AnimVisibilityTag
                fx.Shape.Tags.Add AnimVisibilityTag, "true"
            Else
                fx.Shape.Tags.Delete AnimVisibilityTag
                fx.Shape.Tags.Add AnimVisibilityTag, "false"
            End If
        Else
            ' Log the problem
        End If
    Case msoAnimTypeColor
        ' Change color
        If fx.Shape.HasTextFrame Then
            Dim range As TextRange
            Set range = fx.Shape.TextFrame.TextRange
            assignColor range.Paragraphs(fx.Paragraph).Font.Color, behavior.ColorEffect.To
        End If


    Case Else
        ' Log the problem
End Select
Next n
Exit Sub
UnknownEffect:
MsgBox ("Encountered an error expanding animations: " + Err.Description)
Exit Sub
End Sub

Transportation Simulation Games

2010-03-20T12:14:00.004-04:00

When SimCity 4 was released, I was very disappointed by the broken transportation model, the assumptions built into underlying economic model that resulted in all cities looking like California, and the weird game design that assumed I was more interested in building stories about Sims than about building stories about the city itself. Since then, I became interested in figuring out how the simulations in these games work, but I always got hung up on a small mathematical detail. I finally figured out the problem a couple of weeks ago. Some simple grade 11 math is all you need, but I just couldn't see it until now.

The most intuitive scale to model these simulations at is at the level of individual people. So for each "person" in the city, you code up a model for the person's preferences and behaviour, and you then "run" this model and record what happens. So if a person wants to drive along a road from one building to another, you then increment the traffic on that road segment to account for the person's car. If you simulate enough people, you can figure out the traffic along each street, resulting in a simulation for the entire city.

The problem is that the city is constantly changing and the people being simulated will change their behaviours, so you want to have the simulation running constantly to take these changes into account. This makes the simulation complicated. If your simulator decides that a person will take an alternate route to get to a destination, the simulator needs to reduce the traffic along the old route of the person (since the person no longer drives on those roads) and increase the traffic along the new route. Keeping track of the routes of all these people is complicated, memory-intensive, and slow. If you don't remove the person's traffic from the old route though, then the traffic along the old route will keep on increasing (since there's no way for the traffic to go down to reflect the fact that fewer people are using it).

One solution is to divide your simulation into rounds. In each round, you simulate the actions of all the people in the city once, record the result, and update the UI with these results. Then you start a new round by discarding all the results (i.e. set the traffic of all roads to zero) and running a complete cycle of the simulation again. This approach isn't satisfactory because one cycle of the simulator might take several minutes to complete. So if you change something in the city, it might take several minutes to see the effect of these changes in the simulator because the UI won't be updated until the next simulation cycle.

We want to constantly update the traffic values, but this results in traffic growing without bounds. Resetting the traffic to zero is not practical because we want to be able to display the simulation values as they are updated. What we need is some way to "decay" the traffic along road segments over time. As a result, the traffic along each road segment will constantly decrease, but as you simulate the actions of different people, the traffic along each road segment will increase again. For this to work though, the speed of the decay must be balanced out the speed at which you add new traffic, so that the simulation converges to reflect the correct traffic along a certain road. But I could never figure out the math for this problem. If traffic decays too quickly, then the traffic will be close to zero in most places, but will spike up randomly in places where the new routes of people are being simulated. If traffic decays too slowly, then the total traffic along each road will increase without bound.

Simulating transportation always results in new traffic being accumulated in an additive fashion. i.e. As you simulate the route of one person, the traffic along the route will be incremented by a constant to reflect the traffic of this one person. But the decay must be in the form of a rate. The traffic along a route cannot be decreased by a constant all the time, but by a percentage of its existing traffic (because heavily trafficked routes should have their traffic decreased by a larger amount than lightly-trafficked routes--otherwise the traffic on light routes will fall to zero while the traffic on the heavier routes will increase without bound). Previously, I tried to think of things as being like a physics simulator where the simulator would try to balance things out so that the amount of traffic added by the simulator will be counter-balanced by removing an equivalent amount of traffic due to decay or something like that, but this isn't quite the right thing to do.

In fact, the solution is the geometric series. For example, assume that you don't change your city at all, so that the simulation should converge to a steady-state. So if you simulate all the people in the city, the same amount of traffic will be added will be added to a particular road segment (say, a). If you decay the traffic on any particular road segment by a rate r (let's assume you apply the decay once every time you do a complete simulation cycle of all the people in the city), then over time, this results in a geometric series. Geometric series will converge to a/(1-r). This is exactly what we need! We don't have to fiddle with balancing the rate of new traffic with old traffic or whatever--the geometric series shows that the simulation will converge to nice stable values. And we can then scale a and r to get the convergence rate and overall stability that we want. It all becomes nicely straight-forward.

Background Music in JavaScript without Flash

2010-02-17T17:45:00.006-05:00

So for the last half a year, I've been playing a bit with making larger and more complicated games in JavaScript. I've found a few neat new tricks, but I haven't gotten around to writing about them until now. One thing I figured out is how to play background music in modern browsers without using Flash. This is useful for JavaScript games where you need some music to help set the mood in a game.

So for non-IE browsers, you can use HTML5. Although the APIs seem to work reasonably well, I'm not sure how stable the specification is. There's some occasional weird things in the specification that suggest that the specification is immature. For example, the audio specification makes use of a lot of "boolean attributes" which are HTML attributes that can be defined or not defined instead of simply being true or false (so setting the attribute to false is equivalent to defining it as true). This sort of bizarre, unnecessarily complex, probably XML-incompatible stuff suggests that the specification still contains idiosyncrasies and pet projects of individual developers instead of being polished into a consistent spec. I'd be concerned of a problem like with ECMAScript 4 where once Microsoft and Yahoo! applied some common sense to the specification, a lot of things might end up changing. So I suggest using HTML5 with caution--you should always check to make sure that every method and field that you want to use is supported by your browser before relying on their existence.

Well, anyways, for HTML5 audio, you first need to check if it's supported:

var hasAudio = true;
try {
   var audiotest = new Audio();
   if (!audiotest.canPlayType) hasAudio = false;
} catch (e) { hasAudio = false; }

Every browser supports different audio formats, so you need to make an MP3 version of your files (you can use iTunes for that) for Safari/Chrome and an OGG version (you can use Audacity for that) for Firefox/Chrome. For some reason, the Chrome browser doesn't support WAV files because they claim the files are "too large," and I think this is a clear example of the immaturity surrounding the HTML5 specification in general. There are many good reasons for supporting WAV files in browsers, and for short sound effects, WAV files can even be smaller than OGG or MP3 files. The reason for not including WAV support in Chrome is simply the result of bias and ignorant opinions as opposed to a mature approach to the problem. So anyways, you need to test which background music file to load depending on which formats are supported.

var clip = new Audio();
clip.autoplay = false;
clip.autobuffer = true;
var canOgg = clip.canPlayType("audio/ogg");
var canMp3 = clip.canPlayType("audio/mpeg");
var canMp3Alt = clip.canPlayType("audio/mp3");
var canWav = clip.canPlayType("audio/wav");
if (canMp3 != "" && canMp3 != "no")
   clip.src = mp3File;
else if (canMp3Alt != "" && canMp3Alt != "no")
   clip.src = mp3File;
else if (canOgg != "" && canOgg != "no")
   clip.src = oggFile;
else if (canWav != "" && canWav != "no")
   clip.src = wavFile;

And from there, playing the file is easy (though Firefox 3.5 doesn't support looping music, so you need to do that manually).

clip.addEventListener("ended", function() {
// I'm not sure if this setTimeout() thing is necessary
window.setTimeout(function() {clip.play();}, 1);});
clip.play();

For Internet Explorer, you can use Windows Media Player to play music. First, you have to check to see if Windows Media Player is available using ActiveX:

var hasWmp = true;
try {
   var player = new ActiveXObject("WMPlayer.OCX.7");
} catch (e) {hasWmp = false;

For some reason, when you create the ActiveX object, it isn't bound to your web page properly, so you can't use relative URLs to refer to music files. If you do want to use relative URLs, you actually have to create the player object as an HTML object in your document.

var tmp = document.createElement('div');
tmp.innerHTML = '<OBJECT CLASSID="CLSID:6BF52A52-394A-11d3-B153-00C04F79FAA6"></OBJECT>';
player = tmp.getElementsByTagName('OBJECT')[0];
tmp = null;
if (!player || !player.versionInfo) hasWmp = false;

From there, playing an mp3 file is easy:

player.settings.setMode("loop", true);
player.URL = mp3File;
player.controls.play();

Update 2010-5-3: Apparently, using MP3 files on a web page or in a game requires an mp3 license. In the future, I guess I will only support Ogg Vorbis and let users of Safari and IE endure the silence.

We're Currently in a Golden Age of Literacy, and It's All Downhill from Here

2010-01-22T18:18:00.003-05:00

During the past few months, I've slowly started to notice that a lot of the things that I used to enjoy reading about, I know prefer watching videos about instead. For example, I used to enjoy reading reviews about video games on the web, but recently I'll search for video reviews first, and I'll only fall back to text reviews if I can't find any videos. I'm also starting to do the same for educated political commentary and satire. In fact, if there was enough video content on my favourite topics, I might prefer watching videos to web browsing entirely.

The logical conclusion of all this is that this signals the end of literacy as we know it. Sure, we might now complain about the poor literacy skills of our kids, we decry their unintelligible text messages, and we bemoan their incoherent essays, but ten years from now, we're going to look back on 2010 as a golden age of literacy. It will be considered the pinnacle of literacy in the world--people all over the world actually had to type words in order to find information! People were required to read information and instructions! Children preferred sending messages to each other in the form of text! In between the television age of the 1980s and the Internet video age of the 2020s, the period around 2010 will be considered a renaissance of literacy where people actually had to know how to read and write text to survive in the world!

In ten to twenty years, there will no longer be a need to read and write information; everyone will use video. Instead of web pages, there will be videos. Instead of SMS and tweets, kids will send videos to each other. Instead of textbooks, there will be slides and accompanying video. Society will complain about how kids can't form well-thought out text any more, preferring stream-of-consciousness videos. Kids might now even write text any more but simply make videos, edit it together somehow, and then dump the text out. Similar to how people ignore people talking to themselves in the street (they assume that the person is using a hands-free cellphone) and ignore people checking e-mail during conversations, I think in the future, people will simply get used to the idea of people quietly making short video messages to others in the middle of a meeting (of course, it will seem extremely disruptive to us, but I imagine it's something that future generations will simply get used to).

There are a few weaknesses of video--because it is a linear medium, it's hard to scan through it quickly, so there will still be some text that people will read. This text will mostly be in the form of "headlines," "search results," and "transcripts." When we want to find videos to watch, we'll tell our computer what videos we want to watch (through a webcam, of course!), and the computer will show various video clips with meaningful text headings that we can scan through quickly to find what we want. And every video will have an accompanying transcript (in both text and screencap form) that people can use to quickly jump around to the parts of videos that they're interested in.

I see two impediments to this video future:

patents
speech recognition (specifically video transcription) technology

The main barrier to this future right now are patents on video technology. These patents inhibit standardization (so no two companies can agree on a video e-mail standard or a webcam standard, for example), which prevents a network effect from starting around video technology. The cost and licensing difficulty of patents also inhibit innovation and entrepreneurship in this area. New companies and researchers don't want to develop new ideas in this space because it's too complicated and too expensive to license technology in this area, so the potential rewards (with Internet technology, most of this consumer technology has zero revenue) aren't profitable. I believe this patent issue will work itself out once patents expire or once storage and bandwidth becomes so cheap that we'll just use raw video for everything. The day after a useful video patent expires, a standard for video e-mail will be made (or perhaps there will be some sort of proprietary Facebook thing that comes out before then that everyone will use--unfortunately, it will be a bit of a kludge getting it to work with cellphones and other devices).

The other barrier is the lack of accurate video transcription technology. As I mentioned before, video is a linear medium, so we need a way to search it and to scan through it. The minimum technology we need for this to be practical is automatic video transcription. Currently, speech recognition isn't quite at the point where this is possible, but I imagine this technology will be ready by 2020, perhaps even by 2015 (there might be patent issues on this technology that will delay its widespread use for a few more years).

It's sort of weird knowing that despite all the complaints that people have about literacy in 2010, this is actually the best it's going to get. I'm not sure about the ultimate implications and ramifications of the future age of video on society, but I think it's inevitable, so we might as well start preparing for it now. I suppose other people have also been evangelizing that video is the future, so my musings are perhaps not the most original, but they never tell you that the trade-off is the end of literacy.

Stitching Together Scanned Images

2009-08-30T15:14:00.007-04:00

Recently, I was scanning a lot of legal sized documents, but my scanner could only scan A4 sized paper. So I had to scan each document in parts and then stitch them together afterwards.

There is lots of software available for stitching together photos into a panorama, but surprisingly, I had trouble finding software for stitching together flat images (or for creating a "linear panorama" as some people call it) even though this task would supposedly be a little bit easier than making panoramas. Of course, it's possible to manually load up the images into a paint program and manually align them and blend them, but I had to stitch together a lot of documents, so this was too time-consuming for me.

In the past, I've used software like Hugin, Panotools, or Autostitch for stitching together photos, but I could never quite get the various tutorials on how to handle linear panoramas to work quite right.

I own a copy of Photoshop Elements 6.0, which does contain algorithms for this sort of stitching (under File...New...Photomerge Panorama). Initially, I was quite pleased with the results, but after inspecting the final stitched images more carefully, I began to realize that the algorithm had lots of problems rotating images in order to get good alignment between them. If you only superficially inspect the final result, everything seems fine because Adobe seems to use some sort of fancy blending algorithm (something like Enblend) that hides a lot of these imperfections. Unfortunately, the blending algorithm can't hide the fact that because of poor alignment, lines that should be straight aren't. Even when you manually rotate the images to help the alignment algorithm, Photoshop Elements doesn't help you try to fine-tune the rotation or positioning afterwards, so it's hard to get things aligned quite right (I was hoping that if I could get things close to alignment, the algorithm would "snap" things to the best position). Adobe is always tweaking their algorithms, so it's possible that later versions of Photoshop Elements give better results though.

In the end, I actually found a research tool from Microsoft that provided excellent automated results. Even better, Microsoft's Image Composition Editor was very fast and very easy to use, so I highly recommend this program. Eventually, I hope to figure out what I was doing wrong with Hugin because it's always useful to have an alternative that supports a lot of manual tweaking, but so far the results of the Image Composition Editor have been so good that I've only needed to resort to alternate tools (i.e. Adobe Photoshop Elements) only once, which occurred when I was stitching four images together that had only a small amount of overlap.

Vista Service Pack Installation Problems

2009-06-06T16:21:00.004-04:00

I recently installed Windows Vista SP2, and like Vista SP1, I seemed to have problems getting it installed properly. It would spend a huge amount of time installing itself, reboot, and then fail during its third stage, and then spend a lot of time reverting the install. Windows Update would show Code 80004005 in the error details field for why the update failed.

Fortunately, after browsing the web, I found a forum post (I no longer remember where it is), where people mentioned that the problem comes up with dual-boot machines. My machine has both Linux and Windows installed, and Vista apparently fails its TPM security checks or something like that if the GRUB boot manager starts up in-between the computer starting and Vista starting. Fortunately, I installed GRUB on my Linux partition instead of my MBR, so I could simply change my active/boot partition to boot directly into Windows. Afterwards, the service pack could apply itself, and then I could boot on a Linux live CD to reset the active/boot partition back to the Linux partition.

Personally, I find this sort of annoying. It would be nice if Windows wouldn't die on dual-boot machines or give users a prompt to allow then to ignore TPM problems during the boot process or, at the very least, give more useful error messages.

MTU Problems When Using Vista Internet Connection Sharing (ICS) with an XBox 360

2009-01-24T15:48:00.006-05:00

So like other people, I don't really like the idea of paying $100 for an XBox 360 wifi adapter, so I'm using Internet Connection Sharing through my laptop to get my XBox connected to a wireless access point (yes, there are easier ways of doing this, but like usual, I'm doing something strange).

But when I did this, the XBox kept complaining that my MTU was set too low since it needed an MTU of 1364. This is a little silly since a proper IP stack should automatically fragment its packets to accomodate the MTU, but whatever.

I ran the command netsh interface ipv4 show interfaces to find out what the MTUs on my Vista laptop were, and they were all set to 1300. This seemed a little strange because 1300 is oddly low and also a nice round number that a human must have decided on. But I certainly hadn't set my MTU to 1300, so I'm not sure why it was set to that.

I spent a while browsing around, but finally I figured it out. It was that annoying Cisco VPN client on my laptop. I have no idea why they set the MTU so low (what sort of intermediate router would use 200 bytes of overhead per packet? It's silly to reserve so much), but the VPN Client comes with a Set MTU program that I was able to use to set everything back to normal, and then my XBox stopped complaining.

Running TPC-H Queries on MySQL

2009-01-16T07:37:00.005-05:00

Getting the TPC-H queries to work on MySQL isn't too hard, but it isn't always clear what to do. I took the instructions from here and converted them to work with MySQL.

Once TPC-H is started, you can create a database and tpch account:

mysql -u root -p
mysql> CREATE USER 'tpch'@'%' IDENTIFIED BY 'password';
mysql> CREATE DATABASE tpch;
mysql> GRANT ALL ON tpch.* to 'tpch'@'%';
mysql> USE tpch;
mysql> \. tpch/gen/dss.ddl

Then, in the gen directories, you can modify the query generator to generate queries that are as close as possible to what you need:

cp makefile.suite makefile
#Modify makefile to use
# CC = gcc, DATABASE=SQLSERVER, MACHINE=LINUX, WORKLOAD=TPCH
#In tpcd.h, SQLSERVER section:
# change #define SET_DBASE "use %s;\n"
# change #define SET_ROWCOUNT "limit %d;\n\n"
# change #define START_TRAN "BEGIN WORK;"
# change #define END_TRAN "COMMIT WORK;"
make

Then you can start generating database data at the right scale factor

./dbgen -s 1

And also modify the constraints/indices file so that it's compatible with mysql:

# Modify dss.ri
# use a search and replace in order to remove "CONNECT TO TPCD", remove references to "TPCD." and remove the lines "COMMIT WORK;"

Then you can load all the data into the databases with

mysql -u tpch -p
mysql> use tpch;
mysql> LOAD DATA LOCAL INFILE 'customer.tbl' INTO TABLE CUSTOMER FIELDS TERMINATED BY '|';
# Same with orders, lineitem, nation, partsupp, part, region, supplier
mysql> \. dss.ri

You then need to change the case of the table names because the queries use lower-case table names I think whereas the dss.ddl uses upper-case names for the tables:

mysql> alter table NATION rename nation;
# Ditto for supplier, region, partsupp, part, orders, lineitem, customer

Finally, you can test some of the queries

cp dists.dss queries
cd queries
../qgen -c tpch -s 1 1

I think the queries still need to be modified a bit to be compatible. I think queries with a limit may need the semi-colon moved around, the precision indicator during date arithmetic in query 1 may need to be removed, and the method for naming columns in query 13 might need changing.

Chinese Handwriting Recognition in Windows XP

2008-08-14T01:38:00.003-04:00

If you want to write Chinese characters in Windows XP, there are lots of options available like Google's IME, but a lot of these options aren't practical if you don't know any Mandarin. There are websites for inputting Chinese in Cantonese, but still it isn't ideal.

Apparently, the IME in Windows XP can be upgraded to support limited hand-writing recognition in Chinese, but Microsoft conveniently hides the IME upgrades on its websites. Fortunately, I found a forum, which describes how to download these upgrades from the MS Office website. Once I installed these upgrades, I could then use the IMEPad to write Chinese characters using a mouse or tablet. In fact, the IMEPad option was available in my plain version of Windows XP, but clicking on the IMEPad button did not result in anything happening.

IE7 Erases .XML Files

2008-03-26T23:53:00.003-04:00

So I had spent a few days writing a long .xml file with a corresponding .xsl stylesheet. I was using IE7 to look at the generated html. At one point, I chose Page, then Save As. Then I chose Cancel.

Poof.

IE7 erased my .xml document. Well, I guess I didn't really need the document that badly after all.

Tiles Don't Generalize

2007-12-03T17:31:00.000-05:00

For a couple months, I've been experimenting a bit with SVG during my free time to get a feel for how to use it cleanly on the web. In particular, I've been playing around with trying to create a little tile-based game using SVG and JavaScript.

The nice properties of grid-based tiles using an isometric or 3/4 perspective are well-known. As long as every object in the game fits exactly in a 1x1 grid cell, then everything works great. It's easy to figure out an order to draw the objects in order to ensure that nearer objects properly occlude further objects. You can stack objects within a grid and do other nice stuff too.

After seeing all those isometric-perspective computer games with characters running in-between grid tiles and with all manner of odd-shaped objects though, I assumed that the algorithms for choosing the order to draw objects in the isometric perspective generalized in some nice way. Of course, I realized that things couldn't generalize arbitrarily. If you allowed for arbitrary objects in arbitrary poses, then you'd end up with an arbitrary 3d scene drawn from an orthographic perspective. Then you'd need the full painter's algorithm with polygon chopping etc.

But, I assumed that if all objects were in non-overlapping axis-aligned bounding boxes, then I could figure out some way to order the objects without needing to chop any of them (since you can't really do this is SVG). In particular, I wanted the floor tiles and the objects to be all mixed up in the rendering code. But for the isometric perspective, it is possible to create degenerate examples where objects mutually occlude each other. So you can't generalize algorithms for the isometric perspective this way. In particular, my plan of having floor tiles and wall tiles, plus arbitrarily sized objects sitting on the floor tiles just wouldn't work.

In fact, the same thing happens with the three-quarter perspective as well (I've shifted the perspective a bit so that it's easier to see the depth of the objects).

So having arbitrarily sized objects that can stack on top of each other arbitrarily won't work. Having objects in non-overlapping axis-aligned bounding boxes where all the bounding boxes sit on the same plane, that seems to work ok. With the isometric perspective, it seems like it might be a little bit hard to get the right ordering of objects during drawing, but it seems doable at least. With the 3/4 perspective, everything works out well in that particular situation.

So basically, one way to get around this problem is to have a flat floor and use tiles to cover the floor as one layer, then on a second layer, you can have objects and walls and stuff that you can order separately. I imagine there are other cases that lead to an easy ordering of objects (perhaps if everything has a fixed height? or maybe in the 3/4 perspective, if you allow for only two levels: one for arbitrary height terrain and then another for things on top?), but I haven't really figured it out yet. Perhaps in reality, degenerate cases never really end up occuring, so you can just sort of hack in lots of special cases in the rendering engine to make sure all the objects are rendered in the right order.

Well, in any case, the point of this post is to show that tiles are trickier than I thought. They really don't generalize nicely, so you have to put a lot of thought into how to handle things once you allow for objects that don't fall exactly within grid boundaries.

Resolution Independence in Vista

2007-09-14T11:28:00.000-04:00

I recently got a Thinkpad notebook that crams a 1400x1050 resolution onto a tiny screen. It's a great screen, but unfortunately everything ends up being a bit too small. If you have resolution independent applications, the increased resolution can be a real joy though because the text becomes so clear and easy on the eyes. Although previous versions of Windows had very limited support for resolution independence, things supposedly had improved quite a bit in Vista.

Unfortunately, things don't quite fit together that well. Just like earlier versions of Windows, you can increase the default font size in Vista. Unfortunately, this causes various glitches in things. For example, text no longer fits in the dialog boxes of Windows Media Player (I suspect that the Windows Media Player people must have written some custom dialog box code because I'm pretty sure the default dialog box code scaled things correctly even back during the Windows 95 days). And lots of fonts on web pages are specified in terms of pixel sizes, and their sizes don't get adjusted, so the text ends up being too small to see. Internet Explorer does have a zoom capability that redefines pixel sizes, but it also increases the size of the default font, which has already been increased, making things look too big.

Vista also has the option of simply scaling up all pixels to a larger size. Basically, Windows will fool legacy applications into thinking that the screen has a lower resolution, so that the applications render at a smaller size. This render is then scaled up to fill the larger resolution. Resolution independent applications, however, can render at the full resolution. Unfortunately, Adobe (Acrobat) Reader is considered a legacy application. Being able to read .pdf documents with crisper text is one of the main reasons I chose the high resolution screen, and you lose all those benefits if you render everything to a lower resolution and then scale it up. I imagine the same problem crops up in other applications as well. For example, Internet Explorer doesn't have strong support for vector drawing formats like SVG, so it's not possible to get high resolution graphics on web pages, so you have to live with scaled up versions of bitmaps instead.

Based on this experience, I imagine it will take another few years before it becomes practical to use Windows comfortably on a high resolution display. The new version of MacOS will supposedly have strong support for resolution independence, but I doubt that they've actually managed to solve the problem in a comprehensive manner. I think that doing resolution indepence right probably requires a larger rethinking of UI widgets and layout managers (basically, it will be the same technology needed to layout a single UI design on both tiny mobile device screens and large LCD monitors with needing lots of manual tweaking), but I haven't really heard much about research into that area by Apple, so I doubt they've hit the final solution yet.

Serializing Signals without Atomic Compare and Swap

2007-02-17T10:30:00.000-05:00

So basically, the problem with event handlers in IE6 is that they might become interrupted by other event handlers, making synchronization difficult. What you want is a more traditional event driven model where only one event handler can execute at a time. Essentially, you want a scheme that serializes signals so that the event handlers execute sequentially. Unfortunately, since JavaScript comes with no synchronization primitives like atomic compare and swap, so doing this is messy.

So I think I've come up with a scheme that lets you wrap event handlers in a function that will test if other event handlers are executing at the same time. If they are, it will add itself to a queue to be executed later. There's various annoying synchronization issues involved though, so this is not as simple as it sounds.

Here's the pseudocode for the event wrapper function:


globals root, queue
if root == null
  root := true
  execute own handler
  root := null
  while !queue.empty()
    root := true
    queue.dispatch()
    root := null
else
  queue.add(self)

And here's the pseudocode for the queue methods:


queue.add(fn)
globals end, isClaims[], handlers[], queueLength
myend := end
while(true)
  if isClaimed[myend] != null
    myend++
    if myend >= queueLength
      myend := 0
    if myend == start
      error!
    continue
  isClaimed[myend] := true
  if handlers[myend] != null
    continue
  handlers[myend] := fn
  break
end := myend
 
queue.empty()
globals isClaimed[], start
return isClaimed[start]==null
 
queue.dispatch()
globals isClaimed[], handlers[], start, end, queueLength
if isClaimed[start] != null
  myend := end
  if myend == start
    myend++
    if myend >= queueLength
      myend := 0
    end := myend
  execute handlers[start]
  handlers[start] := null
  isClaimed[start] := null
  start ++
  if start >= queueLength
    start := 0

And here's how you could code it up in JavaScript. Basically, I define a handler function. You can then use the handler function to wrap your own event handlers before setting them to listen for events:


<script>
// Initialization script that creates the "handler" function for wrapping
// handlers
(function () {
  var SIZE = 100;                   // max number of simultaneous events
  var root = false;                 // boolean, indicating whether
                                    // event handler is the first one in a
                                    // chain or not
  var queue = new Array(SIZE);      // Event handlers to be executed later
  var thisQueue = new Array(SIZE);  // Corresponding this objects
  var isClaimed = new Array(SIZE);  // reserves a spot in queue
  var start = 0;                    // position in queue circular buffer
  var end   = 0;
 
  // Define the global handler wrapper function
  handler = function(eventHandler)
  {
    return function() {
        if (root == false) {
          root = true;
          eventHandler.call(this);
          root = false;
          while (isClaimed[start] != null)
          {
            root = true;
            if (isClaimed[start] != null) {
              var myend = end;
              if (myend == start) {
                myend++;
                if (myend >= SIZE) myend = 0;
                end = myend;
              }
              queue[start].call(thisQueue[start]);
              queue[start] = null;
              thisQueue[start] = null;
              isClaimed[start] = null;
              start++;
              if (start >= SIZE) start = 0;
            }
            root = false;
          }
        } else {
          var myend = end;
          while (true) {
            if (isClaimed[myend] != null) {
              myend++;
              if (myend >= SIZE) myend = 0;
              continue;
            }
            isClaimed[myend] = true;
            if (queue[myend] != null) continue;
            queue[myend] = eventHandler;
            thisQueue[myend] = this;
            break;
          }
          end = myend;
        }
      };
  }
})();  // Execute the initialization code
 
function loaded()
{
  alert('loaded ' + this.src);
}
 
var img1 = new Image();
var img2 = new Image();
img1.onload = handler(loaded);
img2.onload = handler(loaded);
img1.src = "test1.png";
img2.src = "test2.png";
alert('done')
</script>

Asynchronous Callbacks in IE6 JavaScript

2007-02-17T10:16:00.000-05:00

Well, back in October, I noticed that Internet Explorer 6 had a few quirks with its usage of event handlers. JavaScript is single-threaded and does not contain any synchronization primitives. As a result, when JavaScript is embedded in a web browser, it is supposed to use an event-driven model: as events occur, they are put into a queue, and then a single thread removes events from the queue and executes handlers for them. Unfortunately, IE6 does not rigorously follow this model. Some of their callbacks follow a model used for interrupts or UNIX signals. Even if another piece of JavaScript code is being executed, the code can be interrupted by an asynchronous event, and the callback for that event will be run. When the event ends, the original code will resume. Unlike signals or interrupts though, IE6 allows these callbacks to interrupt other callbacks.

So, if you put the following code in a web page and run it in IE6, you will get three different dialog boxes showing up simultaneously:

<script>
function loaded()
{
  alert('loaded ' + this.src);
}
 
var img1 = new Image();
var img2 = new Image();
img1.onload = loaded;
img2.onload = loaded;
img1.src = "test1.png";
img2.src = "test2.png";
alert('done')
</script>

I believe this problem was corrected in Internet Explorer 7 because if you run the same code in IE7, you only get one dialog box showing up at a time.

In any case, I think I came up with a solution for this problem back in November, but I never got around to testing it until now. I'll put the code up in my next post.

JavaScript in IE is not Multithreaded

2006-10-25T11:12:00.000-04:00

After coding up my mutex and experimenting with it, I've discovered that Internet Explorer isn't multi-threaded. Instead, it has something worse. Much, much worse.

In any case, here's my mutex code:

function Mutex(maxThreads)
{
 // This mutex is based on the paper "Tight Bounds for Shared Memory Symmetric
 // Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.
 if (maxThreads < 2)
  alert('Mutex is configured incorrectly');
 this.waiting = new Array(maxThreads);
 this.locks = new Array(maxThreads);
 for (var n = 0; n < maxThreads; n++)
 {
  this.waiting[n] = null;
  this.locks[n] = null;
 }
 this.maxThreads = maxThreads;
 this.whoInCriticalSection = null;
 this.turn = null;
 this.get_visible = function(level, retry, me) {  // This is private
  if (level == -1)
  {
   this.waiting[0] = me;
   level = 0;
   retry = true;
  }
  else if (this.waiting[level] != me)
  {
   // Don't write if we can make progress
   if (this.turn != me)
   {
    if (retry)
    {
     // Assume mistake, once
     retry = false;
    }
    else
    {
     level = level + 1;
     retry = true;
    }
    // Make visible again
    this.waiting[level] = me;
   }
  }
  return [level, retry];
 }
 this.enter = function() {
  var me = new Object();  // generate a unique id for this thread
  var level = -1;
  var retry = false;
   while (true)
  {
   // See if lock is available, or if it assigned to me
   while (this.turn != null && this.turn != me)
   {
    var ret = this.get_visible(level, retry, me);
    level = ret[0];
    retry = ret[1];
   }
   this.turn = me;
   var locked;
   while (true)
   {
    // Try to get all locks
    for (var pos = 0; pos < this.maxThreads; pos++)
    {
     if (this.locks[pos] == null)
      this.locks[pos] = me;
    }
    // Do we have all the locks?
    locked = true;
    for (var pos = 0; pos < this.maxThreads; pos++)
    {
     if (this.locks[pos] != me)
      locked = false;
    }
    if (this.turn != me  locked) break;
   }
   if (this.turn != me)
   {
    // Lost, release locks
    for (var pos = 0; pos < this.maxThreads; pos++)
    {
     if (this.locks[pos] == me)
      this.locks[pos] = null;
    }
    var ret = this.get_visible(level, retry, me);
    level = ret[0];
    retry = ret[1];
   }
   else
   {
    break;
   }
  }
  // Acquired lock
  if (this.level > -1 && this.waiting[this.level] == me)
   this.waiting[this.level] = null;
  this.whoInCriticalSection = me;      // Save our id for later
 }
 this.leave = function() {
  var me = this.whoInCriticalSection;  // Get our saved id
  this.whoInCriticalSection = null;
  // Find ID of top waitier or 0 if nobody
  var next = null;
  for (var pos = this.maxThreads - 1; pos >= 0; pos--)
  {
   if (this.waiting[pos] != null) {
    alert('handoff');
    next = this.waiting[pos];
    break;
   }
  }
  // Let them continue, release locks
  this.turn = next;
  for (var pos = 0; pos < this.maxThreads; pos++)
  {
   if (this.locks[pos] == me)
    this.locks[pos] = null;
  }
 }
}

So back to the original point. In the end, JavaScript in Internet Explorer isn't multi-threaded. There's only one thread, but it can be interrupted by callbacks or signals, and the thread won't regain control until after the signal/callback handler completes.

So if you look at this chunk of JavaScript code

var image = new Image();
image.onload = function() {
 alert('a0');
 alert('a1');
 };
image.src = 'blank.gif';
alert('0');
alert('1');

you'll notice that the alerts you get are for a0, a1, 0, and then 1. The onload callback does not give up control back to the main thread until after it finishes giving its two alerts. This means that mutexes and critical sections can't be used in JavaScript because if one thread is inside a critical section and becomes interrupted, the other thread cannot yield to the other thread to let it exit its critical section. So basically, you can't use locks or critical sections or other standard programming techniques to protect important parts of code.

I don't know what the best way to fix this is. It's just messy...very, very messy.

JavaScript Mutexes 2

2006-10-23T12:20:00.000-04:00

Actually, I started thinking some more about symmetric mutual exclusion, and I realize that I was actually mistaken. You don't actually need to use any randomization. Although in a real system, the only way to generate unique thread ids would be to use randomization, JavaScript does have one operation that is guaranteed to generate unique keys--just use new to create a new Object since new is atomic. You can then use this object as your thread id. And since it's an object, JavaScript will automatically take care of cleaning it away once you're finished with it.

So, in conclusion, JavaScript mutexes are possible if you use a shared memory symmetric mutual exclusion algorithm and if you are able to put a bound on the number of threads that may attempt to enter a mutex at any one time. This is the best approach to the problem. There are no unacceptable trade-offs that need to be taken into account (beyond the whole messiness of needing to implement your own mutexes in JavaScript in the first place).

Mutual Exclusion in JavaScript

2006-10-23T09:47:00.000-04:00

I started reading up on some papers, and I've found that the type of mutual exclusion being attempted by Wallace in JavaScript is actually impossible. Totally anonymous mutual exclusion using atomic RW registers cannot be done.

That leaves two choice:

1. One can hand-out thread ids in advance (i.e. assign one to each possible callback) during a stage when one knows the code will have only one thread running

2. Use randomized mutual exclusion algorithms

Personally, I think option #1 is very hard to implement correctly, so option #2 is probably the most feasible. Basically, you randomly generate a thread id for yourself at any time (in fact, you can randomly generate a thread id every time you want to enter a mutex). Then, you can run a symmetric mutual exclusion protocol using atomic RW registers.

I found a paper that seems to give one such algorithm:

"Tight Bounds for Shared Memory Symmetric Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.

JavaScript is Multi-Threaded

2006-10-19T08:48:00.003-04:00

I was doing some JavaScript programming where I hooked a bunch of image onload() callbacks with functions that would generate alerts, when I noticed that various alerts were firing before I had finished hooking up all my callbacks. This caused me a lot of consternation. JavaScript does not come with any threading primitives. As such, it's very hard to do any synchronization. Yet clearly, my version of Internet Explorer was triggering these callbacks asynchronously, in threads other than my main thread, resulting in various race conditions in my code.

Firefox seems to use a more sensible model. It seems like it has only one JavaScript thread (much like the single UI thread in most GUI systems), and asynchronous events queue up and are only fired when your JavaScript thread isn't doing anything (of course, that's brings up the other problem of the fact that Firefox seems to discard events if too many get queued up--but at least that's easier to handle than race conditions).

I went looking around for various mutex code to solve this problem, but nothing seems quite right. Some Bruce Wallace person created a JavaScript version of mutex, but I don't have much confidence in it. First of all, he replaced a fixed size array from Lamport's Bakery algorithm with a Map. The whole point of the fixed size array was that you could perform atomic reads and writes on it--a reasonable assumption. Once you use a Map, you're assuming atomic adds, atomic removes, and atomic iteration, which are much larger assumptions. In any case, if you had an atomic add operation, then you wouldn't need to implement the Bakery algorithm because you could use atomic add to create a mutex. His assignment of thread ids also has a race condition in it. I suppose I could just assign a separate thread id to each callback in advance, thereby avoiding the race condition, but if I did that, then I wouldn't need this Map nonsense and I could use a fixed size array because I would know how many threads there are in advance.

Instead, I simply reshaped my code so as to minimize the race condition to an atomic increment instruction. It seems unsatisfactory though. Personally, I think JavaScript should not be multi-threaded, but if it is multi-threaded, they should at least supply something like Array atomic_add() and atomic_remove() methods so that users at least have the proper primitives available for building synchronization primitives. And I'm not sure whether JavaScript engines are themselves thread-safe. I know that Mozilla's Rhino claims that it is thread-safe (I vaguely remember them stating that get and put operations were atomic), but I don't know about the engines in FireFox and IE.

Update 2011-3-31: I was going through my blog stats for the first time, and I noticed that people seem to read this post occasionally. This is an old blog post, and I explore the situation in more detail in later blog posts. Actually, JavaScript is NOT multi-threaded. In IE6, you do get some weird non-sequential behaviour, but that's due to nested asynchronous callbacks.

Getting an SVG Bounding Box out of Batik

2006-05-18T10:28:00.000-04:00

I was using CorelDRAW to create some GIFs using a script, but CorelDRAW 11 has a lousy GIF exporter, so I couldn't really get the output that I wanted. So, I thought I would export my CorelDRAW data to SVG, and use the Batik SVG libraries to export the data I wanted to GIF (using the GIF exporter I described in the previous post).

I did encounter a problem though in that CorelDRAW defined a page size on the SVG document, and the Batik transcoders always exported the entire page (instead of just the parts of the page that contained my image). If I removed the page information from the SVG document, then Batik would just export an image with a default size. What I needed was a way to get a bounding box on my image, which I could then pass to Batik as the export size.

When I searched on Google, all the information that I could find about creating bounding boxes involved creating UI objects to render into, which triggers Batik to calculate bounding box information. This seemed a little bit overly heavy to me, but by looking at how the Batik transcoders render their images, I was able to just reuse their rendering code to trigger a bounding box calculation without actually rendering to a UI.

The first step is to remove the page sizing information from the SVG document (otherwise, Batik will just use the page size as the bounding box). Just run this XSLT filter over it:

<?xml:namespace prefix = xsl />
<xsl:stylesheet version="1.0" svgns="http://www.w3.org/2000/svg" xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml">

<xsl:template match="@*node()">
<xsl:copy>
<xsl:apply-templates select="@*node()">
</xsl:copy>
</xsl:template>


<xsl:template match="svgns:svg/@height"></xsl:template>
<xsl:template match="svgns:svg/@width"></xsl:template>
<xsl:template match="svgns:svg/@viewBox"></xsl:template>

</xsl:stylesheet>

Then, you can take the resulting SVG code and feed it into Batik to calculate a bounding box like so:

String parser = XMLResourceDescriptor.getXMLParserClassName();
SAXSVGDocumentFactory f = new SAXSVGDocumentFactory(parser);
SVGDocument doc = (SVGDocument)f.createDocument(svg);
GVTBuilder builder = new GVTBuilder();
BridgeContext ctx;
ctx = new BridgeContext(new UserAgentAdapter());
GraphicsNode gvtRoot = builder.build(ctx, doc);
return gvtRoot.getSensitiveBounds();

You can then use the returned information to set the "viewBox," "height," and "width" attributes on the svg tag of the SVG file. When you then run the transformed SVG file through Batik, Batik will export the image with the bounding box set tightly around the contents.

-Ming

Exporting Transparent GIFs from Java

2006-05-18T10:03:00.000-04:00

After spending a while trying to create paletted PNG files with transparency that work in Internet Explorer (after much trying, I couldn't coax ImageMagick to create such a file, though I was able to use GIMP to do it), I decided that GIFs were the only practical file format to be used. But it's hard to get a Java program to output GIF files.

Because of the whole patent licensing issue, there aren't really any good, full-featured, unencumbered GIF exporters for Java. But there are various good bits and pieces on the 'net, which can be pieced together to make something reasonable.

First, you need some code that can actually encode the GIF file. The US government has some code that can do this (offered as part of NIH's ImageJ). All you have to do is download ImageJ and grab their ij.io.GifEncoder class.

The ImageJ code only accepts paletted data as input though. Since most images are in 24-bit colour, you need to perform a colour reduction somehow. Fortunately, someone went and took the colour quantizer used in ImageMagick and rewrote it for use in Java. It uses an octree for its colour quantization, which is a technique described in much detail elsewhere on the Internet. The quantization code needs to be reworked a bit to properly handle transparent pixels, but fixing that isn't too much work. A more important fix though is that the code performs an unnecessary optimization to save memory, which results in poor quality quantization. In the constructor for Cube, it sets the tree depth to log_4 of max_colors. Instead, the tree depth should just be set to the maximum depth of 8. Although the original ImageMagick did limit the tree depth to log_4 of max_colors, they used another optimization elsewhere in the code to reduce the effect of that limitation.

Once you combine these two pieces of code together (you have to change some of the APIs to handle transparency and other things), then you end up with a very reasonable GIF exporter.

Firefox Should Stop Being So Smug About It's CSS Support

2006-03-13T04:14:00.000-05:00

Because, honestly, Firefox is missing some fairly major CSS features. Notably, it's missing support for "inline-block." This problem has been known since 1999 (7 years ago!) and is listed as bug 9458, but the Mozilla people haven't been particularly inclined to fix it.

I think the problem is fairly important because it's the one CSS feature that allows for arbitrary nesting of inlines and blocks. Usually, you can put inlines in blocks and blocks in other blocks. Inline-block is the feature that lets you put blocks in inlines. This opens up a certain class of layouts that aren't otherwise possible.

Reading the bug description in bugzilla, it seems like Mozilla's Gecko rendering engine is fundamentally flawed and can't really handle this feature without a major rewrite. Internet Explorer handles inline-block well, so, in my opinion, IE has superior CSS compliance than Firefox.

Jakarta Commons CLI 1.0 Is Not Very Good

2005-12-06T18:57:00.000-05:00

I wanted to do some quick command-line argument parsing in Java, so I grabbed the CLI component from Jakarta Commons and gave it a whirl. Unfortunately, this component is not very good. I fit it into a jar of about 28KB, which is not large but not that small either. The resulting command-line parser is able to identify various command-line arguments, but it isn't able to do more advanced parsing such as automatically converting arguments to integers (like jargs). It also isn't able to make use of Java annotation coolness (like args4j). It has a nice feature for automatically generating help messages, but the generated option list doesn't really match what the parsers will accept. For example, the help message will say that "-gui" is a valid option, but when using the PosixParser, the parser kept misreading the "-gui" as "-g" and rejecting it for some reason. I had to switch to the BasicParser to get it to do something reasonable.

Overall, it's nothing that I can't live with, but I was hoping for something a little better from Jakarta Commons. I think they should junk the multiple parsers, and just focus on a single more full-featured one.

Recording with Java Sound on the Macintosh

2005-11-17T03:19:00.000-05:00

I was trying out my little Java VoIP application with a friend of mine who owned a Macintosh, and it didn't quite work right. Besides the whole dubious Java 5.0 support for the Macintosh, I couldn't open a TargetDataLine at 8000 kHz.

On PCs, you can record and playback audio at arbitrary sample rates. That's not the case on the Macintosh. After getting another friend to do some probing, I found that the Java sound system on Macintoshes can playback at arbitrary sample rates, but can only record at 44100 Hz. You can record at 8/16-bit depths, with (un)signed types, and at different endianness though, I think.

VoIP in Computer Games

2005-11-12T18:32:00.000-05:00

About a year and a half ago, I started to become curious as to why there were so few computer games with VoIP support. It should be relatively easy, shouldn't it? You just grab an open source sound codec like Speex, throw in some sound code, add some network packet buffering code, mix, and voila--VoIP support. Unfortunately, I became distracted by something else and never got around to looking at the issue more deeply.

Just recently, I became curious again, so I decided to code up a small VoIP application. And, as expected, it did end up being fairly easy. I have to admit that I did waste a week going down the wrong path--I configured my sound card wrongly, resulting in a lot of feedback in the signal, so I spent a week examining algorithms for echo and feedback cancellation. But once I figured out what I was doing wrong, I was able to bang out a working little VoIP application in about a week.
The only part that wasn't really obvious (to someone who's been thinking about the problem for the past year) was the packet buffering code. Conceptually, it should be easy, you just store incoming packets somewhere and wait a few milliseconds before using them to compensate for packets coming in out of order and with jittered delay. But that leaves a lot of unresolved issues such as what should you do if you use up all the packets waiting for you? You can skip a packet (i.e. assume that they are lost) or skip a "heartbeat" (i.e. assume that you're consuming packets too quickly and wait for the packet to arrive). And what happens if you receive too many packets?

The scheme that I ended up using was to trigger everything based on the difference between the highest packet sequence number in the packet buffer and the next packet sequence number that the program is expecting. So whenever my program tries to grab the next packet, if the difference in sequence numbers is below a certain threshhold, then I skip a heartbeat; otherwise, I grab the next packet, skipping it if it hasn't arrived yet. If the difference in sequence numbers ever gets above a certain threshhold, then I advance the expected sequence number to get below the threshhold. I also had different threshholds for deciding when to adjust for clock-skew. Oddly enough, my sound card seemed to playback audio at a different sample rate than what I specified for some reason (it could quite well be my fault), so I put in some code for stretching incoming sound samples to take up more or less time. All of these threshholds should probably be adaptive somehow, but I couldn't be bothered, so I just set them to some default values.

Other than that, everything was pretty straight-forward. In Windows Java, the System.currentTimeMillis() method is very low-resolution, which caused my server to alternate between thinking it was very fast or very slow. Fortunately, newer versions of Java have a nanoTime() method, which provides a better high-resolution timer. I also had a bit of a problem with silence detection because my sound card didn't use 0 as a baseline. Sound samples seemed to center around -100 or so. I was able to get around this by taking the max and min sound samples of every chunk of sound, averaging them, and then exponentially averaging them with my previous estimate of what the baseline was. This seemed to work as an adaptive baseline. I'm not sure how to erect an adaptive silence detection algorithm on top of that though since I put a static algorithm there instead.

So the conclusion of all this is that VoIP support isn't included in more computer games due to laziness on the part of developers. It really is very easy to do. There may be some latency issues where computer game code is stealing so many CPU cycles that the VoIP code can't get CPU resources at regular enough intervals that it causes latency, but I'm sure it's something that game developers could work out with thread priorities and stuff like that.

Adding a Little Colour to Sine Waves

2005-09-14T09:38:00.000-04:00

I've never really been much of a audio creation buff, but when I heard that Propellerhead were releasing their ReBirth audio program for free, I quickly downloaded it because I've always been curious as to what all the fuss was about. ReBirth is apparently an emulator of the TB-303, which is a piece of techno hardware from the 80s that could be used to generate weird instrument sounds and to sequence those sounds into some simple tracks. It also emulates some other pieces of hardware (namely some rhythm boxes). I actually found ReBirth to be really difficult to use and completely confusing, so I uninstalled it.

Fortunately, I also downloaded the free Rubberduck program from d-lusion, and it was quite fun and easy to use (not that I have sufficient talent to get the program to do anything that sounds good, but at least I can make those crappy sounds easily as opposed to with ReBirth). After playing with it for a while, I noticed that if I turned off all the filtering effects, I could still make some nice instrument sounds just by combining sine waves and square waves.

This was significant to me because I occasionally create little Java games, but it's hard to get any music into those games. Java includes support for MIDI output, and the full Java VM even comes with Roland sound patches for its instruments, but the existence of these patches isn't guaranteed, so you can't rely on them for game music. Instead, you have to supply game music via sound files, but then you need to generate these sound files somehow. I purchased some cheap music composition software, but it creates sound files by playing the music out through the computer sound card and recording it. Since my sound card is really cheap, the resulting sound files end up containing much too much noise to be useful. There are open-source programs that can take MIDI songs and output sound files directly, meaning you don't get any noise, but these programs all use sound patch sets of questionable legality, so I didn't want to use them. But if I could just make my own instrument sounds by combining some sine waves and square waves, then I could just create a program for converting MIDI songs into sound files myself without the problems of noise or legal encumbrances.

Unfortunately, once I wrote a program for combining sine waves and square waves in various ways, I realized that the sounds that my program was generating were puny and weak. Even the simple sine wave sound generated by d-lusion's Rubberduck was much fuller and colourful than the sine wave generated by my program.

The documentation for d-lusion's Rubberduck said that they pass their sound through a low-pass filter, but I thought I had turned all the filtering parameters off. Besides, a low-pass filter shouldn't really affect a sine wave. In any case, I'm really weak with signal processing, so I couldn't really design such a filter anyways.

Well, anyways, I was looking over the "Cookbook formulae for audio EQ biquad filter coefficients" document by Robert Bristow-Johnson which is, essentially, the dummies guide to creating various filters using digital feedback mechanisms. When I looked at what Rubberduck did to square waves (it rounded out the corners), I suspected that maybe I could just sort of randomly feedback things into itself and maybe get a similar effect.

So that's what I did:

y[n] = 0.8 * y[n-1] + 0.2 * x[n]

where x[n] is a sine or square wave and y[n] is the final sound output, and the result is exactly what I wanted. Whereas a simple sine wave is teeny and annoying, when you pass it through this filtering, you get a richer, rounder, more bloated sound. Of course, when you look at the raw wave form, it still looks like a sine wave, but I suspect that it's slightly reshaped so that you get some interesting side frequencies going on. I tried doing a spectral analysis, but I couldn't really interpret it (it looked consistent with a sine wave to me), but it sounds a lot different, so there must be some sort of subtle colouring there.

Of course, to get really interesting sounds, you need adjustable filters that allow you to get various cool effects, but I think I have pieces of code for making blip and bop noises for my Java games.

Computer Generation of Road Networks

2005-07-25T08:06:00.000-04:00

For the past couple of days, I've been thinking of how to get a computer to automatically generate a city road network. I really have no idea what the best way to approach this is.

Doing a quick search through the Internet, there are computer techniques for automatically generating terrain, for simulating the growth and sprawl of cities, for simulating the growth of small neighbourhoods, and for simulating traffic on a road network, but only a few simulations for generating accurate road networks themselves. In fact, the simulations that do exist seem to focus on simulating lot use with the expectation that the road network just sort of "falls out."

I think the difficulty is that there isn't that much scientific use for simulating the development of road networks, so a lot of research hasn't gone into that area. Of course, the people who do research on urban sprawl really should do more research into road networks too because urban sprawl tends to be dependent on the location of existing highways etc. Anyways, the problem is also hard because road networks tend to be highly planned and need to take a lot of factors such as geography, cost, etc. into account during their evolution, so it's hard to get a computer to randomly generate this type of data.

Still, I wonder what it takes to build a road network generator. I imagine that an urban growth simulation model might actually be the wrong approach because it'll end up being too complex. I think a top-down approach that lays out some highways, throws down a coast-hugging road network near water, builds a grid patterned downtown, and a squiggly suburb area might actually be the easiest approach. Hmm.

Theoretical Underpinnings for Kids' Programming Tools 2

2005-06-03T07:54:00.000-04:00

Y'know, yesterday I was fretting about the fact that without strong theoretical underpinnings, my programming website for kids would never become a useful tool. But there no reason for me to have such a crisis of confidence because, honestly, which of these people is most likely to make the best programming tool for kids:

A PhD from MIT who has been professionaly developing his patented educational programs for more than 10 years.

A Turing award winner who has spent decades studying user interactions with programming languages.

Me.

Obviously, my approach will be the best. :-)

Teaching about Loops

2005-06-03T07:24:00.000-04:00

So I finally finished most of the artwork for the "if" section of my programming website for kids. It seems that the Java VM has improved a bit since I last used it. I'm finally getting consistent synchronization behaviour between when my applet running in a web broswer and my applet running stand-alone. And Swing now seems to support automatic text cut&paste with Windows applications (sigh, all of this could have been avoided if they used native widgets!).

And I'm now starting the section on loops. I've spent a few months thinking about this topic, but I'm still not sure about what the best approach is.

In traditional programming books about BASIC, the loop section would talk about FOR...NEXT loops:

FOR n=1 to 5
REM Stuff that happens 5 times
NEXT n

Unfortunately, the Javascript for loop is a little bit cryptic (especially since I haven't covered increment operators, the less-than operator, or the greater-than operator). Additionally, the convention for loops is that they start at 0. But, people are more comfortable with loops that start incrementing at 1 (like in BASIC). However, if I use 1-based loops throughout my examples, people might get confused when they later start working with normal code.

I suppose I could treat the syntax of the "for" loop as gobbledygook that should be treated as a black-box. This then reduces the number of concepts that need to be understood to work with loops.

Another alternative is that I could start with while loops. The advantage is that the word "while" actually means something, so it might be easier to understand. Unfortunately, there isn't all that much that one can do with a while loop without understanding the concept of sentry variables, which involves teaching 2 or 3 abstract concepts all at the same time.

I could teach the concept of the infinite loops first via "while(true)," but assuming that I don't teach boolean algebra beforehand (which I don't), then the whole command would need to be treated as a black-box, defeating the whole purpose of starting with the "while" loop in the first place. Then, I could follow that by teaching the concept of using "break" to break out of loops. This seems a little odd to me because no one else teaches loops in this way. Perhaps the "breaking out of loops" concept is simply too abstract a concept. But it does seem like a lot less work than discussing sentry variables and such.

Well, I don't know. For the past few months, I've been keen on the idea of starting with the while loop, but now I'm starting to come around to the idea of starting with infinite for loops. I'll have to ponder this some more.

Theoretical Underpinnings for Kids' Programming Tools

2005-06-02T10:50:00.000-04:00

During the weekend, I happened to come across a cheap scanner for sale, and I grabbed one so I would have the tools to start working on my programmingbasics.org website again. This then inspired me to take another look at the tools available for teaching kids to program. It looks like the same stuff as always--Squeak, ToonTalk, and Logo. Of course, all of these tools have strong theoretical underpinnings describing interaction models, learning processes, etc., whereas my website simply focuses on recreating the programming environment available to me when I was a kid. I'm no longer confident that I'm taking the right approach any more. Will my website (assuming that I ever finish it) have the correct foundation for teaching kids to program? Should I take a more holistic approach to the site and try to provide a complete environment for "experimentation" as opposed to simply creating something that focuses solely on just programming? Hmm. Perhaps I'm being naive. Kids today associate computer with great graphics and sound. Creating an environment that focuses on programming and doesn't allow kids to immediately generate flashy animations might lose their interest too quickly.

When I learned programming, all computers were textual. In fact, I didn't even own a computer. I was fascinated by flowcharts and wrote my first computer program out on paper by hand. The books available for teaching kids to program focused on real languages and on real syntax issues. And that's what I wanted to learn when I read those books. That's why my website is based on Javascript and focuses on syntax. But maybe those old programming books for kids died out for a reason, and maybe that reason was that kids aren't interested in learning programming that way any more. I guess I'll have to think about it.

FBX File Format

2005-06-02T09:52:00.000-04:00

Previously, I've complained about the U3D file format for having such an obscure encoding scheme that I felt it was impossible to read a U3D file without using the unreleased Intel U3D libraries that everyone else apparently uses to read and write this file format.

But after looking at some other 3d file formats, perhaps this isn't so unusual. For example, Kaydara's FBX file interchange format (now owned by Alias) doesn't even have a documented encoding format. As far as I can tell, the only way to read a FBX file is to use the provided SDK libraries. Personally, I can't imagine how you could call something an interchange file format if you don't actually describe what the file format is. But maybe I'm just not used to how things work with 3d graphics.

Oddly enough, the only light-weight 3d file format that seems to be well-documented is Microsoft's DirectX file format. Unfortunately, it's apparently no longer under active development.

Fedora Core 3 and User-Mode Linux

2005-04-27T12:43:00.000-04:00

Previously, I made a Fedora Core 3 disk image for User-Mode Linux by simply copying the disk image of a running system into a loopback disk image and starting User-Mode Linux using that disk image. That works, but I later found that some of my services didn't start up correctly in UML.

It seems that Mysql doesn't work with the current User-Mode Linuxes based on 2.6 kernels. Apparently, UML doesn't implement some of the new threading features of 2.6 kernels, which causes various problems. To avoid that problem, you have to erase the libraries that use these new threading features. I found a forum that listed this fix

mv /lib/tls /lib/tls.backup

that prevents the libraries that make use of the new threading features from being found. While you're at it, it's probably also a good idea to disable the SELinux features because they haven't been designed to be easily configurable in Fedora Core 3 anyways. Just modify /etc/selinux/config so that SELINUX=disabled (instead of "enforcing").

I also had problems with postgresql, but that was because I forgot to make /tmp world-writable. Unfortunately, my postgresql didn't seem to log anything, so I couldn't really diagnose the problem. I tried to play with the boot commands a bit to get it to log something, but in the end, I found it was easiest to simply run the postgres postmaster from the command-line with

su postgres
postmaster -D /var/lib/pgsql/data

Currently, my Fedora Core 3 image for User-Mode Linux seems to be running fine. httpd does seem to crash the UML kernel when it exits, but I can live with that for now.

U3D is Half-Baked

2005-04-17T14:31:00.000-04:00

So during the weekend, I decided to try writing a U3D file viewer. I had high hopes for U3D because U3D seemed to avoid many of the weaknesses of the competing X3D specification. After working with U3D for a bit though, I've concluded that the U3D specification is half-baked. It's almost as if the 33 members of the 3D Industry Forum performed almost no due diligence in reviewing the specification. Personally, I think the spec is unworkable and unimplementable. This is a real shame because Adobe went and added U3D support to Acrobat, meaning that a lot of marketing muscle and mindshare has just been put behind a losing proposition. Even if a better spec were designed in the future, since it wouldn't be supported in Acrobat like U3D, it would likely fail.

I can ignore minor annoying aspects like the fact that the spec itself wasn't well-designed, treating things like arrays in several different ways throughout the spec and going out of its way to avoid simplifying the descriptions of the fields, and such.

But the killer of the spec is its ridiculously overbearing bit encoding scheme. I just cut & paste the code from the specification and translated it to Java, and it's just awful. The code uses something like over 30 lines of code to read an uncompressed 8-bit integer. And the encoding/compression scheme has some characteristics that simply ruin the rest of the specification.

For example, the compression scheme sometimes requires you to feed in parameters of live data structures in order to read subsequent data. This means that you can't simply read the data into data structures and then process it later. You literally have to create a live mesh data structure, manipulate the mesh as data is being read in, and feed the resulting properties of the mesh back into the compression scheme in order to read the next bit of data.

And the encoding scheme has this weird property whereby previous data values read can influence future data values read. So even though the file format is supposedly tag/block-based (meaning that you should be able to process only the types of data that you are interested in and skip the rest), you still need to read, process, and understand every single bit of data in a file in order to read later bits of the file because otherwise the decoding state won't be properly configured when you get there. This even holds true for uncompressed data, which is just wonky. I wouldn't have believed it if I couldn't see it right there in the code that I cut & paste from the spec.

After having spent something like 5+ hours on trying to read in a CLOD Progressive Mesh Continuation Block from a file and failing miserably, I can only conclude that it's simply not worth the trouble to implement. I am now very suspicious about why the 3DIF still hasn't released a reference encoder/decoder three months after the release of the specification. In any case, as far as I'm concerned, U3D is a write-off. It might gain a little bit of mindshare because of its Acrobat-support, but I think it will eventually die off because the only way to create U3D files is to use the rumoured Intel SDK (since it's essentially impossible to write one's own encoder), and most 3D tools developers will decide to ignore it.

Some First Impressions on the U3D Format

2005-04-15T10:11:00.000-04:00

I haven't actually done any examining of U3D files yet, but I did a quick skim through of the specification, and I have a couple of first impressions.

The first thing I noticed was that they put a "file size" field in the file format. Personally, I think no self-respecting file format includes a "file size" field. The inclusion of such a field makes it impossible to stream data to stdout. Instead, you have to write out all the data, then rewind all the way back to the beginning of the file, just to fill-in that field. It would be different if the field served some sort of useful purpose, but I imagine all U3D file readers will just ignore it.

Then, the basic geometry type of the file format is the Continuous-Level-of-Detail (CLOD) triangle mesh. This is a little unusual because I thought the consensus in the 3d graphics community was that no one actually uses this stuff (of course, not being in the 3d graphics community myself, I can't be 100% sure, but that's the impression I get from reading papers). The main uses of CLOD meshes are for progressively refining 3d models during data streaming and for animation. I think the Internet experience has been that progressively refining anything during data streaming just isn't worth the trouble. For example, who uses the "interlace" option on their PNGs and GIFs? And properly getting the synchronization right on browsers so that they can handle the rendering of partially downloaded files is just a big mess. Just look at the old Java image APIs that supported these features: they were almost unbearable to use. It's easiest to simply use less-detailed thumbails/models. And I think CLOD meshes aren't used for animation either. If refined versions of CLOD meshes are computed by the microprocessor, then they have to be transferred to the video card for rendering, which is a waste of video bandwidth. It may be possible to do the refining of CLOD meshes on the video card, but I think no one does this because a) it's hard, b) CLOD meshes take up a lot of memory c) refining CLOD meshes aren't easily parallelizable and exhibit poor memory access behaviour d) you can get nicer looking low-polygon models by editing them by hand and using bump-maps and stuff. I suspect that the only reason CLOD meshes were included in the specification is that Intel wanted them there, but I would have thought that the rest of the 3DIF members would have convinced Intel to leave the feature out for the first version and only include it in version 2.0 (and then decide never to release a version 2.0 of the specification). I think it's possible not to use the CLOD mesh features though.

The U3D file format also uses a large variety of data types. I guess it isn't a real problem, but in this age where bandwidth is cheap (and things can be compressed fairly efficiently anyways), I think it makes more sense to have a couple of floating point types, an integer type, a byte type, and that's it. I haven't really examined what all the different types are used for though--there might be a good reason.

And the "U3D" way of doing things means that most resources are given string names. This seems a little inefficient (especially if you use something like UTF-16 encoding). It would seem to me that named resources would be more the exception than the rule, so it would make sense to have most resources be unnamed, and provide an optional naming interface for those resources that do, in fact, need names so that they can be accessed externally.

Also, the file format uses some weird lossless compression scheme. If the compression scheme were decent (like, say, the lossless compression that comes with jpg, mpg, and png), then I guess it might be worthwhile, but it looks like it's possible to get even better compression just by feeding the data into a zip compressor, so I'm surprised they even bothered.

I haven't really dug all that deep into the U3D file format yet though, so until then, I can't really say anything intelligent about the standard. But hopefully, I'll get around to doing that in the future.

Finding U3D Files

2005-04-15T09:52:00.000-04:00

For the past few weeks, I've been wanting to play with the U3D file format a bit. Unfortunately, no actual U3D files are available on the web. There are U3D files embedded in pdf documents that can be viewed with Acrobat Reader, but if you want to look at an actual U3D file, you're out of luck. Intel apprently has a SDK for creating and reading U3D files, but they haven't released it to the public yet, so the most widespread way for people to get an actual working U3D file right now is to get a trial version of commercial 3d file format conversion software (which has Intel's U3D SDK embedded in it) and to convert some existing files over to U3D.

I tried e-mailing the 3DIF, asking them to put up a plain U3D file somewhere so that I could take a look at it, but they never bothered replying after a week. Fortunately, after a little bit of research, I found a utility called Multivalent. This utility comes with a tool called Uncompress, which is able to take a pdf document and uncompress all the files attached inside. Of course, afterwards, you still have a pdf document with U3D files embedded inside, but since the U3D data is now uncompressed, it's possible to examine the raw U3D data.

Since all U3D files start with the string "U3D\0" you can just discard all of the pdf data that comes before that string, and everything after that is a valid U3D file (I presume). I used a little Python script like this to discard the initial useless pdf data:

f=open('file.pdf')
data = f.read()
f.close()
# You need to take the second "U3D"
idx=data.index('U3D', data.index('U3D')+1)
data = data[idx:]
f=open('file.u3d')
f.write(data)
f.close()

Maybe X3D Isn't Such a Bad Spec After All

2005-04-02T11:48:00.000-05:00

After previously denouncing the X3D specification, I decided to take a look at the competing U3D specification. I skimmed through the specification trying to think about what would be required to implement a U3D reader (the spec mandates a binary encoding with special compression used) when I realized that there aren't any U3D files available for testing U3D implementations. Nowhere. Except when they're embedded in pdf documents. Perhaps one has to be a member of the 3dif to get access to them, but the problems I have with the X3D specification pale in comparison to the no-no of developing a specification that uses a complicated encoding without providing an example file anywhere. Well, I e-mailed the 3dif. Maybe I was just looking in the wrong places.

3D Tools for the Casual 3D Artist

2005-04-02T10:46:00.000-05:00

Every few months, I get the urge to learn how to do rudimentary 3d art, so I do a quick tour of 3d tools available for casual users, and I always come back disappointed. For casual users, it's important that tools be cheap, not require users to have artistic talent in order to create simple objects, and be easy to use.

Immediately, the big, mainstream 3d modelling packages can be ruled out because they're too expensive. Of course, it's possible to use illegal copies of these programs, but I prefer not to do that. Then there are the mid-tier tools, but I'm always hesitant to shell out several hundred dollars for little-known tools from little-known companies that may or may not be any good.

This pretty much leaves low-cost and open source tools. The tool with the most mindshare currently is Blender. Unfortunately, Blender is a good example of a software application where little or no attention has been paid to the user-interface. If you read the development docs, this was an intentional decision on the part of the developers. For example, up until a couple of months ago, Blender proudly touted the fact that it had no undo functionality (telling you to save often instead). Personally, I'm tempted to use terms like "amateur-hour" here, but honestly, if I were a professional 3d artist who had just shelled out thousands of dollars for this tool, I would probably be ok with learning all of the weird UI quirks and hotkeys needed to be productive with the tool. Since I'm not a professional 3d artist and the tool is free, it's probably unfair of me to apply my standards on the tool. I have made a few honest attempts at trying to learn Blender, but all the hotkeys made my head spin and it seemed to crash quite often for me. Plus, based on the tutorials, it seems like users need powerful 3d visualisation skills to make effective use of Blender--skills that I don't possess. There's no way I can think in terms of "take a sphere, extrude this section while rotating it like so, perform a lathe on that object, and then edit the mesh." At best, I can look at a 3d object and play with the vertices a bit to get the shape that I'm looking for.

Milkshape3d is another popular 3d tool, and I've been tempted on many occasions to shell out the cash to go buy it. Milkshape3D is nice because it does only a few small things, but it does those things reasonably well. Unfortunately, every time I'm about to mail away my money to Switzerland, I start to think about the tedium of clicking in multiple windows everytime I want to add a single point to the model, and how I always get confused when I have to keep looking at different windows to know where I am, and I decide to wait for something better. I'm probably being hopelessly optimistic because manipulating 3d geometry on a 2d screen with a 2d input system (the mouse) is, by definition, hopelessly complex. But still, when I've used scaled back versions of professional tools (e.g. GMAX), they always provide nice facilities for manipulating polygon vertices without much hassle, so maybe that's what I'm looking for.

Art of Illusion seems to be reasonably powerful, but I think its 3d graphics isn't hardware accelerated, so it always seems a little sluggish to me. Plus, I can never figure out what the icons mean and the tooltips take too long to show up, so I spend much of my time holding my mouse pointer over icons to figure out which one does what I want.

Recently, I tried Wings 3D, and I really liked it. It's possible to perform lots of complex operations with complete ease. Pretty much all of the UI is self-explanatory and mouseable. The main advantage of the UI is that since everything is explained on-screen, you only have to memorize five things to be productive--namely what G, L, Q, space bar, and the middle mouse button do. With everything else, all you need is a general idea of what you want to do, and you'll probably be able to find it in the menus somewhere. The only problem with Wings 3d is that it doesn't work with many graphics cards. I tried it on an ATI Rage card, and an Intel integrated Extreme Graphics, and the UIs ended up being too horribly mangled to be usable. Finally, on an ATI 7500, the UI still didn't quite render correctly, but it was enough to be usable, and it was a joy to use. I was tempted to dig into the code and see if I could find any workarounds for my problems, but Wings 3D is coded in Erlang, so...yeah.

So in conclusion, if you want to dip your toe into 3d graphics on the cheap, try Wings 3D, and if it doesn't work, give up. Of course, I may be the only person who finds xfig to be an easy-to-learn program that one can quickly become productive in, so perhaps my experiences may differ from that of others.

Creating Fedora Core 3 Disk Images for User Mode Linux

2005-03-30T08:07:00.000-05:00

So, for the past couple of weeks I've been working on creating a Fedora Core 3 disk image for UML. In the end, the process ended up being quite straight-forward, but in a case of "a little bit of knowledge can be a dangerous thing," I kept screwing it up.

Pretty much, all you have to do is to create an ext2 loopback disk image as suggested in the UML docs, and then copy a running fedora core system (using cp -r -d --parents --preserve=all or whatever) into it (obviously, you should avoid copying the disk image into itself). That's pretty much it. Labeling the disk image as /1 doesn't seem to be enough to get UML to mount the disk image properly as its root file system, so you do have to modify the /etc/fstab file so that the root file system is mapped to /dev/ubda (for some reason, the virtual drive appears as /dev/ubda instead of /dev/ubd/0 like in other images) using an ext2 format (unless you compiled ext3 support into the kernel). It's probably a good idea to enable networking in the kernel as well by turning on these kernel options:

UML Network Devices/Virtual network device
UML Network Devices/TUN/TAP transport

Then, you can just boot up UML into the image you created. You don't have to change the Kudzu configuration, change the networking to use something other than eth0, or anything. It just works. Below are the things I tried to do, which ended up being completely unnecessary:

Although Fedora Core 3 intially boots with a small initrd RAM disk image as its root file system before switching to using the hard disk as its root, this initrd is only for loading additional kernel modules. Since User Mode Linux has most options compiled directly into the kernel, it is not necessary to use an initrd image with UML. Also, it is not necessary to create ubd devices in /dev since Fedora seems to do that automatically. And hostfs mounting /sbin or /bin doesn't work out too well. You can mostly get away with hostfs mounting /usr but you have to prevent xfs from starting up (simply remove /etc/init.d/xfs) because I think it tries writing stuff into /usr, which won't work because on the host-side, UML won't have sufficient permissions to write there. I also didn't bother properly installing uml-tools, meaning that UML couldn't use the port-mapper to bring up the virtual console xterms. Since Fedora Core 3 requires you to log-in through a virtual console, you need to get the port-mapper working properly (I had to modify UML to find the port-mapper in my home directory instead of its default location). Also, Virtual Console #7 and #8 won't appear or won't show anything, so don't think the boot-up has failed if you don't see anything there. And that pretty much summarizes many, many days of mistakes.

Off-Screen Buffers in Java

2005-03-21T07:47:00.000-05:00

I recently discovered that off-screen buffers in Java can be really slow. Off-screen buffers are commonly used in Java games so that a frame of animation can be constructed and then displayed on the screen without resulting in flicker. Since the Swing toolkit is double-buffered, most applications don't normally need to create their own off-screen buffers, but I don't like using the UI thread for game logic and rendering in my games (plus my games use AWT), so I have to manage the off-screen buffers myself.

Anyway, many graphics operations in Java are not hardware accelerated yet, and some of the buffer code that I'd been using for a long time has been using some really slow operations; I'd simply never noticed until I started working on a computer with a really old PCI Rage 128 graphics card. With such low bandwidth across the PCI bus, blitting the off-screen buffer images to the screen ended up being really, really slow.

The problem is that I'd created the BufferedImages backing the off-screen buffers as TYPE_INT_ARGB. I think the inclusion of an alpha channel, combined with an assumed lack of hardware acceleration, resulted in a lot of data needing to flow back and forth across the PCI bus unnecessarily. Once I switched the buffers to be TYPE_INT_RGB, everything was back to being snappy and fast.

Running User Mode Linux from 2.6.10 Kernel

2005-02-21T00:21:00.000-05:00

I don't really know anything about mucking around with the Linux kernel (I'm the type of guy whose favourite text editor is pico and who can't figure out how to use Debian meaning he has to use RedHat instead), but somehow I signed up to do a term project involving a bit of kernel hacking, so I guess I have to learn. Since kernel stuff seems a bit messy, I opted to work with User Mode Linux (UML).

Now, when one browses around through the main website, there's a lot of stuff about ancient versions of UML based on 2.4 kernels, there's a couple of mentions of 2.6 kernels, and tucked away somewhere, there's a brief aside that UML has been integrated into Linux kernels 2.6.9 and beyond. Seeing as everything else on the main website seemed a little dated, I thought that it would be best to use the UML that's integrated into the main Linux branch because it would be more likely to be maintained and tested there. In actuality, the UML code that's been integrated into the kernel doesn't work all that well, and it took me a few days of searching through various websites, wikis, forum discussions, etc. to figure that out. So here are the goods on how I got UML working on my Fedora Core 3 system.

Apparently, the UML in the current 2.6.10 vanilla kernel doesn't work. Instead, grab the 2.6.9 vanilla kernel from kernel.org or somewhere. Then, go to Paolo Giarrusso's UML site and grab the latest 2.6.9 patch (it's in his archives in the guest patches section). After you've unzipped and patched everything, simply taking the default configuration from

make menuconfig ARCH=um

isn't sufficient. One has to enable these options in the kernel

Character Devices/File Description Channel Support
Character Devices/Port Channel Support
Character Devices/tty Channel Support
Character Devices/xterm Channel Support
Block Devices/Virtual Block Device
File Systems/Pseudo File Systems/dev File System Support

Then, you can follow the normal instructions about compiling, stashing a root_fs file system somewhere, and then using the devfs=(no)mount option appropriately.

This is enough to get UML to bring up a prompt, but that's as deep as I've dug so far. I'm still weighing whether it would have been easier simply to have started with a Debian package of UML.

CorelDraw 11 Import/Export Woes

2005-02-08T11:24:00.000-05:00

Being from Ottawa, I'm a CorelDraw user (Corel is an Ottawa-based company). I'm not a very good CorelDraw user (I just use it to draw simple diagrams), but I'm still a CorelDraw user. Just like other CorelDraw users, I have to live with both the good and the bad features of CorelDraw. It comes with a lot of features and applications for a good price, but you have to live with the ever expanding resource usage of each version, buggy features, an under-designed user interface, and a general lack of polish. Perhaps things will get better now that they're under new management.

I bought a discount version of CorelDraw 11 a few months ago, and I use it for mostly computer science type things: presentations and LaTeX diagrams. In order to use CorelDraw in this sort of configuration, you need to do a lot of bulk importing and exporting. I just thought I would blog my approach to making CorelDraw 11 do what I want in case the one other person who uses CorelDraw in this sort of configuration is interested :-).

For example, I usually draw all my LaTeX figures in one CorelDraw document and then use a bulk export macro to export each page as a different eps file that I can reference in LaTeX. CorelDraw 11 doesn't let you configure eps export options from a macro, so you have to export one eps file by hand first and configure the export options there, and then when you run the macro, it will just reuse the export options that you set before.

Also, pdflatex prefers to import vector graphics in the pdf format. Unfortunately, CorelDraw 11's pdf exporter doesn't support bounding boxes, so the exported pdf files do not import correctly. I found this program called eps2pdf (I use the one that comes with a nice Windows GUI because I can't figure out how to invoke the preferred eps to pdf conversion utility "epstopdf") that can take eps files exported from CorelDraw and converts them into pdf documents that can be imported into pdflatex. The program chokes if the Corel-exported eps files have text converted to curves or if the Corel-exported eps files are too large. It's possible to invoke eps2pdf from the command-line to convert all eps files in a single directory, which is useful.

Just recently, I've tried to import a lot of xfig-created eps files into CorelDraw 11. This sounds a little odd, because it doesn't make sense to create diagrams in xfig when you own a copy of CorelDraw. The reason I needed to do this was that I needed to generate a lot of complicated machine-generated Postscript diagrams. I don't understand Postscript, but xfig generates very clean, easy to understand Postscript output. So when I'm in this situation, I draw a couple of simple primitives in xfig, export it as eps, then write a program that follows the template generated by xfig in creating its own Postscript diagrams. Unfortunately, Corel's eps importer imports the text in xfig eps files as curves instead of as text. I managed to side-step this problem by using ps2ai.bat to convert the eps Postscript files into ai Postscript files. CorelDraw 11 then imports the text in these ai files without problem. Unfortunately, somewhere along this conversion process, extra outlines get added to objects. It's possible to simply delete these outlines by hand (especially easy if you use the ObjectManager view), or you can import the xfig eps files directly, copy all of the non-text objects, and then use these objects to replace the non-text objects in the imported ai files. There's probably an easier way to do this, but I'm still trying to figure it out.

Extensibility in X3D

2005-02-04T11:32:00.000-05:00

During my rant against X3D yesterday, I wanted to complain about the extensibility model of X3D as well, but I couldn't think of a better approach to supporting extensibility in a 3d file format, so I decided that it would be inappropriate to make a big deal about it.

Of course, I thought up of a better scheme last night, so now I feel justified in complaining about the approach used by X3D to support language extensions. Although I complained about how the X3D event model was too abstract to usefully express certain concepts, I find that the X3D scene graph hierarchy to be too concrete and specific to support extensibility in a graceful manner.

In X3D, scene graph nodes are well-defined types. Each node has specific fields and no others. To add support for different objects, one has to create a new scene graph node with the fields one needs (or insert a lot of meta data, but I'll discuss that later). If an X3D browser encounters a node type that it doesn't understand in an X3D file, probably the best it can do is to simply ignore that node. Unfortunately, this doesn't degrade gracefully. So, for example, consider the mesh objects that are currently in X3D. If I want to make an articulated mesh, I need a way to add weights to each of the mesh vertices describing the influence of various bones on the position of the mesh point. To do this, I need to make a new scene graph node for articulated mesh objects that has a field for holding the bone weights. So now, if an X3D browser encounters my new articulated mesh node type in a file, it won't know what to do and will simply not render it. Ideally, the browser should simply degrade gracefully and render the data as a normal mesh, but it's not possible because there's no way for the browser to know that there's a link between an articulated mesh and a normal X3D mesh. Over time, as more and more node types are added to the standard, the standard becomes so big that no browser is able to implement the whole specification, resulting in many X3D files that are simply incompatible with many X3D viewers. In fact, this can already be seen in the current standard which has different node types for IndexedFaceSets, IndexedTriangleSets, IndexedTriangleFanSets, and IndexedTriangleStripSet. All of these node types are variations on the same theme, but an X3D browser must be explicitly coded to handle all four types separately.

One way around this problem is to use the metadata facilities of X3D. So an articulated mesh could be stored as a normal mesh with all the bone weights stored as metadata in the mesh. A browser that doesn't understand the metadata can just render the mesh as a normal mesh, and a more advanced browser can interpret the metadata and extract the bone weight information. Similarly, all the different triangle sets could be encoded as IndexedFaceSets with metadata suggesting the optimisation of rendering the node as triangles. And therein lies the way to gracefully supporting extensibility in X3D. There shouldn't be set node fields in X3D. Instead, all fields should be metadata. Most 3d objects can be described as a control surface with various extra descriptive data thrown in. As such, X3D should simply abstract all 3d objects to being a base control surface type, and all the extra descriptive data about normals, colours, and shape, etc. should just be metadata. So a cone is a box node that is tagged as a "cone" in its metadata. A height map is just a mesh node that is tagged as being a "height map" with some metadata describing the orientation of the heights. It may not be the most efficient way of storing data, but the benefits in terms of gracefully supporting extensibility is worth it. A minimal X3D browser then only needs to be aware of a small number of abstract node types. Even on very complex 3d models, an X3D browser will always be able to extract something that it can render.

Instead, X3D simply took the flawed VRML model and recoded it in XML. I guess we can always wait until X3D 2.0.

U3D vs. X3D

2005-02-03T08:59:00.000-05:00

I was looking at the website of the purveyor of the X3D format yesterday, and I noticed that they had a newspost slamming the rival 3D format U3D there. I haven't read the U3D spec yet, but based on the newspost, it sounds pretty good. In fact, I think that if the U3D spec had been available when I started my X3D project, I would have used U3D instead.

The newspost complains about how X3D only supports triangle meshes and the like. Honestly though, having just finished implementing a horrible n^4 concave polygon triangulation algorithm for my X3D viewer, I'm liking the idea of a format only supporting triangle meshes more and more.

I've only implemented a small amount of the X3D spec, and I can't help but feel that it lacks a certain elegance and simplicity in its design. I think many of the problems evolved out of the fact that the designers wanted people to be able to code X3D by hand. As such, the spec supports lots of shortcuts and features to aid people coding up X3D manually such as the ability to leave out certain tags or to let the browser automatically calculate normals etc. These sorts of things simply make the implementation more complicated and results in lots of "special cases" in the specification. In reality, no one designs a 3d model using text (believe me, I tried this once. It's totally hopeless), so it would have been better to leave out stuff like that.

I'm not implementing the X3D event model, so I'm not too familiar with it, but my gut feeling is that it is likely too expressive. The Postscript language has a similar problem in that it is a full programming language, meaning that extracting meaning from the language is extremely difficult without actually executing it. For example, let's say I wanted to export an animation to another program. The exported animation will have a clock object whose timing is fed into some sort of coordinate generator whose events would be fed into the actual object being animated or something like that. Would an X3D importer be able to interpret the combination of event objects and event routing as being an animation and to import it as such? Or would it simply have to import these event nodes as is and leave it to the user to figure out that it represents an animation? Just as human language is too expressive for computers to understand, which is why we have programming languages, the X3D model might be too expressive for an import tool to recognize the patterns, which is why more restrictive languages are often more useful. If a language is too expressive for an import tool to understand its meaning, resulting in it being imported as a black box, then the language might as well be some standard language like ECMAScript that people are already familiar with.

And of course, there's my bias against "platforms." I feel that the best specifications are for little self-contained toolkits that can be bolted on to existing applications. X3D was designed as a complete platform for 3D browsing, so it has a tendency to want to take over your application as opposed to being a simple bolt-in. For example, to implement a module for importing animation, you need to add the event model to your application, some sort of reflection mechanism for X3D objects to parse the event code, the actual X3D objects themselves, etc. etc. Afterwards, it's no longer a simple little import tool; you've essentially just written an X3D browser. At that point, you might as well just write your whole application to be X3D-based.

X3D simply tries to do too much and as a result is too complex. U3D focuses on one small aspect of 3D file exchange and hopefully ends up being small, graceful, and easy to use. It's somewhat like the TIFF file format which is so complicated and supports so many features that no one really uses it for anything. It's a coin toss as to whether an arbitrary TIFF file might be importable by a TIFF import tool or not: there might be multiple pages in there, encoded in some weird colour space, compressed using some unknown scheme, etc. With PNG, you're pretty much guaranteed success.

JSR-184

2005-01-22T11:47:00.000-05:00

After a break of a few weeks, I went back to X3D coding, and as a result, I now have a working X3D parser, and I've implemented just enough of the X3D spec that one can look at boxes and set a viewpoint.

I started to become a little worried after I noticed that I was approaching 6-7k of code just to draw a little box, so I decided to port what I had to J2ME to make sure everything worked. Good thing I started early because if I had left the port until the last moment, I surely would have had a seizure or something.

Apparently, vertices and normals are defined using bytes and shorts in JSR-184 (the current Java specification for doing 3-D graphics for cellphones). Yes, I am aware that cellphones do not have floating point units, making floating point math very slow, but bytes and shorts? This makes the porting of any graphics code from desktops to cellphones mind-numbingly difficult. Everything has to be torn out and carefully redesigned so that they work correctly with byte and short values for vertices. And such a design has a shelf-life of about two years because if 3-D graphics ever take off cellphones, floating-point units will be added to the devices, and developers will demand a new API with better floating-point support. Sure, I'm glad that Nokia is very proactive about defining new Java API standards for cellphones; otherwise, the latest cellphone features simply wouldn't be accessible from Java (or, at least, not in a standardized way). But I really do wish that Nokia would spend a little bit more time polishing their APIs before releasing them, so that the APIs wouldn't fall into obsolescence so quickly, necessitating the creation of yet another unpolished API to replace it, which'll become obsolete again in just a few years etc. etc.

Would it have really been so hard to allow vertices and normals to be defined using floating point values? Sure, it would be slow, but it would be nice to have that option at least. And adding that support would add another year or two to the life of the spec, at a minimum. I might expect this sort of lack of foresight from a bunch of amateur hacker coders, but I imagine that Nokia probably has some good people on this. I think it must be part of a larger corporate strategy of planned obsolescence in software. Because the old APIs are so limited and restrictive, developers will have to keep on moving on to newer APIs to make use of newer features. Since the new software is incompatible with older phones because the software makes use of the newer APIs, people have to upgrade their phones to use the newest software. And, if the new phones don't even bother to include the old APIs, then users can't just copy software from their old phone to their new phone; they have to buy all new software for each of their phones. This is good for the corporate establishment not only for the above reasons but also because it hinders piracy and allows vendors to control the availability of software on different platforms. All of this, of course, is meant to oppress the consumer and to wring as much profit as possible out of the pockets of the average worker, the elderly, and teenagers around the world.

Or, maybe Nokia just hired a bunch of amateur hacker coders.

JOGL and Resizing Windows Part 2

2005-01-22T11:45:00.000-05:00

Yeah, apparently the problem I was having before was simply a driver problem. Of course, Intel hasn't updated their drivers in a while, so I guess I'll have to live with it.

JOGL and Resizing Windows

2004-12-14T14:10:00.000-05:00

I'm not sure if I'm the only person who's not using JOGL to do animation, but I seem to have a problem where when I resize a JOGL window, it fails to update its screen correctly. Most people don't encounter this because if they constantly update their screen inside an animation loop, any update failures will correct themselves during the next pass through the animation loop. A quick search through Google brings up nothing.

What happens is that if I use the November 19th build of JOGL, when I resize the window, I get a blank white screen. When I resize it again, I get my image displayed correctly again.

I suspect that the problem has something to do with double-buffering after a resize. Here is my evidence:

a) when I do successive resizing, it alternates between being ok and not being ok
b) after I do a resize, cover the window, and uncover the window, the window looks fine again
c) if I create a single-buffered OpenGL context, JOGL keeps dumping stack traces to the console
d) The following bit of code looks suspicious:
if (autoSwapBuffers && !isReshape) {swapBuffers();}

Still, when I trace through the execution of the code, everything seems to trigger correctly, so I suspect that maybe I'm just doing something incorrectly in OpenGL or elsewhere. If I force an extra buffer swap after a reshape, everything does seem to work correctly (the white screen still shows, but it's quickly overwritten during the successive call to display). Perhaps it's a driver problem. I should try this on a different machine.

X3D and the Importance of High Quality Specifications

2004-12-12T12:03:00.000-05:00

This isn't a real post but more of a rant session about the quality of the X3D specification. This spec is of mediocre quality at best. It's quite clear that they revised the spec many times and forgot to clean up references to old revisions. For other parts of the spec, they seemed to be describing an existing implementation as opposed to specifying how new implementations should behave (i.e. they leave out important details). Various parts of the spec are inconsistent or confusing. Worst of all, some parts of the spec give off the impression that they've NEVER BEEN IMPLEMENTED.

I've only tried to implement a very small amount of the specification so far, but here are various problems I've seen so far:

1. A lot of the example interfaces for the Java language bindings are inconsistent with other parts of the specification or are simply wrong.

2. The Java language bindings have clearly never been implemented or tested.

3. Default values are defined for several field instances when they are simply the same as the defaults for fields themselves

4. They never really make it clear what their notation for node fields are

5. Various inherited fields are listed repeatedly over and over again

I suppose it's a little worse for me because I'm autogenerating code based on the specification, so things that would be glossed over by someone implementing the specification by hand really cause problems for me. Oh well. So far, I haven't hit any part of the spec that was so outrageously wrong that I couldn't figure out what they had intended, so maybe things aren't so bad after all.

X3D Ambitions

2004-12-10T13:29:00.000-05:00

After spending more time trying to understand the X3D spec, I think I've decided that it is simultaneously less ambitious and more ambitious than I had expected. I had initially thought that X3D intended to define specifications for a lot of the annoying 3D programming issues like file exchange, scene graphs, etc. This way, programmers could just use some X3D components instead of having to code their own lower layer 3d code. Based on what I had read from the spec and about the history of X3D, I thought that that's what X3D was for. I'm a little skeptical of that idea, but it does sound intriguing. I'm actually a little disappointed that this isn't wasn't X3D was aiming to do. In fact, X3D seems to be just a standard for a 3d media player/browser. They've essentially designed a file format for X3D media and an API for talking with X3D browsers. If X3D were a database, the X3D specification would describe the file format of the database, an RPC framework for communicating with the database, and a general description of how the database should behave. This is an ambitious vision, but it isn't as generally useful as having a bunch of lower-level components. Hopefully when the 3D Industry Forum comes out with their competing spec, it'll be possible to compare which approach is more useful. I suppose that it's like the difference between white-box and black-box inheritance. Oh well.

In any case, generating code using XSLT seems to work pretty well. It's a little verbose, and you have to watch for those <> characters in the code, but I've been pretty satisfied so far. Hopefully, if all goes according to plan, I'll have a rudimentary partial implementation of a few nodes from the SAI layer of X3D by Monday. Then I can actually start cobbling together a renderer and parser.

Starting with X3D

2004-12-09T11:53:00.000-05:00

So, I somehow committed myself to making a simple X3D browser for mobile devices, but it's really hard to figure out where to start. I've been browsing the specification for several days now, and it's just not really sinking in. Usually, the reference implementation (xj3d) would be the normal place to start, but it's really a VRML browser with a thin veneer of X3D on top of it. In any case, most of xj3d seems to be hand-coded, but the specification looks really amenable to automatic generation, which is the route I want to take.

In order to code up a browser, you need a simple 3d engine first. Since X3D defines a scene graph API, it seems like that working on that API would be an ideal place to start (since one can use a scene graph as the base for a 3d engine), but the more I read about the X3D scene graph API, the more I realize that it's inappropriate for doing any sort of rendering from it. Plus, the interface for getting a browser instance seems cumbersome to code up as well. Still, I suppose it's as good a place to start as any.

For the code generator, I was originally thinking of coding something up in Java, but I think I might make an attempt at putting something together in XSLT. I'm not sure if it'll work, but it's always good to use existing standards, so I suppose it's worth a try. Of course, XSLT doesn't support generating multiple output documents from a single input document, so I'll still have to write some sort of coordinator or something.

I guess I'll start with something simple by auto-generating the exception classes. Already, there are some pecularities in the spec, because initially they define a bunch of abstract language-independent exceptions and then later in the spec, they decide that for the Java version, they'll use a different set of exceptions using a completely different naming scheme. This is actually sort of annoying; I think it's a bug in their spec.

Understanding X3D

2004-11-28T11:41:00.000-05:00

For the past few months, I've been trying to wrap my head around this whole X3D thing. I haven't really done anything with it yet, but I have read a lot of documentation, and it just isn't clicking with me.

I think the problem is that when most people decide to learn X3D, what they're looking for is a nice universal file format for 3d models. My impression is that to work with 3d models now, you have to go about downloading various SDKs describing how to work with certain propriety model formats that are outputted by programs that you could never afford. Developers want some sort of standard file format that they can work with instead, and ideally X3D would be this standard. What they actually get is VRML encoded in XML.

Now VRML sort of puttered out a few years back, and I suspect that this would probably explain the lukewarm reception of X3D right now. Most people that I've talked to have either never heard of X3D or simply don't care.

In any case, because of X3D's VRML past, it actually does three things:

FILE FORMAT

X3D describes a way of encoding 3d geometry in XML. This part of the specification is what people actually want X3D to do.

SCENE GRAPH

I think X3D also defines an API for storing and manipulating scene graphs in memory. In fact, the file format is simply a way of serializing the scene graph to a file. I'm a little ambivalent about this. Admittedly, every time anyone wants to do anything in graphics, they have to put together some sort of scene graph code. Each year, thousands of computer science students taking graphics course have to put together a new scene graph framework so that they can do some 3d work. And anytime a company decides to create a 3d API (e.g. Java3d or JSR184), they always decide to create their own scene graph API to go with it. So I suppose it would be nice if everyone could agree on a single scene graph API. On the other hand, the first thing that people ask upon encountering a scene graph API is "how do I make it show a bunch of triangles on the screen like in OpenGL," so maybe a standardized scene graph API isn't all that useful an abstraction. After all, you don't see people creating a bunch of objects for representing shapes and geometry of 2d scenes. I guess the thing that causes me the greatest concern is the fact that all the X3D implementations that I've looked at (which is, admittedly, only two) take the X3D scene graph and immediately convert it to a different scene graph format before doing anything with it. This includes the X3D reference implementation! If the scene graph API were any good, then there really shouldn't be any reason to convert it to a different representation, right?

PLATFORM

Because of its VRML roots, X3D similarly tries to provide a complete "platform" for doing 3d applications. In other words, X3D seems to provide enough language bindings, scripting support, interactivity features, event models, etc. that X3D can be used as the basis for a complete 3d application. Personally, I think this is the most dubious aspect of X3D because understanding and implementing all of these features is really hard, and people who are only interested in a universal 3d file format really don't care about this stuff. I think it may be possible to make a compliant X3D implementation that ignores all of the platform stuff, but I'm not entirely sure yet, and in any case, I find the X3D documentation extremely hard to read because of all the references to these platform features.

So I guess the primary question is whether X3D fails as a file format because it tries to do many other things as well. Frankly, I don't know. I have committed myself to doing some work with X3D though, so hopefully I'll be able to figure this out as I dig deeper into the specification.

First Post

2004-11-27T16:59:00.000-05:00

Well, I've been thinking of doing some blogging for a long time, but every time I was about to start, I kept getting this horrible feeling that my blog would simply end up being a summary of stuff I read on Slashdot.

I occasionally do some coding though, and sometimes, I hit a snag that I'm sure that someone else has encountered before, but I still have to spend hours and hours researching answers. Afterwards, I can't help but wish that other people had documented their experiences, so that I wouldn't have to waste hours redoing what they've already done.

So skipping right to the point, this blog will be a summary of various issues that I've encountered during coding and the solutions that I found worked.