StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There are several variations, but when building an octree, one approach is this:</p> <ol> <li>Start with one node (ie. a cube) encompassing your entire scene or object being partitioned.</li> <li>For each element in your scene/object (eg. a mesh, or a poly, or whatever granularity you're working to): <ol> <li>Check if that element fits completely inside the node.</li> <li>If yes, subdivide the node into eight children, then recursively do Step 2 for each child.</li> <li>If no, then continue to the next node until there are no nodes left.</li> <li>Add the element to the smallest node that can contain it.</li> </ol></li> </ol> <p>It's also common to stop recursion based on some heuristic, like if the size of the nodes or the number of elements within the node is smaller than a certain threshold.</p> <p>See <a href="http://www.flipcode.com/archives/Introduction_To_Octrees.shtml" rel="nofollow noreferrer">this Flipcode tutorial</a> for some more details about building the octree.</p> <p>Once you have the octree, there are several approaches you can take to render it. The basic idea is that if you can't "see" a node, then you can't see its children either, so everything inside that node (and its children) don't need to be rendered.</p> <p>Frustum culling is easy to implement, and does the "can you see it?" test using your view projection's frustum. <a href="http://www.gamedev.net/reference/programming/features/culling/" rel="nofollow noreferrer">Gamedev.net has an article</a> discussing frustum culling and some other approaches.</p> <p>You can also go further and implement occlusion culling after frustum culling, which will let you skip rendering any nodes which are covered up by nodes in front of them, using the z-buffer to determine if a node is hidden. This involves being able to traverse your octree nodes from closest to furthest. This technique is discussed in <a href="http://www.gamasutra.com/features/19991109/moller_haines_01.htm" rel="nofollow noreferrer">this Gamasutra article</a>. </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