This post shows how to create and delete sub meshes in a mesh without calling OpenGL functions many times. This way, we minimize the OpenGL overhead and speed up our game.

This post is part of the OpenGL 2D Facade series

Create and delete faces

In usual cases, like the mesh that represents the world, the mesh is static. There is always the same number of faces: each layer has width per height cells for the world. In other cases, like text or frame boxes, we need to create and delete meshes many times. The overhead is acceptable for these examples, but for faster ones, like animations based on particles, it can be an issue.

Rather than creating and destroying meshes using the OpenGL API, I propose to create a single, large mesh we send to the GPU at most one time per frame. The trick is to allocate and free faces inside this mesh by ourselves. We display the allocated faces as usual, and we set a fully transparent texture for the other ones.

Face allocator

Idea and usage

The core of the approach is inside a FaceAllocator class that tracks the allocated faces in a range of indices. Furthermore, we associate a unique value (or id) to each set of faces.

For instance, if we need to allocate four faces, we ask for them given a specific id1 (an integer value):

faceAllocator = FaceAllocator()
faceAllocator.allocate(id1, 4)

If we never used the id, we get four face indices dedicated to this id.

We can also ask for two more faces with the same id1:

faceAllocator.allocate(id1, 2)

After this call, id1 has six face indices. We can ask for these indices:

faceIndices1 = faceAllocator.getIndices(id1)

The list faceIndices1 contains six values associated with id1. We can use them safely to create a sub mesh with six faces within a larger one.

Now, if we ask for four with another id, for instance id2, then we can get a new list of face indices:

faceAllocator.allocate(id2, 2)
faceIndices2 = faceAllocator.getIndices(id2)

The allocation algorithm guarantees that faceIndices1 and faceIndices2 have no shared values. We can update each sub-mesh at no risk.

Once we are done with one sub-mesh, we can free the corresponding face indices:

faceAllocator.free(id1)

The algorithm will use faces associated with id1 if we allocate new ones.

The allocation algorithm

There are many algorithms for allocation, and I propose one in this post with good computational complexity. It is not the best one, but it is simple and enough for our case.

The algorithm uses an array that associates an id to each face index. In the beginning, all its cells have no association (for instance, a zero value):

The array has a specific size we call capacity. This capacity is the maximum number of faces we can allocate and equals the number of faces in the main mesh. We can change this size if needed, but most of the time, it is left unchanged.

If we allocate four faces with the id 1, then the algorithm chooses the first free cells from the left:

If we need two more faces with the same id, the same procedure repeats:

When we need the face indices of a given id, we parse the array and add all the indices of cells with the id to a list. In this example, the face indices for id 1 is [0, 1, 2, 3, 4, 5].

If we allocate four more faces, but for a new id 2, the array becomes:

Imagine now that we no more need faces for id 1. In this case, we free all corresponding indices, and the array is:

Finally, if we allocate eight faces for a new id 3, the algorithm uses all the free cells, starting from the left:

As we can see, the face indices for a given id are not necessarily contiguous. With the id 3, the indices are [0, 1, 2, 3, 4, 5, 10, 11].

Speeding up

We can implement the allocation algorithm parsing the array to find the free cells or the ones assigned to an id. It works fine, but the complexity of most operations is O(n) (e.g., linear with the size of the array).

We can speed up the functions using a dictionary that stores each id's indices, including a 0 id corresponding to free cells. Remind that accessing items of a dictionary with Python is O(1) (same speed whatever the size of the dictionary). It is because Python uses hash tables to implement them.

Implementation

Construction

We init the FaceAllocator instance in the following way:

class FaceAllocator:

    def __init__(self, step: int = 256):
        self.__step = step
        self.__face2id = [0] * step
        self.__ids = {
            0: [i for i in range(step)]
        }  # type: Dict[int, List[int]]

The step private field is the number of cells we add to the array when there are no more free cells.

The face2id private field is the main array that maps face indices to face ids.

The ids private field is the dictionary that contains the list of face indices for each id. The id 0 corresponds to free cells: at the beginning, all cells are free.

Allocation

The allocation method is the following one:

def allocate(self, faceId: int, count: int):
    if faceId <= 0:
        raise ValueError("Invalid id {}".format(faceId))
    freeIndices = self.__ids[0]

    # Increase capacity if the array is too small
    while len(freeIndices) < count:
        oldLength = len(self.__face2id)
        newLength = len(self.__face2id) + self.__step
        freeIndices += [i for i in range(oldLength, newLength)]
        self.__face2id += [0] * self.__step
        self.__ids[0] = freeIndices

    # Remove free cells and add them to the faceId list
    freeIndex = freeIndices[0:count]
    del freeIndices[0:count]
    for i in freeIndex:
        self.__face2id[i] = faceId
    if faceId not in self.__ids:
        self.__ids[faceId] = freeIndex
    else:
        self.__ids[faceId] += freeIndex

Lines 2-3 check that the id is valid (strictly positive number).

Line 4 gets the list of free indices.

Lines 7-12 increase the size of the array if there are not enough free cells. I use a while loop because it is easier to implement. Each iteration adds step cells to the main array.

Lines 15-22 are the actual allocation. We first get enough free cell indices (line 15), and we remove them from the list of free cells (line 16). Then, we assign to all these indices the id requested by the user (lines 17-18). Finally, we create a new list for the id if there is no one (line 20) or add to the existing one (line 22).

Get indices of an id

Get the indices of an id is straightforward since we store them in the ids dictionary:

def getIndices(self, faceId: int) -> List[int]:
    if faceId not in self.__ids:
        return []
    return self.__ids[faceId]

Free all cells of an id

Releasing all cells of a given identifier works as follows:

def free(self, faceId: int):
    if faceId <= 0:
        raise ValueError("Invalid id {}".format(faceId))
    if faceId not in self.__ids:
        return
    faceIndices = self.__ids[faceId]
    freeIndices = self.__ids[0]
    freeIndices += faceIndices
    for i in faceIndices:
        self.__face2id[i] = 0
    del self.__ids[faceId]

Lines 2-3 check that the id is valid (strictly positive number).

Lines 4-5 leave the method if there are no cells to free.

Line 6 gets the list of face indices to free

Line 7 gets the list of free indices.

Line 8 adds the face indices to the list of free indices.

Lines 9-10 set a zero id to all face indices to indicate that there are free to use.

Line 11 deletes the list of face indices for the given id.

OpenGL Layer classes

I add to the OpenGLLayer class an instance of FaceAllocator, and three new methods to allocate and free face indices in the main mesh (in the mesh private field). I also add many other improvements that I don't detail here; you can look at the complete code in the download below.

Allocate

The allocateFaces() method finds a set of free face indices in the main mesh:

def allocateFaces(self, facesId: int, faceCount: int):
    assert self.__faceAllocator is not None, "Static layer, can't allocate/free faces"
    self.__faceAllocator.allocate(facesId, faceCount)
    if self.faceCount < self.__faceAllocator.faceCount:
        self.__setFaceCount(self.__faceAllocator.faceCount)
    self.setRenderedFaceCount(self.__faceAllocator.faceCount)
    return self.__faceAllocator.getIndices(facesId)

Line 2 checks that there is a face allocator: we disable this feature when it is unnecessary.

Line 3 allocates the indices.

Lines 4-6 ensure that the size of the main mesh is also increased if the face allocator has to. The setFaceCount() private method adds new transparent faces if we need more faces. We call the setRenderedFaceCount() method to show all faces the allocator considers.

Line 7 returns the indices of the faces we allocated.

Get face indices

The getAllocatedFaces() method returns of indices for an id:

def getAllocatedFaces(self, facesId: int):
    assert self.__faceAllocator is not None, "Static layer, can't allocate/free faces"
    return self.__faceAllocator.getIndices(facesId)

Free

The freeFaces() method free the faces of an id:

def freeFaces(self, facesId: int):
    assert self.__faceAllocator is not None, "Static layer, can't allocate/free faces"
    faceIndices = self.__faceAllocator.getIndices(facesId)
    self.hideFaces(faceIndices)
    self.__faceAllocator.free(facesId)

Lines 3-4 get the indices of the faces to free and hide them. We could also delete the faces in the main mesh and recompute mesh properties accordingly. It will save memory but at a high computational cost. It can be interesting if we have to create a huge sub-mesh a single time, but I don't see any case where it can happen.

Line 5 frees the face indices.

Usage

I use this new feature in the text and UI layers. The implementation is straightforward: every time we create a text or a frame box, we allocate the number of faces we need. When we no more need the component, we free the faces! You can see these implementations in the complete program below.

Final program

Download code & assets

In the next post, I'll show how to shake the screen with shaders.