Lab 5: Basic Mesh Optimizations

Highlights of this lab:

In this lab, you will learn:

Assignment

After the lab lecture, you have one week to modify the files in Lab5.zip to:

Lecture Notes

drawElements vs drawArrays

When you did lab 2 you might have found that you repeated exactly the same vertex information multiple times while creating your drawings. This is wasteful, since all the data is repeated. It is common for one vertex to be repeated multiple times in a mesh. It would be better if we could create a vertex with all its associated attributes once and refer back to it using a simple number.

For example, given a mesh like this one:

Figure 1: A typical rectangular mesh. Notice that many vertices are part of several triangles. Inner vertices all belong to 6 triangles. Outer vertices may belong to 1, 2 or 3 triangles. This leads to much duplication

a call to drawArrays with the TRIANGLES primitive would repeat some vertices 6 times. Even trying to be efficient with TRIANGLE_STRIP would cause all vertices to be repeated twice. If you are repeating colours, texture coordinates and lighting information this can be rather expensive. Fortunately, you can use an index buffer to reduce repetition. Consider the cube from the transformations lab. It was represented like this: 

var cubeVerts = [
	[ 0.5, 0.5, 0.5, 1], //0
	[ 0.5, 0.5,-0.5, 1], //1
	[ 0.5,-0.5, 0.5, 1], //2
	[ 0.5,-0.5,-0.5, 1], //3
	[-0.5, 0.5, 0.5, 1], //4
	[-0.5, 0.5,-0.5, 1], //5
	[-0.5,-0.5, 0.5, 1], //6
	[-0.5,-0.5,-0.5, 1], //7
];

var shapes = {
	wireCube: {Start: 0, Vertices: 30},
	solidCube: {Start: 30, Vertices: 36},
	axes: {Start: 66, Vertices: 6}
};

//Look up patterns from cubeVerts for different primitive types
var cubeLookups = [
//Wire Cube - use LINE_STRIP, starts at 0, 30 vertices
	0,4,6,2,0, //front
	1,0,2,3,1, //right
	5,1,3,7,5, //back
	4,5,7,6,4, //right
	4,0,1,5,4, //top
	6,7,3,2,6, //bottom
//Solid Cube - use TRIANGLES, starts at 30, 36 vertices
	0,4,6, //front
	0,6,2,
	1,0,2, //right
	1,2,3, 
	5,1,3, //back
	5,3,7,
	4,5,7, //left
	4,7,6,
	4,0,1, //top
	4,1,5,
	6,7,3, //bottom
	6,3,2,
];

Which is actually pretty compact. If we don't expand it in JavaScript like we did last week, and instead send the lookups as unsigned bytes to a WebGL buffer for drawing, the total data for this representation is:

vertex bytes = 8 vertices * 4 components * 4 bytes/component = 128 bytes

lookup bytes = 36 lookups * 1 byte/lookup = 36 bytes

Total = 194 bytes.

If we were to fully expand these arrays as was done in Lab 3, you would end up with 66 fully specified vertices:

66 vertices * 4 components * 4 bytes/component = 1056 bytes

That's 194 vs 1056 - using elements the result is 1/5 the size. This may not seem like much, but it can add up quickly - and all that data needs to be transferred from place to place.

Luckily WebGL provides an easy to use solution for situations like this. The cubeLookups can be loaded into a special buffer called an element array buffer. These buffers provide the indices for the regular ARRAY_BUFFER that you have become familiar with. They have one limitation that makes them a little less efficient than you might want though - the indices they specify refer to the same index in all regular array buffers. If you need the same position in blue and in green during the same draw, those will be duplicate positions at separate indices.

You can load the element array buffer with a regular arrays of integers, just like the cubeLookups array. To specify a buffer for the array, you create a buffer as usual, but bind it as ELEMENT_ARRAY_BUFFER. The buffer data must be copied as an integer type, so you can't use Dr. Angel's flatten() function to convert the array for use in the shader since it only produces 1D float array outputs. Instead, there are some simple copy constructors built into Javascript that do the job. For unsigned bytes, you can use Uint8Array.from() and for unsigned short integers you can use Uint16Array.from(). Which you use will depend on how many points there are in your mesh.

So, to load the cube's elements array you could use this code:

//cubeElements should probably so you can rebind it later as needed
cubeElements = gl.createBuffer();
gl.bindBuffer( gl.ELEMENT_ARRAY_BUFFER, cubeElements );
gl.bufferData( gl.ELEMENT_ARRAY_BUFFER, Uint8Array.from(cubeLookups), gl.STATIC_DRAW );

Only one element array buffer can be bound to a shader at a time, so the equivalent to vertexAttribPointer() is folded into the the drawElements() function. Draw elements is specified as:

void drawElements( mode, count, type, indices);

Where:

Here's how that would look in our render function:

gl.drawElements( gl.LINE_STRIP, shapes.wireCube.Vertices, gl.UNSIGNED_BYTE, shapes.wireCube.Start);

Using TRIANGLE_STRIP for Efficient Surfaces

As suggested in the previous section, you can use triangle strips to reduce the number of vertices required to specify a surface. They typically require n+2 vertices to fully specify an inline strip of triangles. The path through the vertices is usually backwards-N or backwards-Z shaped. For example following strip could be started at either end:

Figure 2: The N or sawtooth path that makes up a typical triangle strip. If the end points were reversed, so that the N's were forward, the triangles would be facing backward. To move upwards instead of sideways, rotate the N's as needed - now they should be backward Z's. If you can, try rotating your screen to see if you see any normal N's or Z's - it should be impossible without X-ray vision.

If you need to move to a new strip, you double each end point. This causes a pair of zero width degenerate triangles which won't be drawn. Your next triangle will need to haveIf used sparingly, this can still save a lot of space. You will find examples of this technique in this week's exercise.

Getting direction right can be tricky, so I've added a rule that makes the back of triangles bright green. That way, you'll spot your errors quickly.

Brief description of .OBJ file format

The .OBJ file format is like element arrays on steroids. They mostly contain lists of three different types of coordinates: vertex (position), normal (surface orientation for lighting), and texture. These lists are individually indexed by a list of faces. Each face consists of at least three sets of indices. Each set must have a vertex index, and can optionally specify separate normal and texture indices. The file can also contain references to external .MTL material descriptions.

Here's a sample from the .OBJ file for a cube:

# Blender v2.69 (sub 0) OBJ File: ''
# www.blender.org
# formatted for readability by Alex Clarke

# object name
o Cube

# vertices
v 1.000000 -1.000000 -1.000000
v 1.000000 -1.000000 1.000000
v -1.000000 -1.000000 1.000000
v -1.000000 -1.000000 -1.000000
v 1.000000 1.000000 -0.999999
v 0.999999 1.000000 1.000001
v -1.000000 1.000000 1.000000
v -1.000000 1.000000 -1.000000

# normals
vn 0.000000 -1.000000 0.000000
vn 0.000000 1.000000 0.000000
vn 1.000000 -0.000000 0.000000
vn 0.000000 -0.000000 1.000000
vn -1.000000 -0.000000 -0.000000
vn 0.000000 0.000000 -1.000000
vn 1.000000 0.000000 0.000001


s off

# faces - the // in the middle represents missing texture coordinates
#       - this cube is ready to be lit, but not textured
f 1//1 2//1 4//1
f 5//2 8//2 6//2
f 1//3 5//3 2//3
f 2//4 6//4 3//4
f 3//5 7//5 4//5
f 5//6 1//6 8//6
f 2//1 3//1 4//1
f 8//2 7//2 6//2
f 5//7 6//7 2//7
f 6//4 7//4 3//4
f 7//5 8//5 4//5
f 1//6 4//6 8//6

Comments are in-line and are preceeded by a # symbol.

This is just the beginning. Materials, curves, surfaces and more can be described in a .obj file. Here's the spec for the OBJ 3.0 file format.

Using Blender to create j3di friendly .OBJ files

Our first OBJ loader is from an ~2009 Apple WebGL helper called j3di.js. Like Dr. Angel's helper code it contains initShader() routines and WebGL context creation routines. It can load simple models, but not materials or complex scenes. Though it provides everything we will need to finish up the labs for this class, you want a more capable one. You can find one as part of the materials for WebGL Programming Guide: Interactive 3D Graphics Programming with WebGL. This is the latest in a log running and respected serias, and is as close to an official WebGL guide as you can get.

The first trick is to find a file that Blender will read. Blender supports many file formats, so this isn't too hard, but sometimes things can go wrong. You might want to try TF3DM, which often lists Blender's native .blend format as a download option.

Next, start Blender and click anywhere to dismiss the welcome screen. Blender is big and complex, so don't expect a tutorial. All I will explain is how to load a model, clean it a bit and export a useful .OBJ file.

The default scene contains a cube. This is the very one shown above. If it isn't highlighted in orange, right click on it and press x. This will pop up a delete confirmation menu. Press Enter to confirm. You can use this method to clean unwanted stuff from models you load. Or, you can click on things in the Scene Graph in the upper right corner of the screen. Press shift to make a multiple selection.

Once you have removed everything you don't want, either import the mesh file you downloaded from here:

File | Import | list of supported types...

Or add one of the built in meshes. I recommend Suzanne, the Blender monkey.

Add | Mesh | Monkey

You can position her by clicking and dragging on the arrows. You can rotate her about the view axis by pressing R and moving the mouse, or about one of the x, y or z axes by clicking them then pressing R. Scaling is done by pressing E.

Position you model facing up the positive Z axis near (0,0,0) so her face is pointing to you when you load her. You may want to use "View | Top" to help with this.

Now you are ready to export. If you only want to export a couple things, select them like you did for deletion - right click in the view, then shift click to add more; or left click in the scene graph and shift click to add more.

To export go to

File | Export | Wavefront (.obj)

From here choose:

Click Export .obj

 

Loading OBJ files with j3di

 

Assignment

Goals of this assignment:

Experience different ways to specify a mesh, and observe the benefits of different ways to represent and places to calculate your mesh's data.

Part 1: Reduce the Size of Data

Start with AnimatedMesh.html and AnimateMesh.js from Lab5.zip. You must have a TrianglesToWireframe to run it. If you did not finish yours, download and link translators.js to your AnimateMesh.html.

As written, this exercise generates an animated height map drawn as TRIANGLES and LINES without any drawElements these things all waste a lot of space, and force the animation calculations to be repeated unnecessarily on duplicated point data. Your goal is to compact the data by switching to TRIANGLE_STRIP, LINE_STRIP and drawElements and measure the impact of each change.

  1. Measure the original program
  2. We can do better - the lines are very inefficient. There are many duplicate lines because we are outlining every triangle. It would be better if we removed duplicates somehow. Even better if we switched to gl.LINE_STRIP. Luckily this is pretty easy to do for this shape.
  3. Measure the effect of this change. The buffers should be noticeably smaller again. What is the ratio of the new size to the first one?

  4. OK! Now follow these steps to switch from gl.TRIANGLES to gl.TRIANGLE_STRIP
  5. Measure the effect of your changes. The buffers should be noticeably smaller. What is the ratio of the new size to the old one?

  6. This is not enough! We will now make it even smaller by using drawElements

Part 2: Offload to the GPU

Even if you optimize your memory impact with element arrays and strips, trying to do too much work on the CPU with Javascript can be slow. You can use your vertex shader to do some of that work. Your basic goal is to take the time dependent update done by updateHeightsAndColors(), and perform an equivalent time dependent update in the vertex shader instead.

Here are the details:

Part 3 - Loading OBJ files with j3di.js and managing multiple buffers

For this part use OBJ_demo.html and OBJ_demo.js. Like last week's height map, this program depends on an external file. If you have trouble running it, review the instructions in last week's notes.

This program loads an OBJ file with j3di.js. Notice that all the buffers you need are supplied by the library and I have provided a function to bind them before drawing - it's using lighting information as colours, but you can switch to a uniform colour if you like.

There is also a function that creates (if necessary) and binds buffers for a wireframe for the OBJ using last week's TrianglesToWireframe function. You can't see the wireframe because the code to generate it is commented out in the render function. You will have to add a line to j3di.js to use it as well - read the function header for details.

The program also is drawing the animated mesh from Part 1. There's no need to merge the buffers - you can simply swap to the needed buffer set and adjust necessary state just before drawing an object. There's no need to reload data unless it's changing, or get the attribute location. It helps if you store the buffers and attribute locations globally or as part of a global structure.