THE STRUCTURE OF NEVERBALL
The core Neverball data structure represents all of the different objects that make up both the SOL level files and the simulation state of the running game. This data structure is fairly complex and, as of version 1.5, is composed of 21 different C structures.
Of course each of these structures has a meaningful name, but in addition each has a unique letter. V is for vertex position. T is for texture coordinate. L is for lump. M is for material. Most of these letters make sense, but some are a bit of a stretch, like Z for goal, and X for switch. Some structures do double duty, such as the S which gives the side plane of a lump. Being a plane definition, S is also used to represent normal vectors. The five unused letters happen to be C, K, O, Q, and Y.
This lettering allows a very terse sort of Hungarian notation, where the type and meaning of a variable is immediately inferred from its name. So VP is a vertex pointer, LI and LJ are lump indices, SC is a side count, and so on.
This organization dates all the way back to Super Empty Ball, the earliest versions of which had 14 lettered structures. Recognizing this system’s growing complexity, Parasti refactored it all into subsets of structures for static level state, dynamic level state, and rendering. He preserved the naming convention and produced a really nice modularization of what was originally very monolithic.
So a Neverball level consists of 21 separate vectors of these structures. Each level has a vector of Ts, a vector of Ss, etc, which we call TV and SV respectively. These vectors are accessed by index, TI, TJ, TK, etc. Mapc ensures that all vectors are absolutely optimal, and that each element of every vector is unique. To reuse an object, we simply reuse its vector index. This is a very efficient representation for data on-disk and in memory.
DRAWING THIS STRUCTURE
Real time 3D geometry is almost universally represented by vertices connected by triangles. Each vertex includes a 3D vertex position, 3D normal vector, and 2D texture coordinate. So in Neverball terms, each 3D vertex is defined by a VI, SI, and TI.
A 3D triangle includes 3 such 3D vertices. In Neverball, each piece of triangular geometry is represented by a G structure, which has a material and three full vertex definitions. So, a Neverball triangle looks like this: [ MI, VI, SI, TI, VJ, SJ, TJ, VK, SK, TK ].
Our existing display list renderer is very simple. For each triangle, it enables material MI and calls glVertex, glNormal, and glTexCoord for each V/S/T set of indices. Easy.
Our new vertex array renderer must be more complex. An OpenGL vertex array doesn’t allow for separate vectors for position, normal, and texture coordinates. Instead, each 3D vertex definition must include ALL three. Even if we’re rendering a large flat plane where all normal vectors are the same, we must duplicate the normal vector for every position vector that we want to specify. This might seem like a less efficient representation, but it actually gives better performance due to cache coherence.
Our problem is that the Neverball data structure does not resemble anything like what OpenGL expects.
We could simply expand each G structure out into its corresponding structure elements. This is what Lazrhog did, and it obviously worked well. It’s not optimal though, because each V/S/T sub-element of one G structure is very likely to occur in one or more nearby G structures, and our straightforward expansion would duplicate that data. Theoretically, in the limiting case of an infinite sphere, each V/S/T will occur 6 times, and we definitely don’t want our levels expanding anywhere near 6 times their normal size. As I mentioned in the previous post, OpenGL ES version 1.1 actually limits us to only 65536 V/S/T sets at any one moment, so this data expansion is not just inefficient, it pushes us quickly toward our constraints.
OPTIMIZING THIS AND THAT
What I’d rather do is detect V/S/T duplication and eliminate it. This can be accomplished in one of two ways...
First, the level loader could analyze each G structure, comparing it with all others, looking for duplicates. I’ve implemented this before (in my OBJ optimizer library) and it can be very fast given a clever kind of skip-list structure. However, this optimization would occur every time a level is loaded, which I find inelegant.
I’d prefer the second approach, which is to do the optimization in mapc once and for all. Unfortunately as I noted above, the Neverball data structure does not match the vertex array layout, so the current SOL file is not capable of representing the optimized version of the level.
SO SHUT UP AND CHANGE THE SOL ALREADY
My intention at this time is to introduce a 22nd core structure which will add a layer of indirection to the geometry definition, making it amenable to representation with vertex arrays and optimizable by an offline process such as mapc, while side-stepping the impending doom of the 65536 limit. It will be structure O.
It’s pretty simple: an O structure will consist of a single complete 3D vertex [ VI, SI, TI ]. The G structure will be modified to index these O structures [ MI, OI, OJ, OK ]. In this way, an optimal vertex array will consist only of O structures, rather than sub-elements of G structures. Since mapc will take responsibility for ensuring that each O is unique, each resulting vertex array will therefore be as small as possible.
The level loader will extract a vertex array by forming a linear vector of all of the O structures touched by each material. It will extract the element array by remapping the indices in the G structure into this collapsed O vector. The end result will be significantly more efficient than the display list renderer could ever have been.
The limitation will be that no level may have more than 65536 O structures touched by a single material. None of our current levels come anywhere near this limit (not by a light-year) and if a mapper does go absolutely nuts with some material, then his recourse is to duplicate that material and apply the duplicate to the overflow.
I’ve just been pondering these issues for a few days. I thought some of you might be interested a better understanding of how the game works internally, and it helps me think to write it down. In general, that’s how things will change as we transition toward a world in which 3D-capable mobile devices outnumber PCs, and Neverball lives on thanks to OpenGL ES.