Databases
StackOverflow2013
Postsdbo
PORay - Octree intersection algorithms
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORay - Octree intersection algorithms
    text
    copied!<p>I'm looking for a good ray-octree intersection algorithm, which gives me the leafs the ray passes through in an iterative way. I'm planning on implementing it on the CPU, since I do not want to dive into CUDA just yet :)</p> <p>At the moment, my Voxel raycaster just does 3D DDA (Amanatides/Woo version) on a non-hierarchic array of XxYxZ voxels. You can imagine that this is pretty costly when there's a lot of empty space, as demonstrated in the following picture (brighter red = more work :) ):</p> <p><img src="https://i.stack.imgur.com/icGL9.png" alt="Workload for dumb 3D DDA - red = more work"></p> <p>I've already figured out that there are two kinds of algorithms for this task: <strong>bottom-up</strong>, which works from the leafs back upwards, and <strong>top-down</strong>, which is basicly depth-first search.</p> <p>I've already found Revelles' algorithm from 2000, called <em><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.987" rel="noreferrer">An efficient parametric algorithm for octree traversal</a></em>, which looks interesting, but is quite old. This is a top-down algorithm.</p> <p>The most popular bottom-up approach seems to be <em>K. Sung, A DDA Octree Traversal Algorithm for Ray Tracing, Eurographics'91, North Holland-Elsevier, ISBN 0444 89096 3, p. 73-85.</em> Problem is that most DDA Octree traversal algorithms expect the octree to be of equal depth, which I do not want - empty subtrees should just be a null pointer or something similar.</p> <p>In the more recent literature about Sparse Voxel Octrees I've managed to read through, (most notably <a href="http://code.google.com/p/efficient-sparse-voxel-octrees/" rel="noreferrer">Laine's work on SVO's</a>, they all seem to be based on some kind of GPU-implemented version of DDA (Amanatides/Woo style).</p> <p>Now, here's my question: does anybody have any experience implementing a basic, no-frills ray-octree intersection algorithm? What would you recommend?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload