9.8 范例：追踪光线 (Example: Ray-Tracing)

作为一个数值应用的范例，本节示范了如何撰写一个光线追踪器 (ray-tracer)。光线追踪是一个高级的 (deluxe)渲染算法: 它产生出逼真的图像，但需要花点时间。

要产生一个 3D 的图像，我们至少需要定义四件事: 一个观测点 (eye)、一个或多个光源、一个由一个或多个平面所组成的模拟世界 (simulated world)，以及一个作为通往这个世界的窗户的平面 (图像平面「image plane」)。我们产生出的是模拟世界投影在图像平面区域的图像。

光线追踪独特的地方在于，我们如何找到这个投影: 我们一个一个像素地沿着图像平面走，追踪回到模拟世界里的光线。这个方法带来三个主要的优势: 它让我们容易得到现实世界的光学效应 (optical effect)，如透明度 (transparency)、反射光 (reflected light)以及产生阴影 (cast shadows)；它让我们可以直接用任何我们想要的几何的物体，来定义出模拟的世界，而不需要用多边形 (polygons)来建构它们；以及它很简单实现。

  1. (defun sq (x) (* x x))
  3. (defun mag (x y z)
  4.   (sqrt (+ (sq x) (sq y) (sq z))))
  6. (defun unit-vector (x y z)
  7.   (let ((d (mag x y z)))
  8.     (values (/ x d) (/ y d) (/ z d))))
  10. (defstruct (point (:conc-name nil))
  11.   x y z)
  13. (defun distance (p1 p2)
  14.   (mag (- (x p1) (x p2))
  15.        (- (y p1) (y p2))
  16.        (- (z p1) (z p2))))
  18. (defun minroot (a b c)
  19.   (if (zerop a)
  20.       (/ (- c) b)
  21.       (let ((disc (- (sq b) (* 4 a c))))
  22.         (unless (minusp disc)
  23.           (let ((discrt (sqrt disc)))
  24.             (min (/ (+ (- b) discrt) (* 2 a))
  25.                  (/ (- (- b) discrt) (* 2 a))))))))

图 9.2 实用数学函数

图 9.2 包含了我们在光线追踪器里会需要用到的一些实用数学函数。第一个 sq ，返回其参数的平方。下一个 mag ，返回一个给定 x y z 所组成向量的大小 (magnitude)。这个函数被接下来两个函数用到。我们在 unit-vector 用到了，此函数返回三个数值，来表示与单位向量有着同样方向的向量，其中向量是由 x y z 所组成的:

  1. > (multiple-value-call #'mag (unit-vector 23 12 47))
  2. 1.0

我们在 distance 也用到了 mag ，它返回三维空间中，两点的距离。（定义 point 结构来有一个 nil 的 conc-name 意味着栏位存取的函数会有跟栏位一样的名字: 举例来说， x 而不是 point-x 。)

最后 minroot 接受三个实数， a , b 与 c ，并返回满足等式 \(ax^2+bx+c=0\) 的最小实数 x 。当 a 不为 \(0\) 时，这个等式的根由下面这个熟悉的式子给出:

\[x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]

图 9.3 包含了定义一个最小光线追踪器的代码。 它产生通过单一光源照射的黑白图像，与观测点 (eye)处于同个位置。 (结果看起来像是闪光摄影术 (flash photography)拍出来的)

surface 结构用来表示模拟世界中的物体。更精确的说，它会被 included 至定义具体类型物体的结构里，像是球体 (spheres)。 surface 结构本身只包含一个栏位: 一个 color 范围从 0 (黑色) 至 1 (白色)。

  1. (defstruct surface color)
  3. (defparameter *world* nil)
  4. (defconstant eye (make-point :x 0 :y 0 :z 200))
  6. (defun tracer (pathname &optional (res 1))
  7.   (with-open-file (p pathname :direction :output)
  8.     (format p "P2 ~A ~A 255" (* res 100) (* res 100))
  9.     (let ((inc (/ res)))
  10.       (do ((y -50 (+ y inc)))
  11.           ((< (- 50 y) inc))
  12.         (do ((x -50 (+ x inc)))
  13.             ((< (- 50 x) inc))
  14.           (print (color-at x y) p))))))
  16. (defun color-at (x y)
  17.   (multiple-value-bind (xr yr zr)
  18.                        (unit-vector (- x (x eye))
  19.                                     (- y (y eye))
  20.                                     (- 0 (z eye)))
  21.     (round (* (sendray eye xr yr zr) 255))))
  23. (defun sendray (pt xr yr zr)
  24.   (multiple-value-bind (s int) (first-hit pt xr yr zr)
  25.     (if s
  26.         (* (lambert s int xr yr zr) (surface-color s))
  27.         0)))
  29. (defun first-hit (pt xr yr zr)
  30.   (let (surface hit dist)
  31.     (dolist (s *world*)
  32.       (let ((h (intersect s pt xr yr zr)))
  33.         (when h
  34.           (let ((d (distance h pt)))
  35.             (when (or (null dist) (< d dist))
  36.               (setf surface s hit h dist d))))))
  37.     (values surface hit)))
  39. (defun lambert (s int xr yr zr)
  40.   (multiple-value-bind (xn yn zn) (normal s int)
  41.     (max 0 (+ (* xr xn) (* yr yn) (* zr zn)))))

图 9.3 光线追踪。

图像平面会是由 x 轴与 y 轴所定义的平面。观测者 (eye) 会在 z 轴，距离原点 200 个单位。所以要在图像平面可以被看到，插入至 *worlds* 的表面 (一开始为 nil)会有着负的 z 座标。图 9.4 说明了一个光线穿过图像平面上的一点，并击中一个球体。

../_images/Figure-9.4.png

图 9.4: 追踪光线。

函数 tracer 接受一个路径名称，并写入一张图片至对应的文件。图片文件会用一种简单的 ASCII 称作 PGM 的格式写入。默认情况下，图像会是 100x100 。我们 PGM 文件的标头 (headers) 会由标签 P2 组成，伴随着指定图片宽度 (breadth)与高度 (height)的整数，初始为 100，单位为 pixel，以及可能的最大值 (255)。文件剩余的部份会由 10000 个介于 0 (黑)与 1 (白)整数组成，代表着 100 条 100 像素的水平线。

图片的解析度可以通过给入明确的 res 来调整。举例来说，如果 res 是 2 ，则同样的图像会被渲染成 200x200 。

图片是一个在图像平面 100x100 的正方形。每一个像素代表着穿过图像平面抵达观测点的光的数量。要找到每个像素光的数量， tracer 调用 color-at 。这个函数找到从观测点至该点的向量，并调用 sendray 来追踪这个向量回到模拟世界的轨迹； sandray 会返回一个数值介于 0 与 1 之间的亮度 (intensity)，之后会缩放成一个 0 至 255 的整数来显示。

要决定一个光线的亮度， sendray 需要找到光是从哪个物体所反射的。要办到这件事，我们调用 first-hit ，此函数研究在 *world* 里的所有平面，并返回光线最先抵达的平面（如果有的话）。如果光没有击中任何东西， sendray 仅返回背景颜色，按惯例是 0 (黑色)。如果光线有击中某物的话，我们需要找出在光击中时，有多少数量的光照在该平面。

朗伯定律 告诉我们，由平面上一点所反射的光的强度，正比于该点的单位法向量 (unit normal vector) N (这里是与平面垂直且长度为一的向量)与该点至光源的单位向量 L 的点积 (dot-product):

\[i = N·L\]

如果光刚好照到这点， N 与 L 会重合 (coincident)，则点积会是最大值， 1 。如果将在这时候将平面朝光转 90 度，则 N 与 L 会垂直，则两者点积会是 0 。如果光在平面后面，则点积会是负数。

在我们的程序里，我们假设光源在观测点 (eye)，所以 lambert 使用了这个规则来找到平面上某点的亮度 (illumination)，返回我们追踪的光的单位向量与法向量的点积。

在 sendray 这个值会乘上平面的颜色 (即便是有好的照明，一个暗的平面还是暗的)来决定该点之后总体亮度。

为了简单起见，我们在模拟世界里会只有一种物体，球体。图 9.5 包含了与球体有关的代码。球体结构包含了 surface ，所以一个球体会有一种颜色以及 center 和 radius 。调用 defsphere 添加一个新球体至世界里。

  1. (defstruct (sphere (:include surface))
  2.   radius center)
  4. (defun defsphere (x y z r c)
  5.   (let ((s (make-sphere
  6.              :radius r
  7.              :center (make-point :x x :y y :z z)
  8.              :color  c)))
  9.     (push s *world*)
  10.     s))
  12. (defun intersect (s pt xr yr zr)
  13.   (funcall (typecase s (sphere #'sphere-intersect))
  14.            s pt xr yr zr))
  16. (defun sphere-intersect (s pt xr yr zr)
  17.   (let* ((c (sphere-center s))
  18.          (n (minroot (+ (sq xr) (sq yr) (sq zr))
  19.                      (* 2 (+ (* (- (x pt) (x c)) xr)
  20.                              (* (- (y pt) (y c)) yr)
  21.                              (* (- (z pt) (z c)) zr)))
  22.                      (+ (sq (- (x pt) (x c)))
  23.                         (sq (- (y pt) (y c)))
  24.                         (sq (- (z pt) (z c)))
  25.                         (- (sq (sphere-radius s)))))))
  26.     (if n
  27.         (make-point :x  (+ (x pt) (* n xr))
  28.                     :y  (+ (y pt) (* n yr))
  29.                     :z  (+ (z pt) (* n zr))))))
  31. (defun normal (s pt)
  32.   (funcall (typecase s (sphere #'sphere-normal))
  33.            s pt))
  35. (defun sphere-normal (s pt)
  36.   (let ((c (sphere-center s)))
  37.     (unit-vector (- (x c) (x pt))
  38.                  (- (y c) (y pt))
  39.                  (- (z c) (z pt)))))

图 9.5 球体。

函数 intersect 判断与何种平面有关，并调用对应的函数。在此时只有一种， sphere-intersect ，但 intersect 是写成可以容易扩展处理别种物体。

我们要怎么找到一束光与一个球体的交点 (intersection)呢？光线是表示成点 \(p =〈x_0,y_0,x_0〉\) 以及单位向量 \(v =〈x_r,y_r,x_r〉\) 。每个在光上的点可以表示为 \(p+nv\) ，对于某个 n ── 即 \(〈x_0+nx_r,y_0+ny_r,z_0+nz_r〉\) 。光击中球体的点的距离至中心 \(〈x_c,y_c,z_c〉\) 会等于球体的半径 r 。所以在下列这个交点的方程序会成立:

\[r = \sqrt{ (x_0 + nx_r - x_c)^2 + (y_0 + ny_r - y_c)^2 + (z_0 + nz_r - z_c)^2 }\]

这会给出

\[an^2 + bn + c = 0\]

其中

\[\begin{split}a = x_r^2 + y_r^2 + z_r^2\\b = 2((x_0-x_c)x_r + (y_0-y_c)y_r + (z_0-z_c)z_r)\\c = (x_0-x_c)^2 + (y_0-y_c)^2 + (z_0-z_c)^2 - r^2\end{split}\]

要找到交点我们只需要找到这个二次方程序的根。它可能是零、一个或两个实数根。没有根代表光没有击中球体；一个根代表光与球体交于一点 (擦过 「grazing hit」)；两个根代表光与球体交于两点 (一点交于进入时、一点交于离开时)。在最后一个情况里，我们想要两个根之中较小的那个； n 与光离开观测点的距离成正比，所以先击中的会是较小的 n 。所以我们调用 minroot 。如果有一个根， sphere-intersect 返回代表该点的 \(〈x_0+nx_r,y_0+ny_r,z_0+nz_r〉\) 。

图 9.5 的另外两个函数， normal 与 sphere-normal 类比于 intersect 与 sphere-intersect 。要找到垂直于球体很简单 ── 不过是从该点至球体中心的向量而已。

图 9.6 示范了我们如何产生图片； ray-test 定义了 38 个球体（不全都看的见）然后产生一张图片，叫做 “sphere.pgm” 。

(译注：PGM 可移植灰度图格式，更多信息参见 wiki )

  1. (defun ray-test (&optional (res 1))
  2.   (setf *world* nil)
  3.   (defsphere 0 -300 -1200 200 .8)
  4.   (defsphere -80 -150 -1200 200 .7)
  5.   (defsphere 70 -100 -1200 200 .9)
  6.   (do ((x -2 (1+ x)))
  7.       ((> x 2))
  8.     (do ((z 2 (1+ z)))
  9.         ((> z 7))
  10.       (defsphere (* x 200) 300 (* z -400) 40 .75)))
  11.   (tracer (make-pathname :name "spheres.pgm") res))

图 9.6 使用光线追踪器

图 9.7 是产生出来的图片，其中 res 参数为 10。

../_images/Figure-9.7.png

图 9.7: 追踪光线的图

一个实际的光线追踪器可以产生更复杂的图片，因为它会考虑更多，我们只考虑了单一光源至平面某一点。可能会有多个光源，每一个有不同的强度。它们通常不会在观测点，在这个情况程序需要检查至光源的向量是否与其他平面相交，这会在第一个相交的平面上产生阴影。将光源放置于观测点让我们不需要考虑这麽复杂的情况，因为我们看不见在阴影中的任何点。

一个实际的光线追踪器不仅追踪光第一个击中的平面，也会加入其它平面的反射光。一个实际的光线追踪器会是有颜色的，并可以模型化出透明或是闪耀的平面。但基本的算法会与图 9.3 所演示的差不多，而许多改进只需要递回的使用同样的成分。

一个实际的光线追踪器可以是高度优化的。这里给出的程序为了精简写成，甚至没有如 Lisp 程序员会最佳化的那样，就仅是一个光线追踪器而已。仅加入类型与行内宣告 (13.3 节)就可以让它变得两倍以上快。