Blog

I started tinkering around with 3D programming because of my fascination of procedural content generation and so my focus was on trying to create “worlds” that are entirely generated. Then I challenged myself to participate in a game jam, to test if I can finish a game in a very short period of time. There I noticed, that the toolbox I built up to that point, was full with very specific pieces of code, but didn’t prove to be flexible enough for situations such as a game jam. I had to reinvent the proverbial wheel several times over during the jam, leaving me with too little time for the so important polishing part of making a game. So I decided that after the jam is before the jam and I wanted to create a more solid foundation for my future endeavors in game development.

A library that takes care of the wheel

In comes procshape, a library that integrates with my engine of choice, Panda3D and serves as a foundation for procedural content generation. I haven’t planned this library all the way and I also use it to further enhance my knowledge about the topic at the same time, but fundamentally, I want a library that delivers the more tedious parts right out of the box:

• Geometry
  • Basic shapes
  • Isosurface extraction
  • Level Of Detail (LOD)
• Noise
• Collision Shapes

At first, I was inspired by ThinMatrix and his game equilinox that was under development for a long time and had a look that I just found charming. So to reduce the scope of an initial release of my library, I wanted to do away with smooth vertex normal calculation and texture mapping all together, since it reduces the complexity of generating 3D models and as seen in equilinox, doesn’t mean it has to look ugly. But I quickly changed my mind and for an initial release, I plan to implement a basic feature set that includes configurable smooth vertex normal calculation, but leaving out texture mapping. To prevent the smeared color that comes with only using vertex colors, I decided to use duplicate vertices and calculate a single color per triangle, leaving the option to use either smooth or flat shading to the user by providing implementations of both. This entails, that every triangle, that isn’t surrounded by triangles with the exact same color is clearly visible to the human eye, but at the same time smoothly rounded surfaces remain possible.
This enables per triangle smooth color gradients while also allowing for sharp color edges on a model, limited naturally by the size of the triangles used in it (in contrast to the much higher resolution/fidelity achieved by using texture mapping, textures and the many other techniques used to increase perceived detail).

Having made an initial decision what to implement and what to leave for a later day, I set out to plan an abstract structure, that targets re-usability. I want to be able to not only re-use my library for different projects, but also to be able to re-use additional components built on top of the library. So one of my main goals is to write properly documented and easy to read code, so future me (or who knows who else is going to use it) can read the code, without creating too much of a headache to understand it.

Performance, where it counts

I soon realized, that certain operations, mainly the ones that rely heavily on iterative tasks, shouldn’t be implemented in Python if I want to achieve usable performance (as in real time generation). So I decided to give C++ a go, something I always put off to do another day but crucial in the gamedev world. I learned the basics of both C and later C++ in school, but never got over those basics and other than being able to read and interpret most C++ code out in the wild, I didn’t have the first clue of the language and its intricacies. After a series of failures, things started to slowly make sense and my code started to do what it was intended to do. Mastering the language is still a giant leap and many fundamental concepts around it (looking at you gdb!!) away for me, but I’m starting to get more comfortable with it and some of the algorithms I implemented in Python at first and then ported to C++, started to run extremely fast and that is without actually optimizing anything. So under the hood, there will be a part written in C++, that neatly integrates into Python.

Basic Shapes et al

To do procedural generation, you have to start somewhere and to put together a plant/planet/house/etc. one needs some basic building blocks to actually generate such more complex objects. So I started to think what could prove useful and implemented a plane, that in turn can serve as a side for a cuboid, which in turn, with some basic linear algebra trickery, can become a spheroid. Next I made a cylinder and/or cone shape and left it at that basic state, to come back later to it, when I know more, what I actually need. But already armed with these basic building blocks, I could generate basic plants, planets, houses and much more.

Isosurface extraction

A very useful collection of methods for this topic can be found here. I chose to start out with dual contouring, as described in this tutorial here. This implementation takes an evaluation function, that returns values for points in a fixed grid, indicating whether the selected point sits on the inside (positive scalar) or the outside (negative scalar) and a gradient function, that you can read up on in the linked tutorial, if you want to understand it in more detail.

A dual contouring implementation in my library, enables shapes of high complexity to be created into a single mesh. Of course there’s a lot to it and I just might write a separate blog post, when I get into the actual implementation part of it.

Level Of Detail

Since in real time 3D rendering, resources usually are precious and little on the machine executing it. Even though a single modern GPU today could easily beat a supercomputer from the mid 1990s in computational power, the list of tricks and shortcuts implemented to enable real time rendering is long.

One technique that is widely used, is called Level of Detail or LOD. The underlying principle is, that the farther away an object is relative to the camera, the less “resolution” is needed to display it convincingly. By resolution in a 3D object, we’re talking about the number of polygons and vertices it contains. I recently stumbled upon an old article from the Game Developer Magazine by Steve Melax, that describes polygon reduction through the means of edge collapse (read up on it here), that I believe could serve for my purpose. It reduces the polygon count on a mesh by sequentially collapsing the edge with the least cost (the edge that if collapsed, has the least visual impact) and it does so, that you end up with all versions of your shape, from the original polygon count to 0.

I plan to use this implementation to potentially get various levels of detail for every shape I create. So when an object is calculated once in its highest polygon count, I send it through this algorithm and choose steps along the way to get each object in a different “resolution”.

Noise

Noise functions are the salt and pepper for many parts in procedural generation and will be a prominent part of my library. I plan to use the pyfastnoisesimd module that is blazing fast and gives a broad variety of different noise functions to use. I will implement some sort of playground where one can test the output of different noise configurations, because that was one of the things I re-implemented countless times ever since I started out using noise functions.

Collision Shapes

Using a physics engine in your games is really fun until you start to have many different objects, that need to collide with each other and still behave natural. A physics engine can slow down your game significantly and using basic shapes instead of complex geometry can speed up the process of collision detection.

It is not in the top of the list, but implementing an algorithm that approximates a shape with the means of using one or more basic collision shapes instead of the actual geometry can greatly improve the speed of a physics engine in general.

When is it ready?

There’s no good answer for this. Not right now, since fundamental parts are still in early development. But as soon as at least the core part is implemented and tested, I plan to use it in my next game jam and so can you. It’s all there in my github repository, liberally licensed under the MIT license for you to do with it whatever you wish.

Want me to implement something specific? Or want to contribute something yourself? Contact me or open an issue on my github repository for procshape. I’m open for all kinds of suggestions and knowing my rather noobish coding skills, I’m more than happy to learn if some more experienced dev stumbles upon this post or my github.