C++ 游戏引擎：什么是场景图？

Game engines: What are scene graphs?

提问by Loms

I've started reading into the material on Wikipedia, but I still feel like I don't really understand how a scene graph works and how it can provide benefits for a game.

我已经开始阅读维基百科上的资料，但我仍然觉得我并不真正了解场景图的工作原理以及它如何为游戏提供好处。

• What is a scene graph in the game engine development context?
• Why would I want to implement one for my 2D game engine?
• Does the usage of a scene graph stand as an alternative to a classic entity system with a linear entity manager?

• 什么是游戏引擎开发上下文中的场景图？
• 为什么我要为我的 2D 游戏引擎实现一个？
• 场景图的使用是否可以替代具有线性实体管理器的经典​​实体系统？

采纳答案by andand

What is a scene graph?A Scene graphcontains all of the geometry of a particular scene. They are useful for representing translations, rotations and scales (along with other affine transformations) of objects relative to each other.

什么是场景图？一个场景图包含了所有特定场景的几何形状。它们可用于表示对象相对于彼此的平移、旋转和缩放（以及其他仿射变换）。

For instance, consider a tank (the type with tracks and a gun). Your scene may have multiple tanks, but each one be oriented and positioned differently, with each having its turret rotated to different azimuth and with a different gun elevation. Rather than figuring out exactly how the gun should be positioned for each tank, you can accumulate affine transformations as you traverse your scene graph to properly position it. It makes computation of such things much easier.

例如，考虑一辆坦克（带有履带和枪的类型）。您的场景可能有多个坦克，但每个坦克的方向和位置都不同，每个坦克的炮塔都旋转到不同的方位角和不同的炮塔高度。您可以在遍历场景图以正确定位时积累仿射变换，而不是确切地确定每个坦克的枪应该如何定位。它使这些事情的计算变得更加容易。

2D Scene Graphs:Use of a scene graph for 2D may be useful if your content is sufficiently complex and if your objects have a number of sub components not rigidly fixed to the larger body. Otherwise, as others have mentioned, it's probably overkill. The complexity of affine transformations in 2D is quite a bit less than in the 3D case.

2D 场景图：如果您的内容足够复杂，并且您的对象具有许多未严格固定到较大主体的子组件，则使用2D 场景图可能会很有用。否则，正如其他人所提到的，这可能是矫枉过正。2D 中仿射变换的复杂性比 3D 情况下要少得多。

Linear Entity Manager: I'm not clear on exactly what you mean by a linear entity manager, but if you are refering to just keeping track of where things are positioned in your scene, then scene graphs can make things easier if there is a high degree of spatial dependence between the various objects or sub-objects in your scene.

线性实体管理器：我并不很清楚你用的意思线性实体管理器，但如果你指的只是跟踪的东西在哪里放置在场景中，然后场景图，可以使事情变得更容易，如果有一个高场景中各种对象或子对象之间的空间依赖性程度。

回答by Klaim

What is a scene graph in the game engine development context?

什么是游戏引擎开发上下文中的场景图？

Well, it's some code that actively sorts your game objects in the game space in a way that makes it easy to quicklyfind which objects are around a point in the game space.

嗯，它是一些代码，可以主动对游戏空间中的游戏对象进行排序，从而可以轻松快速地找到游戏空间中某个点周围的对象。

That way, it's easy to :

这样，很容易：

1. quickly find which objects are in the camera view (and send only them to the graphics cards, making rendering very fast)
2. quickly find objects near to the player (and apply collision checks to only those ones)

1. 快速找到相机视图中的对象（并且只将它们发送到显卡，从而使渲染速度非常快）
2. 快速找到玩家附近的物体（并仅对那些物体应用碰撞检查）

And other things. It's about allowing quick search in space. It's called "space partitioning". It's about divide and conquer.

和其他东西。这是关于允许在空间中快速搜索。这就是所谓的“空间分区”。这是关于分而治之的。

Why would I want to implement one for my 2D game engine?

为什么我要为我的 2D 游戏引擎实现一个？

That depends on the type of game, more precisely on the structure of your game space.

这取决于游戏的类型，更准确地说取决于您的游戏空间的结构。

For example, a game like Zelda could not need such techniques if it's fast enough to test collision between all objects in the screen. However it can easily be really really slow, so most of the time you at least setup a scene graph (or space partition of any kind) to at least know what is around all the moving objects and test collisions only on those objects.

例如，如果像塞尔达这样的游戏速度足够快，可以测试屏幕上所有对象之间的碰撞，那么它就不需要这种技术。然而，它很容易变得非常慢，所以大多数时候你至少设置一个场景图（或任何类型的空间分区）来至少知道所有移动对象周围的情况并仅在这些对象上测试碰撞。

So, that depends. Most of the time it's required for performance reasons. But the implementation of your space partitioning is totally relative to the way your game space is structured.

所以，这取决于。大多数情况下，出于性能原因需要它。但是您的空间分区的实施完全与您的游戏空间的结构方式有关。

Does the usage of a scene graph stand as an alternative to a classic entity system with a linear entity manager?

场景图的使用是否可以替代具有线性实体管理器的经典​​实体系统？

No.

不。

Whatever way you manage your game entities' object life, the space-partition/scene-graph is there only to allow you to quickly search objects in space, no more no less. Most of the time it will be an object that will have some slots of objects, corresponding to different parts of the game space and in those slots it will be objects that are in those parts. It can be flat (like a 2D screen divider in 2 or 4), or it can be a tree (like binary tree or quadtree, or any other kind of tree) or any other sorting structure that limits the number of operations you have to execute to get some space-related informations.

无论您以何种方式管理游戏实体的对象生命，空间分区/场景图只是为了让您快速搜索空间中的对象，不多不少。大多数情况下，它是一个具有一些对象插槽的对象，对应于游戏空间的不同部分，在这些插槽中，它将是这些部分中的对象。它可以是扁平的（如 2 或 4 中的 2D 屏幕分隔线），也可以是树（如二叉树或四叉树，或任何其他类型的树）或任何其他限制操作次数的排序结构执行获取一些空间相关的信息。

Note one thing :

注意一件事：

In some cases, you even need different separate space partition systems for different purposes. Often a "scene graph" is about rendering so it's optimized in a way that is dependent on the player's point of view and it's purpose is to allow quick gathering of a list of objects to render to send to the graphics card. It's not really suited to perform searches of objects around another object and that makes it hard to use for precise collision detection, like when you use a physic engine. So to help, you might have a different space partition system just for physics purpose.

在某些情况下，为了不同的目的，您甚至需要不同的独立空间分区系统。通常“场景图”是关于渲染的，因此它以依赖于玩家视角的方式进行优化，其目的是允许快速收集要渲染的对象列表以发送到显卡。它不太适合在另一个物体周围搜索物体，这使得它很难用于精确的碰撞检测，就像使用物理引擎一样。因此，为了提供帮助，您可能有一个不同的空间分区系统，仅用于物理目的。

To give an example, I want to make a "bullet hell" game, where there is a lot of balls that the player's spaceship has to dodge in a very precise way. To achieve enough rendering and collision detection performance I need to know :

举个例子，我想制作一个“子弹地狱”游戏，里面有很多球，玩家的飞船必须以非常精确的方式躲避。为了获得足够的渲染和碰撞检测性能，我需要知道：

1. when bullets appear in the screen space
2. when bullets leave the screen space
3. when the player enters in collision with bullets
4. when the player enters in collision with monsters

1. 当子弹出现在屏幕空间时
2. 当子弹离开屏幕空间时
3. 当玩家进入时与子弹碰撞
4. 当玩家进入时与怪物发生碰撞

So I recursively cut the screen that is 2D in 4 parts, that gives me a quadtree. The quadtree is updated each game tick, because everything moves constantly, so I have to keep track of each object's (spaceship, bullet, monster) position in the quadtree to know which one is in which part of the screen.

所以我递归地将 2D 的屏幕分成 4 个部分，这给了我一个四叉树。四叉树在每个游戏周期更新，因为一切都在不断移动，所以我必须跟踪每个对象（飞船、子弹、怪物）在四叉树中的位置，才能知道哪个在屏幕的哪个部分。

Achieving 1. is easy, just enter the bullet in the system.

实现1.很容易，只需在系统中输入项目符号即可。

To achieve 2. I kept a list of leaves in the quadtree (squared sections of the screen) that are on the border of the screen. Those leaves contain the ids/pointers of the bullets that are near the border so I just have to check that they are moving out to know if I can stop rendering them and managing collision too. (It might be bit more complex but you get the idea.)

实现 2. 我在四叉树（屏幕的平方部分）中保留了屏幕边界上的叶子列表。这些叶子包含靠近边界的子弹的 id/指针，所以我只需要检查它们是否正在移动，以了解我是否可以停止渲染它们并管理碰撞。（它可能有点复杂，但你明白了。）

To achieve 3 and 4. I need to retrieve the objects that are near the player's spaceship. So first I get the leaf where the player's spaceship is and I get all of the objects in it. That way I will only test the collision with the player spaceship on objects that are around it, not all objects. (It IS a bit more complex but you get the idea.)

为了实现 3 和 4。我需要检索玩家飞船附近的对象。所以首先我得到了玩家飞船所在的叶子，然后我得到了里面的所有物体。这样我只会在周围的物体上测试与玩家宇宙飞船的碰撞，而不是所有物体。（这有点复杂，但你明白了。）

That way I can make sure that my game will run smoothly even with thousands of bullets constantly moving.

这样我就可以确保我的游戏即使在成千上万颗子弹不断移动的情况下也能顺利运行。

In other types of space structure, other types of space partitioning are required. Typically, kart/auto games will have a "tunnel" scene-graph because visually the player will see only things along the road, so you just have to check where he is on the road to retrieve all visible objects around in the "tunnel".

在其他类型的空间结构中，需要其他类型的空间划分。通常，卡丁车/汽车游戏会有一个“隧道”场景图，因为在视觉上玩家只会看到沿路的东西，所以你只需要检查他在路上的位置，就可以检索“隧道”中所有可见的物体.

回答by Jupiter

There appear to be quite a few different philosophies on the web as to what the responsebilties are of a scenegraph. People tend to put in a lot of different things like geometry, camera's, light sources, game triggers etc.

网络上似乎有很多不同的哲学关于场景图的响应能力是什么。人们倾向于放入很多不同的东西，比如几何、相机、光源、游戏触发器等。

In general I would describe a scenegraph as a description of a scene and is composed of a single or multiple datastructures containing the entities present in the scene. These datastructures can be of any kind (array, tree, Composite pattern, etc) and can describe any property of the entities or any relationship between the entities in the scene. These entities can be anything ranging from solid drawable objects to collision-meshes, camera's and lightsources. The only real restriction I saw so far is that people recommend keeping game specific components (like game triggers) out to prevent depedency problems later on. Such things would have to be abstracted away to, say, "LogicEntity", "InvisibleEntity" or just "Entity".

一般来说，我会将场景图描述为场景的描述，它由包含场景中存在的实体的单个或多个数据结构组成。这些数据结构可以是任何类型（数组、树、复合模式等），并且可以描述实体的任何属性或场景中实体之间的任何关系。这些实体可以是任何东西，从实体可绘制对象到碰撞网格、相机和光源。到目前为止我看到的唯一真正的限制是人们建议保留游戏特定组件（如游戏触发器）以防止以后出现依赖问题。这些东西必须抽象为“LogicEntity”、“InvisibleEntity”或只是“Entity”。

Here are some common uses of and datastructures in a scenegraph.

以下是场景图中数据结构和数据结构的一些常见用途。

Parent/Child relationships

父子关系

The way you could use a scenegraph in a game or engine is to describe parent/child relationships between anything that has a position, be it a solid object, a camera or anything else. Such a relationship would mean that the position, scale and orientation of any child would be relative to that of its parent. This would allow you to make the camera follow the player or to have a lightsource follow a flashlight object. It would also allow you to make things like the solar system in which you can describe the position of planets relative to the sun and the position of moons relative to their planet if that is what you're making.

您可以在游戏或引擎中使用场景图的方式是描述任何具有位置的事物之间的父/子关系，无论是实体对象、相机还是其他任何事物。这种关系意味着任何孩子的位置、规模和方向都将与其父母的位置、规模和方向相关。这将允许您让相机跟随玩家或让光源跟随手电筒对象。它还允许您制作诸如太阳系之类的东西，如果您正在制作的话，您可以在其中描述行星相对于太阳的位置以及卫星相对于行星的位置。

Also things specific to some system in your game/engine can be stored in the scenegraph. For example, as part of a physics engine you may have defined simple collision-meshes for solid objects which may have too complex geometry to test collisions on. You could put these collision-meshes (I'm sure they have another name but I forgot it:P) in your scenegraph and have them follow the objects they model.

您的游戏/引擎中某些系统的特定内容也可以存储在场景图中。例如，作为物理引擎的一部分，您可能已经为实体对象定义了简单的碰撞网格，这些实体可能具有过于复杂的几何结构而无法测试碰撞。您可以将这些碰撞网格（我确定它们有另一个名称，但我忘记了：P）放在您的场景图中，并让它们跟随它们建模的对象。

Space-partitioning

空间分割

Another possible datastructure in a scenegraph is some form of space-partitioningas stated in other answers. This would allow you to perform fast queries on the scene like clipping any object that isn't in the viewing frustum or to efficiently filter out objects that need collision checking. You can also allow client code (in case you're writing an engine) to perform custom queries for whatever purpose. That way client code doesn't have to maintain its own space-partitioning structures.

场景图中另一种可能的数据结构是其他答案中所述的某种形式的空间分区。这将允许您在场景中执行快速查询，例如剪裁不在视锥体中的任何对象或有效过滤掉需要碰撞检查的对象。您还可以允许客户端代码（如果您正在编写引擎）为任何目的执行自定义查询。这样客户端代码就不必维护自己的空间分区结构。

I hope I gave you, and other readers, some ideas of how you can use a scenegraph and what you could put in it. I'm sure there are alot of other ways to use a scenegraph but these are the things I came up with.

我希望我给了你和其他读者一些关于如何使用场景图以及你可以在其中放入什么的想法。我确信还有很多其他方法可以使用场景图，但这些是我想出来的。

回答by Nick Banks

A scene graph is a way of organizing all objects in the environment. Usually care is taken to organize the data for efficient rendering. The graph, or tree if you like, can show ownership of sub objects. For example, at the highest level there may be a city object, under it would be many building objects, under those may be walls, furniture...

场景图是一种组织环境中所有对象的方式。通常会注意组织数据以实现高效渲染。图形或树（如果您愿意）可以显示子对象的所有权。例如，在最高层可能有一个城市对象，在它下面可能是许多建筑对象，在这些对象下面可能是墙壁、家具......

For the most part though, these are only used for 3D scenes. I would suggest not going with something that complicated for a 2D scene.

但在大多数情况下，这些仅用于 3D 场景。我建议不要使用那些对于 2D 场景来说复杂的东西。

回答by Nick Banks

In practice, scene objects in videogames are rarely organized into a graph that is "walked" as a tree when the scene is rendered. A graphics system typically expects one big array of stuff to render, and this big array is walked linearly.

在实践中，视频游戏中的场景对象很少被组织成一个图，当场景被渲染时，该图作为一棵树“行走”。图形系统通常期望渲染一大堆东西，而这个大数组是线性行走的。

Games that require geometric parenting relationships, such as those with people holding guns or tanks with turrets, define and enforce those relationships on an as-needed basis outside of the graphics system. These relationships tend to be only one-deep, and so there is almost never a need for an arbitrarily deep tree structure.

需要几何亲子关系的游戏，例如有人拿着枪或带炮塔的坦克的游戏，在图形系统之外根据需要定义和强制执行这些关系。这些关系往往只有一层深，因此几乎不需要任意深的树结构。