algorithm - "false 3D"棱镜墙的渲染顺序

Question

我正在使用 Python 和 pygame 开发“伪 3D”游戏。 gfx 仅包含使用不同尺寸和颜色的 2D 图元创建的棱镜:

游戏的 gfx 是如何工作的:

问题出现在第 4 点，当我想在渲染队列中以正确的顺序对墙壁进行排序时(决定哪一个是最接近的并且必须首先渲染，哪个是第二个，哪个是最后一个等)。

目前，为了对墙壁进行排序，我移除了所有不可见的墙壁并测量了 player 和 wall 之间的最短距离。它有效……但只有当场景中只有一个多边形时。示例(2 个多边形):

我可以处理这种特定类型的问题，但我不知道将来是否还会有其他问题。我的问题:是否有任何算法(有效...)可以按正确的顺序对我的墙壁进行排序，并且我能够面带微笑地渲染它们？

Answer 1

我猜我们可以假设多边形不相交。如果是这种情况，我们不需要拆分任何东西。然而，找到正确的顺序在计算上仍然很繁重。尽管人们可能会想出一种增量方法，即逐帧更新必要的内容。

事情是这样的。在您的 2 多边形示例中，基于一条线的两个最近点的顺序显然不起作用，因为它们具有不同的 View 方向。但是如果你选择具有相同视角方向的点(在它们重叠的区域)，你会清楚地看到 A 在 B 的前面。那么，我们需要做什么:

首先找到所有可见的墙。我们将为这些墙创建可见性图。因此，创建一个图表，其中每面墙都由一个节点表示。最后，您将计算此图的拓扑排序以获得绘制顺序。现在，我们如何找到边缘，即关于哪堵墙在另一堵墙前面的信息？为此，首先找到重叠的墙对(挤压墙)。您可能希望使用像 AABB 树这样的加速数据结构来加快速度。

然后我们需要 View 方向的一维参数化。方向和 x 轴之间的角度可能工作得很好 (a = atan2(lineY - playerY, lineX - playerX))，尽管它具有您需要处理的烦人的周期性。我们现在将只考虑两堵墙的原始多边形边(不是拉伸(stretch)的墙)。找出两条线的一维间隔(例如，线 1 在 10° 和 35° 之间，线 2 在 20° 和 135° 之间)。如果这两个间隔不重叠，您可以跳过这对，因为它们的相对顺序无关紧要。如果他们这样做，找到重叠间隔中的任何点(例如 25°)，找到相应的 View 方向(x = playerX + cos(25°), y = playerY + sin(25°))以及线上对应于该方向的点(例如，通过计算线与视线的交点)。然后，简单地计算两条线沿这条射线的距离。选择重叠间隔中的哪个点并不重要，因为线是线性的并且原始多边形不相交。如果到第 1 行的距离小于到第 2 行的距离，则将第 1 行到第 2 行的有向边添加到可见性图中(意味着第 1 行在第 2 行的前面)，否则添加反向边。

最后，计算图形的拓扑顺序，您就有了绘图顺序。

选项 2

这是上述方法的替代方法，对于动态渲染可能更有效。这个想法是基于this publication .

首先对您的场景进行三角测量，即用三角形填充空隙(这只需要完成一次)。然后，我们的可见性图存储三角形(而不是边)。对于从内部看到的每个三角形边，将三角形的边添加到入射到该边的相邻三角形。最后，再次计算拓扑排序并按该顺序绘制墙壁(跳过空三角形)。

动态情况下的效率来自这样一个事实，即您只需对图表进行少量更新。对于每条边，您要确定是从前面还是从后面看到它们。因此，只有当视点穿过边指定的无限直线时，边的方向才会反转。如果您找到所有这些边(自上一帧以来改变了方向)，您可以更新图表并进行相应排序。