One loop is enough

Sylvester has been out for a few days now, and seems to be drawing, ahem, mixed reactions over on Ajaxian (mostly for variable naming rather than its actual functionality). It’s nice that a few people seem to be checking it out, even if it is a little rough-round the edges.

One thing I’m really pleased with is that I’ve got the library’s syntax to be as natural as it is. The maths reads like maths, and your conditions read like sentences: if (A.isPerpendicularTo(B)) { ... }. Nothing staggering, I know, but I’m glad the library works just as I intended. However, while beginning work on a future version, one with polygons and line segments and algorithms like this (PDF), I found out that version 0.1.0 is a little on the slow side. But, I thought, other people have built 3D rendering in JavaScript that goes at a decent clip and has to do the same maths that I’m doing, so why is my test page taking half a second to rotate a bunch of triangles?

The answer is that all the syntactic niceties hide a whole bunch of loops, and lots of unnecessary looping slows code down. If you’re only interested in doing a few one-off vector/matrix calculations that’s fine, but if you want to move dozens of polygons around at once you’re going to run into trouble. So, I’ve been rewriting sections of code to speed the library up, and almost paradoxically that involves making some sections of code much longer.

An example: the rotate method of the Vector class, which rotates a point about a line. This is the code for rotating a 3-vector in version 0.1.0:

var C = line.pointClosestTo(this);
var R = Matrix.Rotation(t, line.direction);
return C.add(R.x(this.subtract(C)));

That all looks rather elegant and very legible. So what’s the problem? The add method loops over the vector’s elements, as does subtract. (Actually, subtract involves two loops in 0.1.0 as it multiplies the argument by -1 and then adds it to the receiver. This is much shorter to code but runs half as fast.) x is a matrix multiplication, which is two loops. All these invoke either Vector.create or Matrix.create, which involves even more loops, although these will go in future versions as they do over-paranoid things like checking that all the arguments are numeric.

So how do we improve things? In this case, we know that all the vectors involved are 3-dimensional – the Line class only works in 3D. This knowledge means we can work out the result explicitly without any unnecessary loops. The code becomes:

var C = line.pointClosestTo(this);
var R = Matrix.Rotation(t, line.direction);
x = this.elements[0] - C.elements[0];
y = this.elements[1] - C.elements[1];
z = this.elements[2] - C.elements[2];
return C.map(function(a, i) {
  return a + R.elements[i-1][0] * x +
      R.elements[i-1][1] * y + R.elements[i-1][2] * z;
});

We’ve rewritten the result all in one map loop, and that means it will run much faster. We could even go one step further and write out all the elements of the result by hand without using map. So far, I’ve managed to get some methods to run up to four times faster by not relying on Sylvester’s API to work things out. Does this make Sylvester seem unnecessary? Quite the opposite: its methods are being rewritten to make them perform better and save you a lot of coding.

Before anyone chimes in about filesize, I should point out that with this project, given where I want to take it, execution speed is number one priority. You can always pack your JS, and a few extra lines in the source won’t blow up the packed version much. And maybe just to annoy the filesize fanatics, here’s what’s happened in Line#pointClosestTo lately:

Before (version 0.1.0):

var A = P.subtract(this.anchor);
return P.add(this.direction.cross(
  this.direction.cross(A)
).toUnitVector().x(this.distanceFrom(P)));

After:

var A = this.anchor, D = this.direction;
var D1 = D.elements[0], D2 = D.elements[1], D3 = D.elements[2];
var A1 = A.elements[0], A2 = A.elements[1], A3 = A.elements[2];
var P1 = P.elements[0], P2 = P.elements[1], P3 = P.elements[2];
var V = Vector.create([
  D2 * (D1 * (P2-A2) - D2 * (P1-A1)) -
      D3 * (D3 * (P1-A1) - D1 * (P3-A3)),
  D3 * (D2 * (P3-A3) - D3 * (P2-A2)) -
      D1 * (D1 * (P2-A2) - D2 * (P1-A1)),
  D1 * (D3 * (P1-A1) - D1 * (P3-A3)) -
      D2 * (D2 * (P3-A3) - D3 * (P2-A2))
]);
var k = this.distanceFrom(P) / V.modulus();
return Vector.create([
  P.elements[0] + V.elements[0] * k,
  P.elements[1] + V.elements[1] * k,
  P.elements[2] + V.elements[2] * k
]);

That runs about four times faster than the 0.1.0 version.

Announcing Sylvester

So, after a couple of weeks beavering away on this of an evening, I’m pleased to announce the initial release of Sylvester, a vector and matrix mathematics library for Javascript. The project site has a bunch more information, and API docs for about half the code. My plan is to build this up into a 3D geometry and rendering framework over time, but I’m trying to make all the classes as generally useful as possible. I’ve seen a bunch of 3D renderers around the web and they seem to mostly be proofs of concept without a more general-purpose API. The one exception to this would be Matt Westcott’s Canvastastic, which I like a lot, but it doesn’t expose its core building blocks – vectors, matrices and the like. It has methods for multiplying specific types of matrices, but no general-purpose classes for doing this type of maths.

I want Sylvester to expose as much as possible of its functionality as useful classes so people can take the bits they like and go and write maths code for whatever they want to do. Each release will add new components that are built on top of the existing ones, so you’ll be able to take away as much or as little of the library as you need.

As always, I’d love to hear what people think – shoot suggestions and bug reports to james@jcoglan.com.

Flagger now at 0.9.4, and a new JS library in the works

See, I knew I wasn’t cut out for blogging. I keep forgetting to post code updates, when that’s precisely the reason I set this thing up. Anyway. Flagger is now at version 0.9.4. Most of the changes are bug fixes. 0.9.4 closes a bug where the wrong callbacks got called in some situations. Since 0.9.1 there’s also been a functional change, in that after_mark_as_* methods are only called if their corresponding attribute is changed by a mark_as_* call.

In other news, I’m working on a JavaScript library. Not a Prototype/jQuery competitor, oh my no. I saw this the other day and decided I’d have a go at writing something similar, as an exercise in not completely forgetting how to do maths. I’ve noticed that much JavaScript that attempts to to anything geometrical does so by throwing piles of arrays around rather than having any real classes doing the work. That is to say, they favour things like

var c = vector_add([0,3,7], [5,2,8]);

whereas I’d rather write

var a = Vector.create([0,3,7]);
var b = Vector.create([5,2,8]);
var c = a.add(b);

Obviously, for this trivial example that’s a lot more work. The point of what I’m working on is that a and b are fully-fledged Vector objects with loads of useful methods attached to them for letting them interact with other vectors, matrices, lines, planes, etc. Also, a more object-oriented approach leads to better code legibility and lets you write code that’s closer to the maths it represents. As a quick sneak-preview, here’s the method for finding the intersection of two lines in 3D space:

this.intersectionWith = function(obj) {
  if (!this.intersects(obj)) { return null; }
  var P = this.anchor, X = this.direction,
      Q = obj.anchor, Y = obj.direction;
  var a = (X.dot(Q.subtract(P)) * Y.dot(Y) / X.dot(X)) +
      (X.dot(Y) * Y.dot(P.subtract(Q)));
  var s = a / (Y.dot(Y) - (X.dot(Y) * X.dot(Y)));
  return P.add(X.x(s));
};

I guarantee that would be a lot harder to follow if we were passing around lots of arrays and for loops. You might not understand what lines 5 and 6 do, but the point is that it reads almost exactly like the maths would on paper. More news on a release date soon (hopefully).