Editing Scene graph (section)

==Scene graphs and spatial partitioning==
An effective way of combining [[Space partitioning|spatial partitioning]] and scene graphs is by creating a scene leaf node that contains the spatial partitioning data.{{clarify|date=December 2014}} This can increase computational efficiency of rendering.

Spatial data is usually static and generally contains non-moving scene data in some partitioned form.{{clarify|date=December 2014}} Some systems may have the systems and their rendering separately. This is fine and there are no real advantages to either method. In particular, it is bad to have the scene graph contained within the spatial partitioning system, as the scene graph is better thought of as the grander system to the spatial partitioning.{{POV-inline|date=December 2014}}

Very large drawings, or scene graphs that are generated solely at [[Run time (program lifecycle phase)|runtime]] (as happens in [[Ray tracing (graphics)|ray tracing]] [[Scanline rendering|rendering]] programs), require defining of group nodes in a more automated fashion. A raytracer, for example, will take a scene description of a [[dimension|3D]] model and build an internal representation that breaks up its individual parts into bounding boxes (also called bounding slabs). These boxes are grouped hierarchically so that ray intersection tests (as part of visibility determination) can be efficiently computed. A group box that does not intersect an eye ray, for example, can entirely skip testing any of its members.

A similar efficiency holds in 2D applications as well. If the user has magnified a document so that only part of it is visible on his computer screen, and then scrolls in it, it is useful to use a bounding box (or in this case, a bounding rectangle scheme) to quickly determine which scene graph elements are visible and thus actually need to be drawn.

Depending on the particulars of the application's drawing performance, a large part of the scene graph's design can be impacted by rendering efficiency considerations. In 3D video games such as [[Quake computer game|Quake]], [[binary space partitioning]] (BSP) trees are heavily favored to minimize visibility tests. BSP trees, however, take a very long time to compute from design scene graphs, and must be recomputed if the design scene graph changes, so the levels tend to remain static, and dynamic characters aren't generally considered in the spatial partitioning scheme.

Scene graphs for dense regular objects such as [[heightfield]]s and polygon meshes tend to employ [[quadtree]]s and [[octree]]s, which are specialized variants of a 3D bounding box hierarchy. Since a heightfield occupies a box volume itself, recursively subdividing this box into eight subboxes (hence the 'oct' in octree) until individual heightfield elements are reached is efficient and natural. A quadtree is simply a 2D octree.