# Lab 5: Basic Mesh Optimizations

## Highlights of this lab:

In this lab, you will learn:

• the drawElements function, a drawing method that is more efficient than drawArrays for meshes that frequently repeat vertices with the same attributes.

• the advantages of TRIANGLE_STRIP, especially as applied to parameterized surfaces like height maps and rectangular patches.
• how to export OBJ files from Blender and load them into your WebGL program with j3di.js
• how to observe the state of your WebGL program.

## Assignment

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

• Move a procedurally generated height field animation calculation from Javascript to a vertex shader and observe the performance impact.
• Convert a TRIANGLE mesh to a TRIANGLE_STRIP mesh and observe the memory impact.
• Convert the resulting TRIANGLE_STRIP mesh to a work with drawElements and observe the memory impact.
• Import at least one OBJ into a WebGL program with j3di.js - it uses drawElements and now you know what to do!

## 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:

• mode is what primitive to draw with
• count is how many vertices to draw.
• type is the data type specified in the buffer
• first is what vertex to start at in the array you loaded. The documentation calls it a pointer, but it is relative to the currently bound elements array buffer.

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.

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:

• Selection only: if you made a specific export selection
• Triangulate faces: very important!
• Include Normals: only if you plan to light the model
• Include UVs: only if you plan to texture the model and it is set up for texturing.
• Forward: my instructions expect -Z forward which is the default for .obj and for OpenGL
• Scale: adjust this if the model is the wrong size - too large or too small is common.

Click Export .obj

• Include j3di.js in your HTML file
• Put the obj file in your lab folder.
• Make a global variable called var obj;
`   obj1 = loadObj(gl, "relative reference to .obj file");`
It loads all needed databuffers and adds them to the returned object. You are responsible for binding them to the shader program when you want to draw.

• A function like this can help you bind the necessary buffers to draw the OBJ
```function bindBuffersToShader(obj) {
//Bind vertexObject - the vertex buffer for the OBJ - to position attribute
gl.bindBuffer(gl.ARRAY_BUFFER, obj.vertexObject);
gl.vertexAttribPointer(program.vPosition, 3, gl.FLOAT, gl.FALSE, 0, 0);
gl.enableVertexAttribArray(program.vPosition);

//repeat for normalObject (3 floats) and textureObject (2 floats)

//j3di.js ignores materials - surface colors - so we'll set a basic one here
// -- interesting idea: bind normalObject to vColor
gl.disableVertexAttribArray(program.vColor);
gl.vertexAttrib4f(program.vColor, 0.8, 0.8, 0.8, 1.0); // specify colour as necessary

//j3di.js stores OBJs as vertex arrays with an element array lookup buffer
//the buffer describes TRIANGLES with UNSIGNED_SHORT
gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, obj.indexObject);
}
```
```   //It might take time for the OBJ file to load. Only draw when it is ready.
//You might want to make an alternate render that shows a loading animation
//until all external files are loaded...

//Bind buffers related to OBJ

//Apply transformations/colors if necessary

//draw OBJ using the element buffer
gl.drawElements(gl.TRIANGLES, obj1.numIndices, gl.UNSIGNED_SHORT, 0);
}

//At this point, you will need to rebind buffers or re-enable the colour
//attribute array to draw other objects...

```

## 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

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
• You will measure your buffer sizes with WebGL Inspector (GitHub). For ease of use, I recommend that you use a live link as described in their GitHub page/readme. If you like it and you have access to your own UNIX environment with NPM installed, you can build your own version to use.
• You should see a GL button to the right of your address bar, and it should be dark red, not grey. Click it to reveal the WebGL Inspector drawer.
• Click the green UI button
• Click the Buffers tab.
• Write down the size of the visible buffers. There will be two - one for colours and one for positions. They should be the same size.

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.
• You won't have to write a new function to generate line strips - I have provided one already: generateWireStrip(). Please note that this function is not general purpose.
• Take a moment to study how the function works, then replace the whole line that calls TranglesToWireframe() with a new one that calls generateWireStrip().
• In the render() function, change the gl.LINES to gl.LINE_STRIP
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
• In the generateTriangles() function:
• Reduce the six vertices, two triangles, being produced in the inner loop to just two points:
first the one at the current i and j, then one at i and j+1.
This will produce the zig-zag or pattern typical of line strips.
• The previous change makes it so that we are no longer visiting the last column of vertices.
Change the comparison for the inner loop from < to <=
• Immediately after the inner loop, but still inside the outer one, we need to connect this row of triangles to the next with a pair of degenerate triangles — an undrawn line. To do this:
• duplicate the last point that was added to the points array,
• then add the first point from the next row - it should be this one: 0 + (j+1)*(width+1)
• In the render() function change the 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
• Create a global elements array
• In generateTriangles() and generateLineStrips() stop storing the values in the points array and start storing just the indices in the elements array.
ie. Stop doing stuff like this:
`points.push(points[i + j*(width+1)]);`
and start doing stuff like this:
`elements.push(i + j*(width+1));`
• In init():
• After the call to generatePoints(), add some code to push the numbers 0 to elements.length - 1 onto the elements array. This will allow you to continue drawing points if you want them.
• Change how all the Start and Vertices values are calculated - the calculations should now be based on the size of the elements array.
• Load elements into an ELEMENT_ARRAY_BUFFER as described in the notes.
Don't forget:
• use Uint16Array if you want to have meshes bigger than 256, or 16x16, points. Uint16Arrat will allow up to 16,536, or 256x256, points.
• you need an elementsBuffer variable - you should probably declare that like vertexBuffer and colorBuffer.
• In render(), switch to using drawElements as described in the notes.
Don't forget that you will need to multiply your Start by two - the "first" or "offset" argument is in bytes.
• Measure the effect of your changes.
• Notice the new element buffer. Calculate the combined size of these buffers and the vertex position buffer. They are all measured in bytes, so no conversions are necessary.
• What is the ratio of this new size to the original size of the buffers? Do you think it is this worth the effort?

### 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:

• Work with a copy of AnimatedMesh.html and AnimatedMesh.js. You can use the copy from Part 1, or start fresh from Lab5.zip.
• The variables r and c at the top of AnimatedMesh.js control the resolution of the animated surface. They represent rows and columns of squares. Initally, both are set to 20 making a 21x21 vertex surface.
• Check your CPU usage in the Task Manager on Windows, or in Activity Monitor on a Mac.
• Usage should be fairly low.
• You can also record performance in a Chrome web browser using Developer Tools | Performance tab. Press record and get a few seconds time. Check how much time is spent in Javascript (Scripting) vs WebGL (Rendering). You'll also be able to see each frame and the fps.
• Change r and c to 255, this will make a 256x256 vertex mesh - a total of 65,536 individual vertices, the maximum number addressable by the unsigned short type used in an ELEMENT_ARRAY_BUFFER.
• The framerate should slow down, even on powerful systems, because just to set a single value for every vertex at the default 60fps, you would need to assign 3,932,160 values which is a lot of work for Javascript already. But wait... there's more!
• Look at the updateHeightsAndColors() function. It is called every frame by the render() function to animate the surface.
• You can see that for every vertex we are doing much more than a simple assign: it does sin() function calls, sets a z coordinate, sets RGBA values, and then we have to copy the results to graphics hardware. This is too much for most CPUs to do at 60fps.
• Find the code in updateHeightsAndColors() that changes the z coordinate and the vertex colour.
• Move it to the vertex shader:
• Supply the time argument to the shader as a uniform
• you don't need Math. to perform basic math operations in glsl
• you don't have a 2D array of points in the vertex shader, you have a single vec4 called vPosition.
• you'll have to devine PI: const float PI = 3.1415926535897932384626433832795;
• you might want to make use of the pos variable I declared to help you break the changes into separate steps
• remove the updateHeightsAndColors() call and the buffer updates from the render() function.
• Check the performance again. Was there an improvement? How much less does the CPU seem to be doing? How much more does the GPU seem to be doing?

### 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.

• Get your octahedron from last lab to draw in this OBJ scene.
It might help to write your own buffer binding function to help with swapping to regular, non-indexed objects. Maybe take a cue from how buffers are stored on OBJ objects.
Don't forget to draw with the correct function for your own object - probably drawArrays.