Generating Instead Of Storing Meshes

The 64kB is a category in the demoscene where the total executable size must be less than 65,536 bytes, and at that size, storing vertexes, edges, and normal maps is a waste of space. [Ctrl-Alt-Test] is a French Demoscene group that has been doing incredible animations for the last 13 years. They’ve written an excellent guide on how they’ve been procedurally generating the meshes in their demos.

It all starts with cubes. By stacking them, overlaying them, reusing them, and tiling them you can get better compression than raw vertexes. Revolution was the next trick, as it uses just a few points, plotting it via Catmul-Rom splines, and revolving around an axis. The numbers are pairs of 32-bit floats and before compression, a detailed pawn on a chess board can weigh in at just 40 bytes. Just these few techniques can take you surprisingly far (as seen in the picture above).

They later worked on deforming cubes and placing them into a semi-randomized column, which happened to look a lot like plants. This isn’t the first generated vegetation we’ve seen, and the demoscene technique focused more on getting the shape and setting the mood rather than being accurate.

Signed distance fields are another useful trick that allows you to generate a mesh by implementing a signed distance function and then running a marching cubes algorithm on it. In a nutshell, a signed distance function just returns the distance to the closest point on a surface from a given point. This means you can describe shapes with just a single mathematical equation. As you can imagine, this is a popular technique in the demoscene world because it is so space efficient in terms of code and data. [Ctrl-Alt-Test] even has a deep dive into one of their projects, Immersion, with a breakdown of where the space is allocated.

There are plenty of other tips and tricks here, such as generating textures and developing a C++ hot reload system for faster iteration. It’s just incredible that the executable that plays the whole video is smaller than just a JPEG screenshot of the video. It’s a reminder that the demoscene is still fascinating with new tricks and experiences even as the hardware stays the same. Continue reading “Generating Instead Of Storing Meshes”

Procedurally Generated Trees

As the leaves fall from the trees here in the Northern Hemisphere, we are greeted with a clear view of the branches and limbs that make up the skeleton of the tree. [Nicolas McDonald] made a simple observation while looking at trees, that the sum of the cross-sectional area is conserved when a branch splits. This observation was also made by Leonardo Da Vinci (according to Pamela Taylor’s Da Vinci’s Notebooks). Inspired by the observation, [Nicolas] decided to model a tree growing for his own curiosity.

The simulation tries to approximate how trees spread nutrients. The nutrients travel from the roots to the limbs, splitting proportionally to the area. [Nicolas’] model only allows for binary splits but some plants split three ways rather than just two ways. The decision on where to split is somewhat arbitrary as [Nicolas] hasn’t found any sort of rule or method that nature uses. It ended up just being a hardcoded value that’s multiplied by an exponential decay based on the depth of the branch. The direction of the split is determined by the density of the leaves, the size of the branch, and the direction of the parent branch. To top it off, a particle cloud was attached at the end of each branch past a certain depth.

By tweaking different parameters, the model can generate different species like evergreens and bonsai-like trees. The code is hosted on GitHub and we’re impressed by how small the actual tree model code is (about 250 lines of C++). The power of making an observation and incorporating it into a project is clear here and the results are just beautiful. If you’re looking for a bit more procedurally generation in your life, check out this medieval city generator.

Procedurally Generating Random Medieval Cities

With procedural content generation, you build data algorithmically rather than manually — think Minecraft worlds, replete with all the terrains and mobs you’d expect, but distributed differently for every seed. A lot of games use algorithms similarly to generate appropriate treasure and monsters based on the level of the character.

Game developer [Oleg Dolya] built a random city generator that creates excellently tangled maps. You select what size you want, and the application does the rest, filling in each ward with random buildings. The software also determines the purpose of each ward, so the slum doesn’t have a bunch of huge mansions, but instead sports a tangle of tiny huts. [Oleg] shows a little of how the application works, using polygons created with the guard towers serving as vertices. You can learn more about the project on Reddit.

As new as this project is, it’s limited. All the maps feature a walled community, each has one castle within a bailey, and none of the cities includes a river or ocean port. [Oleg] designed it to make cool-looking maps, not necessarily accurate or historically realistic ones. That said, he’s already tweaked the code to reduce the number of triangular buildings. Next up, he wants to generate shanty towns outside the city walls.