Getting There Quickly

World Geometry

Step 1

As we've outlined in our earlier post on abstraction, these are the options that we'll be choosing to implement first, for renderer and world geometry respectively:

• Low-resolution software rendering,
• A simple if-then-else function to determine the contents of the world geometry, e.g. if (position in [0,0,0],[10,10,10]) or (position in [-30, -5, -30],[30, 2, 30]) then [this is rock], else if (y<=0) then [this is sea], else [this is air].

This allows us to develop player and camera movement, and basic interaction with the world geometry.

Step 2

From there, we'll progress to higher resolution rendering (only where it maintains playable rates, and perhaps using some optimizations to achieve higher resolutions without doing too much work), and a regular array of cubes for the world geometry. Those optimizations can take on a life of their own, our favourite methods being 'local ray cacheing', 'progressive rendering', and picture processing operations (borrowed from video encoding) that avoids re-casting predictable regions for a few frames. We'll try to remain focused!

Steps 3, 4

That gives us some options for terrain modification in step 3, which is a single octtree, along with optimizations that minimize memory usage (more on that later). Step 4 gives us the infinite world using side-links to other nodes, along with the memory management utilities that enable the disposal and paging of world geometry.

Rendering

As we hinted before, there are many possible ways to render the scene. We'll concentrate our efforts on raycasting and polygonal rendering, and the hybrid methods anywhere in between. Our strategy for rendering will be to evolve through several stages, each stage being more polished than the previous stage:

1. Low-resolution software renderer.
2. Simple triangle geometry.
3. Optimized triangle geometry.
4. Optimized software renderer.

Hardware Rendering or Software Rendering?

We believe that writing a full software-driven renderer is not likely to result in a playable frame-rate; indeed to do so would need a lot of low-level optimisations that (frankly) we don't have time to implement. We'd rather get the other elements of the game working, and perhaps return to writing and heavily optimizing the rendering engine later.

Aiming for a Hybrid Approach

Our hybrid approach will be to analyse the world geometry for visible blocks using ray-casting (also face culling, frustrum culling, and outsideness testing), convert those to triangle geometry, and render the triangles.

We think efficiencies can be gained by limiting the amount of ray-casting that we do, using a heirarchical scanning technique. We start by scanning a few points, which correspond to a few widely-spaced point on a grid placed on the screen (the projection plane of the camera's frustrum). Say our screen has 320x200 pixels (that's side-screen, 16:10); we might scan every 16th pixel. This image by itself won't look good, but we can use its data to smartly render the remaining pixels. We do this by interpreting the rays from the coarse grid to decide whether to omit the other rays.

Here's an example: if we look at four rays, cast from a point, through viewing plane in a square formation, we can calculate, for any given distance from the origination point, the largest size of cube that can be enclosed by those four rays, without any of the rays passing through the cube, i.e. all four rays pass around the cube but not through it. What we're doing here is calculating the resolvable real-world resolution of a raycasting grid. It tells us that, for example, the coarse grid will start to miss cubes at a distance of 3 metres from the camera. If we're using Octtrees, then we can obtain a 'level of detail' that a grid can resolve at any given distance, and use that to limit the work that is needed by each ray-casting operation.

This becomes exploitable when a square of four sample points from our coarse grid all hit distant scenery: it tells us that between the camera origin and the 'resolvable distance', there will be no obstructions, because they are big enough to get in the way of at least one of the four rays that we cast using the coarse grid, and we exploit this by not needing to test anything in this span, choosing instead to start the rays from our fine-grid at the resolvable distance instead of starting them from the origin.

There are many variations on this, which can exploit different situations, which can tell us: when we'll hit a cube, when we're likely to hit a cube, and when we're likely not to hit a cube. The most useful optimization will help us tune the level of detail according to the placement of geometry found in nearby rays.

Prototyping

Perhaps the fastest route to prototyping is to write a basic software renderer. We said at the beginning that this wouldn't be practical, but I think it will be useful to have a low-resolution renderer, because it is simpler to write than an optimized triangle pipeline.

The first rendering step is to throw some rays out from the camera position into the scene, and put coloured pixels on the screen corresponding to what those rays find. We choose which materials on the world to regard as transparent, and only return a colour when we hit something that is not transparent. If the ray travels straight through all available data without hitting anything, or reaches a distance that we regard as 'too far to display', then we return a sea or sky colour depending on the direction we're looking in.