July 26, 2009

Octree in DirectX

Posted in Computer Graphics tagged , , , , , , , , , , , , , at 11:27 am by sagito

Hello everyone! Back to some news from the Conspiracy… 😉 This time I’m implementing a feature that is quite new for me. An octree! Ok… Wait… What’s an octree? Well, an octree is basically a technique for dividing the drawing space. You start with a huge cube which surrounds the entire scene. If there is something inside it, then you subdivide that cube in eight smaller and identical cubes. Then, for each of these cubes, we must check if there is something inside them, if there is we subdivide them again, and so on…

Ok, now… Why is this so useful? Lets consider rendering… It is not necessary to render everything that we don’t see (because its behind us for example). This seems quite logic to me. But, the DirectX backface culling and occlusion system should be capable of doing this, right? Yes and no! In a matter of fact it really does not render the objects that we can’t see… However, it sends them to the graphics pipeline, executes a draw and only checks if they are visible afterwards. Only at this moment it decides if it really sent to the screen or not. With an octree, we are actually able to avoid such a thing, because we just don’t sent the objects which belong to an octant that we cannot see to the pipeline, avoiding some unwanted overhead.

Another example is the picking! Why try to perform picking on something that we cannot select? It is a heavy operation and we want to be able to ignore such operations if they are unnecessary!

However, there is a small problem, at least, with my implementation. I can reach 6 iterations of depth in an admissible time… Seems that these are few iterations, and maybe they really are… But if we think it through, each subdivision creates 8 space divisions. So, for 6 iterations, that stands for 8^6 = 262144 divisions (maximum). After doing the maths, this seems quite acceptable now… 😛

So, standby for new updates, as they are coming fast! 😀


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

%d bloggers like this: