Trees:

(very brief) Trees are used to sub-divide the world into smaller parts. a BSP tree (binary space parition tree) uses planes to divide up the world. Octrees use boxes. Quadtrees use squares. They can also be used to speed up frustum culling...

Frustum Culling

the process of taking an object and seeing if it falls into the field of view of the camera. Most game objects are surrounded by a box which you check against the frustum (the viewable area). If it's partially or completely inside then the object should be drawn. If not, then there's no need to send it to the graphics card. Objects need to be chekced each frame.

Trees help frustum culling because trees can also contain objects. If an entire node ("space") isn't visible then nothing from that node should be drawn. If it is completely inside the frustum then EVERYTHING should be drawn. If it's partially inside the frustum, then all the objects the node contains need to be checked individually.

Nodes can also contain other nodes, which can contain more nodes. The actual content of a node is called a leaf.


Google: bsp tree, octree, kdtree, frustum culling

I would point you to gametutorials.com for frustum culling, but they seemed to have sold out and now want $5 for one of the most common techniques used in gamedev.

Oh, if you really want to get into it, google "scene graph management" (the collective term for managing objects in the world).


You don't need to cull triangles manually - ever. Just make sure Direct3D is only drawing the front-facing triangles (don't know how - I'm a gl guy) and the zbuffer will take care of the rest.

np. We all have to tackle it at some stage or another (and sadly we never stop tackling it from then on!)

http://www.devmaster.net/articles/rendering_trees/ just appeared. It's refering to 2D games, but it had an excellent description of trees, nodes and children.

To enable backface culling, you can do:
pDevice->SetRenderState( D3DRS_CULLMODE, D3DCULL_CCW );

Another thing to make sure is to use lots of batching... So, instead of making 1000 drawprimitive calls, each one with 10 polygons, make 10 drawprimitive calls with 1000 polys. (Or whatever). Also, try not to change render states too often, since I guess this screws with the pipelined nature of how video cards work.

Anyways, to answer your question:

Quote:is (frustum culling) alone enough of an optimization (again, we're not talking something that's going to be shooting out massive amounts polygons per frame) in and of itself, or will (many) other optimizations need to be implimented as well?

Short answer: yes :)

Long answer: If your objective is to make a basic game from start to finish and you don't want to waste lots of time, then frustum culling should be enough. However, if you're serious about learning graphics programming, or if you want your game to be able to handle lots of polys or heavy use of shaders, then it's definitely worth it to spend some time looking into optimizations.

Hope that helps,

roos

Occlusion culling is an optimization when frustum culling is not enough. It consists of not drawing objects that are hidden by another objects. Much is described here: http://www.hybrid.fi/main/academic/aila/TIMOAILA_thesis.pdf.

Np... Good luck man :) I think if you're shooting for hi quality, it's definitely worth spending time w/ optimization. Even if modern video cards can push a ridiculous number of polys, optimization will really pay off when you start integrating effects like per-pixel lighting and shadows. Some techniques also require you to render the scene more than once from different viewpoints (e.g. dynamic cubemap), so that would just be downright painful w/o good optimization.

Be warned though, occusion culling tend to be more hassle then it's worth and can quite often slow the game down if implemented poorly.