Pixelate:Issue 14/Voxel Landscape Renderization

From Allegro Wiki

Scripting
Original author:	Ñuño Martínez (aka Niuno)
Website:
zip:	UOVLR.zip

Contents 1 Voxel Landscape Renderization 2 What's a landscape? 3 What are voxels? 4 3D concepts. 5 The algorithm 6 Improvements and optimizations 7 Conclusion

Voxel Landscape Renderization

So, you want to write your own Landscape Renderer, don't you? Then, you come to the right place! Here, I'll explain how a Voxel Landscape Renderer works and how to write a simple one by yourself.

Open your eyes, you'll need them.

What's a landscape?

See: Lands-cape. That is, the visible part of the land surface. That was easy, wasn't it?

But how can be the landscape data stored?

A landscape has two main characteristics: a height and a color.

To store the height, we can divide the landscape into a lot of squares or cells and store the average height of each cell into a 2D array. This is also known as height-map. One way used quite often to store an height-map is to use a bitmap, i.e. an 8 bit bitmap. This way, the color 0 would be the lowest level and 255 the highest one. Using a bitmap to store the height-map allows to use graphic tools and programs to create it.

An 8 bit bitmap. Black is the lowest cote, white is the highest.

We can use another bitmap to store the color-map (or texture) of our landscape.

An 8 bit bitmap.

Hum... It wasn't too hard...

What are voxels?

That's a good question.

The word voxel cames from the expression volume element, in the same way than pixel comes from picture element. So, a voxel is similar than a pixel but in 3D. That is, a pixel is a small 2D rectangle to build 2D pictures and a voxel is a small 3D box to build 3D objects. As a pixel, a voxel can be transparent or solid, with color, and when more voxels you have, the more precise the object will be.

Q: Ok, I understood it. But when I zoom in my Quake game I don't see those small boxes!

A: That's because voxels aren't the only way to define 3D objects, as pixels aren't the only way to define 2D pictures. If you use 'Corel Draw' you see that the pictures are defined with lines (vectors) and curves, and if you zoom in the pictures you don't see any pixel. On 3D objects you can use points (vectors), even curves, to define them, so you can zoom in without see any voxel.

There are a lot of games that uses voxels to define objects or worlds. Blood, Delta Force and some Electronic Arts' simulators (as The M1Abrahams or Apache ones) are few examples.

You can learn more about voxels at [ http://www.advsys.net/ken/voxlap.htm Ken Silverman's Voxlap page]. Ken was the guy who wrote the engine used in Duke Nukem 3D, Blood, Shadow Warrior, Redneck Rampage and some others games.

3D concepts.

Before to explain how to render a voxel landscape, you should know and understand some 3D concepts.

The 3D concepts used in this tutorial aren't hard, but I don't go to waste my time explaining them. So, before to continue reading, you should learn a bit about 3D and about Allegro's 3D structs and routines. There are some tutorials at the internet, but I'll recommend the Steel's Basic 3D Tutorial and Amarilion's Sin & Cos: The Programmer's Pals! article at Pixelate #5. This last doesn't explains 3D concepts but has some information I'll use in the next demo, and also would give you some interesting ideas around the concepts.

Once you read that tutorials, you're prepared to understand this tutorial.

The algorithm

Now, we want to draw the landscape on to the screen. A first solution would be to go through all pixels of the height-map, get his xyz coordinates, apply the transformation matrix, project it to the screen and plot the voxel. It is feasible, isn't it?

Well, the first problem is that we need to sort the voxels because the nearest ones should occlude the farest. By the way, if you have read the Amarilion's article, you should know that there isn't necessary to go through all the voxels because only a part of them are visible. How we can do that? Fortunately, prior developers found a way to do both sort and know visible voxels in a simple step. The technique named Ray Cast.

Before to explain how the Ray Cast work I have a question for yoy: Do you know how a photograph camera works? I'm sure you do:

The objective gets the light rays reflected by the objects and guide them to the film, where the image is taked.

The Ray Cast algorithm just do the inverse than the photograph camera. That is, it gets a light ray and follows it backwards until it finds and object that collides with it. This technique is similar than the one used by Pixar^tm on his animations.

Q: Hey! Ho! Wait a minute. That's too complex for me.

A: No, it shouldn't be. See the next picture, that is a piece of the complete texture bitmap shown above:

Here, the blue lines means the rays we're casting. If you have read the 'Sin & Cos' article, as I suggested, you know how we can go along each ray and get the voxels coordinates. If you can't, please, re-read it again and pay attention on the polar-Cartesian coordinate systems.

Ok then. If we cast a ray each column of the screen, the render routine would be something like:

  FOR each column DO
    calculate increments of the ray (ix and iy)
    SET ray position at view point position (px an py)
    SET max_height = 0
    WHILE px and py are inside the height-map DO
      project voxel height to the screen (current_height)
      IF current_height > max_height THEN
        draw vertical span from current_height to max_height
        SET max_height = current_height
      END IF
      increments px and py using ix and iy
    END WHILE
  END FOR

I think it's pretty easy to understand, isn't it?

And here you have my [UOVLR.zip Voxel Landscape demo] sources. It uses the Allegro Game Library. And here you have a screenshot if you want to see what you'll get:

Improvements and optimizations

The example is simple and a bit slow. We can do it faster and more interesting adding some improvements and optimizing some parts. Let's start with improvements:

=== Tilemap ===

That's easy. Since both heightmap and texturemap are bitmaps, you can use the tilemap thechinques to create maps and render them. This way you can create bigger and more interesting worlds with less memory. You only must change the GET_HEIGHT macro and you can use the same loop.

=== Fog ===

That's easy too. Since you have the voxel distance stored at dt, you can use this value to calculate the fog color and blend it with the voxel color. If you don't know how to calculate a real fog, you can use an array to store the fog colors. Then, shift down the dz variable (e.g.: ((int)(dz)>>8)) and use it as index on the array, blending with the voxel colors using the OR operator (that is, ||). Note: 8 bit mode is hard to create soft fog efects easily. True color modes are better for this.

=== Sprites ===

Just now, our engine renders empty worlds. To fill it with objects and characters, we need to render sprites. I didn't implement this issue, but it shouldn't be too hard. Just now I'm working on it. When I finish it I'll write a new tutorial explaining it that will be published on this e-zine.

Now, I'll explain some ways to render landscapes faster:

=== Limit the ray length ===

At moment, the example renders all the heightmap. You can add a new condition on the inner loop and limit the ray length.

=== Render half of the columns ===

The idea is that each frame render only the pair or the odd columns, but draw a vertical span twice wider. It will be less accurate but near to twice faster, though.

=== Increase ray steps ===

After increase the dz variable, at the end of the inner loop, you can include a line like this: if ((dz%150)==0) { iy *= 2; iz *= 2;}. This whay, it will rend all near voxels, but not all the far ones. This would create gaps but speed will increase.

=== Partial ray length limitation ===

This is a combination of the two first optimizations. The idea is to limit the rays alternatively. This way:

As you can see, the even rays are shorter than the odd ones. This way it renders only a half of the farest voxels. To avoid gaps you can draw the odd columns twice wider.

There are more optimization tips, but there are, mostly, general optimization so I don't tell them here now.

Conclusion

I think you know everithing you need to write your own voxel engine. Even to render sprites (Don't worry if you haven't an idea. Anybody will write a tutorial about this). It was easy, wasn't it?

If you have any question, write it on the Pixelate forums. I log in quite ofte, so I (or somebody else) will answer to you.

Happy codding.