Mesh Breeding

Morphose was the first demo I posted for the JS1K Spring-2013 challenge. The idea came when I was trying to apply my simple 3D renderer to different kind of scenes, while my head was buzzing with a resurgent interest in the demoscene. Morphose just sprouted out of this context, almost by accident.
I was trying to tesselate a planet, discovered cube-mapping, and the next moment I was observing the strange offspring a cube and a sphere can generate when mixed. Some tweakings later, I had a new demo for js1k...

Now in this article, I will try to formalize the whole process, covering the meshes generation, the tweening, the tweaking, etc. This demo is quite simple, but I found some results interesting, and I hope you will.

Manipulated structures

A mesh, the 3D representation of our object geometry, is a complex structure, usually defined by faces and vertices. There are many different ways to implement all this.

For instance, in my article about the Painter's Algorithm, I've opted for something like $Mesh: Array<Faces>$ with $Faces: Array<Vertex>$ and $Vertex: Array<float>$ (the 3 cartesian coordinates). Thanks to the underlying use of pointers, this implementation was quite light.

But in this demo, my main constraint was the code concision, so I opted for a different solution. Each face is directly an $Array<float>$, like this: $TriangularFace = [X_1, Y_1, Z_1, X_2, Y_2, Z_2, X_3, Y_3, Z_3]$ with $(X_n, Y_n, Z_n)$ the cartesian coordinates of each vertex.

This structure is more compact, but heavier: every face has its vertices values hard-coded. Unlike the previous implementation where the faces shared pointers to the same common vertices, here each face is independant to the other ones (the vertices are duplicated). So we aren't exactly manipulating a coherent mesh, but a collection of faces we could explode at will (which is done in the demo).

Rendering

As it is better not to walk blind, let's deal first with the rendering of our yet-to-be-created scene. For that, we can use the simple renderer described in my previous article, so please read it if you need the explanations.

Only minor modifications are required to adapt it to the specificity of our mesh structure. However, as we are limited in the number of bytes, we should also condense the whole, even if it means losing in clarity or generality (the code below is still much crush-able, by condensing some operations for instance):

/**
 * ===Render===
 * Projects and renders the scene. - To be called every frame.
 * Parameters:
 *	- sceneFaces 	 (Array>):	Faces defining the scene to render
 *	- canvas 		 (Canvas): 				Output canvas
 *	- context 		 (CanvasContext): 		Context of the output canvas
 *	- camPosition 	 (Vector3): 			Position of the camera
 *	- camOrientation (Vector3): 			Orientation of the camera
 */
function Render (sceneFaces, canvas, context, camPosition, camOrientation) {
	
	// Clearing the canvas (not optimal, but short) and adapting its size to the screen:
	var canvasWidth = canvas.width = innerWidth-21,
		canvasHeight = canvas.height = innerHeight-21;
	canvasWidth/=2; canvasHeight/=2;

	// PROJECTION:
	var cosYaw = Math.cos(camOrientation[0]),
		sinYaw = Math.sin(camOrientation[0]),
		cosPitch = Math.cos(camOrientation[1]),
		sinPitch = Math.sin(camOrientation[1]),
		cosRoll = Math.cos(camOrientation[2]),
		sinRoll = Math.sin(camOrientation[2]),
		minDim = (canvasWidth < canvasHeight) ? canvasWidth : canvasHeight;

	var screenCoord = [];
	
	for (l in sceneFaces) {  // Not optimal, but shorter.
		screenCoord[l] = [];
		
		for (j = 9;j;) {
			// 3D Projection:
			var relZ = sceneFaces[l][--j] - camPosition[2],
				relY = sceneFaces[l][--j] - camPosition[1],
				relX = sceneFaces[l][--j] - camPosition[0],
				
				temp1 = cosYaw*relY - sinYaw*relX,
				temp2 = cosRoll*relZ + sinRoll*(sinYaw*relY + cosYaw*relX),
				
				dX = cosRoll*(sinYaw*relY + cosYaw*relX) - sinRoll*relZ,
				dY = sinPitch*temp2 + cosPitch*temp1,
				dZ = cosPitch*temp2 - sinPitch*temp1;
			
			// Transform to project on the screen:
			screenCoord[l].push(dZ
								dX / dZ * minDim + canvasWidth,
								dY / dZ * minDim + canvasHeight); 					
		}
		// If we have other pieces of info we want to pass to the projected face:
		screenCoord[l][9] = sceneFaces[l][9]; // Here it is the distance to the center of the mesh.
	}
	
	// PAINTING:
	screenCoord.sort(function(f1,f2){return f2[10]-f1[10]}); // Sorting
	
	for (l in screenCoord) // Evaluating the face color and drawing it  (to adapt):
		context.strokeStyle = context.fillStyle = 'hsl('+[
			60*screenCoord[l][9],				// Hue - Function of the distance.
			'70%',								// Saturation - constant
			100-l/screenCoord.length*50]+'%)',	// Luminosity - Cheap fog effect by using the index
		
		context.beginPath(),
		context.moveTo(screenCoord[l][8], screenCoord[l][7]),
		context.lineTo(screenCoord[l][5], screenCoord[l][4]),
		context.lineTo(screenCoord[l][2], screenCoord[l][1]),
		context.closePath(),
		context.stroke(),
		context.fill();
};

Mesh weaving

To get the shape-shifting object, the idea is the following: we generate two meshes, a cube and a sphere, with the same number of vertices/faces (each one is associated with an other one of the 2nd mesh). Then every frame, we compute an intermediate mesh from a pseudo-tweening between the geometries of the two original ones, and display it.

In this section, we will cover the creation of our two primitive meshes with as few bytes as possible.

Cube

The objective is to define a cube of size $D$, centered on the origin (to simplify the generation), and made of $6 \cdot N^2$ triangular faces ($N^2$ per side). We could just statically define its structure, like I did in an example for the rendering:

// Definition of a simple 2x2x2 cube, made of quad faces
// (building the mesh procedurally isn't complicated, but not the subject of this article):
var cubeVertices = [[-1,  1,  1], [ 1,  1,  1], [ 1, -1,  1], [-1, -1,  1],
					[-1,  1, -1], [ 1,  1, -1], [ 1, -1, -1], [-1, -1, -1]];
var cubesQuadriFaces = [[cubeVertices[0], cubeVertices[1], cubeVertices[2], cubeVertices[3]],
						[cubeVertices[4], cubeVertices[5], cubeVertices[6], cubeVertices[7]],
						[cubeVertices[1], cubeVertices[5], cubeVertices[6], cubeVertices[2]],
						[cubeVertices[4], cubeVertices[0], cubeVertices[3], cubeVertices[7]],
						[cubeVertices[4], cubeVertices[5], cubeVertices[1], cubeVertices[0]],
						[cubeVertices[3], cubeVertices[2], cubeVertices[6], cubeVertices[7]]];

But we want a more refined mesh, with more vertices to play with later, and writing down the coordinates of our $3 \cdot 6 \cdot N^2$ vertices would be as painful as long. So... how can we procedurally define our cube? Here is a first possibility:

with each side defined as:

Do you see the pattern? Here is a condensed definition, for $n \in \{0,\dots,5\}$:

We use a modulo 3 operation to express the cyclic permutation of the coordinates (the two varrying and the one fixed), and a modulo 2 operation to define the value of the fixed coordinate. With this, we cover the 6 cases...

The only thing left is to split the sides into triangular faces (if you want to use quadfaces, the modifications are minor), which can be easily achieved with loops to sample a regular repartition of vertices and the faces:

• One loop to iterate over the 6 sides;
• Two loops to iterate over our subdivisions of our sides into N² rectangles;
• One loop of 2 iterations to divide each rectangle into the 2 triangular faces.

The final generation method is:

/**
 * ===GenerateVertexForCube===
 * Given the subdivision indices, generates the corresponding vertex for the cube mesh
 *(centered on the origin), and gives it to the current triangle faces.
 * Parameters:
 *	- i 	(Int):			Row num
 *	- j 	(Int): 			Col num
 *	- n 	(Int): 			Side of the cube we are currently dealing with
 *	- face 	(Array): Face the vertex will belong to
 */
function GenerateVertexForCube (i, j, n, face) {
	// First we generate the cube vertex. Using some modulos on the side index,
	// we can cover each case, by swapping the coordinates order or moving the vertex along the depth axis:
	var v = [i/NB_DIV*SIZE-RADIUS, j/NB_DIV*SIZE-RADIUS, RADIUS*(1-2*(n%2))], 
		x = v[n%3],
		y  = v[(n+1)%3],
		z = v[(n+2)%3];
	face.push(x, y, z);
}

var facesCube=[],	// Mesh
	NB_DIV = 16,	// Number of rows and colums per cube's side, which means our meshes will be made of 6*16*16 vertices
	SIZE = 4,		// Dimension of our meshes
	RADIUS = SIZE/2,// Mid-dim
	trId = 0;
	
// To save some bytes, we iterate desc. The idea is that for each element we iterate on,
// we evaluate the triangles faces of the square which as for top-left corner this element:
for (var n = 6; n--;)
	for (var i=NB_DIV; i--;)
		// X --- o	Schema representing the faces extracted from a square. X is the current element.
		// |  \  |
		// o --- o
		for (j = NB_DIV; j--;) for (k=2;k--;) // We iterate 2 times for each square in order to generate the 2 corresponding triangle-faces.
			// We store each face information into an array [V1.X, V1.Y, V1.Z, V2.X, V2.Y, V2.Z, V3.X, V3.Y, V3.Z, dist(V3, center)]:
			facesCube[trId] = [],
			GenerateVertexForCube(i,j, n, facesCube[trId]), 		// 1st vertex (top-left corner of the square)
			GenerateVertexForCube(i+1,j+1, n, facesCube[trId]),		// 2nd vertex (bottom-right)
			GenerateVertexForCube(i+k, j+1-k, n, facesCube[trId]),	// 3rd vertex - the one varying (either corresponding to the element on the next row,
																// or the one on the next col). We use a modulo 2 on the face's id to select the good one.
			// Byte saving trick:(faceId+1)%2 = k. And we don't mind which triangle we generate first, so k makes a cheaper way to distinguish them
			trId++;

Sphere

Now we want a sphere of diameter $D$, made of the same number $6 \cdot N^2$ of faces.

There are many possible ways to tesselate a sphere, but we have one condition we wish to fulfill: to get a smooth transition when tweening the geometries of our cube and sphere. So we are looking for a similar repartition of the vertices.

The quadcube tesselation (or cubic sphere tesselation) is what we want for our sphere. This method is commonly used to map flat textures to spheres, but can also be adapted to generate their mesh.[1]

The idea is to take a regular cube mesh (so like the one we generated), and to project every vertex on the spherical surface, by normalizing the length of the vector to the center of the mesh, to the value we want as radius.

In other words, for every vertex, we compute their distance to the center, divide their coordinates by the obtained value, and multiplie them back with the radius value.

Thus, by just adding these two operations to our previous tesselation function, we can return a sphere instead of a cube (or both):

/**
 * ===GenerateVertexForCube===
 * Given the subdivision indices, generates the corresponding vertex for the cube mesh
 *(centered on the origin), and gives it to the current triangle faces.
 * Parameters:
 *	- i 	(Int):			Row num
 *	- j 	(Int): 			Col num
 *	- n 	(Int): 			Side of the cube we are currently dealing with
 *	- faceC (Array): Face of the cube the vertex will belong to
 *	- faceS (Array): Face of the sphere the vertex will belong to
 */
function GenerateVertexForCubeAndSphere (i, j, n, faceC, faceS) {
	// First we generate the cube vertex. Using some modulos on the side index,
	// we can cover each case, by swapping the coordinates order or moving the vertex along the depth axis:
	var v = [i/NB_DIV*SIZE-RADIUS, j/NB_DIV*SIZE-RADIUS, RADIUS*(1-2*(n%2))], 
		x = v[n%3],
		y  = v[(n+1)%3],
		z = v[(n+2)%3];
	faceC.push(x, y, z);
	
	// Then the sphere vertex, by "cube-mapping" (the following formula speaks for itself):
	var dist = Math.sqrt(x*x + y*y + z*z);
	faceS.push(x/dist*RADIUS, y/dist*RADIUS, z/dist*RADIUS);
	
	// return dist; // Value used in the demo to define the color of each face.
}

var facesCube=[],	// Cube Mesh
	facesSphere=[],	// Sphere Mesh
	NB_DIV = 16,	// Number of rows and colums per cube's side, which means our meshes will be made of 6*16*16 vertices
	SIZE = 4,		// Dimension of our meshes
	RADIUS = SIZE/2,// Mid-dim
	trId = 0;
	
for (var n = 6; n--;)
	for (var i=NB_DIV; i--;)
		// X --- o	Schema representing the faces extracted from a square. X is the current element.
		// |  \  |
		// o --- o
		for (j = NB_DIV; j--;) for (k=2;k--;) // We iterate 2 times for each square in order to generate the 2 corresponding triangle-faces.
			facesCube[trId] = [],
			facesSphere[trId] = [],
			GenerateVertexForCube(i,j, n, facesCube[trId], facesSphere[trId]), 			// 1st vertex (top-left corner of the square)
			GenerateVertexForCube(i+1,j+1, n, facesCube[trId], facesSphere[trId]),		// 2nd vertex (bottom-right)
			GenerateVertexForCube(i+k, j+1-k, n, facesCube[trId], facesSphere[trId]),	// 3rd vertex - the one varying
			trId++;

Mingle Mingle Little Mesh

The next step is the dynamic generation of our metis shape. For every couple of vertices from the cube and sphere, we simply want to calculate an intermediate one.

We could use a linear tweening over time, like in the example above... or go for something crazier. Basically, you can use any function you want, taking as parameters, among others, your two vertices, and returning a new, more-or-less correlated, one.

I spent much time time tweaking around such a function to get something visually interesting. Here are some observations I made which could help you create your own:

• Parameters
  • Taking time into consideration seemed evident in my case.
  • I also adopted the distance of the corresponding face to the center of the mesh. It allowed me to apply transforms per face: combined with the looseness of our structure (see first section), it's how I get the implosive-kaleidoscopic result.
  • Interactivity is always nice: I take the user's clicks into account, but you can think of other inputs.
  • An idea I couldn't integrate to my demo was the use of an external signal as main parameter. You could easily make your object dance to the music of your liking...
• Functions
  • Compute the cosine values of the smoothly-varying parameters to get some periodicity.
  • Use different prime numbers as coefficients (periods) to make the global periodicity less obvious.
  • Why restricting ourselves to the segment between our two original vertices? Go beyond (ie try to apply coefficients beyond [0, 1] to thstrong).
  • Cubic pulsations is an interesting effect I abused to deal with the sudden inputs (clicks) (learn more about at the source of the idea, Iñigo Quílez's website [2] - this website is full of coding and maths gems)

Once you got the wanted effect, just wrap it all in a function you'll call in your rendering method:

///
// Linear tweening...
// Parameters:
//	- cubeCoord - Coordinate from the 1st mesh
//	- sphereCoord - Coordinate from the 2nd mesh
// Returns: the "intermediate" value
///
function Tween (cubeCoord,sphereCoord, coef) {
	return cubeCoord*coef + sphereCoord*(1-coef); // Replace with your funky mingling effect.
}

///
// Projects and renders the scene with mingling.
///
function Paint (facesCube, facesSphere) {
	// PROJECTION:
	/** ...
	 *	Usual initialization here
	 * 	... */
	
	for (l in facesCube) {  // Not optimal, but shorter.
		screenCoord[l] = [];
		var baryDepth = 0;
		for (j = 9;j;) {
			// We compute the tweened vertex and its projection:
			var vX = Tween(facesCube[l][--j], facesSphere[l][j], coefTween) + camDist*cosPitch,
				vY = Tween(facesCube[l][--j], facesSphere[l][j], coefTween) + camDist*sinPitch*cosYaw,
				vZ = Tween(facesCube[l][--j], facesSphere[l][j], coefTween) + camDist*sinPitch*sinYaw,
					
			/** ...
			 *	Usual projection here, using vX, vY, vZ instead of the original coordinates.
			 * 	... */
		}
	}
	
	// PAINTING:
	/** ...
	 *	Usual rendering here
	 * 	... */
}

Below a small application displaying the outcome of some effects:

Polishing: Colors and movements

Here again, it's all about personal tastes.

For the coloring, I opted for a dynamic solution: the color of each face is computed just before drawing it. I use this dynamism to vary the hue over time, but also to apply a pseudo depth fog.

This effect is obtained by using the index of the sorted faces as coefficient for the luminosity (here, the further from the camera, the smaller its index, the smaller the coefficient for luminosity and thus the darker).

By the way, I now only swear by the HSL color system. If it is not the case yet, I highly recommend you to consider it, at least when it comes to represent complex scenes.

	// Method used in the demo to compute the colors - called in the painting loop.
	a.fillStyle = a.strokeStyle='hsl('+[
		500*timeCos/screenCoord[l][9],	// Hue - Function of the time and of the original distance
										//		to the origin.
		'50%',							// Saturation - constant
		l/75*Math.cos(pulseCoef/7)		// Luminosity - Function of the periodic pulse + Cheap fog
										//		effect by using the sorted index
	]+'%)',

As for the camera's movements, the shape-shifting function was already inducing momentum, inflating or deflating the mesh's dimensions.

Indeed, one consequence of having a scene containing a single element is the absence of landmarks. Without looking at the source, it is left to the viewer's appreciation to conclude if it is the camera which is nearing or the object which is growing.

I decided to only add rotations around the center of the scene (over time + binded to the mouse position), to emphasize the 3D nature of the demo.

At that point, I was kind of satisfied with the result. Only one effect was somehow hurting my sensibility, literally speaking: the collision between the inflated shape and the camera.

As much as I wanted to preserve the eye-catching unpredictability of the morphose, I found unaesthetic the obstructed effect of some collisions, when the object was imploding or stretched to its limit.

While trying to adapt the rendering method to ignore the colliding faces, I inadvertently altered my Painter's method, inverting the depth sorting... and enjoyed the resulting sight.

The solid, material, aspect of the object was lost, but that nicely solved my problem: the too-near faces which the camera was colliding with were now painted under the further ones. Instead of hitting the object's surface, we were now observing it as if inside.

Conclusion

Even if most of those methods are already covered by 3D libraries, it may come handy to know the maths or logic behind. This knowledge is one of the main reasons why I enjoyed working on those small applications.

After all, « Don't Reinvent The Wheel, Unless You Plan on Learning More About Wheels »... [3]

References

1. ^ Steven Wittens - Article - « Making Worlds 1 - Of Spheres and Cubes » - acko.net/blog/making-worlds-1-of-spheres-and-cubes
2. ^ Iñigo Quílez - Article - « Useful Little Functions » - iquilezles.org/www/articles/functions/functions.htm
3. ^ Jeff Atwood: « Don't Reinvent The Wheel, Unless You Plan on Learning More About Wheels » - codinghorror.com/blog/2009/02/dont-reinvent-the-wheel-unless-you-plan-on-learning-more-about-wheels.html