Underwhelming Screenshot 5: Gelatinous Cube Eats Bunny

Significantly more whelm than previous entries, still lacking that whole voxel thing I set out to accomplish. As far as I can tell, the only thing that's not working is for some reason the voxel rendering shader can't get brick id's, which is curious as the brick creation shader is most certainly writing to the brick texture (I checked). The really amazing part about this, is how fast it runs. This is *very* real-time. This Octtree is 7 levels deep, and it took 7 frames to generate. Frame rate appeared to stay well above 40fps. It's quite mesmerising watching a bunny form out of blocky nothingness. Even though it doesn't completely work, I'm still quite chuffed, as building the Octtree and associated 3D texture took tens of seconds in the old version, where as this does it's job tens of times per second. Source for the adventurous.

Underwhelming Screenshot 4: Yet Another Cube

While this happens to be the very same cube as the last one, from exactly the same angle IIRC, this one is of note for being output from GLSL, and more importantly this should run on AMD GPU's... but I haven't tested it. In the "Display" menu there is an option to switch between GLSL and OpenCL for rendering on the fly. I took the time to make sure they are pixel for pixel the same, correcting the GLSL fragment coords to achieve this.

Of particular interest is the horizontal line through the middle of the cube. It only appears at certain angles, and I believe it to be the result of GLSL not handling infinity quite as nicely as OpenCL does, as the AABB-Slab method I used exploits floating points ability to store both positive and negative infinity. Alas I'm not sure if this is a bug or intended behaviour. Back in good news land, there as yet appears to be no difference in performance between the two implementations on my GTX 680. Here's the relevant commit.

One Shiny Dragon + Source

This is viewing a hollow shell of the XYZ RGB Asian Dragon at 1024^3, using what I've written so far of my attempt to implement Cyril Crassin's GigaVoxel method. At the moment it would be optimistic to say I have partly implemented a quarter of it, but it's capable of drawing shiny dragons, and I'd like to share them :-) The original dragon has a tad more detail than 2048^3 can store, which I intend to address in the next phase of the method, mip-mapping. In the mean time, I for one always get sad when I read a blog post about something really cool, and I can't play with it myself.

GitHub - Win32 Binaries - zlib licensed.
This should build with minimal fiddling on your favourite linux distro. I use Debian, but it only depends on X and zlib, so should be easy to build. It also loves clang. It's written in pure C99, at least that's what I tell the compiler.

---

Going Deeper...

To all yee who explore the source code, fair warning, it's a hatchet job. With that in mind I hope it should make a kind of sense. The first thing you'll want to look at is the Makefile. convert and convertoct convert simple Wavefront OBJ files, as output by Blender, into a format suitable for throwing at a video card. Worth grabbing the win32 binaries for the included data file, it's not in the git repo.

convert and polyview

convert turns the OBJ file into the format that polyview expects for a VBO. polyview loads the file into memory, tells OpenGL where it is in memory and how it's formatted, and runs a simple display loop. It's not terribly clever, but it does push all of the load onto the video card, leaving the CPU idle in my tests.

convertoct and octview

convertoct produces a Sparse Voxel Octtree by discarding the polygons of a mesh file produced by convert, and throwing the points (and their normals) into a buffer. Hatchet Job. So this will only work with models that have a uniform vertex density, mostly 3D scanned objects (like the dragon, and the bunny).

The Data

A 1024^3 cube is big. That's out of the box we're talking about a Gigabyte of data if we're only using a single byte per voxel, but I'm using 4 floats. This means we don't have enough video memory. Well, it's sparse, which brings it down to 900Mb. The texture data is zipped up with zlib, which brings the data file down to a much more reasonable 17Mb. It's still extracting to 900Mb of RAM though. Due to ?!?!?, the current Nvidia drivers don't like me allocating 900Mb of texture memory on Windows 7, so the drivers convert it to 16bit floats, bringing it down to 450Mb, which it's quite happy with. This doesn't seem to affect performance in this instance, as I'm already abusing the video card in plenty of other ways. 64bit executables solve this problem, I've updated the binary and now it does allocate the full 900Mb.

The Build System & Porting

The idea is win32.c and x11.c are "shivs", all platform dependant things are in there, they obey their respective OS's rules, and they toggle fullscreen when pressing F11. They call main_* functions in polyview.c or octview.c depending which one is linked. polyview.c has almost no intelligence at all, it's just a test mesh displayer. octview.c is marginally better, providing simple FPS controls, and handballing off to voxel.c. Making a osx.c shiv should be pretty easy, and I'm fairly sure I already have one laying around from an older project.

voxel.c

This is where we find the initialisation, the texture block is decompressed with zlib, and loaded into a vanilla old OpenGL 3D floating point texture. The Node Pool is loaded into the format that Nvidia requires when you're planning on breaking the legs of the GLSL standard, like I am doing here. The main brains of the program is located in the fragment shader, which this file dutifully loads and compiles it ready for the GPU to use. The final text in this file is a few lines that update variables for the shader, such as the camera position, and then render a single flat polygon covering the whole screen. As all of the work is done in the fragment shader, it will be called once per pixel on the screen (unless you're using antialiasing, then this will run horribly slow, and at no visual benefit at all, this rendering method is aliasing free to begin with). OpenGL experts will marvel at how primitively I'm drawing the quad, and possibly be driven to self harm. Pressing the R key will reload the shader from disk, useful for debugging.

render.frag

To understand this code you'll really have to read Cyril Crassin's PhD, which can be found here. The quick version is that for each pixel it traces a path through the Sparse Voxel Octtree that was built by convertoct. There's nothing more complicated than that going on, so there's currently no point comparing it to Gigavoxels. Also it does it in GLSL, as opposed to a real GPU compute language, so mine is an amusing abuse of GPU power, at best. For now...

OpenGL Vertex Buffer Objects

It took me some time, but I've finally got them working the way I want, and now you can too. But first, an example...



Now you can see why that broken foot silhouette was so exciting for me. Now onto the making it happen for you.

VBO's in a nutshell

Traditionally Vertex Buffers were a place you could upload carefully formatted geometry to the video card, and that's about it. Then came the ARB_matrix_palette extension, and things got a bit exciting. Nowadays we have GLSL, and can put whatever we feel like in them. Lets take a look at how that's done...

// VBO init code
GLuint vbo = -1;
glGenBuffers(1, &vbo);
glBindBuffer(GL_ARRAY_BUFFER, vbo);
glBufferData(GL_ARRAY_BUFFER, num_vert * sizeof(vertex), vert_ptr, GL_STATIC_DRAW);

After that, you upload the vertex indicies for your polygons...

// Element Array Init Code
GLuint ebo = -1;
glGenBuffers(1, &ebo);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, &ebo);
glBufferData(GL_ELEMENT_ARRAY_BUFFER, num_quad * 8, quad_ptr, GL_STATIC_DRAW);

And to draw you call...

// Draw Code
glBindBuffer(GL_ARRAY_BUFFER, vbo);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ebo);
glVertexPointer(3, GL_FLOAT, 0, 0);
glEnableClientState(GL_VERTEX_ARRAY);
glDrawElements(GL_QUADS, num_quad * 8, GL_UNSIGNED_SHORT, 0);

At least, that's what you would expect from reading the spec. And indeed this code may just render your pile of flat untextured polygons. On some cards.

This is where it gets fun. Buckle up.

Thar be dragons ahead

Lets start with the VBO init code. Actually that's almost perfect - however a lone vertex doesn't cut it. Now a float is 4 bytes, so a lone vertex is 12 bytes. We also want Normals - another 12 bytes, and a Texture Coordinate, 8 more bytes bringing us to 32 bytes exactly, which is really convenient as we will find out, but first allow me to segway onto skeletal animation techniques for a moment.

Skeletal Animation

So you have 2 bones connected by a joint, lets imagine a knee. Now when you bend your knee, say 90°, everything from a bit below the knee moves in a straight forward 100% of 90degrees motion. It's the points along your knee that are tricky, otherwise you get nasty artifacts like this...



So we need a method of partially rotating the points along your knee, depending how close they are to the joint, or whatever, we don't care, that's the modellers problem. What we need to care about is how it's done, with Weights. So the bone will have a list of which points it affects, and to what extent it affects each of them. In the bad old scary days when this was all done in software people used Quaternions. Quaternions can be used similar to matrices, in that they can store rotation, and you can bash some vertices against a quaternion and it will spit out rotated vertices. Quaternions have the very cool property that it is possible to interpolate between 2 quaternions, depending on the method you use, it will correctly follow the plane you want it to rotate in. Also Quaternions use less operations that Matrices do. Anyhow, these days we have hardware that does Matrix * vertex multiplication really fast, and the modern day trick is to use these weights to do weighted averaging of the points that are spit out by the two separate matrices.

Back to our Vertex Buffer Object

So our nice friendly lovable artists have given us a model with a bunch of bones, which each reference a bunch of vertices and weights. We need to find out how many bones reference each vertex, and specifically find out what is the most bones referencing a single vertex. For the particular build of MakeHuman I'm using models from, this is 6.

ATI recommends that your vertex entries are multiples of 32 bytes, to speed up fetch operations. This is sound advice no matter what hardware you're using. So the vertex entry I'm uploading looks like this...

12 bytes of Vertex (3 floats)
12 bytes of Normal (3 floats)
8 bytes of TexCoord (2 floats)
24 bytes of Bone Weights (6 floats)
6 bytes of bone indicies (1 byte each)
1 byte of number of bones actually referencing this vert
1 byte of zero padding

Now we have that settled, lets look at the final version of the VBO init code...

// VBO init code - Final
GLuint vbo = -1;
glGenBuffers(1, &vbo);
glBindBuffer(GL_ARRAY_BUFFER, vbo);
glBufferData(GL_ARRAY_BUFFER, num_vert * 64, vert_ptr, GL_STATIC_DRAW);

It's nice when things work out like that. Onto the Element Buffer. This is where things get a bit annoying. Here it is again to refresh your memory.

// Element Array Init Code
GLuint ebo = -1;
glGenBuffers(1, &ebo);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, &ebo);
glBufferData(GL_ELEMENT_ARRAY_BUFFER, num_quad * 8, quad_ptr, GL_STATIC_DRAW);

On my ATI 4870x2, that call to glBufferData(), while it does allocate the appropriate memory on the video card, doesn't actually copy any data. No problem, a quick read of the spec says we can do this...

glBufferSubData(GL_ELEMENT_ARRAY_BUFFER, 0, num_quad * 8, quad_ptr);

No you can't. That call actually crashes the video driver on my card. Yeah not happy at all. All is not lost... here is the Element Buffer init code that actually works...

// Element Array Init Code
GLuint ebo;
void *tmp;
glGenBuffers(1, &ebo);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ebo);
glBufferData(GL_ELEMENT_ARRAY_BUFFER, num_quad * 8, NULL, GL_STATIC_DRAW);
tmp = glMapBuffer(GL_ELEMENT_ARRAY_BUFFER, GL_WRITE_ONLY);
memcpy(tmp, quad_ptr, num_quad * 8);
glUnmapBuffer(GL_ELEMENT_ARRAY_BUFFER);

Last Wave of Dragons, I Promise

Here's the code I'm using to draw my mesh...

glBindBuffer(GL_ARRAY_BUFFER, vbo);
glVertexPointer(3, GL_FLOAT, 64, 0);
glNormalPointer(GL_FLOAT, 64, 12);
glTexCoordPointer(2, GL_FLOAT, 64, 24);
glVertexAttribPointer(bw1, 4, GL_FLOAT, GL_FALSE, 64, 32);
glVertexAttribPointer(bw2, 2, GL_FLOAT, GL_FALSE, 64, 48);
glVertexAttribPointer(bi1, 4, GL_BYTE, GL_FALSE, 64, 56);
glVertexAttribPointer(bi2, 4, GL_BYTE, GL_FALSE, 64, 60);

glEnableVertexAttribArray(bw1);
glEnableVertexAttribArray(bw2);
glEnableVertexAttribArray(bi1);
glEnableVertexAttribArray(bi2);
glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_NORMAL_ARRAY);
glEnableClientState(GL_TEXTURE_COORD_ARRAY);

glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, obj->ebo);

glDrawElements(GL_QUADS, obj->nquad*8, GL_UNSIGNED_SHORT, 0);

glDisableVertexAttribArray(bw1);
glDisableVertexAttribArray(bw2);
glDisableVertexAttribArray(bi1);
glDisableVertexAttribArray(bi2);
glDisableClientState(GL_VERTEX_ARRAY);
glDisableClientState(GL_NORMAL_ARRAY);
glDisableClientState(GL_TEXTURE_COORD_ARRAY);
glDisable(GL_TEXTURE_2D);

glBindBuffer(GL_ARRAY_BUFFER, 0);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);

And here is the vertex shader I used...

uniform mat4 SkinMat[80];

attribute vec4 weight1;
attribute vec2 weight2;
attribute vec4 boneid1;
attribute vec4 boneid2;

varying vec4 pos;
varying vec3 normal;

void main()
{
 normal = gl_NormalMatrix * gl_Normal;

 pos = vec4(0,0,0,0);

 vec4 weight = weight1;
 vec2 w2 = weight2;
 vec4 bone = boneid1;
 vec4 b2 = boneid2;
 int nbone = int(boneid2.w);

 if(nbone==0)
 {
  pos = gl_Vertex;
 }
 else
 {

  for(int i=0; i<nbone; i++)
  {
   pos += weight.x * (SkinMat[int(bone.x)] * gl_Vertex);
 // Rotate variables
   weight = vec4(weight.yzw, w2.x);
   w2.x = w2.y;
   bone = vec4(bone.yzw, b2.x);
   b2.x = b2.y;
  }

 }
 gl_FrontColor = weight1;
 gl_Position = gl_ModelViewProjectionMatrix * pos;
 pos = gl_ModelViewMatrix * gl_Vertex;
}

So it's important to mention that all of those..

glEnableVertexAttribArray(bw1);
glEnableVertexAttribArray(bw2);
glEnableVertexAttribArray(bi1);
glEnableVertexAttribArray(bi2);

calls were preceded with...

bw1 = glGetAttribLocation(prog, "weight1");
bw2 = glGetAttribLocation(prog, "weight2");
bi1 = glGetAttribLocation(prog, "boneid1");
bi2 = glGetAttribLocation(prog, "boneid2");
SkinMatUnif = glGetUniformLocation(prog, "SkinMat");

Lastly I should mention this... looking at the spec may make you think that you can just throw whatever you want at the shader, and it's all good. Not so! While I'm sure one day there may be a device that supports every conceivable combination out there, something like...

glVertexAttribPointer(foo, 3, GL_BYTE, GL_FALSE, 64, 60);

Is going to end in tears. The short version is this... only expect it to work with the types that can be sent individualy old-school style... as documented here. Want to send 3 GL_SHORT's to the video card? Is there a glVertexAttrib3s() function? no. Hope that helps.