Sign in with
Sign up | Sign in

Octree And Ray Casting

Next-Gen 3D Rendering Technology: Voxel Ray Casting
By

The tree is a frequently-used data structure in computer science because it makes it possible to arrange data hierarchically. Everybody uses tree structures every day without even realizing it, such as when you're working with the files on your computer.

With a file-system tree structure, there’s the root of the hard disk, which contains several “children” (the folders), which in turn contain children of their own (subfolders), and so on until you reach the “leaves” (the files themselves). That example should give you an intuitive idea of one of the advantages of using trees: accessing the parts of a balanced tree is a lot faster than if all the parts were scattered around.

The nodes of a tree can have a different number of branches. For example, when there is a maximum of two branches, we speak of a binary tree, while zero or four branches represent a quaternary tree (quadtree), and finally, zero or eight branches represent an octal tree (octree).

But where do tree structures come into play here? Well, up until now, we’ve used voxels by placing them on a regular grid, which in fact wastes an enormous amount of data by encoding empty space. Octrees enable more efficient use of memory space by using the finest-grained resolution only where it’s necessary. Thinking in three dimensions isn’t the easiest thing in the world, and it’s not easy to represent in an article, so we’ll start by presenting the idea two-dimensionally.

Here’s an approximation of a circle, on a grid with a resolution of 12 x 12. The approximation is very rough because the resolution is too low, but as you can see, a large number of cells are blank and thus useless. If we use a quadtree, here’s what we get:

Building the quadtree is simple. You start with the initial image and subdivide it in two in both directions, which produces four quadrants. When a quadrant is either empty or completely filled, the algorithm stops there. If the quadrant is only partially filled, then the quadrant is subdivided in two again, and so on. The algorithm stops when all the quadrants are homogeneous (that is, uniformly empty or filled) or more traditionally when a given depth is reached (in the example above, we stopped at a tree depth of four, which is a division by 16 in each dimension). As you can see, even with our basic example, the end result is a little more faithful to the initial circle and yet we’ve used less data (97 nodes, or “cells” if you prefer, in this case as opposed to 122 with the regular grid). An octree is the simple extension of this technique into three dimensions.

In practice, the gain in memory space for a given definition is a little less than you might imagine at first. This is because in the case of a regular grid, the position of the voxels is implicit. Conversely, in the case of an octree, each node must maintain a “link” to each of its children. In practice, each node has to have eight pointers in addition to the color and normal of the voxel.

But that’s only a slight disadvantage compared to the many other advantages of octrees. To get a good understanding of the more important contributions of octrees, we first have to describe the way the data structure is displayed. There are several ways to display voxels, but the technique chosen by id Software is ray casting. Here’s a description.

Ray Casting

Like ray tracing, ray casting is based on emitting or “casting” rays for each pixel of the image. But where it differs is that as soon as an intersection is found, the algorithm stops there and casts no secondary rays.

Consequently, ray casting is faster than ray tracing because, as we showed in our earlier article, these secondary rays are what introduce problems related to their memory accesses. Another advantage is that calculating the intersection of rays with voxels is much faster than with triangles. And what’s more, there’s no need to build an additional data structure to speed up these intersection calculations. The octree is both the data (geometry and textures) and the acceleration structure.

Ask a Category Expert

Create a new thread in the Reviews comments forum about this subject

Example: Notebook, Android, SSD hard drive

Display all 47 comments.
This thread is closed for comments
  • 4 Hide
    DjEaZy , October 21, 2009 6:17 AM
    ... the 'matrix' is near... by this rate of progress...
  • 3 Hide
    doomtomb , October 21, 2009 6:23 AM
    This stuff is pretty interesting but a little over my head. The only thing I really care about is when we will start seeing this in our games.
  • 2 Hide
    curnel_D , October 21, 2009 6:53 AM
    This technology sounds a TON more promising than Ray tracing.
  • 2 Hide
    the_krasno , October 21, 2009 7:09 AM
    This is awesome, the people that can really gain something here are amateur filmmakers that can't afford the giant rendering farms big studios have! :) 
  • 0 Hide
    the_krasno , October 21, 2009 7:09 AM
    the_krasnoThis is awesome, the people that can really gain something here are amateur filmmakers that can't afford the giant rendering farms big studios have!

    I meant independent, not amateur. Sorry.
  • 1 Hide
    Anonymous , October 21, 2009 7:10 AM
    personally i like raytracing, except for the performance issues. if you've ever tried doing a little 3d rendering, ray tracing is very good, makes things look very real if done properly. again i know it is slow
  • -2 Hide
    liquidsnake718 , October 21, 2009 7:41 AM
    Very interesting stuff, I do understand how limiting cubes or voxels can be limited in terms of depth and height(same height per distance) as polygons have that advantage where the triangle gives us just that, an angle that can be measured in terms of height and distanve. We have a vanishing point with a triangle as well.....

    Iwonder if they can impliment both polygons and advanced cubes with different sizes for the initial layers creating a more fluid and complexed scenario or landscape........
  • 0 Hide
    JonathanDeane , October 21, 2009 7:59 AM
    Interesting but voxels will have some extreme performance and space constraint hurdles to overcome before they become the main rendering of any game. I just downloaded a small demo http://www.advsys.net/ken/voxlap/voxlap03.htm its a little over 500K for the whole works but after you hit the genall batch file (it speeds up loading) the thing occupies about 120MB's of space for this simple game. Something like Quake 3 would have been a multi DVD file...
  • -2 Hide
    mlopinto2k1 , October 21, 2009 10:40 AM
    Pretty cool stuff.
  • -2 Hide
    amdfangirl , October 21, 2009 11:08 AM
    Better put off upgrading my computer... again :p 
  • -2 Hide
    Anonymous , October 21, 2009 11:33 AM
    In the regular resolution 12x12 you get 144 cells instead of 122 as stated in the text
  • -5 Hide
    fatedtodie , October 21, 2009 11:59 AM
    Based on John Carmack's record if he says it is bad... you should do it, seeing as anyone with a memory will recall the time he said multi-core was a waste of time and we should continue the Ghz race (even those the Ghz race achieved Moore's Law).

    John Carmack is a dinosaur and will try any new technology if paid enough (see his changing his mind on multi-core to "help" on the xbox 360).

    Please get an expert that isn't a moron.
  • -3 Hide
    bin1127 , October 21, 2009 12:43 PM
    “pixel” is a fusion of the terms “picture” and “element,”, learned something new.

    But i wouldn't want destructible walls. How am i going to camp when all the walls are gone?
  • -4 Hide
    manwell999 , October 21, 2009 1:11 PM
    Since when does a tree have attached children?
    It's unfortunate that the example of MRI scan example was used. Medical software must avoid the habit of naming branches in tree structures as children, lest an error message is displayed accidentally to a patient such as "Out of memory allocating children, child process aborted." Which would be a lawsuit if scanning a pregnant female. But this bad coding practice is quite common.
  • -8 Hide
    zak_mckraken , October 21, 2009 1:43 PM
    @manwell999 : lawl
  • 1 Hide
    JimmiG , October 21, 2009 3:37 PM
    fatedtodieanyone with a memory will recall the time he said multi-core was a waste of time and we should continue the Ghz race


    Well, back in the day, everyone was talking about higher GHz as the solution to everything. Even Intel did:
    http://www.theinquirer.net/inquirer/news/1026758/desktop-chips-hit-15ghz-2010
    "LUCKY PUNTERS WILL BE ABLE TO BUY 15GHZ INTEL CHIPS, containing a billion transistors, by the end of the decade, said Pat Gelsinger, Intel veep and CTO in his keynote at the Intel Developer Forum in Tokyo today. Gelsinger also predicted that PDAs will hit 5GHz in the same timeframe. It's unlikely the chips will use the existing Pentium 4 architecture which is reckoned to only be good up to around 10GHz. "

    Then Intel hit the thermal/power wall some time in 2004-2005, before even making it to 4 GHz. This of course signaled the end of such optimism. If that hadn't happened, higher clock speeds would still have been the best way to make faster CPUs. That makes all code run faster, not just code that is carefully optimized to extract parallelism. Multi-core CPUs for desktops and laptops initially came around not because it was the best choice for improving performance, but because it was not possible to further increase clock speed.
  • -1 Hide
    precariousgray , October 21, 2009 3:41 PM
    Here's what I saw.

    That example should give you an intuitive idea of one of the advantages of using trees.
  • -1 Hide
    kikireeki , October 21, 2009 5:28 PM
    What happened to Normal Mapping?
  • -1 Hide
    JonathanDeane , October 21, 2009 5:54 PM
    kikireekiWhat happened to Normal Mapping?


    Hmmm maybe using a skin of voxels on top of a polygon mesh would be good for facial animation stuff, that sounds interesting to me or a mesh of polygons on top of the voxels for deformation purposes. Ok my mind is officially fried you may all proceed to LOL at me :) 
  • 0 Hide
    spiketheaardvark , October 21, 2009 6:43 PM
    I wish the article discussed how such a system would handle transparent objects and refracted light sources , such as an image of a glass of water.
Display more comments