实践-光线追踪1

全局光照

多数程序员听到 3D / CG ，就会联想到 Direct3D 、OpenGL 等 API。事实上，这些流行的 API 主要为实时渲染 ( real-time rendering ) 而设，一般采用光栅化 ( rasterization ) 方式，渲染大量的三角形 ( 或其他几何图元种类 ( primitive types ) )。

这种基于光栅化的渲染系统，只支持局部光照(local illumination)。换句话说，渲染几何图形的一个像素时，光照计算只能取得该像素的资讯，而不能访问其他几何图形资讯。

理论上，阴影 (shadow) 、反射 (reflection) 、折射 (refraction) 等为全局光照 (global illumination) 效果，实际上，栅格化渲染系统可以使用预处理 ( 如阴影贴图 ( shadow mapping )、环境贴图 ( environment mapping ))去模拟这些效果。

全局光照计算量大，一般也没有特殊硬件加速(通常只使用 CPU 而非 GPU )，所以只适合离线渲染 (offline rendering)，例如3D Studio Max、Maya等工具。

其中一个支持全局光照的方法，称为光线追踪 (ray tracing) 。光线追踪能简单直接地支持阴影、反射、折射，实现起来亦非常容易。

本文的例子里，只用了数十行JavaScript代码 (除canvas外不需要其他特殊插件和库)，就能实现一个支持反射的光线追踪渲染器。

光线追踪可以用来学习很多计算机图形学的课题，也许比学习 Direct3D / OpenGL 更容易。现在，先介绍点理论吧。

光线追踪

光栅化渲染，简单地说，就是把大量三角形画到屏幕上。当中会采用深度缓冲 (depth buffer, z-buffer) ，来解决多个三角形重叠时的前后问题。三角形数目影响效能，但三角形在屏幕上的总面积才是主要瓶颈。

光线追踪，简单地说，就是从摄影机的位置，通过影像平面上的像素位置(比较正确的说法是取样(sampling)位置)，发射一束光线到场景，求光线和几何图形间最近的交点，再求该交点的着色。如果该交点的材质是反射性的，可以在该交点向反射方向继续追踪。

光线追踪除了容易支持一些全局光照效果外，亦不局限于三角形作为几何图形的单位。任何几何图形，能与一束光线计算交点(intersection point)，就能支持。

TIP

TODO img

上图(來源)显示了光线追踪的基本方式。要计算一点是否在阴影之内，也只须发射一束光线到光源，检测中间有没有障碍物而已。不过光源和阴影留待下回分解。

初试画板

光线追踪的输出只是一个影像(image)，所谓影像，就是二维颜色数组。

要在浏览器内，用JavaScript生成一个影像，目前可以使用HTML 5的 <canvas>。但现时Internet Explorer(直至版本8) <canvas>，其他浏览器如Chrome、Firefox、Opera等就可以。

以下是一个简单的实验，把每个象素填入颜色，左至右越来越红，上至下越来越绿。

var canvas = document.getElementById("demo24_1");
var ctx = canvas.getContext("2d");
var w = canvas.attributes.width.value;
var h = canvas.attributes.height.value;
ctx.fillStyle = "rgb(0,0,0)";
ctx.fillRect(0, 0, w, h);
var imgdata = ctx.getImageData(0, 0, w, h);
var pixels = imgdata.data;
var i = 0;
for (var y = 0; y < h; y++)
    for (var x = 0; x < w; x++)
    {
        pixels[i++] = x / w * 255;
        pixels[i++] = y / h * 255;
        pixels[i++] = 0;
        pixels[i++] = 255;
    }
ctx.putImageData(imgdata, 0, 0);

渲染结果

这实验说明，从canvas取得的影像资料canvas.getImageData(...).data是个一维数组，该数组每四个元素代表一个象素(按红, 绿, 蓝, alpha排列)，这些象素在影像中从上至下、左至右排列。

解决实验平台的技术问题后，可开始从基础类别开始实现。

基础类

三维向量

三维向量(3D vector)可谓CG里最常用型别了。这里三维向量用 Vector3 类实现，用(x, y, z)表示。 Vector3 亦用来表示空间中的点(point)，而不另建类。先看代码：

export const Vector3 = function (x, y, z) {
  this.x = x;
  this.y = y;
  this.z = z;
};

Vector3.prototype = {
  copy: function () {
    return new Vector3(this.x, this.y, this.z);
  },
  length: function () {
    return Math.sqrt(this.x * this.x + this.y * this.y + this.z * this.z);
  },
  sqrLength: function () {
    return this.x * this.x + this.y * this.y + this.z * this.z;
  },
  normalize: function () {
    var inv = 1 / this.length();
    return new Vector3(this.x * inv, this.y * inv, this.z * inv);
  },
  negate: function () {
    return new Vector3(-this.x, -this.y, -this.z);
  },
  add: function (v) {
    return new Vector3(this.x + v.x, this.y + v.y, this.z + v.z);
  },
  subtract: function (v) {
    return new Vector3(this.x - v.x, this.y - v.y, this.z - v.z);
  },
  multiply: function (f) {
    return new Vector3(this.x * f, this.y * f, this.z * f);
  },
  divide: function (f) {
    var invf = 1 / f;
    return new Vector3(this.x * invf, this.y * invf, this.z * invf);
  },
  dot: function (v) {
    return this.x * v.x + this.y * v.y + this.z * v.z;
  },
  cross: function (v) {
    return new Vector3(
      -this.z * v.y + this.y * v.z,
      this.z * v.x - this.x * v.z,
      -this.y * v.x + this.x * v.y
    );
  }
};

Vector3.zero = new Vector3(0, 0, 0);

这些类方法(如 normalize、negate、add 等)，如果传回 Vector3 类对象，都会传回一个新建构的Vector3。这些三维向量的功能很简单，不在此详述。

注意 multiply 和 divide 是与纯量(scalar)相乘和相除。

Vector3.zero用作常量，避免每次重新构建。值得一提，这些常量必需在prototype设定之后才能定义。

光线

所谓光线(ray)，从一点向某方向发射也。数学上可用参数函数 (parametric function) 表示：

$\vec{r}(t) = o + t\vec{d}, t\geq{0}$

当中，o即发谢起点(origin)，d为方向。在本文的例子里，都假设d为单位向量(unit vector)，因此t为距离。实现如下：

export const Ray3 = function (origin, direction) {
  this.origin = origin;
  this.direction = direction;
};

Ray3.prototype = {
  getPoint: function (t) {
    return this.origin.add(this.direction.multiply(t));
  }
};

球体

球体(sphere)是其中一个最简单的立体几何图形。这里只考虑球体的表面(surface)，中心点为c、半径为r的球体表面可用等式(equation)表示：

$||\vec{x} - \vec{c}|| = r$

如前文所述，需要计算光线和球体的最近交点。只要把光线 x = r(t) 代入球体等式，把该等式求解就是交点。为简化方程，设 v = o - c，则:

$\begin{aligned} \vec{c} = \vec{v} - \vec{o} \\ x = \vec{o} + t\vec{d} \\ || \vec{x} - \vec{c} || = r \\ || \vec{v} + t\vec{d} || = r \\ || \vec{v} + t\vec{d} ||^2 = r^2 \\ (\vec{v} + t\vec{d})(v + t\vec{d}) - r^2 = 0 \\ \vec{v}^2 + 2(\vec{d}\cdot\vec{v})t + t^2\vec{d}^2 - r^ 2 = 0 \\ t^2\vec{d}^2 + 2(\vec{d}\cdot\vec{v})t + \vec{v}^2 - r^ 2 = 0 \\ \end{aligned}$

因为d为单位向量，所以二次方的系数可以消去。

$t^2 + 2(\vec{d} \cdot \vec{v})t + \vec{v}^2 - r^ 2 = 0$

t 的二次方程式的解为

$\begin{aligned} t = \frac{-2\vec{d}\cdot\vec{v}\pm \sqrt{(2\vec{d}\cdot\vec{v})^2 - 4 (\vec{v}^2 - r^2)}} 2 \\ t = -\vec{d}\cdot\vec{v}\pm \sqrt{(\vec{d}\cdot\vec{v})^2 - (\vec{v}^2 - r^2)} \end{aligned}$

若根号内为负数，即相交不发生。另外，由于这里只需要取最近的交点，因此正负号只需取负号。代码实现如下：

IntersectResult = function() {
  this.geometry = null;
  this.distance = 0;
  this.position = Vector3.zero;
  this.normal = Vector3.zero;
};

IntersectResult.noHit = new IntersectResult();

export const Sphere = function (center, radius) {
  this.center = center;
  this.radius = radius;
};

Sphere.prototype = {
  copy: function () {
    return new Sphere(this.center.copy(), this.radius.copy());
  },

  initialize: function () {
    this.sqrRadius = this.radius * this.radius;
  },

  intersect: function (ray) {
    const v = ray.origin.subtract(this.center); // 球体指向光线光源的向量 v
    const delta = v.sqrLength() - this.sqrRadius; //  v^2 - r^2
    const DdotV = ray.direction.dot(v); // 光线的方向向量 点乘 球体指向光源的向量 d * v

    if (DdotV <= 0) {
      const discr = DdotV * DdotV - delta;  // 根号内
      if (discr >= 0) {
        const result = new IntersectResult();
        result.geometry = this;
        result.distance = - DdotV - Math.sqrt(discr); // 光线和球体的距离
        result.position = ray.getPoint(result.distance);
        result.normal = result.position.subtract(this.center).normalize();
        return result;
      }
    }

    return IntersectResult.noHit;
  }
};

这里用到一个IntersectResult类，这个类只用来记录交点的几何物件(geometry)、距离(distance)、位置(position)和法向量(normal)。 IntersectResult.noHit的 geometry 为null，代表光线没有和任何几何物件相交。

摄像机

摄影机在光线追踪系统里，负责把影像的取样位置，生成一束光线。

由于影像的大小是可变的(多少像素宽x多少像素高)，为方便计算，这里设定一个统一的取样座标(sx, sy)，以左下角为(0,0)，右上角为(1 ,1)。

从数学角度来说，摄影机透过投影(projection)，把三维空间投射到二维空间上。常见的投影有正投影(orthographic projection)、透视投影(perspective projection)等等。

透视摄影机

透视摄影机比较像肉眼和真实摄影机的原理，能表现远小近大的观察方式。透视投影从视点(view point/eye position)，向某个方向观察场景，观察的角度范围称为视野(field of view, FOV)。除了定义观察的向前(forward)是那个方向，还需要定义在影像平面中，何谓上下和左右。为简单起见，暂时不考虑宽高不同的影像，FOV同时代表水平和垂直方向的视野角度。

TIP

TODO img

上图显示，从摄影机上方显示的几个参数。 forward和right分别是向前和向右的单位向量。

因为视点是固定的，光线的起点不变。要生成光线，只须用取样座标 ( sx, sy) 计算其方向d。留意 FOV 和 s 的关系为：

$tan(\frac{FOV}{2}) = s$

把 sx 从 [0, 1] 映射到 [-1 , 1]，就可以用 right 向量和 s，来计算r向量，代码如下:

import { Ray3 } from "./light.js";
export const PerspectiveCamera = function (eye, front, up, fov) {
  this.eye = eye;
  this.front = front;
  this.refUp = up;
  this.fov = fov;
};

PerspectiveCamera.prototype = {
  initialize: function () {
    this.right = this.front.cross(this.refUp);
    this.up = this.right.cross(this.front);
    this.fovScale = Math.tan((this.fov * 0.5 * Math.PI) / 180) * 2;
  },

  generateRay: function (x, y) {
    const r = this.right.multiply((x - 0.5) * this.fovScale);
    const u = this.up.multiply((y - 0.5) * this.fovScale);
    return new Ray3(this.eye, this.front.add(r).add(u).normalize());
  }
};

代码中fov为度数，转为弧度才能使用Math.tan()。另外，fovScale预先乘了2，因为sx映射到[-1,1]每次都要乘以2。 sy和sx的做法一样，把两个在影像平面的向量，加上forward向量，就成为光线方向d。因之后的计算需要，最后把d变成单位向量。

渲染测试

写了Vector3、Ray3、Sphere、IntersectResult、Camera五个类之后，终于可以开始渲染一点东西出来！

基本的做法是遍历影像的取样座标(sx, sy)，用Camera把(sx, sy)转为Ray3，和场景(例如Sphere)计算最近交点，把该交点的属性转为颜色，写入影像的相对位置里。把不同的属性渲染出来，是CG编程里经常用的测试和调试手法。

渲染深度

深度(depth)就是从IntersectResult取得最近相交点的距离，因深度的范围是从零至无限，为了把它显示出来，可以把它的一个区间映射到灰阶。这里用[0, maxDepth]映射至[255, 0]，即深度 0 的像素为白色，深度达 maxDepth 的像素为黑色。

function renderDepth(canvas, scene, camera, maxDepth) {
  const ctx = canvas.getContext("2d");
  const w = canvas.width;
  const h = canvas.height;
  ctx.fillStyle = "rgb(0,0,0)";
  ctx.fillRect(0, 0, w, h);
  const imgdata = ctx.getImageData(0, 0, w, h);
  const pixels = imgdata.data;
  //
  scene.initialize();
  camera.initialize();
  let i = 0;
  for (let y = 0; y < h; y++) {
    let sy = 1 - y / h; // 裁切空间坐标
    for (var x = 0; x < w; x++) {
      let sx = x / w; // 裁切空间坐标
      var ray = camera.generateRay(sx, sy);
      var result = scene.intersect(ray);
      if (result.geometry) {
        var depth = 255 - Math.min((result.distance / maxDepth) * 255, 255);
        pixels[i] = depth;
        pixels[i + 1] = depth;
        pixels[i + 2] = depth;
        pixels[i + 3] = 255;
      }
      i += 4;
    }
  }
  //
  ctx.putImageData(imgdata, 0, 0);
}

const canvas = document.getElementById("demo24_02");
const scene = new Sphere(new Vector3(0, 10, -10), 10);
const camera = new PerspectiveCamera(
  new Vector3(0, 10, 10),
  new Vector3(0, 0, -1),
  new Vector3(0, 1, 0),
  90
);
const maxDepth = 20;
renderDepth(canvas, scene, camera, maxDepth);

渲染法向量

相交测试也计算了几何物件在相交位置的法向量，这里也可把它视觉化。

法向量是一个单位向量，其每个元素的范围是[-1, 1]。把单位向量映射到颜色的常用方法为，把 (x, y, z) 映射至 (r, g, b)，范围从[-1, 1]映射至[0, 255]。

function renderNormal(canvas, scene, camera) {
  const ctx = canvas.getContext("2d");
  const w = canvas.width;
  const h = canvas.height;
  ctx.fillStyle = "rgb(0,0,0)";
  ctx.fillRect(0, 0, w, h);
  const imgdata = ctx.getImageData(0, 0, w, h);
  const pixels = imgdata.data;
  //
  scene.initialize();
  camera.initialize();
  let i = 0;
  for (let y = 0; y < h; y++) {
    let sy = 1 - y / h; // 裁切空间坐标
    for (var x = 0; x < w; x++) {
      let sx = x / w; // 裁切空间坐标
      var ray = camera.generateRay(sx, sy);
      var result = scene.intersect(ray);
      if (result.geometry) {
        pixels[i] = (result.normal.x + 1) * 128;
        pixels[i + 1] = (result.normal.y + 1) * 128;
        pixels[i + 2] = (result.normal.z + 1) * 128;
        pixels[i + 3] = 255;
      }
      i += 4;
    }
  }
  //
  ctx.putImageData(imgdata, 0, 0);
}