Handling polygons in multiple nodes of an Octree

Question

I'm building a 3d software renderer for grins to learn the math and rendering concepts. I've implemented the basic drawing of polygons with some basic optimizations like back face culling and frustum culling. Its going pretty well for it being java and all (15k polygons at 30fps at 1900x1080) but I want to implement an Octree to reduce the amount of overdraw happening and correctly sort the polygons for drawing without using a z-buffer for the entire screen.

I get the basic ideas of how to partition the world and how to traverse the tree from front to back to order the polygons correctly, but I'm a bit confused on how to handle polygons that are in more than one node of the Octree.

Some example cases I'm concerned about are: A floor of 2 big polygons that intersect all of the nodes at the bottom of the Octree A polygon that extends across a node boundary I figure I should split the polygon at the node boundaries, but then do I need to check on each frame for objects that have moved in the world that need recalculation in the Octree.

Answer 1

Actually, I don't think that octrees are the appropriate data structures for what you are trying to do, at least not if you are dealing with arbitrary polygons (which I assume you are). For sorting polygons (at least static ones), you may want to look into BSP (Binary Space Partitioning) trees instead, see

http://www.gamers.org/dhs/helpdocs/bsp_faq.html

They are vaguely similar to octrees, but space is only split into two parts at each node, and the planes are not required to be axis aligned. They are fairly easy to build for an arbitrary scene (consisting of planar polygons), and you get correct front to back ordering of polygons fairly efficiently (though you may need to split a lot of polygons to achieve this).

AFAIK neither octrees nor BSP's can help you reduce overdraw directly, but a correct front to back ordering of polygons will certainly simplify the problem. If you are doing software rendering, one fairly simple possibility is the so-called "coverage buffer". See the article "The Coverage Buffer (C-buffer)" by Jacco Bikker on

http://www.flipcode.com/archives/articles.shtml

for an explanation. On that same site, you'll also find the article "Fine Occlusion Culling Algorithms", which describes several alternatives.

There is also Michael Abrash's "Graphics Programming Black book" (do a google search; presently, I'm not allowed to include more than 2 hyperlinks in a single post), which describes (among a lot of other things) how they dealt with this problem in Quake.

Approaches that works well both in software and hardware are beam trees (described in the flipcode.com article on "Fine occlusion culling algorithms") and portal rendering; the latter will also solve the sorting problem, if you only use convex cells. It will also handle dynamic scenes at no additional cost. A good introduction is the article series "Building a 3D Portal Engine" by Jacco Bikker, (the most relevant parts would be issue 9 and 11), which can also be found in the flipcode archives (see link above).