Raytracing is slow. Incredibly slow. Painfully slow. That’s because you’ve got to check a lot of things to accurately determine what you’re seeing, if it’s in shadow, if it reflects off of something, etc., so it helps quite a bit to be able to get an idea beforehand of where everything is. Enter octtrees.

We’ve got a picture of a model (in this case, the Stanford bunny model). It consists of thousands of tiny triangles that make a surface. Then, imagine a cube surrounding the entire model. If there are two many triangles in that cube, you cut the cube in to eight smaller cubes, and repeat. What this build is a tree where “busy” portions of the space get divided more.

And now for pretty pictures: [caption id=”attachment526” align=”aligncenter” width=”300” caption=”The bunny on its own. There are tricks to smooth it out, but I left it highly triangulated to better represent the idea.”][/caption] [caption id=”attachment527” align=”aligncenter” width=”300” caption=”Bunny with balanced wireframe octtree around it.”][/caption] [caption id=”attachment_528” align=”aligncenter” width=”300” caption=”Profile of the bunny with a very deep octtree.”][/caption]

I’m finishing up the implementation, and then I’ll be using it as part of my octtree as a intersection speedup.