So long, Cube

It’s time to look into getting different geometry into our scene.

In the Vulkan version of StaticRectangle, I was using OBJ files for meshes and a 3rd party library called tinyobjloader to load them. This was fine for that application because the size of the files wasn’t much of a concern.

I mean it’s always a concern, but it wasn’t as much of a concern in the early stages. It’s something that can be optimised later.¹

Now we’re on the web, size is very much a concern as we’ll be expecting the client to download these resources.

Up until now, my geometry has been defined in JavaScript²

/**
 * Create simple cube geometry.
 * 
 * @returns Cube geometry with size 1x1x1
 */
export function ExampleCube(): Geometry {
    const positions = new Float32Array([
        // Front
        -0.5, -0.5, 0.5,
        0.5, -0.5, 0.5,
        -0.5, 0.5, 0.5,
        0.5, 0.5, 0.5,
        // Top
        -0.5, 0.5, 0.5,
        0.5, 0.5, 0.5,
        -0.5, 0.5, -0.5,
        0.5, 0.5, -0.5,
        // Back
        -0.5, 0.5, -0.5,
        0.5, 0.5, -0.5,
        -0.5, -0.5, -0.5,
        0.5, -0.5, -0.5,
        // Bottom
        -0.5, -0.5, -0.5,
        0.5, -0.5, -0.5,
        -0.5, -0.5, 0.5,
        0.5, -0.5, 0.5,
        // Right
        0.5, -0.5, 0.5,
        0.5, -0.5, -0.5,
        0.5, 0.5, 0.5,
        0.5, 0.5, -0.5,
        // Left
        -0.5, -0.5, -0.5,
        -0.5, -0.5, 0.5,
        -0.5, 0.5, -0.5,
        -0.5, 0.5, 0.5
    ]);

    const indices = new Uint16Array([
        0, 1, 2, 2, 1, 3,       // Front
        4, 5, 6, 6, 5, 7,       // Top
        8, 9, 10, 10, 9, 11,    // Back
        12, 13, 14, 14, 13, 15, // Bottom
        16, 17, 18, 18, 17, 19, // Right
        20, 21, 22, 22, 21, 23  // Left
    ]);

    const colors = new Uint8Array([
        // Front - Blue
        0, 0, 255, 255,
        0, 0, 255, 255,
        0, 0, 255, 255,
        0, 0, 255, 255,
        // Top - Green
        0, 255, 0, 255,
        0, 255, 0, 255,
        0, 255, 0, 255,
        0, 255, 0, 255,
        // Back - Blue
        0, 0, 255, 255,
        0, 0, 255, 255,
        0, 0, 255, 255,
        0, 0, 255, 255,
        // Bottom - Green
        0, 255, 0, 255,
        0, 255, 0, 255,
        0, 255, 0, 255,
        0, 255, 0, 255,
        // Right - Red
        255, 0, 0, 255,
        255, 0, 0, 255,
        255, 0, 0, 255,
        255, 0, 0, 255,
        // Left - Red
        255, 0, 0, 255,
        255, 0, 0, 255,
        255, 0, 0, 255,
        255, 0, 0, 255
    ]);

This geometry has no UVs (so could not receive a texture) and no normals (so could not be lit)³.

While certainly possible to write the other vertex attributes by hand (in fact, I did) it should be fairly obvious that it isn’t something you’d do for more complex geometry—even the six-sided cube is tedious.

To define more complex geometry, we need to move past handwritten arrays and think about converting/exporting geometry from a different source.

Geometry Interface

Before we do that, let’s look at the Geometry interface currently in StaticRectangle

/**
 * Geometry data used to create a Mesh.
 * Includes vertex positions, optional UVs, normals, colors, and indices.
 */
export interface Geometry {
    positions: Float32Array; // Vertex positions
    uvs?: Float32Array;      // Optional texture coordinates
    normals?: Float32Array;  // Optional vertex normals
    colors?: Uint8Array;     // Vertex colors as Uint8Array
    indices?: Uint16Array | Uint32Array;   // Optional index buffer
}

The only requirement to create Geometry is vertex positions and we expect them as a flat Float32Array.

There are different options we can define on the pipeline about how to treat this flat array of positions, by default it’s treated as a triangle-list

“triangle-list”: Each consecutive triplet of three vertices defines a triangle primitive.

So, every three values in our array form a corner of a triangle, there are three corners to a triangle, two triangles in a face and six faces on a cube.

3 * 3 * 2 * 6 = 108

Hang on, the positions array in our example cube isn’t 108 values, it’s 72! (just trust me, or don’t… you can count them if you like)

Indices

The reason we are able to define less positions than the 108 we calculated, is because many of these vertices are sitting on top of each other. If you consider the first line of the indices array which defines our ‘front’ face

0, 1, 2, 2, 1, 3, // Front

we only need these 4 positions to draw the two triangles that make up the face. But what about the top, sides and bottom? can we not also share those positions too, then we’d only have 8 vertices and that is less than the 24.

Yep, we could do that—an optimisation for later perhaps. It would be interesting to see how much savings you get in storage vs CPU time to expand for the GPU. I have decided to keep it simple and compress the files instead, which in essence is a similar thing. I’m sure I’ll do a number of optimisation posts in the future.

So… what happens if you don’t include an indices array?

If you don’t include indices, then it’s just assumed that what are you providing are fully expanded vertex positions (sometimes referred to as polygon/triangle soup), so for the cube we’d be expecting 36 positions (108 elements) and apart from the obvious x, y z triplets the ordering doesn’t matter. There is a different draw call you make for this, in WebGPU it’s draw vs drawIndexed. There are times when you don’t bother with an index buffer, something I’ll get into in the future when it comes to particle systems and dive into render / storage optimisations.

In case you were curious, this is what happens if you give our non-expanded positions array for the cube to the draw command sans index buffer. Which is actually one of the early bugs I ran into getting my handwritten arrays to render.

Quick note before we move on, the order in which these indices define the triangles is important, or at least, the ‘winding order’ is important to our indices. If you look at the indices of the front face, you may notice they are going in a clockwise direction. This lets the renderer know which side of the face is considered the front. We use this for a common rendering optimisation called back face culling to cull faces that are facing away from you.

Preparing to export Geometry

I know I said I was done with the cube but let’s dust it off one last time. The reason it’s such a great example is because of how simple it is to understand.

Here we are in Autodesk Maya, I have created the same 1x1x1 cube that I had previously defined by hand.

In order to export the geometry, we need to iterate over the mesh to pull out positions, normals, uvs and vertex colours. Maya provides multiple ways to do this, but I’ll use the maya.api.OpenMaya API in python 3.10

First, we’ll define the same Geometry interface (using dataclasses.dataclass)

from dataclasses import dataclass

@dataclass
class Geometry:
    positions: list[float]
    normals: list[float]
    uvs: list[float]
    colors: list[int]
    indices: list[int]

The next part got complicated thanks to UVs and the myriads of options we have to define them in 3d modelling software. Not so much for my simple cube example, but I do intend to export more than just that.

The majority of this is really just Maya implementation detail, what is important is that I am able to iterate over the polygons in a mesh—a polygon could be quads, triangles or n-gons, doesn’t matter thanks to getPolygonTriangleVertices—grab all the details I need for that polygon, and eventually pop out an instance of the Geometry dataclass.

import maya.api.OpenMaya as om


def convert_to_geometry(object_path: str) -> Geometry:
    """ Converts the given Maya object to Geometry for
    export to StaticRectangle
    """
    # Get the mesh
    sel = om.MSelectionList()
    sel.add(object_path)
    dag_path = sel.getDagPath(0)
    mesh_fn = om.MFnMesh(dag_path)
    poly_iter = om.MItMeshPolygon(dag_path)
    # getPoints returns an MPointArray of deduped vertices
    point_array = mesh_fn.getPoints(om.MSpace.kObject)
    positions = []
    normals = []
    uvs = []
    colors = []
    indices = []
    # vertex_map[(global_idx , uv_id , normal_id )] = expanded vertex index
    vertex_map = {}
    current_vertex_index = 0
    while not poly_iter.isDone():
        poly_index = poly_iter.index()
        # We iterate over the triangles, even for quad meshes because that is what 
        # we need for the GPU. We shouldn't expect the mesh to be triangulated.
        num_tris = poly_iter.numTriangles()
        for tri_id in range(num_tris):
            # global vertex indices for the current triangle
            a, b, c = mesh_fn.getPolygonTriangleVertices(poly_index, tri_id)
            for global_idx in [a, b, c]:
                local_vert_idx = None
                for local_idx in range(poly_iter.polygonVertexCount()):
                    if poly_iter.vertexIndex(local_idx) == global_idx:
                        local_vert_idx = local_idx
                        break
                # Handle the no UVs case, doesn't appear to be a nicer way?
                try:
                    uv_id = mesh_fn.getPolygonUVid(poly_index, local_vert_idx)
                except RuntimeError:
                    uv_id = -1
                normal_id = poly_iter.normalIndex(local_vert_idx)
                vert_key = (global_idx, uv_id, normal_id)
                if vert_key not in vertex_map:
                    pt = point_array[global_idx]
                    positions.extend([pt.x, pt.y, pt.z])
                    normal = mesh_fn.getFaceVertexNormal(poly_index, global_idx)
                    normals.extend([normal.x, normal.y, normal.z])
                    if uv_id !=-1:
                        u, v = mesh_fn.getPolygonUV(poly_index, local_vert_idx)
                        uvs.extend([u, v])
                    color = poly_iter.getColor(local_vert_idx)
                    colors.extend([
                        int(color.r * 255),
                        int(color.g * 255),
                        int(color.b * 255),
                        int(color.a * 255)
                    ])
                    vertex_map[vert_key] = current_vertex_index
                    indices.append(current_vertex_index)
                    current_vertex_index += 1
                else:
                    indices.append(vertex_map[vert_key])
        
        poly_iter.next()
    # If all the vertex colors are unset (all black) then we don't
    # export them
    if colors == [0, 0, 0, 255] * (len(positions) // 3):
        colors = []

    return Geometry(positions, normals, uvs, colors, indices)

I say this part is just Maya implementation detail, because you could do the exact same thing in any other software (that supports python scripting) and provided you can spit out the same Geometry dataclass, then you can use the next snippet in any software.

Exporting the Geometry

This next part is actually pretty simple, at least in comparison to the preparation stage. I’m using gzip to compress a bytearray that I’m constructing using struct to pack the various arrays of the Geometry.

import gzip
import struct

def export_geometry(geometry: Geometry, filename: str) -> None:
    """ Write geometry data to a binary file

    Format: All data is little-endian
    - Header: 5 uint32s (vertex_count, index_count, index_format, has_uvs, has_colors)
    - Positions: float32 array
    - Normals: float32 array (if has_normals)
    - UVs: float32 array (if has_uvs)
    - Colors: uint8 array (if has_colors)
    - Indices: uint16/32 array

    # TODO: Handle optional indexing
    """
    vertex_count = len(geometry.positions) // 3
    index_count = len(geometry.indices)
    has_uvs = 1 if len(geometry.uvs) else 0
    has_colors = 1 if len(geometry.colors) else 0
    index_format = 16 if index_count < 65535 else 32
    data = bytearray()
    data.extend(struct.pack('<5I', vertex_count, index_count, index_format, has_uvs, has_colors))
    data.extend(struct.pack(f'<{len(geometry.positions)}f', *geometry.positions))
    data.extend(struct.pack(f'<{len(geometry.normals)}f', *geometry.normals))

    if has_uvs:
        data.extend(struct.pack(f'<{len(geometry.uvs)}f', *geometry.uvs))

    if has_colors:
        data.extend(struct.pack(f'<{len(geometry.colors)}B', *geometry.colors))

    dtype = 'H' if index_format == 16 else 'I'
    data.extend(struct.pack(f'<{len(geometry.indices)}{dtype}', *geometry.indices))

    with gzip.open(filename, 'wb', compresslevel=9) as handle:
        handle.write(data)

The first thing I do is write some data as a header for the file. This is necessary so we know how to read the data back in on the other side. We refer to this as a specification, as we are specifying how the bytes are laid out. If this were a proper specification, it would likely include other metadata, like version info and other bits and pieces. But for now, I’m keeping it simple.

A few things to point out here, index_format I’m storing this in the header, so I know what TypedArray to create when reading it in. For anything less than 65535 indices, we’ll use a Uint16Array, this will save some space. For anything else, we use a Uint32Array which will allow us to store up to 4,294,967,295 indices.

If you’re not overly familiar with python syntax, the struct.pack calls takes the endianness, datatype and how many to allocate as the first string, then the data to pack as a flat list.

Breaking down the header is the simplest:

The string '<5I'

‘<‘: little endian
‘5‘: 5 elements
‘I‘: 32bit integer

then packing the vertex_count, index_count, index_format, has_uvs (1/0) and has_colors (1/0) into those bytes. If you’re wondering, a 32bit integer is 4bytes, so the header is 4bytes * 5 elements = 20bytes.

The other lines look more complex, the string formatting is adding an extra complication, but it’s doing the same thing:

The string f’<{len(geometry.positions)}f'

f': the initial f tells python to do f-string formatting, substituting in place at runtime.
<: little endian
{len(geometry.positions)}: when evaluated results in the number of positions, e.g ‘72’
f: 32bit float

Using our cube as an example, this would result in the string '<72f' which means we’re going to pack 72 elements into those bytes in the bytearray.

The next argument *geometry.positions is some syntactic sugar that tells python to unpack the geometry.positions array in place, so it would be as if we have manually done this:

struct.pack('<72f', -0.5, -0.5, 0.5, 0.5, -0.5, 0.5, -0.5, 0.5, 0.5, 0.5....)

The very last line is where I use gzip to write out the bytearray to disk, compressing it at the same time.

Importing the Geometry

Getting the geometry out is great, but how about getting it back in again? Would you believe this is actually quite simple. Because I have written this data out precisely how the renderer expects it, then all we need to do is uncompress then unpack our byte arrays using the header data to tell us how many bytes to read into each.

/**
 * Parse StaticRectangle binary geometry file.
 * Format:
 * 
 * Header (20 bytes):
 *   - uint32: vertex count
 *   - uint32: index count
 *   - uint32: index format (16 or 32)
 *   - uint32: has UVs
 *   - uint32: has colors
 *
 * Vertex Positions (vertexCount * 3 * float32)
 * Vertex Normals (vertexCount * 3 * float32)
 * Vertex UVs (if has UVs) (vertexCount * 2 * float32)
 * Vertex Colors (if has colors) (vertexCount * 4 * uint8)
 * Indices (indexCount * uint16 or uint32)
 */
function parseGeometryBuffer(buffer: ArrayBuffer): Geometry {

    const header = new DataView(buffer, 0, 20);
    const vertexCount = header .getUint32(0, true);
    const indexCount = header .getUint32(4, true);
    const indexFormat = header .getUint32(8, true);
    const hasUVs = header .getUint32(12, true) === 1;
    const hasColors = header .getUint32(16, true) === 1;

    let offset = 20;

    const positions = new Float32Array(buffer, offset, vertexCount * 3);
    offset += vertexCount * 3 * 4;

    let normals: Float32Array | null = null;
    normals = new Float32Array(buffer, offset, vertexCount * 3);
    offset += vertexCount * 3 * 4;

    let uvs: Float32Array | undefined = undefined;
    if (hasUVs) {
        uvs = new Float32Array(buffer, offset, vertexCount * 2);
        offset += vertexCount * 2 * 4;
    }

    let colors: Uint8Array | undefined = undefined;
    if (hasColors) {
        colors = new Uint8Array(buffer, offset, vertexCount * 4);
        offset += vertexCount * 4;
    }

    let indices: Uint16Array | Uint32Array;
    if (indexFormat == 16) {
        indices = new Uint16Array(buffer, offset, indexCount);
    } else {
        indices = new Uint32Array(buffer, offset, indexCount);
    }

    return {
        positions,
        uvs,
        normals,
        colors,
        indices
    };
}

This should be reasonably easy to follow, as it’s just the reverse of what we just went through in python, but in TypeScript.

You may notice I have hardcoded the number/sizes of bytes, this is one benefit of a specification you’re allowed to make assumptions. It’s the reason many formats will store version information before a header, so you first read in the version and then you can adjust any parser logic on the fly, including changes to the file header.

Lastly, we need something to call this parsing logic, and this is where the file decompression happens.

export async function loadGeometry(url: string): Promise<Geometry> {

    const response = await fetch(url);

    if (!response.ok) {
        throw new Error(`Failed to load geometry: ${response.statusText}`);
    }

    let buffer: ArrayBuffer;

    if (typeof DecompressionStream === 'undefined') {
        log('DecompressionStream API not available, cannot load compressed geometry.', LogLevel.CRITICAL);
        // For now throw, unitl we can show the fail card.
        throw new Error('DecompressionStream API not available in this browser');
    }

    // Decompress using DecompressionStream API
    const stream = response.body!.pipeThrough(
        new DecompressionStream('gzip')
    );
    const decompressedResponse = new Response(stream);
    buffer = await decompressedResponse.arrayBuffer();

    return parseGeometryBuffer(buffer);
}

That’s it! instead of calling scene.createShape(name, ExampleCube()) I can now call scene.createShape(name, await loadGeometry('/resources/models/cube.bin'))

and hey presto, cube!

Eagle-eyes may spot the orientation difference between Maya/StaticRectangle, it’s because the I moved the camera.

Ok, So long, Cube.

How about a nice axis model that can show us which way things are oriented.

How about something with a few more vertices?

Unfortunately, without lighting or textures it’s kind of hard to tell what that is. I can actually make a very small tweak to the pipeline and change that topology from a triangle-list to line-list and instead of rendering triangles, we render edges (lines)⁴.

Now I’m getting custom geometry into StaticRectangle that supports all the Geometry features like UVs for textures and normals for lighting, that is where we’re heading next!

I’ve read many posts/articles on this topic, some ‘elitists’ think game developers have gotten lazy when it comes to optimisations for storage vs memory etc. but I think that is probably a bit of a generalisation. You can always make things better, but I do understand that it comes down to cost vs reward. ↩︎
You may (probably not) notice that my code snippets don’t use the NZ/UK English spelling of words, but I do in prose. This is purely habitual and because I have worked with a lot of American code in my career. If I see colour written as color outside of code it just looks wrong, and the same thing goes vice versa! stange… ↩︎
Not technically true, but IYKYK ↩︎
Something doesn’t look quite right here, it seems like some edges are missing but I haven’t looked into it yet. It’s probably not quite as simple as swapping this parameter around if you want to render wireframe properly. ↩︎

Geometry Interface#

Indices#

Preparing to export Geometry#

Exporting the Geometry#

Importing the Geometry#

Geometry Interface

Indices

Preparing to export Geometry

Exporting the Geometry

Importing the Geometry