I've ported my Improved Noise algorithm to JavaScript, as the file inoise.js.

You can use it to model shapes in various ways. For example, a bumpy spheroid might be implemented like this:

    var sph = function(u,v) {
       var theta = 2 * Math.PI * u,
           phi = Math.PI * (v - .5),
           cosT = Math.cos(theta) , cosP = Math.cos(phi) ,
           sinT = Math.sin(theta) , sinP = Math.sin(phi) ;
       var x = cosT * cosP, y = sinT * cosP, z = sinP;
       var r = 1 + noise(2*x, 2*y, 2*z) / 12
                 + noise(4*x, 4*y, 4*z) / 24;
       return [ r * x, r * y, 1.3 * r * z ];
    }

Feel free to use this function in your geometric modeling.

Triangle strips allow you to keep the transfer of geometry data from your CPU to your GPU down to rougly one vertex per triangle. In the version of gl.js I provided last week, g.TRIANGLE_STRIP is already enabled, so all you need to do is add vertices to your vertices array in the proper order.

A way to do this with a general M×N mesh it to scan through rows (0 ≤ n ≤ N) in the outer loop, and by columns (0 ≤ m ≤ M) in the inner loop, scanning from left to right for even rows, then back from right to the left for odd rows. At each step of the inner loop, append the two vertices [m,n] and [m,n+1] to the vertices array. In order to avoid spurious triangles between rows, you can repeat the last vertex two more times in each row. This will create a degenerate triangle, which is harmless. To the right is an example of such an ordering.

For fine perturbations of a surface, it can be very expensive to generate and render the large number of triangles required for true surface normal perturbation. Therefore for finely detailed bumps, we sometimes just use Bump Mapping, a technique first described by Jim Blinn about 40 years ago.

The basic idea is to modulate the surface normal, within the fragment shader, to reflect the changes in surface direction that would be produced by an actual bumpy surface. Since the human eye is more sensitive to variations in shading than to variations in object silhouette, this technique can produce a fairly convincing approximation to the appearance of surface bumpiness, at a fraction of the computational cost of building finely detailed geometric models.

To do bump mapping of a procedural texture T that is defined over the (x,y,z) domain (the noise function is an example of one such procedural texture), we can think of the value of T(x,y,z) as a variation in surface height. In order to simulate the hills and valleys of this bumpy surface, we subtract the derivative of T from the normal (because the normal will point toward the valleys), and then renormalize to restore the normal vector to unit length.

We can approximate the vector valued derivative at surface point (x,y,z) by finite differences (where ε below is some very small positive number):

p₀ = T(x,y,z)

p_x = (T(x+ε, y, z) - p₀) / ε
p_y = (T(x, y+ε, z) - p₀) / ε
p_z = (T(x, y, z+ε) - p₀) / ε

normal ← normalize( normal - vec3(p_x,p_y,p_z) )

Advanced topic: Bump mapping from a texture image is more tricky, since you need to know the direction to move the surface normal with respect to changes in the u and v directions of the texture, respectively. Note that in the implementation of function createParametric(), I already compute exactly those quantities for each vertex, as ux,uy,uz and vx,vy,vz, respectively. These two direction vectors, which are both tangential to the surface, are sometimes called the tangent and binormal vectors. In order to do bump mapping from a texture image, you will need to include the tangent and binormal vectors as part of your vertex data for each vertex. This will increase the data size in each element of the vertices array from 10 numbers to 16 numbers. Only try this if you are very confident, and you think you understand the interface to WebGL.

Forward kinematics

Often we want to create hierarchical mechanisms. Such hierarchically structured mechanisms generally use forward kinematics, in which transformations form a tree structure that descends from a single root.

Here is a swinging arm, a simple example of forward kinematics.

Given a matrix object m that has methods to implement translate, rotate and scale, as well as the ability to maintain an internal stack of matrix values via push() and pop() methods, the swinging arm is implemented via the following code: m.push(); standardView(.5,.5,0,0,.5); m.translate(-.5,2,0); m.push(); m.rotateZ(sin(3*time)); m.translate(0,-1,0); m.push(); m.scale(.1,1,.1); unitCube(); m.pop(); m.translate(0,-1,0); m.rotateZ(.5 - .5 * cos(3*time)); m.translate(0,-1,0); m.push(); m.scale(.1,1,.1); unitCube(); m.pop(); m.pop(); m.pop();

For clarity, I implemented the above example using push and pop methods. But if you want to create a system that allows users to put together their own object hierarchies, you are better off using explicit objects.

In such a scheme, each object would have its own matrix transformation, and would also maintain a list of child objects. The transformation of a child object would be relative to its parent, thereby forming a tree of object nodes.

When creating animations, it is often convenient to specify values only at certain frames, and then use smooth curves to interpolate values at the frames between these key frames. In-betweening with ease curves which start and stop with zero derivative, such as 3t²-2t³ produce natural looking interpolations.

Here is a hand that can be animated by setting key frames.

To show different animations of the hand, type "a1" or "a2" or "a3" followed by the space key. You can also read the on-line instructions on that page to learn how to vary the key-frame animation.

Inverse kinematics is the opposite of forward kinematics. In an inverse kinematic system, you start with the location of an end effector (such as a hand or a foot or a robot gripper), and the system needs to figure out the corresponding chain of intermediate matrices from the root of the object hierarchy. There are two common approaches to inverse kinematics, general N-link IK and special purpose 2-link IK. The N-link approach requires an iterative solver, whereas the 2-link approach has a closed form solution, with no need for iteration. To talk about 2-link IK, consider the case of an leg, where the locations of the hip and ankle are known, and we need to find the location of the knee. To make the math simpler, let's assume a hip located at the origin [0,0,0], an upper leg of length A and a lower leg of length B. If the ankle is located at some point P, we want to find the knee location Q. Knee location Q can lie anywhere on the circle of intersection between two spheres: The sphere of radius A centered at hip location [0,0,0] and the sphere of radius B centered at ankle location P. To pick the best point on this circle, we need to specify an aiming direction D that says which way is "forward" (since knees generally point forward). What we need is a function that computes Q, given A, B, P and D. Here is my solution to this, given a two-link chain at the origin, with limb lengths a and b, respectively, reaching toward point C, with elbow aim hint vector D: c = C•C x = ((a2-b2)/c + 1)/2 D -= C(C•D)/c y = √max(0, a2 - x2c) Q = xC + yD/|D| My implementation of this in Java is here. Feel free to use and adapt my algorithm.

There is an entire sub-field of computer animation devoted to swarms and particle animation. One historically important example of this was Craig Reynold's Boids, which he first published in 1987. This technique for simulating herding and flocking behavior showed convincingly that a few simple procedural rules can create the impression of compelling group and social behavior. In cinema, this technique was first used in the 1992 feature film Batman Returns, and has since become a staple of the movie and game special effects industry.

You can create a procedurally animated mesh, in which you define a VertexFilter. Behind the scenes this object loops through a mesh's vertices one by one, handing each one to a method filterVertex(double[] v) that allows you to modify their x,y,z values in place.

If you implement something like this in JavaScript, you will need to keep two copies of your mesh: The original unmodified mesh, and the one that gets copied from the original and then vertex-filtered at every animation frame.

When you modify the mesh, you will end up needing to change the vertex normals. To recompute vertex normals for a mesh, you can use the following algorithm:

1. Compute the normal to the plane of all the mesh's faces. You can do this for any polygonal face with vertices v₀ ... v_n-1 by summing the cross products of successive edges: (v_{i+1mod n} - v_i) × (v_{i+2mod n} - v_{i+1mod n})

2. For every vertex, sum the face normals of all faces adjoining that vertex, then normalize the result. This will give you a good approximation to the normal at that vertex.

If you are feeling ambitious, you can also try implementing this sort of filter in a vertex shader. In that case, you will need to be a bit more clever about modifying vertex normals. For example (since you will have greater compute power to work with), you can do finite differences to compute the new surface normals.

      timeL += saw(time)
      timeR += saw(time+1)

      function saw(t) = { t%=2; return t<1 ? t : 2-t; }

Layered animation allows you to create layered transparency for parts of movement, in a way analogous to how PhotoShop lets you do layered transparency for just some pixels of an image but not others.

Examples of uses of particle systems:

This week we just scratched the surface of particle systems. Next week we will go into more detail about this rich topic. Meanwhile, here's a high level introduction to the subject.

Particle systems are very flexible; they can be used to simulate many natural phenomena, including water, leaves, clouds/fog, snow, dust, and stars.

When they are "smeared out" so that they are rendered as trails, rather than as discrete particles, they can be used to render hair, fur, grass, and similar natural objects.

Basic mechanism:

Generally speaking, particles in a particle system begin by being emitted from the surface of an "emitter" object. When a particle begins its life, it has an initial trajectory, which is usually normal to the surface of the emitter object.

After that, the path of the particle can be influenced by various things, including gravity and other forces, and collisions with object surfaces.

Particles usually have a lifetime, after which they are removed from the system.

Also, a particle can itself be an emitter of other particles, spawning one or more other particles in the course of its lifetime. In this way, particles can be made to cascade, generating complex patterns such as flamelike shapes.

All of the qualities of a particle -- its lifetime, its velocity and mass, how many particles it spawns, can be a randomly chosen value within some range. By controlling the ranges from which these various properties are chosen, artists can control the look and feel of a particle system.

History:

Particle systems were first developed by Bill Reeves at Pixar in 1981. Its first public use was for the Genesis Effect in Star Trek 2, the Wrath of Khan 1982. Since then, it has become a mainstay of computer graphic films and games.

Rendering:

One nice thing about particle systems is that they are not that difficult to implement in vertex shaders. In addition to their behavior, their appearance can also be hardware accelarated. One common technique is to render each particle as a "billboard": a polygon that is always perpendicular to the camera. This polygon is textured with a translucent image of a fuzzy spot. The effect is to make the particle look like a small gaseous sphere, but at fairly low computational cost.

Here we discuss an approximation to animating the soft skin of game characters which is cheap and can be implemented very easily in vertex shaders.

In an animated character, the rigid bones of the character's articulating skeleton are generally covered in some sort of soft skin. A fairly accurate way to model this skin would be to think of each point on its surface (approximated by the vertices of a polygon mesh), as being influenced by the various rigid matrix transformations of nearby bones in the skeleton.

To do this properly, one would compute a composite transformation matrix that was influenced by all of those individual bone matrices. However, in practice this is a more expensive operation than can be accommodated in the real-time rendering budget of game engines.

So most games instead do a kind of cheat called linear blend skinning. The basic idea is to compute the matrix transformation of each vertex as a part of each of the various nearby bones. This will result in a different position for each bone. Then these positions are blended together into a weighted average to find the final position for the vertex.

To make this work, each vertex maintains a list of [bone,weight] pairs, where all of the respective weights sum to 1.0.

This technique is very fast, and very easy to implement efficiently in hardware accelarated vertex shaders, but it has some practical deficiencies. For example, twisting between the two ends of a limb can cause the middle of the limb to appear to collapse. To handle cases like this linear blend skinned skeletons are rigged with extra bones to mitigate the effects of such problems.

Marching Squares (2D case):

Given a function f(x,y), where (x,y) are pixels in an image, marching squares is a way to approximate the curve along f(x,y) = 0. For example, consider the function below (which you can edit), evaluated over the unit square: function(x, y) { return 6 / (.1 + (2*x-0.8)*(2*x-0.8) + (2*y-1.0)*(2*y-1.0)) + 1 / (.1 + (2*x-1.6)*(2*x-1.6) + (2*y-1.0)*(2*y-1.0)) - 16; } RUN WITH CHANGE To the right you can see a very low resolution (10×10) rendering of this function. Suppose we want to know the shape of the curve where this function has its roots (that is, where f(x,y) = 0). Ideally we'd like to know this without having to evaluate the function at more samples.
Marching squares provides a way to get a sense of what a level-set curve of a unction looks like, without taking more samples. The key insight is that the curve can be approximated just by looking at those pixels bounded by corner points (i,j),(i+1,j),(i+1,j+1),(i,j+1) for which the signs of f at the four corners are not all the same. If the signs of f are different at two adjoining corner points of a pixel's square, that means the curve will cut the edge which connects those two corners.

One thing we need to figure out is where :his transition happens along each such edge. Given a value of A at corner a, and a value of B at adjoining corner b, we can compute the proportional distance t of the transition point along the edge [a,b] by observing, by similar triangles:      t/A = (1-t)/-B →      -Bt = (1-t)A →      -Bt = A - tA →      (A-B)t = A →      t = A / (A-B)

Each corner can have two states: f<0 or f≥0, so in general, there are sixteen cases, as shown in the diagram to the right. Consider the second case along the top row of the diagram, where f at the top left corner (i,j) of a pixel is positive, but is negative at the other three corners of the pixel. In this case, there is a transition point p along the top edge -- between (i,j) and (i+1,j), and another transition point q along the left edge -- between (i,j) and (i,j+1). Within this pixel, we can approximate the f(x,y)==0 curve by the line segment [p,q]. So that for any pixel we need to do three things: Figure out which edges, if any, of the pixel contain transition points Compute the locations of these points; Draw line segments between transition points, to approximate pieces of the curve.

Marching Cubes (3D case): Marching cubes is the 3D equivalent of marching squares. Rather than approximate a closed curve where f(x,y)=0 via small straight edges inside square pixels, as in marching squares, the marching cubes algorithm approximates a closed surface where f(x,y,z)=0 via small triangles inside cubic voxels. The technical paper describing this algorithm, published by Lorensen and Cline in 1987, has been cited more often than any other paper in the field of computer graphics. Each voxel cube has eight corners, which can be numbered as follows: 0 x=0 y=0 z=0 1 x=1 y=0 z=0 2 x=0 y=1 z=0 3 x=1 y=1 z=0 4 x=0 y=0 z=1 5 x=1 y=0 z=1 6 x=0 y=1 z=1 7 x=1 y=1 z=1 Because the value of f(x,y,z) at each of these eight corners can be either positive or negative, there are 28 or 256 cases to consider. These are shown in the figure to the right. I have included a table to make things easier for you. The table has 256 entries, one for each of the 256 cases. Each entry contains between 0 and 4 triangles, which is the number of triangles that will be produced by the marching cube algorithm for a voxel of that type. Each triangle is described by the three edges of the cube that contain its respective vertices, and each vertex is described by identifying one cube corner as well as the orientation of the cube edge that contains that vertex. For example, a particular vertex of a triangle in the table may be described by the number sequence 0,1, indicating that this vertex lies on edge [0,1] of the cube. This is the edge that connects the x=0 y=0 z=0 corner of the cube and the x=1 y=0 z=0 corner of the cube.

Marching Tetrahedra (simpler to implement, less efficient):

To avoid the big table look-up of Marching Cubes, a technique I've used is to split up each voxel into six tetrahedra. Given the same corner numbering we used for Marching Cubes, we can partition the voxel cube by "turning on" the binary bits of the numbered corners in different orders, giving the six tetrahedra: Since a tetrahedron has only four edges, there are only two non-trivial boundary cases: (1) the boundary is a single triangle, or (2) the boundary is a four sided shape, which can be split into two triangles. This algorithm is less efficient than Marching Cubes, because it generally produces more triangles for each boundary cube. However it requires much less code, and therefore is easier to program, to debug, and to port to a vertex shader.