CS315 Lab 3.5 &mDash; 3D Meshes: Generation and Representation


Highlights of this lab:

In this lab, you will learn:

Assignment

After the lab lecture, you have one week to modify the files in Lab3.5.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 wireCubeStart = 0;
var wireCubeVertices = 30;

var solidCubeStart = 30;
var solidCubeVertices = 36;

//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 0, 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 use unsigned bytes to represent the cubeLookups, the total data for this representation is:

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

66 lookups * 1 byte/lookup = 66 bytes

Total = 194 bytes.

In last week's code, the compact lookups array was expanded into 66 fully specified vertices:

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

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 specify the buffer using regular arrays of integers, just like the cubeLookups buffer. To specify a buffer, you create a buffer as usual, but bind it as ELEMENT_ARRAY_BUFFER. You can't use Dr. Angel's flatten() function to convert the array for use in the shader though. 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, toload the cube's elements array you could use this code:

	//cubeElements should probably be global so it can be rebound before calling drawElements
	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, wireCubeVertices, gl.UNSIGNED_BYTE, wireCubeStart);

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 shaped, like this:

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

How to request external files like meshes and textures from Javascript

See code samples. The lab exercise shows how to request an image's raw colour information. This is more than you'll need to do texturing later on.

The lab exercise will also show how to load the .OBJ file. The code is a bit odd because you have to wait for the .OBJ file to load before you can bind its buffers and draw it. It would be better to register a function that is triggered by an on load call.

You will also need to make special changes to your web browser if you want to load external files from your local disk.

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.

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

Start with HeightMapExercise.html and HeightMapExercise.js from Lab3.5.zip.

As written, this exercise loads an image, gets the data out of it and uses it as a height map by applying it to the z-axis of a grid. The resulting height map is drawn as gl.TRIANGLES with gl.drawArrayswhich wastes a lot of space. Your goal is to compact the data in two ways: switch to gl.TRIANGLE_STRIP and gl.drawElements and measure the impact of each one.

Please use Chrome for this exercise!

  1. Measure the default application
  2. Follow these steps to switch from gl.TRIANGLES to gl.TRIANGLE_STRIP
  3. Measure the effect of your changes. The vertex position buffer should be noticeably smaller. What is the ratio of the new size to the old one?
  4. This is not enough! We will now make it even smaller by using drawElements
  5. Measure the effect of your changes.

Part 2

Even if you optimize your point references by using, 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 generatePoints(), and perform an equivalent time dependent update in the vertex shader instead.

Here are the details:

Part 3

Design an octahedron like this one, and draw it with the draw method of your choice. Each side should have its own colour.

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.

Part 4

Change the code from Part 2 so it loads and renders something from an OBJ file of your choice. The line overlay may or may not work. Do your best!