I have to admit that when generating isosurfaces, I’ve come to prefer polynomial-trigonometric functions over noise arrays. Where noise gives samey-looking blobs in all directions, PTFs (polytrigs?) provide structure and asymmetry at low cost.

Here’s the source function I used to generate those surfaces.

var k1 = M.rng.get(-1, 1);
var k2 = M.rng.get(-1, 1);
var k3 = M.rng.get(-1, 1);

var source = function(x, y, z) {
	if (y < 0.1)
		return -1;
	var a = x + y + k1;
	var b = y + z + k2;
	var c = z + x + k3;
	var d = a + b * c;
	var e = a * b + c;
	return Math.cos(a * d + b * d + c);
};

Rolling up a few random offsets gives us a variety of surfaces. The specifics of the math don’t matter: I just want a polynomial that’s complex enough to be interesting. We take the cosine to smooth the results and limit them to the range (-1, 1).

For the field function, I’ve dropped the cube-based point field thingy I used in the last couple of posts in favor of a modified 3D interpolator.

var field = function(x, y, z) {

	function lerp(y0, y1, mu) {
		return mu * y1 + (1 - mu) * y0;
	}

	var xi0 = Math.floor(x);
	var mux = x - xi0;

	var yi0 = Math.floor(y);
	var muy = y - yi0;

	var zi0 = Math.floor(z);
	var muz = z - zi0;

	var xi1 = xi0 + 1;
	var yi1 = yi0 + 1;
	var zi1 = zi0 + 1;

	var i1, i2, i3, i4;
	i1 = lerp(source(xi0, yi0, zi0), source(xi0, yi0, zi1), muz);
	i2 = lerp(source(xi0, yi1, zi0), source(xi0, yi1, zi1), muz);
	i3 = lerp(i1, i2, muy);

	i1 = lerp(source(xi1, yi0, zi0), source(xi1, yi0, zi1), muz);
	i2 = lerp(source(xi1, yi1, zi0), source(xi1, yi1, zi1), muz);
	i4 = lerp(i1, i2, muy);

	return lerp(i3, i4, mux);
};

It’s a stripped-down version of the code I use to generate isosurfaces from noise arrays. It uses linear rather than cosine interpolation. Initially, I made the change to improve its performance, but found that it also allowed a greater variety of shapes.

Following up on my last post, I was able to generate a scene with less eye static.

There are two important changes under the hood. One is the noise generator that we sample to construct the field. I removed the huge multipliers and offsets from the old function, leaving the essential trig/polynomial stuff.

var v = Math.cos(x0 + Math.sin(y0 + Math.cos(z0) * x0) * z0);

What remains can’t properly be called a noise function. If I remove the sampling code and graph the function itself, this becomes pretty obvious.

It’s all foldy and warpy, but it’s not noisy. There is structure here. It comes out in the end.

The other change is the addition of a “floor”. I’ve noticed that when I generate 3D environments that go off in all directions and try to navigate them, I become disoriented quickly. I’ve been toying with the idea of creating a game based in such an environment, and this is the biggest obstacle. Humans evolved in a gravity well. Even in virtual reality, we need a sense of where “down” is. Take that away, and I’m not sure anyone will want to play for very long.

I’ve been marching the cubes again, looking for interesting spaces to march them through. Most of these spaces have been based around Perlin noise generators, which simulate smooth functions by interpolating across a grid of random numbers. They do a fine job of creating a blobby-looking world, assuming you like that sort of thing.

Hm. What else you got?

The WebGL Caves demo uses a point field to fine effect, so I thought I’d give that a try. I managed to create things I liked, but I was missing one of the benefits of a noise generator: it’s usable everywhere. Point fields tend to be limited to a finite set of source points. (I suspect an infinite set would have difficulty operating in polynomial time.)

Of course, you can always cheat. Cheaters always prosper, right?

I needed a field function that could simulate an infinite number of points. To keep it simple, I decided to map these points to integral boundaries. (If this were a film, you’d be hearing ominous foreshadowing music right about now.)

// generate the upper and lower bounds 
var x0 = Math.floor(x);
var x1 = x0 + 1;
var y0 = Math.floor(y);
var y1 = y0 + 1;
var z0 = Math.floor(z);
var z1 = z0 + 1;

The (x, y, z) point is whatever real point in space we want to get a field value for. I obtain the integral upper and lower bounds. From these, I can build a cube of points that surround the supplied point, and generate a sum of contributions to the total field.

// sum over the contributions to the field
// from each point on the cube
var f = 0;
f += con(x0, y0, z0, x, y, z);
f += con(x0, y0, z1, x, y, z);
f += con(x0, y1, z0, x, y, z);
f += con(x0, y1, z1, x, y, z);
f += con(x1, y0, z0, x, y, z);
f += con(x1, y0, z1, x, y, z);
f += con(x1, y1, z0, x, y, z);
f += con(x1, y1, z1, x, y, z);

The con() function supplies a value for the source point, and divides that value by the inverse square of the distance between the source point and the point in space, thus implementing a simple potential field.

function con(x0, y0, z0, x, y, z) {
	var dx = x - x0;
	var dy = y - y0;
	var dz = z - z0;
	var d2 = dx * dx + dy * dy + dz * dz;
	
	var v = Math.sin(x0 * 128374.123 * Math.sin(y0 * 2183423.234 * Math.sin(z0 * 94823921.2834 + 19873923.9384 * x0) + 2384923.398293 * z0) + 48392034.837439 * y0);
	return v / d2;
}

The weird nested sines thing serves as a sort of noise function. It seems to work well for integral points, and it’s defined everywhere. I also tried lookups of random numbers but that actually ran slower. I’m assuming the nested trig function is JIT-compiled to a few floating point instructions with register access, whereas the table lookup requires hitting the cache.

The end result of all this clever trickery?

Why, it’s another blobby-looking world!

Okay, they’re not exactly the same. The cheater field tends to produce tunnel-like structures instead of blobs, and its surfaces are a little rougher. These differences aren’t that obvious at a casual glance, however. I don’t see it as a viable alternative to using a Perlin noise field.

What went wrong? Well, even though I’m summing over field contributions rather than interpolating, I’m still relying on random noise sampled at integral boundaries. This underlying source tends to express itself no matter what the technique, resulting in what I’ve come to regard as visual monotony. Though the surface you see is actually different everywhere you look, it doesn’t matter. The essential form is always the same.

Now, if I could break up that visual static—clump it, cluster it, gather it all into little structures—I might have something worth looking at. We’ll see where that leads.

Ever since Web Workers arrived, I’ve been thinking about how to use them in my own stuff. I’ve been developing a game that involves a procedurally generated cliff path and I want that path, like all good things, to go on forever.

(Want to see it in action? Try the Live Demo. WSAD moves, Q for fullscreen.)

I update the scene every time the player moves a set distance from the last update. If I do this within an animation frame, I’m going to get a drop in frame rate, and possibly a visible skip in the game experience. That’s an immersion killer. Workers to the rescue!

Well, not so fast.

The GL context itself can’t be used in a worker thread, as it’s derived from a DOM object. I can’t update my display meshes directly, and I can’t send them back and forth—function members are stripped out when sending objects between threads. Only data is allowed. So: data it is. Generate updates in the worker thread, and hand the results over to the main thread for display. (I was worried that objects would be serialized JSON-style across thread boundaries, but Chrome and Firefox perform a higher-performance binary copy of the data instead.)

Creating a thread is simple enough.

T.worker = new Worker("thread.js");
T.worker.onmessage = function(e) {
	T.handle(e);
};
T.worker.onerror = function(e) {
	console.log("worker thread error: " + 
		e.message + " at line " +
		e.lineno + " in file " +
		e.filename);
};

Sadly, that error handler is all the debugging support you’re likely to get. Because the worker thread is running inside another page context, you can’t set a breakpoint in it. Back to the heady days of printf debugging! Ah, memories.

After creating the thread, I want to tell it to construct whatever objects it needs to fulfill my requests—in this case, the objects that describe the cliff path surfaces. There’s a problem, however, as I also need those objects in the main thread to handle collisions. I can’t share the surface objects directly as they contain function members. So, I create the surface maps, which are data-only, and ship those across.

// generate road and cliff surface maps
this.road.map = SOAR.space.make(128);
SOAR.pattern.randomize(this.road.map, T.seed(), 0, 1);
this.road.height = SOAR.space.makeLine(this.road.map, 6, 0.05);

this.cliff.map = SOAR.space.make(128, 128);
SOAR.pattern.walk(this.cliff.map, T.seed(), 8, 0.05, 1, 0.5, 0.5, 0.5, 0.5);
SOAR.pattern.normalize(this.cliff.map, 0, 1);
var surf0 = SOAR.space.makeSurface(this.cliff.map, 10, 0.05, 0.1);
var surf1 = SOAR.space.makeSurface(this.cliff.map, 5, 0.25, 0.5);
var surf2 = SOAR.space.makeSurface(this.cliff.map, 1, 0.75, 1.5);
this.cliff.surface = function(y, z) {
	return surf0(y, z) + surf1(y, z) + surf2(y, z);
};

// send the maps to the worker thread and let it initialize
T.worker.postMessage({
	cmd: "init",
	map: {
		road: this.road.map,
		cliff: this.cliff.map
	},
	seed: {
		rocks: T.seed(),
		brush: T.seed()
	}
});

On the thread side, a handler picks up the message and routes it to the necessary function.

this.addEventListener("message", function(e) {

	switch(e.data.cmd) {
	case "init":
		init(e.data);
		break;
	case "generate":
		generate(e.data.pos);
		break;
	}

}, false);

The initialization function uses the surface maps to build surface objects, plus a set of “dummy” mesh objects.

function init(data) {

	// received height map from main thread; make line object
	road.height = SOAR.space.makeLine(data.map.road, 6, 0.05);
	// generate dummy mesh for vertex and texture coordinates
	road.mesh = SOAR.mesh.create(display);
	road.mesh.add(0, 3);
	road.mesh.add(0, 2);

	// received surface map from main thread; make surface object
	var surf0 = SOAR.space.makeSurface(data.map.cliff, 10, 0.05, 0.1);
	var surf1 = SOAR.space.makeSurface(data.map.cliff, 5, 0.25, 0.5);
	var surf2 = SOAR.space.makeSurface(data.map.cliff, 1, 0.75, 1.5);
	cliff.surface = function(y, z) {
		return surf0(y, z) + surf1(y, z) + surf2(y, z);
	};
	cliff.mesh = SOAR.mesh.create(display);
	cliff.mesh.add(0, 3);
	cliff.mesh.add(0, 2);

	// received RNG seed
	brush.seed = data.seed.brush;
	brush.mesh = SOAR.mesh.create(display);
	brush.mesh.add(0, 3);
	brush.mesh.add(0, 2);

	rocks.seed = data.seed.rocks;
	rocks.mesh = SOAR.mesh.create(display);
	rocks.mesh.add(0, 3);
	rocks.mesh.add(0, 2);
}

Creating these dummy objects might seem strange. Why not just use arrays? Well, the mesh object wraps a vertex array plus an index array, and provides methods to deal with growing these arrays and handling stride and so on. It’s more convenient and means I have to write less code. When I send the mesh object across the thread boundary, I can simply treat it as a data object.

On every frame update, I check the player’s position, and once it’s moved a set distance from the position of the last update, I tell the worker thread to get busy.

update: function() {

	SOAR.capture.update();
	T.player.update();

	// update all detail objects if we've moved far enough
	var ppos = T.player.camera.position;
	if (T.detailUpdate.distance(ppos) > T.DETAIL_DISTANCE) {

		T.worker.postMessage({
			cmd: "generate",
			pos: ppos
		});

		T.detailUpdate.copy(ppos);
	}

	T.draw();
}

The worker handles the request by populating the dummy meshes and sending them to the display thread.

function generate(p) {

	// lock the z-coordinate to integer boundaries
	p.z = Math.floor(p.z);

	// road is modulated xz-planar surface
	road.mesh.reset();
	indexMesh(road.mesh, 2, 64, function(xr, zr) {
		var z = p.z + (zr - 0.5) * 16;
		var y = road.height(z);
		var x = cliff.surface(y, z) + (xr - 0.5);
		road.mesh.set(x, y, z, xr, z);
	}, false);

	// cliff is modulated yz-planar surface
	// split into section above path and below
	cliff.mesh.reset();
	indexMesh(cliff.mesh, 32, 64, function(yr, zr) {
		var z = p.z + (zr - 0.5) * 16;
		var y = road.height(z) + yr * 8;
		var x = cliff.surface(y, z) + 0.5;
		cliff.mesh.set(x, y, z, y, z);
	}, false);
	indexMesh(cliff.mesh, 32, 64, function(yr, zr) {
		var z = p.z + (zr - 0.5) * 16;
		var y = road.height(z) - yr * 8;
		var x = cliff.surface(y, z) - 0.5;
		cliff.mesh.set(x, y, z, y, z);
	}, true);

	// brush and rocks are generated in "cells"
	// cells occur on integral z boundaries (z = 0, 1, 2, ...)
	// and are populated using random seeds derived from z-value

	brush.mesh.reset();
	(function(mesh) {
		var i, j, k;
		var iz, x, y, z, a, r, s;
		// 16 cells because path/cliff is 16 units long in z-direction
		for (i = -8; i < 8; i++) {
			iz = p.z + i;
			// same random seed for each cell
			rng.reseed(Math.abs(iz * brush.seed + 1));
			// place 25 bits of brush at random positions/sizes
			for (j = 0; j < 25; j++) {
				s = rng.get() < 0.5 ? -1 : 1;
				z = iz + rng.get(0, 1);
				y = road.height(z) - 0.0025;
				x = cliff.surface(y, z) + s * (0.5 - rng.get(0, 0.15));
				r = rng.get(0.01, 0.1);
				a = rng.get(0, Math.PI);
				// each brush consists of 4 triangles
				// rotated around the center point
				for (k = 0; k < 4; k++) {
					mesh.set(x, y, z, 0, 0);
					mesh.set(x + r * Math.cos(a), y + r, z + r * Math.sin(a), -1, 1);
					a = a + Math.PI * 0.5;
					mesh.set(x + r * Math.cos(a), y + r, z + r * Math.sin(a), 1, 1);
				}
			}
		}
	})(brush.mesh);

	rocks.mesh.reset();
	(function(mesh) {
		var o = SOAR.vector.create();
		var i, j, k;
		var iz, x, y, z, r, s;
		var tx, ty;
		for (i = -8; i < 8; i++) {
			iz = p.z + i;
			// same random seed for each cell--though not
			// the same as the brush, or rocks would overlap!
			rng.reseed(Math.abs(iz * rocks.seed + 2));
			// twenty rocks per cell
			for (j = 0; j < 20; j++) {
				s = rng.get() < 0.5 ? -1 : 1;
				z = iz + rng.get(0, 1);
				y = road.height(z) - 0.005;
				x = cliff.surface(y, z) + s * (0.5 - rng.get(0.02, 0.25));
				r = rng.get(0.01, 0.03);
				tx = rng.get(0, 5);
				ty = rng.get(0, 5);
				// each rock is an upturned half-sphere
				indexMesh(mesh, 6, 6, function(xr, zr) {
					o.x = 2 * (xr - 0.5);
					o.z = 2 * (zr - 0.5);
					o.y = (1 - o.x * o.x) * (1 - o.z * o.z);
					o.norm().mul(r);
					mesh.set(x + o.x, y + o.y, z + o.z, xr + tx, zr + ty);
				}, false);

			}
		}
	})(rocks.mesh);

	// send mesh data back to main UI
	postMessage({
		cmd: "build-meshes",
		cliff: cliff.mesh,
		road:  road.mesh,
		brush: brush.mesh,
		rocks: rocks.mesh
	});
}

Once it’s received an update, the display thread copies over the mesh data.

copyMesh: function(dest, src) {
	dest.load(src.data);
	dest.length = src.length;
	dest.loadIndex(src.indexData);
	dest.indexLength = src.indexLength;
},

build: function(data) {
	this.cliff.mesh.reset();
	this.copyMesh(this.cliff.mesh, data.cliff);
	this.cliff.mesh.build(true);

	this.road.mesh.reset();
	this.copyMesh(this.road.mesh, data.road);
	this.road.mesh.build(true);

	this.brush.mesh.reset();
	this.copyMesh(this.brush.mesh, data.brush);
	this.brush.mesh.build(true);

	this.rocks.mesh.reset();
	this.copyMesh(this.rocks.mesh, data.rocks);
	this.rocks.mesh.build(true);
}

And that’s that. Nice work, worker! Take a few milliseconds vacation time.