Building a 3D Engine

Screenshots and comments as I gradually put together a 3D rendering environment with C++.

[q39engine]

This scene has a hundred thousand models and over a million triangles, yet the time to pick any single triangle is a millisecond or less. And this is without any optimizations. That's how well the bounding volume hierarchy works so far.

[q39engine]

This is preparation for testing the BVH, bounding volume hierarchy. I want to see how it performs when I try to click on one of the blocks.

[q39engine]

If you want to render a randomly generated terrain in 3D, one way is to simply generate a height for each point on a grid (height map). It’s easy to triangulate the grid squares and create a mesh. But if you want to create terrain that might have overhangs or caves, you can’t use a height map. (What is the value of the height map at an overhang? There is no longer a unique value.) To generate terrain that might have these features, you generally need some kind of contouring algorithm.

For 3D modeling in general, I’ve found the dual contouring algorithm to be invaluable. But when I tried to render terrain with dual contouring, I immediately encountered various problems, and it was far from clear that there were even good solutions to these problems. It’s possible that I didn’t spend enough time with it. But since I had already experimented a bit with marching cubes for terrain generation, I decided to pursue that approach. No matter which algorithm you choose (and there are others), there will be certain problems that have to be addressed. But at the time, the problems with marching cubes seemed less severe.

One of the main problems turned out to be levels of detail (LODs). For performance and efficiency reasons, you want to render the nearby geometry at a high resolution and the distant geometry at a progressively lower resolution. If you do this with marching cubes, the first thing you see is that there are gaps in the geometry between the levels of detail. The reason is that if you approach this naively, LODs basically break the marching cubes algorithm in an obvious way. For a long time, I thought there must be some relatively simple trick to overcome this difficulty. Ultimately, I found that the only “trick” is to apply a very logical, methodical approach. The seams (gaps) between the LODs can be “fixed”. The seams can be closed perfectly -- without adding any extraneous geometry. To summarize how this is done in a single sentence: It does involve calculating the precise point at which the surface crosses voxel boundaries at the seam and using only that (or those) point(s) when constructing the marching cubes triangles for those voxels.

Here are two images. One shows marching cubes terrain with the levels of detail regions color-coded. The innermost region is brown, then green, yellow, red and light blue (the lowest resolution, which could extend indefinitely). There are some light blue and white triangles in between that serve debugging purposes (and orange triangles are at the LOD boundaries, likewise for debugging and visualization). The other screenshot shows a closer view of the seam between two LODs. This is always a perfect seam. There are never any gaps, and there is never any “extra” geometry.

[q39engine]

Given a 3D scene, you’ll want some way to easily interact with the rendered objects. So I’ve implemented “picking”. In other words, if I want to select the orange cuboid (or a certain part of it), I simply click on it -- and presto, the application gives some kind of feedback to indicate that I’ve selected that particular object or primitive. Doing this properly requires a good understanding of the 3D rendering process: a good understanding of the basics of projecting a 3D scene onto a 2D surface (the computer display). Here, I’ve clicked on a primitive (a triangle) of the orange cuboid, and it turned green in response.

This is set up as a debugging example so that I can pick any triangle in the orange cuboid. But suppose I want to click on any object in the scene. It’s inefficient to manually check each rendered object directly to find out whether my mouse click is picking that particular object. To allow this sort of functionality efficiently, I need an extra data structure that basically knows the position of each rendered object, so that when I click on the green prism, for example, the application already knows the general region of space where I’m clicking, and knows there’s nothing there but the green prism. This extra structure I need is called a "bounding volume hierarchy" (BVH). And fortunately, that’s a fairly straightforward thing. (Still in the works at the moment.)

[q39engine]

This project is still active, though I didn’t have as much time to work on it as I wanted during the pandemic. The one major piece that’s missing is some way to animate the models, and that’s still on the roadmap somewhere.

I’ve worked a lot on various bug fixes. To mention just a couple of major ones that come to mind: there was an important fix for the shift-reduce parser that reads the modeling script. And another one involved the function that simplifies the voxel octrees that are (sometimes) used to define a visible surface and render models. There are two screenshots here, and the first one is supposed to show the latter fix. This is a set of voxels (cubes) of various sizes. If it hadn’t been simplified to remove voxels that had no useful data in them, all of the voxels would have an edge length of 1. But as you can see, the voxel at the upper right has an edge length as large as 8. Being able simplify these voxel trees like this will be useful however they are ultimately used, even if it’s only to create models for use later.

Another thing I’ve worked on is refinements to the modeling script. The second screenshot shows a simple function being called in this script. It’s passed floating-point arguments that represent the dimensions of a cuboid. The function then creates a box with those dimensions (the long purple box). The function itself is in a different text file, and it’s written in the very same modeling script. This is a simple example to demonstrate and debug the basic functionality.

[q39engine]

Film vs. game

Developers of interactive graphics really have to know what they're doing:

“A game needs to run 60 frames per second, or 120 frames per second, so it needs to compute each frame in 16 milliseconds,” says Tony Tamasi, vice president of technical marketing at graphics card developer Nvidia. “Whereas a typical film frame is pre-rendered, and they can take eight or 12 or 24 hours to render a single frame.”

[q39engine]

If you do lighting calculations in a pixel shader, you may encounter the issue of gamma encoding. Instead of providing my own breakdown of this, I’d rather just link to one or two sites that give a better and more thorough explanation than I could. This one, for example.

Mainly, though not exclusively, this concerns images that you might use as textures in 3D scenes. These image files generally use an encoding scheme that allows them to store more, or more relevant, information than they otherwise would. In certain instances, this image data has to be decoded appropriately when it’s manipulated in algorithms.

I was looking for a simple way to test my understanding of the issues involved. The screenshot is what I came up with. I’m checking that my pixel shader handles the attenuation of a light source correctly, which necessarily implies that gamma encoding or decoding is taken into account. We are told that light attenuates in proportion to the square of the distance from a light source (the intensity is inversely proportional to the square of the distance). So I placed a point light at a distance of 1.414 in front of the checkerboard pattern. If you’re a mathematically inclined person, you probably recognize that 1.414 approximates the square root of 2. What this means is that the white light reflected from a white square on the checkerboard should be only half as bright as the light right at the source. So I would expect not a full white value of RGB (255, 255, 255) but only half of that. However, for the reasons explained in the linked article at Figure 12, the color at the white square, when it leaves my pixel shader, is not RGB (128, 128, 128) but closer to RGB (187, 187, 187). This should indicate that the image data is being manipulated properly by the shader.

[q39engine]

Just a couple more images to convince you that each triangle is being assigned more or less correct texture coordinates at each of the vertices. As you can see from the second image, the square is made up of many triangles, each with three sets of texture coordinates.

[q39engine]

Now a texture can finally be added to a model from the script. In this example, a primitive orange peel texture was applied to the triangle (no normal mapping or anything). A 2D texture can be applied to a 3D surface in various ways, and defining how this should be done isn’t a trivial task, so there will always be an opportunity for more tweaking. But now at least there’s a basic framework for quickly putting various things on the screen with images mapped onto them, and that should make it easy to test whether the gamma handling is right.

[q39engine]

Recently, I made some additions to the modeling script so that scene lights can be changed with a script. Then, I wanted to test whether the rendering environment is handling gamma correctly. For that, it seemed like a good idea to give the script an ability to put actual textures on surfaces (textures from images files, in other words). Basically, for any vertex of a mesh, I had to calculate coordinates that define how a 2D image is mapped to the 3D surface at that point.

The screenshot shows the initial outcome. This is very unusual, because despite the fact that a large amount of new code had to be written, partly involving advanced mathematics, the result basically seems to have turned out right the very first time without any immediate debugging. It’s not complete though. Right now, the code is just painting the triangle with whatever texture happened to be loaded in the graphics pipeline at the moment (the cobblestone). But the texture coordinates appear to be correct.

[q39engine]

To make sure my export routines are working properly, I exported a more sophisticated model. This was very helpful to do, not just for debugging purposes but also for the sake of reviewing exactly how the models are structured. The fish has many surfaces of different types and several colors (materials).

[q39engine]

Now I’m exporting the Wavefront *.mtl file properly (knock on wood), so I can export the yellow block in the *.obj format and import it into Blender with the right color...

[q39engine]

This was kind of a detour or sidetrack. Now I can export models created in my own environment to the Wavefront OBJ format, a popular file format for 3D models. The first image is Blender, of course, where I imported the yellow block as an *.obj file. (There’s a bit more to do to bring the material over properly -- the color or texture. The .obj format uses a separate file to describe materials...)

[q39engine]

Back to the rastertek tutorials for a bit. This shows a sky created with the sky dome technique. When you look at the sky, you’re basically looking at the polygons on the inside of a sphere that’s centered on the viewer at all times.

[q39engine]

This is a work in progress. The fins are still inconsistent, and I didn’t use reference material for the body. Everything is made up of operations on geometric primitives. For example, the dorsal fin is a triangle with a piece of a circle cut from it. The body is the intersection of two spheres, and then that’s scaled slightly on the z axis. The reason I didn’t use reference material for the body is that I currently don’t have the tools to create purely “organic” shapes anyway.

When I was doing this, I noticed that the decimation routines still need some debugging. From a debugging point of view, that’s been the most challenging thing I’ve worked with, because the algorithm is highly recursive -- also because small amounts of error in the positions of vertices can throw the results off. So I often find that I have to use graph paper to plot the positions of points in order to understand what’s going wrong. Not long ago, I found a helpful (free) tool for this online: https://www.desmos.com/calculator

[q39engine]

If I had splines, I could make a better heart ...

[q39engine]

A rainbow is a good way to test adding the 2D surfaces. This highlights some limitations. I had to create each arc separately, which isn’t ideal. That also leads to some visible cracks between them. (But I think higher quality is possible with better modeling techniques, regardless of the programming.)