So Much More than "Just Data"

"It's just data."

Any student I've ever taught has heard me say these words.  Most times in this order, sometimes not, just to mess with them.  But it's true: when dealing with graphics, animation, any kind of memory... you really need to know what it is you're dealing with it, where it lives and how you deal with it.  This post discusses my week struggling to build procedural geometry and a couple takeaways.

TL;WR: 

Always remember, kids: sharing is caring, but don't forget to mind the implications of the data you're using: where is it stored and how many bytes!

The Purpose

Since it's about prototyping animation algorithms and not so much about the finished product, the intent behind adding procedural geometry to the mix was to be able to generate meshes that resemble animate body parts or bounding boxes.  I feel as though skipping to the OBJ or FBX loader would distract my students from the point of development, which is, again, the algorithms, not making everything look pretty.  Of course, we may need high quality loadable meshes later on to make what we do believable, but to start I just wanted something "simple" and 100% programmer accessible.  The course I'll be using this framework for assumes that the 3D modelers and animators are doing their job elsewhere, and it is up to the students --the programmers --to provide them with an environment in which they can bring life to their subjects.

Thus, I took it upon myself to produce a set of algorithms that would generate 2D and 3D primitives with programmer-defined parameters.  For example, you want a full-screen quad?  Go and make yourself a 2x2 procedural plane with texture coordinates!  You want something that looks like a bone for a skeleton?  An elongated wireframe pyramid should do the trick!  How 'bout a big ol' shiny sphere?  Tell it the radius, slices and stacks, and you're golden.  Etc.  This way we're generating prototyping primitives quickly without needing to worry about finding free models that are perfect for the framework or actually modeling things.  That being said, I did not expect to spend an entire week on geometry, but it was fun so well worth it.  I hope my students appreciate the hours I put in so they won't have to... seriously.

The Outcome

My original system design was to pass a pointer to a VAO, VBO and IBO to 14 different generator functions.  Then I remembered I'm a modularity freak and this would not be good for reusable primitives and sharing buffers.  So I simplified the system: 

• Procedural Geometry Descriptor: a shape-agnostic data structure that holds "shape parameters" (see descriptions below) and "flags" (see next bullet), a vertex and index descriptor, and the vertex and index counts.
• Flags: different options that one can set to help with generation: 
• Axis: the option to change the default orientation of the shape; the default for 2D shapes is to have the normals point along +Z, for 3D the axis is also +Z.
• Attribute options: 
• "Vanilla" mode: enables vertex positions, and indices for shapes that need them.  Simple, small, efficient.
• Wireframe: the shape produced will be made of lines instead of solid, positions and indices only to keep it ultra simple.  This option also removes the diagonal lines that cut across rectangular faces.
• Texture coordinates: enables UVs for the shape.
• Normals: enables vertex normals for the shape.
• Tangents: the generation algorithm will calculate and store a tangent basis for every vertex; this option automatically enables texture coordinates and normals, since normals are part of the basis and "tangent space" is actually a fancy name for "texture space", or the 2D space that is UV land.  If you didn't already know that, now you do.
• Also (and this is super important) a tangent is indeed tangential to the surface in 3D, but it only describes one basis vector; tangent is along the surface, normals point away from the surface... but what's the third?  Just want everybody to know that this is called a "bitangent" when dealing with a 3D surface, because it is a) secondary (hence, 'bi') and b) tangential to the surface, instead of pointing away from it like a normal.  For a line or curve, the equivalent basis vector is known as a "binormal" because it shares the "point away" behaviour or a normal.  I often hear the two terms being used interchangeably but this drives me nuts because they are different things in different contexts.  Students if you're reading this I will dock you points if you mix these up.  Argh.  End rant.

Along with these options, the user calls a "descriptor setter" for a given shape type, since they all have different parameters.  All setters take a pointer to a descriptor, flag and axis, and the following shape-specific parameters: 

• Triangle: nothing special, ultimately a hard-coded data example to prove that the geometry system is alive.
• Circle: input a radius, number of slices (divisions around the axis), and radial subdivisions (divisions away from the axis), and you get a circle.
• Plane: width, height, and subdivisions for each.  'Nuff said.
• Pyramid: Base width (square) and height.
• Octahedron: A double-pointed pyramid, base width and total length.
• Box: 3D box that doesn't ask for axes, but you specify the width, height and depth, and subdivisions for each.
• Semisphere (or hemisphere, whatever): radius, slices, stacks (divisions along axis), base divisions (circle divisions).
• Cone: ditto.  Side note, what I love about this shape is that it has the exact same topology as a semisphere, so once I had that done, this was super easy, just using a different algorithm to position the vertices.
• Sphere: radius, slices, stacks.
• Diamond: ditto, also same idea as cone, but there is an extra ring at the center because the normals switch from directions instantaneously instead of smoothly.
• Cylinder: radius, slices, body divisions and cap divisions.
• Capsule: ditto.  What I love about this one is that, even though people think it's so crazy, it has literally the exact same topology as a sphere; the only difference is that the body vertices and normals are prepared using the cylinder's algorithm.  I thought this one would take me forever but I completed it faster than any of the other shapes.  Maybe that's because all the bugs had been destroyed by this time?
• Torus (coming soon): in simple terms, a donut.  Major radius describes the size of the ring itself, while minor radius describes the thickness of the ring.
• Axes (coming soon): a helpful coordinate axis model.

The actual generation of renderable data is done by first creating a VAO to represent a primitive's vertex descriptor, then passing a descriptor to one "generate" function, which calls the appropriate procedural generation algorithm.

All of the currently-available shapes can be seen in the GIF at the top of this post, but there are a couple unimplemented for the moment.  Like I said, I didn't expect to spend this long on procedural, but hey, I'm learning and stomping out flaws as I go.

The Struggles

I am very happy about this undertaking because, as you know from last week, up until this I had a bunch of untested graphics utilities.  Procedural geometry, in my opinion, is the ultimate stress test; I think I've seen just about every fatal flaw with my existing utilities.  Here I'll discuss three of them that drove me absolutely batshit insane.  We're talkin' 4am nights of "I've almost got it... nope there's another thing..."

The whole thing about putting together renderable primitives is that they are made of vertices, and vertices are made of attributes, and attributes have elements, and an element has a byte size, and all of this comes together to occupy some block of memory... but in order to draw a primitive, even just a single triangle, OpenGL needs to be told all of this information, therefore you need to know it.  If you're a memory freak like me, you'll want to know the address of every damn byte you use.  This process becomes particularly difficult when dealing with the GPU, since it's harder to actually see the data (although modern IDE's have some graphics debugging tools), so when something goes utterly wrong one can only scrutinize the code until something jumps out as unfamiliar.

Here are the three main discoveries that I really learned from while creating procedural geometry.

1. Modularity

Figure 1: The two steps to generating a wireframe sphere: 

a) rings perpendicular to the body; 

b) spokes parallel to the body

This one is not so much a bug but more of a takeaway. About halfway through the implementation of the cone I realized that I was "reinventing the wheel" (heh) to get the base geometry.  I said, "It's a circle, I have a circle already, why not integrate that?"  So that is what I did: converted the circle generator into a publicly accessible algorithm so that other primitives could use it to make my life easier as a programmer (can't emphasize that enough).  I consider it a wise investment, since said circle is now used for the circle geometry itself, the base of the cone, the base of the semisphere, and the two caps of the cylinder.  In addition to creating algorithms that prepare the physical geometry, I realized that I should do the same to create indices for shapes that have similar topology; for example, to create a wireframe sphere, one must first draw the lines that make up the body, then draw "spokes" that extend from cap to cap, all without creating any duplicate vertices or cutting the line strip.  This exact principle also applies to the cone, diamond, semisphere, cylinder, and capsule, and soon to be torus.  This process is illustrated in Figure 1... yes I'm using figures now, it's easier.  Obviously, writing a single robust algorithm that handles all of these cases is the most engineer thing one could do.  So I did.

2. Mind the Gap

This one took me an entire day to track, I was very tired and sad.  At the end of the day I had a very unlucky situation that actually ended in me being thankful that it occurred.

As I may have mentioned in a previous post, I fully intended for OpenGL buffer objects to contain whatever data the programmer wants, to save both space and keep everything contiguous.  This ultimately has two implications: 

Figure 2: A buffer that stores 3 different kinds of 

vertices, each described by a VAO.

1. Multiple vertex formats can be stored in the same buffer, whether you're building geometry primitives that have the same attribute arrangement or different (I call these arrangements "vertex formats").  Recall that a VBO is agnostic to what it contains, while the VAO minds the data and what it represents, i.e. where to find the start of a vertex attribute in a sea of bytes.  So, you can have one VBO and two VAOs that describe what it contains and where.  See Figure 2 for an example of this.



Figure 3: A buffer that contains both vertex attribute 

and index data for a model.

2. Index data coexisting with vertex data: on top of attributes; a block of index data could be stored either before or after the index data; it's important to be sure that a VAO describing vertex data after index data uses the appropriate offset.  Figure 3 illustrates a buffer that contains both vertex and index data.

Seems pretty logical, right?  What I attempted while building all of these primitives was taking these two principles and smashing them together.  Here's the story: 

Figure 4: Ohgawdwhy.

I discovered this bug while implementing the octahedron, which I started after implementing the pyramid.  For some bizarre and sadistic reason, while my solid octahedron was perfect, the wireframe one was true nightmare fuel.  See Figure 4 for an approximate illustration.  The pyramid was fine in both modes, but the octahedron just could not even.  Naturally I investigated...

...and suddenly it was 1:00 AM.  Now, I'm not usually one to throw my hands up in the air but I did exactly that and said, "I am le tired."  So, since there are no buses running at this hour, I decided to walk home and take the time to clear my head.  This trek takes about 35 mins.  So I'm walking and thinking about this issue, nothing.

Now, my apartment uses key cards to open the doors instead of physical keys, which was kinda novel at first but I prefer hardware.  It also makes me anxious every damn day because you never know when electronics will fail.  Trust me, I'm a graphics programmer.  Anyway, my worst fear came to fruition at 1:35 AM when I took my key out and swiped it.  As my first instinct is to push and move forward, I ended up faceplanting the door as it did not open.  I tried again.  And again.  And again... Well, shit.  For my reaction, please see Figure 4 again.

Lucky for me, I have a spare key, which I keep at the office.  To make things worse, for some reason at that moment, my phone decided it would not cooperate for any reason.  So I said, "Welp, I guess I'm walking back."  I retrieved the key at 2:10 AM and fought the urge to keep pressing at the mysterious octahedron.  I defeated the urge and left for home.  During my second walk home I had the following train of thought: 

The thing about the octahedron is, when it's solid, all of the vertices are different, even if they share the same positions, because the other attributes are different.  One thing to understand about indexing is that it should only be used if indices refer to a set of the exact same vertex multiple times, i.e. the exact same combinations of positions, normals, UVs, etc. occur repeatedly.  Since a solid octahedron vertices are all different, I decided not to use indexing.  However, for a wire octahedron , most of the vertices are used at least twice to produce a line-strip that forms a octahedron shape.  Since the only attribute I use for wireframe is position, a duplicate position means a duplicate vertex, so indexing is more than appropriate.

Figure 5: Bad buffer architecture: Index data for the first 

model is wedged between two vertex sets; indices for the 

second model make no sense.

The kicker: all of the previous shapes have the same number of indices for solid and wireframe mode, but suddenly here's Mr. Octahedron, who has zero indices for solid and 12 for wireframe.  I realized that in exercising both storage principles discussed above I had created a buffer with multiple vertex formats and index data, with indices immediately following vertex data, then more vertex data after that.  Figure 5 shows an example of this scenario, with the problem explicitly marked with a big X: the indices used for the wire octahedron were pointing at index data for the previous shape, not its own vertex data as expected.  Alas, this makes sense if the vertex and index data are wildly interleaved.  Thus, the indices for Mr. Octahedron were telling the VAO to use someone else's index data as if it were vertices, so the monstrosity from Figure 4 came into existence.

Figure 6: The correct buffer architecture: All of the vertex
data is grouped together at the start of the buffer (could also
be a mix of vertex formats), and the indices refer to the
correct vertex data.

I realized that the desired result would require re-evaluation of how my primitives stored their data within the provided buffer.  Since stuffing it all right at the end produces an unwanted gap in vertex data, I would need some sort of barrier that explicitly separates all vertex data from all index data, seen in Figure 6.

The solution: the general data structure that I use for buffers now has a "split" index: the limit for occupancy in the first half of the buffer, used for one grouping of data; anything after that byte is used for a different grouping of data.  So now it can be used to explicitly separate vertex data of mixed types (again, the VAO distinguishes formats, so I don't need dividers for this).  The procedural generator function knows that vertices should be stored in the first half of the buffer, while indices should be stored after the divider.  Piece of cake.

I made it home at 2:45 AM.  Would my key work?  Yes.  Now I had to fight the urge to go back to work and fix the bug.  But we all know that a "quick fix" that "should only take a couple of minutes" is usually deceptive, which it was.  The octahedron cost me two days before I finally achieved the solution described above.  Now then...

3. Size Matters

With a solution to problem #2 in place, here's another juicy graphics engineering problem.  I mentioned that a wire octahedron requires 6 unique vertices; it's one of the most basic shapes.  Let's add a circle to the mix with 16 slices and 4 subdivisions, so we have 65 more unique vertices.  How about a sphere with 16 slices and 12 stacks?  This shape has 219 unique vertices.

Figure 7: When indices are larger than the maximum
allowed by their data type, they will roll over to zero
and your shape will be drawn using vertices from who-
knows-where in the vertex set.

What do all of these numbers have in common?  Well, each one is less than 256, so on their own we would be able to store their indices as unsigned chars (single bytes).  The problem arises when storing multiple models' data in the same buffer.  If the above octahedron, circle and sphere all live in the same buffer and have exactly the same attributes enabled, then they share a common format and VAO, which means the "base vertex" for the next shape should accumulate how many vertices have been stored before it.  If the octahedron was stored first, the index of its first vertex would be 0, the circle's first vertex would be at index 6, and the sphere's base index would be 71... but what about the next shape?  We add 219 and suddenly the next shape to be stored has a base index of 290.  While the individual shapes could use bytes to store their indices, as soon as they are sharing a buffer, half of the sphere described above and the entirety of the next shape would be messed up.  Figure 7 shows what happens when your maximum index exceeds the maximum allowed by the storage type.  Naturally, I learned this the hard way; please refer to Figure 4 once more for what I saw.

If we use indices to draw instead of storing repeated vertices, we must consider the total number of vertices because it would otherwise be incredibly difficult to determine which primitive starts at which address.  Therefore, my solution to the problem was to implement a "common index format" that is shared for all primitives using the same VAO.  The algorithm for preparing geometry is as follows: 

• Create shape descriptors
• Add up the total number of vertices using the common vertex format
• Create common index format given total number of vertices
• Add up the space required to store vertices using the common vertex format (A)
• Add up the space required to store indices using the common index format (B)
• Generate "split" buffer with A bytes for vertices and B bytes for indices
• Generate VAO for common vertex format
• Generate all renderables

When calling the "generate" function, the programmer passes a "base vertex" number, which changes the first index from 0 to however many vertices represented by the current VAO are stored in the buffer before the current shape.  There is also an optional parameter, a pointer to a "common index format" that should be provided for drawables sharing a buffer with others; otherwise the generator will defer to the shape's own maximum index to decide how much space it needs.

This algorithm seems tricky but I think it's well worth it taking the time and care to produce a shared buffer that is rather self-sufficient; you allocate some space and the procedural shapes just know what to do with it.

TL;DR: 

Always remember, kids: sharing is caring, but don't forget to mind the implications of the data you're using: where is it stored and how many bytes!

Demo time...

With geometry [almost] out of the way, I should now be able to prototype my own animation algorithms for the class.  Inspiration for the students, if you will.  I sincerely hope that the number of bugs I experience in the future will be minimal, now that I've caught and fixed pretty much everything that could have gone very wrong graphics-wise.  I only have two weeks left in the time I originally challenged myself to complete everything in, so I'm somewhat hopeful that I'll have enough to go on.  For the amount of work I put in, I damn well better.

Until next time, remember to respect your data.