Trees and frustum culling in C++ with raylib

Intro

0:00 Hello and welcome back to episode sixteen, where trees grow on the island from last time, and we make the client draw all of it a lot faster. Let's begin with a quick look at where we're going to be by the end of the episode.

0:14 We're running across an island, which the server and the client both make from a seed number, with hills, woods and a sea around it. The camera follows me, and turns around me when I ask it to, while the trees fade into the fog.

0:30 On the website of the series you can find more information about the project. The code for the project is open source on GitHub, tagged at each step of each episode so that you can follow along.

Last time

0:42 Now, before we get to today's work, let's quickly go over what we did last time. Our board became an island, five hundred and twelve metres across, made from value noise and a seed, in a library that the server and the client both build. Both compute it to the last bit, as we turned off fused multiply-adds, with a test that pins its fingerprint. The client draws it as flat-shaded triangles, with a sea and fog, and a camera follows you, while the server lets you wade and slide along the coast, with camps of skeletons around the island.

Today

1:13 Today, trees grow on our island, where the seed puts them, and the server makes their trunks solid, so you can't walk through one. The trees are a lot more to draw, so then we measure how fast the client draws all of it, with a benchmark of its own. And with those numbers, we cut the island into chunks, and draw the ones in sight and no others, which makes it a lot faster. All right, let's get started with where the tree comes from.

Trees

1:42 An island needs trees, and ours comes from Poly Pizza, like the skeleton and the sword. It's a low-poly tree that Google made for Poly, its old site for three D models, which closed in twenty twenty-one, and Poly Pizza keeps its models. At about a hundred and sixty triangles, we can have thousands of them. Its licence is Creative Commons Attribution, so we can put it in our repo and ship it, as long as we credit Poly by Google. Download gives us an OBJ or a g l b file, and we take the g l b, like our other models. It has no normals, and its colours come from a small texture, which is four squares of colour, a palette. So the client is going to turn it into triangles of its own, each with its face's normal and one colour, like our ground.

2:30 Where the trees stand goes in the terrain too, as the server has to know which ones are in your way, and the client where to draw them. In terrain dot h, a struct, tree, with its x and z, and its yaw, in radians, around the vertical. And its scale is how much bigger or smaller than the model it is. K tree spacing is four metres, as the trees grow on a grid of squares this size, at most one in each. That keeps them apart, and it lets the server find the trees near a point without looking at all of them. K trunk is how close to the middle of a trunk a player can stand, half a metre. And walkable's comment gets the trees: on the grid, out of the sea, and not in a tree. Then a getter for the trees, for the client to draw, and in the private part, plant, which places them, and in a tree, for walkable. The terrain keeps the trees, and tree in, which is the tree in each square of the trees' grid, or minus one. And tree squares is how many squares there are along each side. In terrain dot c c, numbers, for pi, as the trees turn all the way around. In the unnamed namespace, k clearing, as the players start in a clearing, with no trees within sixteen metres of the middle. Trees grow between one metre and eleven: above the beach, and below the rock. Unit turns the top twenty-four bits of a hash into a number from zero to one, like value did in the noise. The island's constructor calls plant, once the heights are there, as a tree needs the height under it. Plant works out the squares along each side, the size of the grid over four metres, which is a hundred and twenty-eight. Then it fills tree in with minus one, as none of the sixteen thousand squares has a tree yet, and two loops go over the squares, row by row. Each square works on its own, so the trees don't depend on the order we go in. Inside, a comment: each square rolls its own dice, for where in the square its tree stands, whether it grows, which way it faces, and how big it is. Roll is a lambda that hashes the seed plus a thousand plus a die number, with the square, so each die gives a number of its own. And the dice don't line up with the hills, whose hashes use numbers close to the seed. We roll with hashes, and not with a twister and a distribution like the camps, as the server and each client have to plant identical trees, whatever their standard library. X and z come from the first two dice, in the middle sixty percent of the square. So trees in neighbouring squares don't touch, and don't line up in rows, as they would at the middle of each square. Then the noise again, with the seed plus two thousand, and three octaves, over sixty metres, and over it: woods where the noise is high, and a few lone trees elsewhere. Chance is the share of squares that grow a tree there, between five and ninety-five percent. Three times the noise reaches those limits quickly, so the woods are thick, and the open ground stays open, instead of trees scattered evenly. A square skips its tree when its third roll is over the chance, when the ground under it is too low or too high, or within the clearing. Otherwise, tree in keeps the index the tree is going to have in the list, so that in a tree can find it from its square. Then the tree goes in, with a yaw from the fourth die, all the way around. And its scale comes from the fifth, from point eight to one point four. Turning and sizing each tree keeps woods of a single model from looking copied and pasted. Walkable gets one more check, that the point is not in a tree. In a tree finds the square the point is in, i and j, with floor, like height does for cells. Then two loops, down over the rows and across over the columns, look at that square and the eight around it, three by three. At the sides of the grid, max and min keep the loops on it, so a point near the edge doesn't look up a square that isn't there. For each of the nine, tree in gives us its tree, if it has one. And if any of them is closer than k trunk, the point is in a tree. The comment over the loops says why we look at nine squares: a trunk near the side of its square is closer to us than its square is. Nine squares is a few comparisons, instead of one for each tree on the island, so the server can do it for each player, each tick. In the terrain test, the fingerprint covers the trees too, and its comment says so: over the bits of each corner's height, and of where each tree stands. Add is a lambda that hashes a float's bits into the hash, with the XOR and the multiply from before. And we call it over each corner, and then over each tree's x and z. So the expected number changes, to the one Linux gave me, and my Mac gives it too. And the land and sea test checks that the island has trees, with assert false on empty, and that the first tree's trunk isn't walkable.

7:14 On the client, the tree's model needs a header of its own, trees dot h, which starts with raylib, string and vector, and then our triangles and terrain headers. K tree height is five metres, before each tree's own scale, and trees folder is where the model goes, next to the client, like the characters' folder. Face is a triangle, its three corners and its colour, which we read from the model once, and use for all the trees. Load faces reads a model's triangles, and the comment says how: standing on y equals zero and a metre tall. And each is in the colour of its texture under the middle of the face. It returns none if the file isn't there, so the client still runs without it. Tree transform takes a tree, and gives the matrix that sizes the model, turns it, and moves it to the tree's place. And add faces is for the renderer now, and for the chunks later on. It adds the faces to the triangles we pass in, moved by the transform. It moves the corners on the CPU, and not in a shader, so that many trees can go into one set of triangles. In trees dot c c, after our header, raymath, for the matrices, then algorithm, for clamp, string and vector. In the unnamed namespace, color at reads the texture's colour at u and v, which go from zero to one across it. It turns u and v into a pixel's x and y, clamped to the texture, so that a u of one stays on the last pixel, and get image color reads it. Each face gets a single colour from the texture, and the triangles carry it in their corners, so the trees need no texture when we draw them. Trees folder is the application's folder, with trees after it, like the others. Load faces checks that the file is there first, and then load model reads the g l b, as raylib reads glTF. Its bounding box gives us the scale that makes it a metre tall, as the model is about five hundred units tall in its file. For each of its meshes, and this one has one, we take its material. Then load image from texture gets the material's diffuse map, and the comment over it says why: raylib has uploaded the texture already, so we read it back. We read the mesh's arrays directly, as raylib keeps a copy of them. The corners are three floats each in the mesh's vertices, as x, y and z. So to read them, corner is a lambda that captures the mesh, the scale and the box. It takes a corner's index, and reads its position, scaled, with its bottom moved to zero. Then, for each triangle, its three corners come from the mesh's indices if it has them, as this one shares corners between triangles, and in order if it doesn't. U and v add up a third of each corner's texture coordinates, if the mesh has them, which is the middle of the face on the texture. The palette's squares are big, and each face sits in one of them, so the colour there is the face's colour. Then the face goes on the list, with its three corners and that colour. Then we unload the image and the model, as we've copied what we need, and return the faces. Tree transform scales the model by the tree's height, five metres times its scale, turns it by its yaw, and moves it to its place, at the tree's x and z. Raylib's matrix multiply applies the left one first, so it's scale, then turn, then move. In the other order, the turn would swing each tree around the middle of the island, instead of around its trunk. And as the model's base is at its origin, the trunk's base ends up at the tree's place. Add faces takes the matrix by const reference, as it's sixteen floats, and goes through the faces. For each one, it transforms the three corners with the matrix, using raylib's vector three transform, before it adds the triangle in its colour. Triangles works out each normal from the moved corners, so a turned tree's faces are lit the way they face now. Add faces doesn't upload anything, so the renderer and the chunks decide when the triangles go to the GPU. In renderer dot h, our trees header, and two members: the tree as a model, which is optional, as the file may not be there, and a vector with each tree's transform. In renderer dot c c, raymath, for the identity matrix, vector, and our triangles header. The constructor loads the tree's faces from the trees folder, and if there are any, it adds them to triangles as they are, with the identity matrix. Then it uploads them, and makes a model, drawn with the cube's shader, like the ground, which the destructor unloads, if there is one. Set terrain makes each tree's transform once, after clearing the ones from any terrain before. Draw goes through them after the ground, and draws the tree's mesh with each transform, one draw for each tree. In the client's CMakeLists, trees dot c c goes in the core library. And the assets step copies the trees folder next to the client, like the characters, the monsters and the weapons. The trees folder gets a README too, like the weapons' and the monsters'. And its table credits the tree to Poly by Google, from Poly Pizza, under C C by three point oh.

12:18 Let's build it, log in, and head north-east, out of the clearing in the middle, to see the trees. And something's wrong with them, as there are no trunks, and the tops of the trees sit on the grass, like bushes. Further on, where the ground is higher, some of them are gone. And when we walk into one of those treetops, the server stops us, at the trunk that's hidden under the grass. The server has the trunks in the right place, from the seed, so it's the client that draws the trees too low.

12:48 So, back in tree transform, the move takes the tree to its x and z, at a height of zero. Zero is sea level, and around the woods, the island's ground is a couple of metres above it, and more inland. So each tree stands that far down, under the grass. The height has to come from the terrain, and first, in the unnamed namespace, k sunk, fifteen centimetres. A tree stands at the height under the middle of its trunk, and on a slope, one side of the trunk would be in the air. So we sink it a little, and the comment over it says why: so that the trunk doesn't float over a slope. Then tree transform takes the terrain too, by const reference, and the move goes to the ground's height under the tree, less k sunk. In the header, the declaration takes the terrain as well, and its comment now says that it stands the model on the ground. And in the renderer, set terrain passes the terrain along, as it has it already.

13:43 Let's head north-east again, out of the clearing in the middle. A few lone trees stand in the grass, and ahead of us are the woods. And each tree is turned and sized by its square's dice, in the colours from the palette. When we walk into a trunk, the server stops us, and we slide around it, as walk does at the coast. As we turn the camera, the woods go on into the fog.

How fast it draws

14:08 The island and its trees are a lot more to draw than our board. So to know how fast the client draws them, we need a benchmark, like the one we wrote for the server in episode eight. The renderer has to tell the benchmark what it drew each frame. So in renderer dot h, a struct, work, with a comment: what the last draw asked the GPU for, the terrain, the trees and the sea. Draws counts the draw calls, where each one is the CPU asking the GPU to draw a mesh. Triangles counts what those meshes hold, and a getter lets the benchmark read them. Draw counted is a private helper that draws a mesh and counts it, with the mesh, the material and the transform, which is what raylib's draw mesh takes. The renderer keeps the work as mutable, which lets a const function change it. The comment over it explains: draw is const, as drawing doesn't change what we draw, but it counts. In renderer dot c c, set terrain gives the sea's material its colour, k sea, as draw counted takes a material, and no tint like draw model does. Draw counted calls draw mesh with the mesh, the material and the transform, then adds one to the draws, and the mesh's triangle count to the triangles. Draw starts each frame by zeroing the work, before anything is drawn. After clearing, as before, come the ground and the trees, which are most of the frame. The ground goes through draw counted with the identity matrix, as it's in place already, and each tree with its transform. The figures and the cube stay on draw model, and out of the count, as the benchmark has no players, and the terrain is what we're measuring. The sea comes last, as before, through draw counted too, with a translation to sea level as its transform. Then the benchmark, in a new file, bench main dot c c, as a program of its own. It's the client without a server: a window, a terrain from a seed, a renderer and a follow camera, so it starts with raylib. Then the standard headers, with fstream, for writing the results to a file, and from Abseil, status or, for the window, and numbers, for reading the arguments. Then our camera, renderer and window headers, and the terrain's. Main's comment says what it does: walks once around the middle of the island, through the woods, and draws those frames again on each run, as fast as it can. It takes the number of frames, twelve hundred by default, the seed, one by default, with simple a to i, and a file for the results. If either isn't a number, or there's less than one frame, it prints how to use it, and returns one. Then we open our client's window, with the title nanoMMO bench, at a fixed twelve eighty by seven twenty. The pixels to fill change how long a frame takes, so a fixed size lets runs on different screens compare. If it doesn't open, we print the status, which says why, and return one. Our window caps the frame rate at sixty, so set target FPS of zero takes the cap off, and each frame takes as long as it takes to draw. Then the terrain, the renderer and the camera, like the client has. The walk is a circle, eighty metres out, and k warm up is sixty frames, as the first frames load and warm up the GPU, so they don't count. Step is how far around the circle each frame goes, so the frames make one lap, whatever the speed, and each run draws identical frames. Times keeps each frame's time, and draws and triangles add up the work, as sixty-four-bit integers, as that's a lot of triangles. The loop starts at minus the warm-up, so the frames from zero on are the ones that count, and it stops early if the window closes. For each frame, the angle gives x and z on the circle, and during the warm-up, we stay at the start. The camera follows a point there, on the ground, and turns by the step. And the comment gives the reason: turning with us, so that it looks over us at the middle of the island. Then we draw, like the client, and get time after end drawing gives the time from one frame to the next. End drawing swaps the buffers, and the driver holds us there when the GPU falls behind, so that time covers the GPU's work too. After the warm-up, each frame's time goes into times, in milliseconds, and the work goes into the totals. At the end, a sorted copy of the times gives us percentiles, with a small lambda, which picks the time at that share of the way through the list. The total of the times gives the frames per second, which gets a variable of its own, as we print it twice, here and in the JSON. Then we print it all to standard out, a line for each number, with a label, so a person or a script can read it. We print the frames, the frames per second and the two percentiles, where p fifty is the median frame and p ninety-nine the slowest one in a hundred. And then come the draws and the triangles for each frame, on average, as the totals divided by the frames. With a third argument, the results go into that file too, as JSON, for scripts and charts to read. An ofstream opens the file, and we write the object into it by hand, as six numbers in braces don't need a library. The keys are frames, f p s, p fifty and p ninety-nine in milliseconds, with m s on the end of their names, and the draws and the triangles. The stream gives each double six significant digits, which is plenty for a benchmark that varies from run to run anyway. Then we check the stream, as writing can fail, say if the folder isn't there. And if it failed, we print that we couldn't write it, and return one, and otherwise, we return zero. In the client's CMakeLists, nanommo client bench is an executable of its own, linked with the client's core. It depends on the client's assets too, so the trees are copied next to it, and it draws them.

19:50 We build it as release, with optimisations on, as a debug build tells us little about what players get. And we run it on my Mac, with a file for the results as its third argument. Its window shows the lap around the island, at whatever speed the GPU manages. It drew twelve hundred frames, at around five hundred and forty a second, with a median frame of about one point six milliseconds, and a p ninety-nine of around five. Each frame took fifteen hundred draws, and three hundred and seventy thousand triangles, and my Mac gets through that quickly, as it has a capable GPU. I also ran it in Docker, where Mesa's llvmpipe draws on the CPU, which is how this series records the game. There, the median frame takes around fifteen milliseconds, and it manages about sixty-six frames a second, not far above sixty, with no more than the island to draw.

20:43 So let's look at where the time in each of those frames goes. Each tree is a draw call of its own, and each one costs the CPU and the driver some work. And for each one, they set up the shader, the matrices and the buffers, for a mesh of a hundred and sixty triangles. And each frame, we hand the GPU all of the island, five hundred and twelve metres of it, and all of the trees on it. Most of that is behind the camera, or past the fog at a hundred and forty metres, where nobody can see it. So the GPU transforms all of it, and then throws it away. So we're going to cut the island into chunks, which are squares of thirty-two metres, and put each chunk's ground and trees into one mesh. That's two hundred and fifty-six chunks, so at most that many draws, for all of it. And each frame, we draw the chunks in sight, closer than the fog and inside what the camera sees, and skip the rest. Skipping what nobody can see like that is called culling.

21:40 To know whether a chunk is in sight, we use what the GPU uses. The camera's view and projection matrices, multiplied together, take a point in the world to what's called clip space, four numbers, x, y, z and w. The point is on the screen when x and y are between minus w and w, and between the near and the far planes when z is. What the camera sees is a pyramid with its top cut off, called the frustum, and these six checks are its six sides. Each chunk has a box around it, from its mesh. If all eight corners of the box are past one side, the whole box is out of sight, and we skip it. If the corners are past different sides, it may still cross the screen, so we draw it. And that way, we may draw a few chunks we didn't need, and we don't miss one we did.

22:27 The ground mesh was the whole island at once, and a chunk needs a square of it. So ground dot h now includes triangles dot h, as ground mesh becomes add ground, which takes the triangles to add to. As its comment says, it adds the two triangles in each cell of a square of cells, from the cell at left and top, coloured by height and slope. In ground dot c c, triangles dot h goes, as the header has it now. And add ground's loops go from top and left, for that many cells. And min stops them at the grid's edge, if the square goes past it. Leaving the upload to the caller lets a chunk put its trees into those triangles too, before they go to the GPU. Then a new header, chunks dot h, with raylib and vector, and our trees and terrain headers. K chunk cells is sixteen, which its comment says is thirty-two metres, small enough to cull a lot, and big enough that the island is two hundred and fifty-six chunks. A chunk is a struct with a model and its bounding box. Over it, we write what it holds: a square of the terrain, its ground and its trees in one mesh, so that one draw draws all of it. Load chunks builds them from the terrain, the tree's faces, and the shader to draw them with, and unload chunks unloads them. And in sight is the check we just saw, from the box, the eye, the matrix, and the farthest we see, which the renderer sets to the fog's far distance. Its comment: whether any of the box is closer to the eye than the farthest we see, and inside the view, past none of its six sides. So a chunk out of sight costs the renderer no more than this check, with no draw call. In chunks dot c c, after our header, raymath, for vector three clamp and distance, algorithm, for clamp and none of, array, for the counts, and vector, and our ground and triangles headers. Load chunks works out across, how many chunks there are along each side, rounding up. So a grid that isn't a multiple of sixteen still gets all its cells, in a smaller chunk at the edge. It makes triangles for each chunk, in a vector of squares, which all stay on the CPU until the trees are in them too. First, it adds each chunk's ground, with add ground, for its sixteen by sixteen cells, starting at i and j times sixteen. Then the trees, and over them, a comment: each tree goes in with the ground under its trunk. Size is a chunk's size in metres, which is thirty-two. For each tree we planted, the chunk's i and j come from the tree's x and z, clamped to the grid. A crown can reach over into the next chunk, and that's fine, as the chunk's box comes from its mesh, crown and all. Then add faces puts the tree's faces in that chunk's triangles, moved by the transform we drew each tree with before. So the trees aren't drawn on their own any more, as they're part of the chunk's mesh, with a few dozen of them in a chunk of the woods. Raylib can also draw one mesh many times in a single draw, which is called instancing, but it needs a shader that reads each tree's transform. Baking the trees into the chunks keeps our shaders as they are, and the cost is memory, for a copy of each tree's triangles. Then each chunk's triangles go to the GPU, as a mesh, and the chunk is a model of it, with get mesh bounding box for its box. The material gets the shader, and the chunk goes on the list. Unload chunks goes through the chunks, unloads each model, and clears the vector, so that calling it again doesn't unload them twice. In sight starts with the distance, which is the quicker check. Vector three clamp gives us the point of the box closest to the eye. And if that's further than the farthest we see, the chunk is in the fog, and out of sight. Then the frustum, and its comment: on the screen, a point's x, y and z are between minus w and w. The box is out of sight if all eight of its corners are past one of those. So past counts, for each of the six sides, how many corners are past it, starting at zero. The textbook way pulls six planes out of the matrix instead, and for two hundred and fifty-six boxes, either is quick. Then a loop over the eight corners, where the three bits of the corner's number pick the box's minimum or maximum, one bit for each axis. So x comes from the first bit, y from the second, and z from the third. Then the corner goes through the matrix by hand, into clip, its x, y and z, and then its w. The names look odd, as raylib keeps its matrices a column at a time, so m zero, m four, m eight and m twelve are the first row. We write it out, as raylib's vector three transform gives us x, y and z, and not w. For each axis, the corner counts as past the low side if it's below minus w, and past the high side if it's above w. At the end, none of, with a lambda, says the chunk is in sight if no side has all eight of the corners past it. In renderer dot h, our chunks header goes in, next to the trees. The members change: the tree is its faces now, as we bake it into the chunks. And the ground and the trees' transforms become the chunks, while the sea stays as it was, as a single square. In renderer dot c c, rlgl, the layer under raylib that talks to OpenGL, and the triangles header goes, as the chunks build them. The constructor keeps the tree's faces, and the destructor doesn't unload a tree model any more. Set terrain loads the chunks, and the comment from before now says the ground, the trees and the sea have no bones either. Unload terrain unloads the chunks, and the sea if it's there. In draw, after begin mode three D, the view projection matrix comes from r l get matrix modelview and r l get matrix projection. And the comment says why: as begin mode three D set them up, so we cull with what the GPU will use. Then each chunk in sight, closer than the fog's far distance, goes through draw counted, so the benchmark sees what we skip. In the client's CMakeLists, chunks dot c c goes in the core library. And the renderer test that looks out to sea checks the draws, with a comment: the sea, and of the island's two hundred and fifty-six squares, the few ahead of us. It expects more than one draw, and fewer than thirty-two, so it fails if the culling lets the whole island through, or hides the chunks in front of us.

28:50 Let's run the benchmark again, on that lap, with the chunks. Its window looks like before, as the chunks we skip are ones nobody could see. The median frame is now about two hundred and ten microseconds, around eight times faster, and it draws about thirty-eight hundred frames a second. Each frame takes twenty draws, instead of fifteen hundred, and about sixty-two thousand triangles, which is seventeen percent of what it was.

29:17 Side by side, the median frame on my Mac went from one point six milliseconds to zero point two one, and the draws from fifteen hundred to twenty. In Docker, with llvmpipe drawing on the CPU, it went from about fifteen milliseconds to thirteen, which is a lot less of a gain. Most of the time there goes on filling the pixels, and there are as many pixels on the screen with chunks as without. So the chunks pay off most where the GPU is waiting on the CPU and the driver, like on my Mac. And the island can grow, with more trees, without each one costing a draw.

Docs

29:52 Last, the README, where the island gets its woods, and the section on the world says how the trees grow, on a grid of squares, where the noise is high, and that you can't walk through a trunk. The fingerprint covers the trees now too, and the tree's part says where it comes from, with its licence. Then a part on drawing the island fast covers the chunks and how they're culled, and the commands to run the client's benchmark, as a Release build on the Mac and in Docker, with my numbers to compare against.

Wrap-up

30:22 So, today about fifteen hundred trees grew where the seed says, all from one model on Poly Pizza, and the server made their trunks solid. A benchmark of the client's own measured the frames, and chunks, drawn when they're in sight, took the draws from fifteen hundred to twenty. And the median frame on my Mac got eight times faster.

Playing it

31:44 Let me know in the comments what you'd like to see next. And if you want to follow along with the series, subscribe to the channel. I hope you find this useful, and thanks for watching.