Olimi

Introduction#

The content of this column is from the online course "Fundamentals of 3D Game Engine Architecture and Design" on XuetangX. I have converted it into a text and image version (I personally prefer text tutorials as they are much faster to read), making it easier to reference.
Original course link: Fundamentals of 3D Game Engine Architecture and Design.

Scene Management#

Overview of Scene Management and BVH#

In order to improve the efficiency of scene management, the logical organization structure of scene objects is usually a tree-like structure. For example:

The architecture of game scene organization includes:

• Scene graph, used for managing dynamic scenes.

• Octree, used for managing large outdoor scenes.

• Binary Space Partitioning (BSP) tree, used for managing indoor scenes.

Bounding Volume Hierarchies (BVH) is a hierarchical structure of bounding volumes used to quickly determine the geometric relationship between scene objects. BVH calculates bounding volumes for each object using the BVH method. BVH is a tree-like structure with nodes that contain bounding volume information. For example:

The types of bounding volumes include: bounding spheres, axis-aligned bounding boxes, oriented bounding boxes, and k-discrete oriented polytopes. The computational complexity increases gradually. The calculation methods are shown in the following figures:

Scene Organization Structure: Scene Tree, Octree, and BSP Tree#

Scene Tree#

• Represents objects in the scene using a hierarchical structure.

• Operations on higher-level objects affect all objects in their subtrees.

• Directed acyclic graph.

The abstract description of the scene graph is as follows:

Octree#

Divides space into eight equal parts. If a part is filled with scene content or if a part has no scene content, it is no longer divided. Otherwise, it continues to be divided until the termination condition is met.

Organization of Octree:

The disadvantage is that the pointer space of leaf nodes is empty, resulting in a lot of wasted space. One improvement is:

Linear octree saves storage space and makes scene operations very simple.

Octree Splitting Algorithm:

The geometric relationship between the splitting cube and the geometric bounding volume can be determined by calculating their containment relationship. The recursive splitting algorithm is very concise and fast.

The idea of octree construction determines the order of scene traversal when the camera position and direction are determined. The octree traversal can be done from back to front or from front to back. The former is also known as the painter's algorithm, which does not require calculating occlusion relationships but needs to render each face, resulting in low efficiency. The latter renders the nearest face first, and then determines the final rendering result of pixels through occlusion relationships or depth buffer information. This method requires depth buffer operations in image space, but reduces a lot of rendering calculations and is more efficient.

The advantages of octree are as follows:

BSP Tree#

It recursively divides space into convex polyhedra using hyperplanes and represents the divided space with a binary tree.

The definition of convex polyhedra: A polyhedron formed by several planar polygons that enclose a closed solid is called a polyhedron. These planar polygons are called faces of the polyhedron, and the edges and vertices of these polygons are called edges and vertices of the polyhedron, respectively. If the polyhedron is on the same side of the plane determined by each of its faces, it is called a convex polyhedron or an Euler polyhedron. Any section of a convex polyhedron is a convex polygon, which is opposite to a concave polyhedron.

The division idea is as follows:

The construction algorithm is as follows:

The algorithms for several geometric problems include:

• How to determine if a polyhedron is convex:
  

• How to determine the geometric relationship between two faces:
  

• Determining the geometric relationship between a face and a vertex:
  
  

After solving the above geometric problems, the construction of the BSP tree can be discussed. Another problem is how to determine the splitting hyperplane, and the selection steps are as follows:

• Removing convex hull faces
  
• Calculating NF, NB, NS
  
• Selecting the splitting hyperplane of the splitting space
  
  Finally, the complete construction algorithm of the BSP tree is:
  
  BSP tree traversal algorithm (painter's algorithm):
  
  Optimization can be achieved by traversing from front to back and performing calculations using depth buffer.

Applications of BSP tree:

Finally, a comparison of several algorithms:

Scene Management Examples#

OGRE Scene Management#

OGRE scene types include: static, dynamic, and extended:

1. Static type: very large, irregularly spread, immovable objects composed of triangles, including terrain, skyboxes, etc., represented by: SkyPlane, Skybox, SkyDome (SceneNode *); World geometry, usually a specific SceneManager; Static geometry, usually the tree structure of SceneManager is fixed, such as indoor scenes.

2. Dynamic type: movable, discrete, relatively small objects in the scene, mainly including entities (Entity), particles, cameras, etc., represented by SceneNode class and MovableObject class.

3. Extended type: mainly includes BSPSceneNode, OctreeNode, PCZSceneNode, etc.

OGRE scene management class diagram:

Description of main classes:

SceneManager (scene management singleton) main functions diagram:
Example of creating scene objects in OGRE:

OSG Scene Management#

OSG's main scene management modules:
OSG scene relationship class diagram:

Below are descriptions of several core classes in OSG scene management:

Design analysis of OSG scene management:

Panda3D Scene Management#

Concepts of Panda3D scene management:

1. The scene graph has a common base class (abstract class PandaNode), which is derived by all scene node classes.

2. Any node in the scene graph can have more than one parent node, so the scene graph is a directed acyclic structure.

3. Derived geometry node classes are leaf nodes of the scene graph and are renderable nodes.

4. NodePath class is the interface class for managing the scene graph, which operates on scene nodes, obtains the path from the root to the accessed node, etc.

Panda3D scene management class diagram:

Panda3D scene management base class definition:

Below are descriptions of several core classes in Panda3D scene management:



Panda3D scene management module relationship diagram:

Panda3D scene management example:

• Comparison of several game engine scene management methods: