This is maybe the easiest way to manage the objects in a scene and is also often a very good choice. It’s a simple uniform grid with equally sized cells/buckets/patches (or whatever you want to call it). When rendering, all that is needed for culling is to check the view frustum against these cells to determine which ones are visible. This grid can most of the time be in only 2D but can of course in special cases be 3D if necessary. This spatial data structure works well with both static and dynamic objects.
A scene graph is a tree structure that tries to structure the objects in a scene accordingly to transformations, textures, materials and much more instead of just the geometrical representation of objects like for example a quadtree does. All games does contain a scene graph in some way, in the most simple form it could just be a root node and all other rendered objects as child nodes to the root node.
Here’s a list of useful links concerning scene graphs. Most links are borrowed from a post on gamedev.net but copied to this post so that I could remove broken links and include new ones.
- Wikipedia Entry for Scene Graphs
- Game Engine Architecture – Book Except (Scene Graphs)
- Understanding and Implementing Scene Graphs
- Scene graph & moving objects
- Terrain and scene graphs
- Scenegraph Management
- Scenegraphs: Past, Present and Future
- Game Object Structure: Scene Graphs
- Game Object Structure: Scene Graphs Revisited
- The GDC 2003 Game Object Structure Roundtable (scene graph section)
- Scene Graph/Renderer interface
- Scene Graph. DAG or Tree With Mesh List?
- Design Patterns used in the OpenSceneGraph
- API-agnostic vertex storage and conversion to API-usable storage
- Some UML class diagrams
- Nvidia implementation of a scene graph dedicated for good shader support
- SG integration
- Material/Shader implmentation
- Shader system implementation
- Shader Engine Design Decisions
- Optimized View Frustum Culling Algorithms for Bounding Boxes
- Optimized View Frustum Culling Algorithms
- Efficient View Frustum Culling
Most of this list was copied from the following gamedev.net forum thread.
Nearly the same as a Octree but instead of dividing the space in cuboids in 3D it’s rectangles in 2D space. This is useful for rendering terrain and you want to cull a lot of the terrain fast.
A visual demonstration of a quadtree used for fast collision detection:
Introduction to quadtrees and sample code:
More info about quadtrees, including source:
Octrees are one of many ways to divide the space into smaller volumes structured in a tree. This is useful for culling objects while rendering or for finding collisions between objects. First cover the entire space that is of important into one big cuboid. Then the dividing algorithm for the tree goes as follows:
- First select the maximum number of objects in each cuboid. This determines how deep the tree will go.
- For each cuboid that contains more objects than the maximum allowed, split it into eight (oct = eight) new cuboids with the same volume and dimensions. Repeat this step until all cuboids fulfill the requirement.
The procedure looks like the following:
More information about octrees.
Source of the image:
A little description of octrees.