Z Ordering and the Depth Problem

Since the post about particles generated a bit of comments regarding their perceived depth on our twitters (and I dearly thank all who took their time to talk with us, you are great!) I thought it would be nice to explain a few things about how things work in Wizards’ Duel.

But first of all: Wizards’ Duel will definitely have Z-Ordering!

These particles have a Z-Order: they change their "depth" to go around Exekiel

These particles have a Z-Order: they change their “depth” to fly around Exekiel

This post will be a bit more technical than the usual so let’s get started.

Premise

As you may know, Z-Ordering is the practice of sorting things drawn by the computer so that things in front cover the things on the back. For a human this is natural common sense: nearer objects occlude objects farther away, it is what we call line of sight and it happens because light travels in a line, at least in non relativistic conditions.

Computers on the other hand have a bit of a problem with “human things” like emotions and, perhaps surprisingly, sorting things. Since the dawn of Computer Science, sorting algorithms have been studied to find the best and most efficient among them (I will not go trough all the possibilities here, if you are interested the Wikipedia page is a good starting point to get an idea of the problem and compare several algorithms and their performances). Keep this in mind, it will come useful in a bit.

Solutions to the Z-Ordering problem in Computer Graphics

In computer graphics you have mainly two ways to draw a scene with the correct order, one is to use a Z-Buffer and the other is to sort the objects to be drawn from the furthest to the closest, so that you are sure that the closest ones are drawn-over the ones in the background (this is sometimes called the Painter’s Algorithm).

Z-Buffer is a very fast and proven in use technique but it applies to 3D Accelerated graphics. The concept is that you draw in any order but the graphic card stores also the depth of the drawn pixels in a special buffer, the Z Buffer or Depth Buffer, that acts a bit like an heightmap. Whenever a pixel is drawn the graphic card first checks the Z Buffer and if the new pixel is less deep (thus it is nearer than the last one drawn) it will be drawn and the Z Buffer will be updated with the new depth, otherwise the pixel will be skipped.

While it has other problems, chiefly with transparent pixels, this technique is fast and probably good enough alone for WD. Problem is that WD is completely 2D and the graphical library that we are using, SFML, does not support giving a Z value to the drawn objects, thus I needed to go the another route.

Wizards’ Duel’s Solution

Example of level depths in the worldview

The mountains stand on different layers. At the top of the walk cycle Exekiel is in front of them, at the bottom his feet are covered by the tops of the mountains in the foreground.

Wizards’ Duel world is drawn in layers, as I discussed very briefly in another post. Layers are drawn in a predetermined order so that the background is always drawn first and the foreground is always drawn last.

However WD’s graphics is what is called 2.5D, that is, it is viewed from an angle that gives the impression of depth, and objects on the same layer will have to overlap in several occasions.

This finally explains why I have begun by speaking about sorting. Every object will have a static depth, let’s call it Z-Index, and a Drawing Order that is calculated according to the position of the object’s bounding box along the Y axis (that is: whose “feet” are closer to the top of the screen).

Each layer will keep a list of objects and these will be sorted, each frame, according to both Z-Index and Drawing Order and then drawn using the Painter’s Algorithm.

There is a thing to be wary tough. Since sorting is not actually a very fast procedure it is better to keep the mathematical operations behind it at a minimum. To achieve this the first obvious way is to the treat the whole particle system as a single object and forget about sorting all the individual particles. Another possibility, that I will explore only if things start to slow down, according to the YAGNI principle, is to keep a Dirty Flag on each layer and only do the sorting when there is a change to an object’s Z-Index or Y-Coordinate.

That just about sums it all up. I dearly hope that being a bit more technical has not bored some of our readers. What do you think about it?

Thanks for reading.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s