Lode 的计算机图形学教程

光线投射

目录

返回索引

简介

光线投射是一种在 2D 地图中创建 3D 透视效果的渲染技术。在计算机性能较弱的年代，无法实时运行真正的 3D 引擎，光线投射便是第一个解决方案。光线投射速度非常快，因为屏幕上每一条垂直线只需进行一次计算。使用这项技术最著名的游戏当然是 Wolfenstein 3D。



Wolfenstein 3D 的光线投射引擎非常有限，甚至可以在 286 计算机上运行：所有墙壁高度相同，并且是 2D 网格上的正交方块，如下图 Wolf3D 地图编辑器的截图所示：



楼梯、跳跃或高度差等功能在这个引擎中无法实现。后来的游戏如 Doom 和 Duke Nukem 3D 也使用了光线投射，但采用了更先进的引擎，支持斜面墙、不同高度、带纹理的地板和天花板、透明墙等。精灵（敌人、物体和道具）是 2D 图像，但精灵不在本教程的讨论范围之内。

光线投射与光线追踪不同！光线投射是一种快速的半 3D 技术，即使在 4MHz 的图形计算器上也能实时运行；而光线追踪是一种真实感渲染技术，支持真实 3D 场景中的反射和阴影，直到近年来计算机才足够快，能够在较高分辨率和复杂场景中实时运行。

本文档完整给出了无纹理和有纹理光线投射器的代码，但内容较长，你也可以直接下载代码：

raycaster_flat.cpp
raycaster_textured.cpp


基本原理

光线投射的基本思想如下：地图是一个 2D 方形网格，每个方格的值要么为 0（= 无墙），要么为正数（= 具有某种颜色或纹理的墙）。

对于屏幕上的每个 x 坐标（即屏幕上的每条垂直条纹），从玩家位置发出一条射线，其方向取决于玩家的朝向和屏幕的 x 坐标。然后让这条射线在 2D 地图上向前移动，直到碰到代表墙的地图方格。如果射线碰到了墙，计算碰撞点到玩家的距离，并用这个距离来计算墙在屏幕上应该画多高：墙越远，在屏幕上越小；墙越近，看起来越高。这些都是 2D 计算。下图是两条射线（红色）的俯视图，它们从玩家（绿点）出发并碰到蓝色的墙：



要找到射线遇到的第一面墙，需要让射线从玩家位置出发，然后不断检查射线是否在墙内。如果在墙内（命中），则循环可以停止，计算距离，并以正确的高度绘制墙。如果射线位置不在墙内，则需要继续追踪：沿射线方向在其位置上加上某个值，然后对新位置再次检查是否在墙内。持续这样做，直到最终碰到一面墙。

人眼可以立刻看出射线碰到墙的位置，但用单一公式立即找出射线碰到哪个方格是不可能的，因为计算机只能检查射线上有限个位置。许多光线投射器每步给射线增加一个常量值，但这样可能会错过一面墙！例如，对于这条红色射线，在每个红点处检查其位置：



如你所见，射线直接穿过了蓝色的墙，但计算机没有检测到，因为它只检查了红点处的位置。检查的位置越多，计算机漏检墙的概率越小，但需要的计算也越多。下图中步长减半，现在能检测到射线穿过了墙，但位置并不完全准确：



要用这种方法实现无限精度，需要无限小的步长，从而需要无限次计算！这非常糟糕，但幸运的是，有一种更好的方法，只需极少的计算就能检测到每一面墙：其思路是在射线将要遇到的每面墙的每条边上进行检查。我们给每个方格宽度为 1，所以墙的每条边都是整数值，中间的位置有小数点后的值。现在步长不是常量，它取决于到下一条边的距离：



如上图所示，射线恰好在我们想要的位置碰到了墙。本教程中使用的算法基于 DDA（数字微分分析）。DDA 是一种快速算法，通常用于方形网格，用来找出一条直线经过哪些方格（例如在屏幕上画一条线，屏幕是方形像素的网格）。因此我们也可以用它来找出射线经过地图中的哪些方格，并在碰到墙的方格时停止算法。

一些光线追踪器使用欧几里得角度来表示玩家和射线的方向，并用另一个角度确定视野（Field Of View）。然而我发现，使用向量和摄像机来处理要容易得多：玩家的位置始终是一个向量（x 和 y 坐标），现在我们也将方向设为向量：方向由两个值确定，即方向的 x 和 y 坐标。方向向量可以这样理解：如果沿玩家的朝向，过玩家位置画一条线，则该线上的每个点都是玩家位置与方向向量某个倍数之和。方向向量的长度并不重要，只有方向重要。将 x 和 y 乘以相同的值会改变长度，但保持相同的方向。

这种向量方法还需要一个额外的向量，即摄像机平面向量。在真正的 3D 引擎中也有摄像机平面，那里的平面是真正的 3D 平面，需要两个向量（u 和 v）来表示。然而，光线投射发生在 2D 地图上，所以摄像机平面实际上不是一个平面，而是一条线，用单个向量表示。摄像机平面应始终垂直于方向向量。摄像机平面代表计算机屏幕的表面，而方向向量垂直于它并指向屏幕内部。玩家的位置是摄像机平面前方的一个点。屏幕上某个 x 坐标对应的射线，就是从玩家位置出发、穿过屏幕（即摄像机平面）上对应位置的射线。



上图表示这样一个 2D 摄像机。绿点是位置（向量 "pos"）。以黑点结尾的黑线表示方向向量（向量 "dir"），所以黑点的位置是 pos+dir。蓝线表示完整的摄像机平面，从黑点到右侧蓝点的向量表示向量 "plane"，所以右侧蓝点的位置是 pos+dir+plane，左侧蓝点的位置是 pos+dir-plane（这些都是向量加法）。

图中的红线是几条射线。这些射线的方向可以从摄像机轻松计算出来：它是摄像机方向向量与摄像机平面向量的一部分之和。例如图中第三条红色射线，穿过摄像机平面右侧约 1/3 长度处的点。所以这条射线的方向是 dir + plane*1/3。这个射线方向就是向量 rayDir，该向量的 X 和 Y 分量随后被 DDA 算法使用。

两条最外侧的线是屏幕的左右边界，这两条线之间的角度称为视野（Field Of Vision）或 FOV。FOV 由方向向量长度与平面长度之比决定。以下是几个不同 FOV 的示例：

如果方向向量和摄像机平面向量长度相同，FOV 将为 90°：



如果方向向量比摄像机平面长得多，FOV 将远小于 90°，视野会非常窄。但你会看到更多细节，深度感减弱，这相当于放大（zoom in）：



如果方向向量比摄像机平面短，FOV 将大于 90°（最大为 180°，当方向向量接近 0 时），视野会宽得多，相当于缩小（zoom out）：





当玩家旋转时，摄像机也必须旋转，因此方向向量和平面向量都需要旋转。这样，所有射线也会自动跟着旋转。



要旋转一个向量，将其与旋转矩阵相乘

[ cos(a) -sin(a) ]
[ sin(a)  cos(a) ]

如果你不了解向量和矩阵，可以尝试用搜索引擎查找相关教程，本教程后续计划增加相关附录。

没有什么规定摄像机平面必须垂直于方向向量，但如果不垂直，结果看起来会像一个"倾斜"的世界。

无纹理光线投射器

在此下载源代码：raycaster_flat.cpp

从基础开始，我们先实现一个无纹理光线投射器。本示例还包含一个 FPS 计数器（每秒帧数），以及带碰撞检测的移动和旋转输入按键。

世界地图是一个 2D 数组，每个值代表一个方格。如果值为 0，该方格代表一个空的、可穿越的方格；如果值大于 0，则代表具有某种颜色或纹理的墙。这里声明的地图非常小，只有 24×24 个方格，直接在代码中定义。对于真实游戏（如 Wolfenstein 3D），你会使用更大的地图并从文件加载。网格中所有的 0 都是空地，所以基本上你会看到一个非常大的房间，周围有一圈墙（值为 1），内部有一个小房间（值为 2），几根柱子（值为 3），以及一条带房间的走廊（值为 4）。注意，这段代码还不在任何函数内，需要放在 main 函数之前。

#define mapWidth 24
#define mapHeight 24
#define screenWidth 640
#define screenHeight 480

int worldMap[mapWidth][mapHeight]=
{
  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,2,2,2,2,2,0,0,0,0,3,0,3,0,3,0,0,0,1},
  {1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,3,0,0,0,3,0,0,0,1},
  {1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,2,2,0,2,2,0,0,0,0,3,0,3,0,3,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,0,0,0,5,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
};

首先声明几个变量：posX 和 posY 表示玩家的位置向量，dirX 和 dirY 表示玩家的方向，planeX 和 planeY 表示玩家的摄像机平面。确保摄像机平面垂直于方向向量，但可以改变其长度。方向长度与摄像机平面长度之比决定 FOV，这里方向向量比摄像机平面稍长，所以 FOV 将小于 90°（更准确地说，FOV 为 2 * atan(0.66/1.0)=66°，非常适合第一人称射击游戏）。之后通过输入按键旋转时，dir 和 plane 的值会改变，但它们始终保持垂直并保持相同长度。

变量 time 和 oldTime 用于存储当前帧和上一帧的时间，两者之差可用于确定按下某个键时应移动多少（无论帧计算耗时多少都能保持恒定速度），也用于 FPS 计数器。

int main(int /*argc*/, char */*argv*/[])
{
  double posX = 22, posY = 12;  //x and y start position
  double dirX = -1, dirY = 0; //initial direction vector
  double planeX = 0, planeY = 0.66; //the 2d raycaster version of camera plane

  double time = 0; //time of current frame
  double oldTime = 0; //time of previous frame

现在开始 main 函数的其余部分。首先，以所选分辨率创建屏幕。如果选择较大的分辨率（如 1280×1024），效果会相当慢，不是因为光线投射算法慢，而仅仅是因为将整个屏幕从 CPU 上传到显卡的速度很慢。

  screen(screenWidth, screenHeight, 0, "Raycaster");

设置好屏幕后，游戏循环开始，这个循环每次绘制完整的一帧并读取输入。

  while(!done())
  {

这里开始实际的光线投射。光线投射循环是一个遍历每个 x 的 for 循环，因此不需要对屏幕上的每个像素进行计算，只需对每条垂直条纹计算，计算量非常少！在开始光线投射循环之前，需要声明并计算一些变量：

射线从玩家位置（posX，posY）出发。

cameraX 是摄像机平面上当前屏幕 x 坐标对应的 x 坐标，这样屏幕右侧对应坐标 1，屏幕中心对应坐标 0，屏幕左侧对应坐标 -1。由此可以按前面所述计算射线方向：即方向向量与平面向量一部分之和。这需要对向量的 x 和 y 坐标分别进行（因为两个向量相加就是将它们的 x 坐标相加，y 坐标相加）。

    for(int x = 0; x < w; x++)
    {
      //calculate ray position and direction
      double cameraX = 2 * x / double(w) - 1; //x-coordinate in camera space
      double rayDirX = dirX + planeX * cameraX;
      double rayDirY = dirY + planeY * cameraX;

在下一段代码中，声明并计算了更多与 DDA 算法相关的变量：

mapX 和 mapY 表示射线当前所在地图方格的坐标。射线位置本身是浮点数，包含了我们在地图哪个方格以及在该方格哪个位置的信息，但 mapX 和 mapY 只是该方格的坐标。

sideDistX 和 sideDistY 初始值是射线从起始位置到第一条 x 边和第一条 y 边所需行进的距离。在后续代码中，每走一步它们会相应增加。

deltaDistX 和 deltaDistY 是射线从一条 x 边到下一条 x 边，或从一条 y 边到下一条 y 边所需行进的距离。下图展示了初始的 sideDistX、sideDistY 以及 deltaDistX 和 deltaDistY：



通过几何方法推导 deltaDistX，利用勾股定理可得如下公式。对于蓝色三角形（deltaDistX），一条边长度为 1（恰好是一个格子），另一条边长度为 raydirY / raydirX，因为这正是射线在 X 方向走 1 步时在 y 方向走的单位数。对于绿色三角形（deltaDistY），公式类似。

deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX))
deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY))

但可以简化为：

deltaDistX = abs(|rayDir| / rayDirX)
deltaDistY = abs(|rayDir| / rayDirY)

其中 |rayDir| 是向量 rayDirX、rayDirY 的长度（即 sqrt(rayDirX * rayDirX + rayDirY * rayDirY)）：你可以验证，例如 sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX)) 等于 abs(sqrt(rayDirX * rayDirX + rayDirY * rayDirY) / rayDirX)。然而，我们可以用 1 代替 |rayDir|，因为对于后续的 DDA 代码，只有 deltaDistX 和 deltaDistY 之间的*比值*才重要，所以得到：

deltaDistX = abs(1 / rayDirX)
deltaDistY = abs(1 / rayDirY)

因此，代码中使用的 deltaDist 和 sideDist 值与上图中显示的长度不匹配，但它们的相对大小仍然一致。

[感谢 Artem 发现了这个简化方法]

变量 perpWallDist 将在后面用于计算射线的长度。

DDA 算法每次循环都会恰好跳过一个方格，要么是 x 方向的方格，要么是 y 方向的方格。是向负还是正 x 方向，以及向负还是正 y 方向，取决于射线的方向，这一信息存储在 stepX 和 stepY 中。这些变量的值始终为 -1 或 +1。

最后，hit 用于判断循环是否可以结束，side 用于记录碰到的是墙的 x 边还是 y 边。如果碰到 x 边，side 设为 0；如果碰到 y 边，side 设为 1。这里的 x 边和 y 边是指网格中两个方格之间边界线。

      //which box of the map we're in
      int mapX = int(posX);
      int mapY = int(posY);

      //length of ray from current position to next x or y-side
      double sideDistX;
      double sideDistY;

       //length of ray from one x or y-side to next x or y-side
      double deltaDistX = (rayDirX == 0) ? 1e30 : std::abs(1 / rayDirX);
      double deltaDistY = (rayDirY == 0) ? 1e30 : std::abs(1 / rayDirY);
      double perpWallDist;

      //what direction to step in x or y-direction (either +1 or -1)
      int stepX;
      int stepY;

      int hit = 0; //was there a wall hit?
      int side; //was a NS or a EW wall hit?

注意：如果 rayDirX 或 rayDirY 为 0，通过将其设为一个非常大的值 1e30 来避免除以零。如果你使用 C++、Java 或 JS 等语言，实际上不需要这样做，因为这些语言支持 IEEE 754 浮点标准，会给出 Infinity 的结果，在下面的代码中可以正确工作。然而，某些语言（如 Python）不允许除以零，所以上面给出了适用于所有语言的通用代码。1e30 是一个任意选择的足够大的数，如果你的编程语言支持赋值该值，也可以设为 Infinity。

现在，在实际 DDA 开始之前，还需要计算 stepX、stepY 以及初始的 sideDistX 和 sideDistY。

如果射线方向的 x 分量为负，stepX 为 -1；如果 x 分量为正，stepX 为 +1。如果 x 分量为 0，stepX 的值无关紧要，因为它不会被使用。
y 分量同理。

如果射线方向的 x 分量为负，sideDistX 是从射线起始位置到左侧第一条边的距离；如果 x 分量为正，则使用右侧第一条边。
y 分量同理，但现在是位置上方或下方的第一条边。
计算这些值时，使用整数值 mapX 并减去实际位置，在某些情况下根据使用左侧还是右侧、上方还是下方的边加上 1.0。这样得到到该边的垂直距离，再乘以 deltaDistX 或 deltaDistY 即可得到真实的欧几里得距离。

      //calculate step and initial sideDist
      if (rayDirX < 0)
      {
        stepX = -1;
        sideDistX = (posX - mapX) * deltaDistX;
      }
      else
      {
        stepX = 1;
        sideDistX = (mapX + 1.0 - posX) * deltaDistX;
      }
      if (rayDirY < 0)
      {
        stepY = -1;
        sideDistY = (posY - mapY) * deltaDistY;
      }
      else
      {
        stepY = 1;
        sideDistY = (mapY + 1.0 - posY) * deltaDistY;
      }

现在实际的 DDA 开始了。这是一个每次将射线推进 1 个方格的循环，直到碰到墙为止。每次要么在 x 方向跳一个方格（用 stepX），要么在 y 方向跳一个方格（用 stepY），每次始终跳 1 个方格。如果射线方向是 x 方向，循环每次只需在 x 方向跳，因为射线不会改变 y 方向。如果射线略微偏向 y 方向，则每跳若干次 x 方向后，射线需要在 y 方向跳一个方格。如果射线恰好是 y 方向，则永远不需要在 x 方向跳，以此类推。

每次在对应方向跳跃时，sideDistX 和 sideDistY 分别增加 deltaDistX，mapX 和 mapY 分别增加 stepX 和 stepY。

当射线碰到墙时，循环结束，此时变量 "side" 记录碰到的是 x 边还是 y 边，mapX 和 mapY 记录碰到的是哪面墙。但我们不知道墙被碰到的确切位置，不过目前不需要，因为我们暂时不使用纹理墙。

      //perform DDA
      while (hit == 0)
      {
        //jump to next map square, either in x-direction, or in y-direction
        if (sideDistX < sideDistY)
        {
          sideDistX += deltaDistX;
          mapX += stepX;
          side = 0;
        }
        else
        {
          sideDistY += deltaDistY;
          mapY += stepY;
          side = 1;
        }
        //Check if ray has hit a wall
        if (worldMap[mapX][mapY] > 0) hit = 1;
      }

DDA 完成后，我们需要计算射线到墙的距离，以便计算墙应该画多高。

我们不使用到玩家点的欧几里得距离，而是使用到摄像机平面的距离（即点在摄像机方向上投影到玩家的距离），以避免鱼眼效果。鱼眼效果是使用真实距离时出现的现象，会使所有墙看起来是弯曲的，旋转时可能令人不适。

下图说明了为什么使用到摄像机平面的距离而不是到玩家的距离。P 是玩家，黑线是摄像机平面：玩家左侧显示了几条从墙上碰撞点到玩家的红色射线，代表欧几里得距离。玩家右侧显示了几条从墙上碰撞点直接到摄像机平面（而非到玩家）的绿色射线。这些绿线的长度就是我们将使用的垂直距离示例，而非直接欧几里得距离。

图中玩家直视墙壁，此时你期望墙的顶部和底部在屏幕上形成完美的水平线。然而，红色射线长度各不相同，会为不同垂直条纹计算出不同的墙高，从而产生弯曲效果。右侧的绿色射线长度相同，因此会给出正确的结果。玩家旋转时同样适用（此时摄像机平面不再水平，绿线长度会有所不同，但相邻之间的变化是恒定的），墙在屏幕上变为斜线但仍是直线。这个解释有些不够严谨，但传达了基本思路。

perpWallDist

注意，这部分代码不是"鱼眼校正"，本教程使用的光线投射方式不需要这种校正，鱼眼效果只是通过这里的距离计算方式自然避免了。计算这个垂直距离甚至比计算真实距离更简单，我们甚至不需要知道墙被碰到的确切位置。

这个垂直距离在代码中称为 "perpWallDist"。一种计算方式是使用点到直线最短距离的公式，其中点是墙被碰到的位置，直线是摄像机平面：

perpWallDist

然而，还有更简单的计算方式：由于上面 deltaDist 和 sideDist 都按 |rayDir| 的因子缩放，sideDist 的长度已经几乎等于 perpWallDist。我们只需从中减去一次 deltaDist，退回一步，因为在上面的 DDA 步骤中我们多走了一步，最终落在了墙内。

根据射线碰到的是 X 边还是 Y 边，公式分别使用 sideDistX 或 sideDistY 计算。 

      //Calculate distance projected on camera direction (Euclidean distance would give fisheye effect!)
      if(side == 0) perpWallDist = (sideDistX - deltaDistX);
      else          perpWallDist = (sideDistY - deltaDistY);

下图更详细地展示了 perpWallDist 公式的推导，针对 side == 1 的情况。

各点含义：

实际推导过程：

perpWallDist

[感谢 Thomas van der Berg 于 2016 年指出代码的简化方式（perpWallDist 可以简化，且该值可复用于 wallX）。
[感谢 Roux Morgan 于 2020 年帮助澄清 perpWallDist 的说明，此前教程缺少一些相关信息]
[感谢 Noah Wagner 和 Elias 发现了 perpWallDist 的进一步简化方法]

现在我们已经计算出距离（perpWallDist），可以计算屏幕上需要绘制的线段高度：这是 perpWallDist 的倒数，再乘以屏幕像素高度 h，转换为像素坐标。当然也可以乘以其他值，例如 2*h，以使墙更高或更低。使用 h 会使墙看起来像高度、宽度和深度相等的立方体，而较大的值会产生更高的方块（取决于你的显示器）。

然后根据这个 lineHeight（即应绘制的垂直线段的高度），计算实际应绘制的起始和结束位置。墙的中心应位于屏幕中心，如果这些点超出屏幕范围，则截取为 0 或 h-1。

      //Calculate height of line to draw on screen
      int lineHeight = (int)(h / perpWallDist);

      //calculate lowest and highest pixel to fill in current stripe
      int drawStart = -lineHeight / 2 + h / 2;
      if(drawStart < 0)drawStart = 0;
      int drawEnd = lineHeight / 2 + h / 2;
      if(drawEnd >= h)drawEnd = h - 1;

最后，根据碰到的墙的编号选择颜色。如果碰到 y 边，颜色会变暗，这样效果更好看。然后用 verLine 命令绘制垂直线段。至此光线投射循环结束，它已为每个 x 完成了上述操作。

      //choose wall color
      ColorRGB color;
      switch(worldMap[mapX][mapY])
      {
        case 1:  color = RGB_Red;  break; //red
        case 2:  color = RGB_Green;  break; //green
        case 3:  color = RGB_Blue;   break; //blue
        case 4:  color = RGB_White;  break; //white
        default: color = RGB_Yellow; break; //yellow
      }

      //give x and y sides different brightness
      if (side == 1) {color = color / 2;}

      //draw the pixels of the stripe as a vertical line
      verLine(x, drawStart, drawEnd, color);
    }

光线投射循环结束后，计算当前帧和上一帧的时间，计算并打印 FPS（每秒帧数），重绘屏幕使一切（所有墙和 FPS 计数器的值）可见。之后用 cls() 清除后缓冲区，这样下一帧再次绘制墙时，地板和天花板会重新变黑，而不是保留上一帧的像素。

速度修正量使用 frameTime 和一个常量值来确定输入按键的移动和旋转速度。通过使用 frameTime，可以确保移动和旋转速度与处理器速度无关。

    //timing for input and FPS counter
    oldTime = time;
    time = getTicks();
    double frameTime = (time - oldTime) / 1000.0; //frameTime is the time this frame has taken, in seconds
    print(1.0 / frameTime); //FPS counter
    redraw();
    cls();

    //speed modifiers
    double moveSpeed = frameTime * 5.0; //the constant value is in squares/second
    double rotSpeed = frameTime * 3.0; //the constant value is in radians/second

最后一部分是输入部分，读取按键。

如果按下上箭头，玩家将向前移动：将 dirX 加到 posX，将 dirY 加到 posY。这假设 dirX 和 dirY 是归一化向量（长度为 1），它们初始时就是这样设置的，所以没问题。还内置了简单的碰撞检测：如果新位置在墙内，则不移动。不过这个碰撞检测可以改进，例如检查玩家周围的圆形区域是否会进入墙内，而不仅仅检查单个点。

按下下箭头时做同样的操作，但方向是减法而非加法。

旋转时，如果按下左或右箭头，方向向量和平面向量都通过旋转矩阵乘法公式（以 rotSpeed 为角度）进行旋转。

    readKeys();
    //move forward if no wall in front of you
    if (keyDown(SDLK_UP))
    {
      if(worldMap[int(posX + dirX * moveSpeed)][int(posY)] == false) posX += dirX * moveSpeed;
      if(worldMap[int(posX)][int(posY + dirY * moveSpeed)] == false) posY += dirY * moveSpeed;
    }
    //move backwards if no wall behind you
    if (keyDown(SDLK_DOWN))
    {
      if(worldMap[int(posX - dirX * moveSpeed)][int(posY)] == false) posX -= dirX * moveSpeed;
      if(worldMap[int(posX)][int(posY - dirY * moveSpeed)] == false) posY -= dirY * moveSpeed;
    }
    //rotate to the right
    if (keyDown(SDLK_RIGHT))
    {
      //both camera direction and camera plane must be rotated
      double oldDirX = dirX;
      dirX = dirX * cos(-rotSpeed) - dirY * sin(-rotSpeed);
      dirY = oldDirX * sin(-rotSpeed) + dirY * cos(-rotSpeed);
      double oldPlaneX = planeX;
      planeX = planeX * cos(-rotSpeed) - planeY * sin(-rotSpeed);
      planeY = oldPlaneX * sin(-rotSpeed) + planeY * cos(-rotSpeed);
    }
    //rotate to the left
    if (keyDown(SDLK_LEFT))
    {
      //both camera direction and camera plane must be rotated
      double oldDirX = dirX;
      dirX = dirX * cos(rotSpeed) - dirY * sin(rotSpeed);
      dirY = oldDirX * sin(rotSpeed) + dirY * cos(rotSpeed);
      double oldPlaneX = planeX;
      planeX = planeX * cos(rotSpeed) - planeY * sin(rotSpeed);
      planeY = oldPlaneX * sin(rotSpeed) + planeY * cos(rotSpeed);
    }
  }
}

无纹理光线投射器的代码到此结束，效果如下，你可以在地图中行走：



下面是摄像机平面不垂直于方向向量时的效果示例，世界看起来是倾斜的：




有纹理光线投射器

在此下载源代码：raycaster_textured.cpp

有纹理版本的光线投射器核心几乎相同，只是在末尾需要为纹理做一些额外计算，并且需要一个 y 方向的循环来遍历每个像素，以确定应使用纹理的哪个纹素（纹理像素）。

垂直条纹不能再用垂直线命令绘制，而是需要逐像素绘制。最好的方式是这次使用 2D 数组作为屏幕缓冲区，一次性复制到屏幕，这比使用 pset 快得多。

当然，现在还需要一个额外的纹理数组，由于 "drawbuffer" 函数使用单个整数值表示颜色（而非 R、G、B 三个独立字节），纹理也以这种格式存储。通常你会从纹理文件加载纹理，但在这个简单示例中，我们直接生成一些简单纹理。

代码大部分与前一个示例相同，粗体部分是新内容。只对新部分进行说明。

screenWidth 和 screenHeight 现在在开头定义，因为 screen 函数和创建屏幕缓冲区都需要相同的值。这里还新增了纹理宽度和高度的定义，它们显然是纹理的纹素宽度和高度。

世界地图也有变化，这是一个更复杂的地图，有走廊和房间，用于展示不同纹理。同样，0 是可穿越的空地，每个正数对应一种不同的纹理。

#define screenWidth 640
#define screenHeight 480
#define texWidth 64
#define texHeight 64
#define mapWidth 24
#define mapHeight 24

int worldMap[mapWidth][mapHeight]=
{
  {4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,7,7,7,7,7,7,7,7},
  {4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,7},
  {4,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7},
  {4,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7},
  {4,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,7},
  {4,0,4,0,0,0,0,5,5,5,5,5,5,5,5,5,7,7,0,7,7,7,7,7},
  {4,0,5,0,0,0,0,5,0,5,0,5,0,5,0,5,7,0,0,0,7,7,7,1},
  {4,0,6,0,0,0,0,5,0,0,0,0,0,0,0,5,7,0,0,0,0,0,0,8},
  {4,0,7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,7,7,1},
  {4,0,8,0,0,0,0,5,0,0,0,0,0,0,0,5,7,0,0,0,0,0,0,8},
  {4,0,0,0,0,0,0,5,0,0,0,0,0,0,0,5,7,0,0,0,7,7,7,1},
  {4,0,0,0,0,0,0,5,5,5,5,0,5,5,5,5,7,7,7,7,7,7,7,1},
  {6,6,6,6,6,6,6,6,6,6,6,0,6,6,6,6,6,6,6,6,6,6,6,6},
  {8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4},
  {6,6,6,6,6,6,0,6,6,6,6,0,6,6,6,6,6,6,6,6,6,6,6,6},
  {4,4,4,4,4,4,0,4,4,4,6,0,6,2,2,2,2,2,2,2,3,3,3,3},
  {4,0,0,0,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,0,0,0,2},
  {4,0,0,0,0,0,0,0,0,0,0,0,6,2,0,0,5,0,0,2,0,0,0,2},
  {4,0,0,0,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,2,0,2,2},
  {4,0,6,0,6,0,0,0,0,4,6,0,0,0,0,0,5,0,0,0,0,0,0,2},
  {4,0,0,5,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,2,0,2,2},
  {4,0,6,0,6,0,0,0,0,4,6,0,6,2,0,0,5,0,0,2,0,0,0,2},
  {4,0,0,0,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,0,0,0,2},
  {4,4,4,4,4,4,4,4,4,4,1,1,1,2,2,2,2,2,2,3,3,3,3,3}
};

屏幕缓冲区和纹理数组在这里声明。纹理数组是一个 std::vector 数组，每个元素包含特定 width * height 个像素。

int main(int /*argc*/, char */*argv*/[])
{
  double posX = 22.0, posY = 11.5;  //x and y start position
  double dirX = -1.0, dirY = 0.0; //initial direction vector
  double planeX = 0.0, planeY = 0.66; //the 2d raycaster version of camera plane

  double time = 0; //time of current frame
  double oldTime = 0; //time of previous frame

  Uint32 buffer[screenHeight][screenWidth]; // y-coordinate first because it works per scanline
  std::vector texture[8];
  for(int i = 0; i < 8; i++) texture[i].resize(texWidth * texHeight);

main 函数现在从生成纹理开始。我们用一个双重循环遍历纹理的每个像素，然后根据 x 和 y 计算每种纹理对应像素的值。有些纹理是 XOR 图案，有些是简单渐变，另一些是砖块图案，基本上都是非常简单的图案，看起来不会太好看，更好的纹理请参见下一章。

  screen(screenWidth,screenHeight, 0, "Raycaster");

  //generate some textures
  for(int x = 0; x < texWidth; x++)
  for(int y = 0; y < texHeight; y++)
  {
    int xorcolor = (x * 256 / texWidth) ^ (y * 256 / texHeight);
    //int xcolor = x * 256 / texWidth;
    int ycolor = y * 256 / texHeight;
    int xycolor = y * 128 / texHeight + x * 128 / texWidth;
    texture[0][texWidth * y + x] = 65536 * 254 * (x != y && x != texWidth - y); //flat red texture with black cross
    texture[1][texWidth * y + x] = xycolor + 256 * xycolor + 65536 * xycolor; //sloped greyscale
    texture[2][texWidth * y + x] = 256 * xycolor + 65536 * xycolor; //sloped yellow gradient
    texture[3][texWidth * y + x] = xorcolor + 256 * xorcolor + 65536 * xorcolor; //xor greyscale
    texture[4][texWidth * y + x] = 256 * xorcolor; //xor green
    texture[5][texWidth * y + x] = 65536 * 192 * (x % 16 && y % 16); //red bricks
    texture[6][texWidth * y + x] = 65536 * ycolor; //red gradient
    texture[7][texWidth * y + x] = 128 + 256 * 128 + 65536 * 128; //flat grey texture
  }

这又是游戏循环的开始，以及 DDA 算法之前的初始声明和计算。这里没有任何变化。

  //start the main loop
  while(!done())
  {
    for(int x = 0; x < w; x++)
    {
      //calculate ray position and direction
      double cameraX = 2*x/double(w)-1; //x-coordinate in camera space
      double rayDirX = dirX + planeX*cameraX;
      double rayDirY = dirY + planeY*cameraX;

      //which box of the map we're in
      int mapX = int(posX);
      int mapY = int(posY);

      //length of ray from current position to next x or y-side
      double sideDistX;
      double sideDistY;

      //length of ray from one x or y-side to next x or y-side
      double deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
      double deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));
      double perpWallDist;

      //what direction to step in x or y-direction (either +1 or -1)
      int stepX;
      int stepY;

      int hit = 0; //was there a wall hit?
      int side; //was a NS or a EW wall hit?

      //calculate step and initial sideDist
      if (rayDirX < 0)
      {
        stepX = -1;
        sideDistX = (posX - mapX) * deltaDistX;
      }
      else
      {
        stepX = 1;
        sideDistX = (mapX + 1.0 - posX) * deltaDistX;
      }
      if (rayDirY < 0)
      {
        stepY = -1;
        sideDistY = (posY - mapY) * deltaDistY;
      }
      else
      {
        stepY = 1;
        sideDistY = (mapY + 1.0 - posY) * deltaDistY;
      }

这又是 DDA 循环，以及距离和高度的计算，这里同样没有任何变化。

      //perform DDA
      while (hit == 0)
      {
        //jump to next map square, either in x-direction, or in y-direction
        if (sideDistX < sideDistY)
        {
          sideDistX += deltaDistX;
          mapX += stepX;
          side = 0;
        }
        else
        {
          sideDistY += deltaDistY;
          mapY += stepY;
          side = 1;
        }
        //Check if ray has hit a wall
        if (worldMap[mapX][mapY] > 0) hit = 1;
      }

      //Calculate distance of perpendicular ray (Euclidean distance would give fisheye effect!)
      if(side == 0) perpWallDist = (sideDistX - deltaDistX);
      else          perpWallDist = (sideDistY - deltaDistY);

      //Calculate height of line to draw on screen
      int lineHeight = (int)(h / perpWallDist);

      //calculate lowest and highest pixel to fill in current stripe
      int drawStart = -lineHeight / 2 + h / 2;
      if(drawStart < 0) drawStart = 0;
      int drawEnd = lineHeight / 2 + h / 2;
      if(drawEnd >= h) drawEnd = h - 1;

然而，以下计算是新内容，替换了无纹理光线投射器中的颜色选择器。
变量 texNum 是当前地图方格的值减去 1，原因是存在纹理 0，但地图格 0 没有纹理，因为它代表空地。为了能使用纹理 0，减去 1 使得值为 1 的地图格对应纹理 0，以此类推。

wallX 表示墙被碰到的精确位置，而不仅仅是墙的整数坐标。这是确定应使用纹理哪个 x 坐标所必需的。计算方法是先计算世界中精确的 x 或 y 坐标，然后减去墙的整数值。注意，即使叫做 wallX，当 side==1 时它实际上是墙的 y 坐标，但它始终是纹理的 x 坐标。

最后，texX 是纹理的 x 坐标，由 wallX 计算得出。

      //texturing calculations
      int texNum = worldMap[mapX][mapY] - 1; //1 subtracted from it so that texture 0 can be used!

      //calculate value of wallX
      double wallX; //where exactly the wall was hit
      if (side == 0) wallX = posY + perpWallDist * rayDirY;
      else           wallX = posX + perpWallDist * rayDirX;
      wallX -= floor((wallX));

      //x coordinate on the texture
      int texX = int(wallX * double(texWidth));
      if(side == 0 && rayDirX > 0) texX = texWidth - texX - 1;
      if(side == 1 && rayDirY < 0) texX = texWidth - texX - 1;

现在我们知道了纹理的 x 坐标，该坐标在同一垂直条纹内保持不变。现在需要一个 y 方向的循环，为垂直条纹的每个像素确定正确的纹理 y 坐标，称为 texY。

texY 的值通过每个像素增加一个预计算步长来计算（这是可行的，因为在垂直条纹内步长是常量）。步长表示在垂直屏幕坐标每移动一个像素时，纹理坐标（浮点数）增加多少。然后需要将浮点值转换为整数来选取实际的纹理像素。

注意：对此可能存在更快的纯整数 Bresenham 或 DDA 算法。

注意：这里进行的步进是仿射纹理映射，意味着我们可以在两点之间线性插值，而不必为每个像素计算不同的除法。一般情况下这不是透视正确的，但对于完全垂直的墙（以及完全水平的地板/天花板）来说是正确的，所以可以用于光线投射。

待绘制像素的颜色直接从 texture[texNum][texX][texY] 获取，即正确纹理的正确纹素。

与无纹理光线投射器一样，如果碰到墙的 y 边，颜色值也会变暗，因为这样看起来更好（像是有某种光照效果）。然而，由于颜色值不是由独立的 R、G、B 值组成，而是这 3 个字节合并在一个整数中，所以使用了一种不太直观的计算方式。

通过将 R、G、B 各除以 2 来使颜色变暗。将十进制数除以 10，可以通过去掉最后一位数字来实现（例如 300/10 是 30：去掉了最后的零）。类似地，将二进制数除以 2（这里就是这样做的）等同于去掉最后一位。可以通过右移 >>1 来实现。但是，这里我们对一个 24 位整数（实际上是 32 位，但前 8 位未使用）进行位移。因此，一个字节的最后一位会变成下一个字节的第一位，这会破坏颜色值！所以位移后，每个字节的第一位必须设为零，可以通过与二进制值 011111110111111101111111（十进制为 8355711）进行二进制"与"运算来实现。这样的结果确实是一种更暗的颜色。

最后，将当前缓冲区像素设为该颜色，然后继续处理下一个 y。

            // How much to increase the texture coordinate per screen pixel
      double step = 1.0 * texHeight / lineHeight;
      // Starting texture coordinate
      double texPos = (drawStart - h / 2 + lineHeight / 2) * step;
      for(int y = drawStart; y<drawEnd; y++)
      {
        // Cast the texture coordinate to integer, and mask with (texHeight - 1) in case of overflow
        int texY = (int)texPos & (texHeight - 1);
        texPos += step;
        Uint32 color = texture[texNum][texHeight * texY + texX];
        //make color darker for y-sides: R, G and B byte each divided through two with a "shift" and an "and"
        if(side == 1) color = (color >> 1) & 8355711;
        buffer[y][x] = color;
      }
    }

现在缓冲区还需要绘制，之后必须清除（在无纹理版本中只需使用 "cls"。为了速度，确保按扫描线顺序执行，以利用缓存的内存局部性）。其余代码再次相同。

    drawBuffer(buffer[0]);
    for(int y = 0; y < h; y++) for(int x = 0; x < w; x++) buffer[y][x] = 0; //clear the buffer instead of cls()
    //timing for input and FPS counter
    oldTime = time;
    time = getTicks();
    double frameTime = (time - oldTime) / 1000.0; //frametime is the time this frame has taken, in seconds
    print(1.0 / frameTime); //FPS counter
    redraw();

    //speed modifiers
    double moveSpeed = frameTime * 5.0; //the constant value is in squares/second
    double rotSpeed = frameTime * 3.0; //the constant value is in radians/second

这里又是按键部分，同样没有任何变化。如果你愿意，可以尝试添加横移按键（向左和向右横移）。这需要与上下键相同的方式实现，但使用 planeX 和 planeY 代替 dirX 和 dirY。

    readKeys();
    //move forward if no wall in front of you
    if (keyDown(SDLK_UP))
    {
      if(worldMap[int(posX + dirX * moveSpeed)][int(posY)] == false) posX += dirX * moveSpeed;
      if(worldMap[int(posX)][int(posY + dirY * moveSpeed)] == false) posY += dirY * moveSpeed;
    }
    //move backwards if no wall behind you
    if (keyDown(SDLK_DOWN))
    {
      if(worldMap[int(posX - dirX * moveSpeed)][int(posY)] == false) posX -= dirX * moveSpeed;
      if(worldMap[int(posX)][int(posY - dirY * moveSpeed)] == false) posY -= dirY * moveSpeed;
    }
    //rotate to the right
    if (keyDown(SDLK_RIGHT))
    {
      //both camera direction and camera plane must be rotated
      double oldDirX = dirX;
      dirX = dirX * cos(-rotSpeed) - dirY * sin(-rotSpeed);
      dirY = oldDirX * sin(-rotSpeed) + dirY * cos(-rotSpeed);
      double oldPlaneX = planeX;
      planeX = planeX * cos(-rotSpeed) - planeY * sin(-rotSpeed);
      planeY = oldPlaneX * sin(-rotSpeed) + planeY * cos(-rotSpeed);
    }
    //rotate to the left
    if (keyDown(SDLK_LEFT))
    {
      //both camera direction and camera plane must be rotated
      double oldDirX = dirX;
      dirX = dirX * cos(rotSpeed) - dirY * sin(rotSpeed);
      dirY = oldDirX * sin(rotSpeed) + dirY * cos(rotSpeed);
      double oldPlaneX = planeX;
      planeX = planeX * cos(rotSpeed) - planeY * sin(rotSpeed);
      planeY = oldPlaneX * sin(rotSpeed) + planeY * cos(rotSpeed);
    }
  }
}

以下是结果的几张截图：



注意：通常图像按水平扫描线存储，但对于光线投射器，纹理是按垂直条纹绘制的。因此，为了最优地利用 CPU 缓存并避免缺页，将纹理在内存中按垂直条纹存储（而非按水平扫描线）可能更高效。要实现这一点，在生成纹理后，通过以下方式交换其 X 和 Y（此代码仅在 texWidth 和 texHeight 相同时有效）： 

  //swap texture X/Y since they'll be used as vertical stripes
  for(size_t i = 0; i < 8; i++)
  for(size_t x = 0; x < texSize; x++)
  for(size_t y = 0; y < x; y++)
  std::swap(texture[i][texSize * y + x], texture[i][texSize * x + y]);


或者直接在生成纹理时交换 X 和 Y，但在许多情况下，从图像文件加载或从其他格式获取纹理后，纹理本身就是按扫描线存储的，仍需用这种方式交换。

从纹理获取像素时，改用以下代码： 

Uint32 color = texture[texNum][texSize * texX + texY];

Wolfenstein 3D 纹理

与其只是生成一些纹理，不如从图像文件加载几张！例如以下 8 张纹理，来自 Wolfenstein 3D，版权归 ID Software 所有。



只需将代码中生成纹理图案的部分替换为以下内容（并确保这些纹理在正确的路径下）。你可以在这里下载纹理。

  //generate some textures
  unsigned long tw, th;
  loadImage(texture[0], tw, th, "pics/eagle.png");
  loadImage(texture[1], tw, th, "pics/redbrick.png");
  loadImage(texture[2], tw, th, "pics/purplestone.png");
  loadImage(texture[3], tw, th, "pics/greystone.png");
  loadImage(texture[4], tw, th, "pics/bluestone.png");
  loadImage(texture[5], tw, th, "pics/mossy.png");
  loadImage(texture[6], tw, th, "pics/wood.png");
  loadImage(texture[7], tw, th, "pics/colorstone.png");




在原版 Wolfenstein 3D 中，墙的一面颜色也比另一面更暗以创造阴影效果，但他们每次使用两张独立纹理：一张暗色，一张亮色。然而在这里，每面墙只使用一张纹理，将 R、G、B 各除以 2 的那行代码使 y 边变暗。

性能考量

在现代计算机上，使用高分辨率（如 2019 年的 4K）时，这个软件光线投射器会比 GPU 用 3D 显卡渲染的某些复杂得多的 3D 图形更慢。

本教程光线投射代码至少有两个影响速度的问题，如果你想为超高分辨率制作极速光线投射器，可以考虑这些：



下一部分

直接跳转到第二部分


最后编辑：2020 年

版权所有（c）2004-2020 Lode Vandevenne。保留所有权利。