Question

Graphics

Graphics 是绘画、制图的意思。左图是 2D 绘图、右图是 3D 绘图，相信大家一眼就能看出差异：

Image 的演算法著重于让既有图片产生变化，Graphics 的演算法专注于从无到有产生图片。两者相辅相成、密不可分。

2D Graphics

先前已经介绍过“像素 Pixel”。2D 绘图就是逐步设定每个像素的 RGB 值，呈现我们想要的图案。

以人工方式，一点一点设定每个像素的 RGB 值，称作 Pixel Art ，常常出现于电玩游戏及牆壁磁砖。

以演算法，一点一点设定每个像素的 RGB 值，则是这裡要谈的重点。

2D Graphics 相关资源

C 与 C++没有 2D 绘图的函式库。更高阶的程式语言都有内建 2D 绘图函式库，例如 Qt 的 QPaint、C#的 Graphics、Java 的 Graphics。

知名的 2D 绘图工具，例如 HTML5 Canvas 。

知名的 2D 绘图软体，诸如 Microsoft Paint 、 AutoCAD 、 Microsoft Visio 、 Adobe Illustrator 等等。

Shape Rendering

Shape Rendering

前言

想要画一张複杂的图，无论是艺术家还是数学家，都是从简单的几何形状：直线、方、圆开始。本篇文章将介绍如何绘制简单的几何形状。

Shape Rendering 的演算法已经在显示卡上烧成电路、并且包装成函式库。前人种树后人乘凉，我们大可不必痛下苦功编写程式码。然而本篇文章不谈函式库。

Shape Rendering 拥有相关的档案格式 SVG 。然而本篇文章不谈资料结构。

操控键盘滑鼠即时绘制图形，我们需要了解监听和处理事件的机制。然而本篇文章不谈事件处理。

绘制直线、曲线、方形、圆形等等图形，管理键盘、滑鼠、视窗等等介面，我们需要规划编排大量程式码。然而本篇文章不谈物件导向。

Shape Rendering 的软体已经发展成熟。然而本篇文章不谈如何制作软体，也不谈如何使用软体。

像素

直线

给定线段的两个端点，如何找到线段对应的像素呢？

脑筋灵活的读者肯定马上联想到 线性内插 。不过像素看起来零零散散的，根本没有连成一线。

Font Rendering

Font Rendering

gsave newpath 509 711 moveto 203 711 lineto 167 657 127 607 87 569 curveto 78 583 58 611 45 624 curveto 106 677 166 756 201 839 curveto 262 821 lineto 254 801 244 783 233 763 curveto 509 763 lineto 509 711 lineto closepath 389 633 moveto 332 611 lineto 324 633 306 664 288 687 curveto 345 706 lineto 361 684 381 653 389 633 curveto closepath 769 503 moveto 769 564 lineto 247 564 lineto 247 503 lineto 769 503 lineto closepath 769 397 moveto 769 458 lineto 247 458 lineto 247 397 lineto 769 397 lineto closepath 769 288 moveto 769 352 lineto 247 352 lineto 247 288 lineto 769 288 lineto closepath 646 150 moveto 646 242 lineto 385 242 lineto 385 176 lineto 385 168 385 159 384 150 curveto 646 150 lineto closepath 952 765 moveto 952 712 lineto 776 712 lineto 800 689 826 658 839 636 curveto 785 610 lineto 774 633 748 666 725 690 curveto 773 712 lineto 624 712 lineto 599 673 570 637 539 610 curveto 837 610 lineto 837 242 lineto 713 242 lineto 713 150 lineto 944 150 lineto 944 94 lineto 713 94 lineto 713 -74 lineto 646 -74 lineto 646 94 lineto 371 94 lineto 348 31 287 -32 144 -81 curveto 135 -67 116 -44 102 -32 curveto 218 3 273 49 298 94 curveto 59 94 lineto 59 150 lineto 316 150 lineto 318 160 318 169 318 177 curveto 318 242 lineto 181 242 lineto 181 610 lineto 537 610 lineto 524 620 496 636 481 643 curveto 540 691 592 763 620 839 curveto 682 825 lineto 675 804 666 785 656 765 curveto 952 765 lineto closepath fill grestore gsave newpath 292 31 moveto 767 31 lineto 841 31 857 68 864 236 curveto 883 226 912 216 932 212 curveto 919 9 883 -37 762 -37 curveto 301 -37 lineto 161 -37 93 13 93 96 curveto 93 167 120 243 648 684 curveto 98 684 lineto 98 752 lineto 741 752 lineto 756 757 lineto 803 724 lineto 800 720 795 717 790 714 curveto 198 227 164 154 164 101 curveto 164 53 217 31 292 31 curveto closepath fill grestore

Character

Character 就是电脑符号。译作“字元”或“字符”。

电脑符号都有编号。世界公定的编号方式是 Unicode 。例如第 30399 号是“算”，第 9775 号是“☯”。电脑符号包括了世界各国文字、数字、图示、表情符号等等。

电脑符号必须编码，节省储存空间。Unicode 有著 UTF-8 和 UTF-16 两种主流的编码方式。

字元编码，是 编码理论 的范畴。字元操作，是 字串理论 的范畴。字元显示，是 计算机绘图 的范畴，是我们现在要谈的内容。

Font

Font 就是文字的造型。译作“字体”或“字型”。

从书写的观点：中文字体有楷书、行书、草书、隶书、篆书等五大类，有名的楷书如颜真卿、柳公权等等。字体是书法家发明的。

从电脑的观点：繁体中文字型有标楷体、细明体、微软正黑体等等。英文字型有 Times New Roman、Verdana、Arial 等等。字型是美术设计师和程式设计师发明的。

只要有文字的地方，通常都能更换字型，例如文字编辑器、浏览器、作业系统、命令提示字元。电脑可供使用的字型，主要是看你的电脑安装了哪些字型。有专门制作字型、贩售字型的公司，例如专精繁体中文字型的 JustFont 、 文鼎 、 华康 。亦有人号召制作字型，例如 文泉驿 。

电脑显示字元，必须透过字型。每一套字型都只替一部分的字元设计造型，例如 Times New Roman 只设计了英文字母、拉丁字母、少量的特殊符号，例如微软正黑体只设计了英文字母、中文字、少量的特殊符号。一套字型当中，没有设计造型的字元，就无法显示，或者是显示问号、空白方格等等莫名其妙的符号。儘管 现今没有任何一套字型涵盖 Unicode 规定的所有字元 ，不过 其实也不需要一套万能的字型 。对于没有设计造型的字元，作业系统将另寻其他字型。

字型由作业系统控管。想要让视窗程式显示特定字型，土法炼钢的方式是 Windows API ，轻鬆写意的方式是程式语言内建的函式库。想要让网页显示特定字型，利用 CSS 的 font-family 即可。

Glyph

接著到了本篇文章的主角“字形”。 首先玩个小游戏吧 ！拖曳控制点，按 Enter 评分。美感和眼力必须很杰出。设计师的日常。

“字形”就是单独一个字元的形状。由演算法自动调整形状，或由文字设计师手动调整形状。

Glyph 的资料结构

共三种：点阵字 dot-matrix、笔画字 stroke、轮廓字 outline。

点阵字 ：用黑色方格（像素）拼成字形。

电脑已经淘汰点阵字型了，例如 Fixedsys 。然而有些字型为了支援极小尺寸，仍会搭配点阵字型，例如 文泉驿点阵宋 。

点阵字使用最多的地方不是电脑，而是电子辞典、大众运输的 LCD 跑马灯、统一发票。

笔划字：直觉的方式。特别适合汉字。

记录起点座标、终点座标、写法（永字八法：侧勒努趯策掠啄磔）（ 英文字母笔划剖析 ）、曲率参数、变换矩阵。最后以演算法加粗笔划，生成字型。优点是容易创造新字型，缺点是美感不佳。累死工程师、闷死设计师。

可惜的是，我们无法获得笔划资料。中文笔画资料，属于商业机密，更有 专利保护 。大家不得其门而入。例如 王汉宗字型 侵权案，个人猜测是 从神秘管道得到笔划资料 ，再自创加粗笔划的演算法。

可惜的是，我们无法得知笔划加粗的演算法。即便是开源字型，也从未公开演算法。必须跟字型公司签技术合作。

这多少阻碍了 组字 、 造字 、 文字资料库 、 笔划检索 、 手写辨识 的进展。

轮廓字：公定的方式。现今字型皆是轮廓字。

轮廓由许多线条组成，线条一律是“ 直线线段 ：两个端点”和“ Bézier Curve ：两个端点与两个控制点”。最后以演算法填充轮廓内部，生成字型。

幸运的是，我们可以获得轮廓资料。安装免费开源的字形编辑软体 FontForge ，下载免费开源的字型 思源黑体 、 文泉驿正黑 ，将字形汇出成.eps 或.svg 档案即得。上面的“算”就是这样来的。

注意到，字型都有著作权，未经授权不可使用字型档案裡面的数据，即使免费。读者做实验时，一定要记得选择免费且开源的字型，以免触法。

轮廓字的档案格式主要有两种：囊括所有格式的 OpenType（.otf）、早期的 TrueType（.ttc .ttf）。OpenType 是当今主流，网路上有不少资讯。如果你有志鑽研字型渲染，可以自己写程式存取 OpenType 档案，也可以参考开源的字型渲染引擎 FreeType 。

em square：字形的编辑区域

活字印刷当中，em 是指铅字宽度。电脑字型当中，em square 是指字形的编辑区域。就这样。

outlining：描绘轮廓

运用上个章节的绘制直线与绘制曲线演算法即可。

描绘轮廓目前没有公定标准。即便是相同字型相同字形，在 Firefox、Chrome、Windows、OS X 的显示结果通常略有不同。不同的字型渲染引擎，呈现不同结果。你也可以自己写一个。

为了让轮廓座标变成像素座标，这裡介绍一下 pt 和 dpi。

电脑字型大小，单位是 pt (PostScript point)，是长度单位。72pt = 1 英吋，pt 除以 72 得到英吋。电脑字型通常预设 12pt。

长度变成像素数量，单位是 dpi (dot per inch)，每英吋多少点（像素）。电脑萤幕通常是 96dpi，实体印刷至少是 300dpi。

比方说，12pt 字型，96dpi 解析度，一个字形的边长含有 12 / 72 * 96 = 16 个像素。

假设 em square 的边长是 1024。轮廓座标(x,y)，等比例缩放得到像素座标(round(x/1024*16), round(y/1024*16))。

filling：填充轮廓

运用上个章节的 Scanline Fill Algorithm 。轮廓不能交叉重叠，以利判断内外。

如果让轮廓具有方向性，顺时针为正，逆时针为负，则得以设计联集与差集。

overlap removing：重叠的轮廓，简化成一个轮廓

为了顺利填充轮廓，凡是轮廓交叉重叠，就必须重新整合。

有两种状况：一个轮廓自身交叉、两个轮廓互相重叠。

需要处理的事情：求交点、求联集或差集、重新安排顶点顺序。需要的演算法： 线段交点 、 Bézier Curve 交点 、 多边形交集 。不太容易实作，读者可以挑战看看。

字形编辑软体有此功能，节省设计师的作业时间。

hinting / grid fitting：微调字形位置

像素座标只能是整数。座标四捨五入变成整数，可能往左往下跑、可能往右往上跑，笔画粗细有所改变。尤其是字形缩放大小，例如从 12pt 到 14pt，问题更加严重。

像素大小固定。当字形缩小至非常小，例如 6pt，所有笔划通通黏结在一起。此时整个字形都得重新设计，甚至改成点阵字。

目前已经有演算法，可以自动微调字形位置。不过凡事总有例外，仍需设计师人工检视、手动微调。各种常见缩放尺寸，都得一一检视。中文数万字，一字一字做，一日一日做，愚公移山、精卫填海！

anti-aliasing：微调字形边缘的像素数值

在字形边缘设定渐层颜色，使得字形边缘柔顺、清晰。

像素整齐排列。对于一条斜线，黑白显示器，无可避免地，一定有锯齿；灰阶显示器、彩色显示器，则可以微调邻近像素数值，达到平滑效果。演算法共三种。

面积 ：像素视作正方形格子。如果佔据 40%的面积，就将数值设定为 40%，也就是 255 - (255 * 40%) = 153。

距离 ：像素到轮廓的最短距离，非常推荐的方式！把贝兹曲线转换成多项式，再解方程式（求根）求得最短距离。 也可以用分治法 。

分割像素 ：彩色显示器，一个像素由 RGB 三个元件组成，调整 RGB 亮度比重，强调边缘。缺点是边缘五颜六色，相当刺眼，不是每个人都喜欢。最有名的演算法是微软的 ClearType。

metrics：设定字形间距

http://www.freetype.org/freetype2/docs/glyphs/glyphs-3.html

字形的部分已经介绍完毕了，接下来是排版的部分。

FreeType 的说明文件已经有精美图片。这裡就不重画了。

ligature / kerning：微调字形间距

比方来说，AV 合在一起时，视觉感受是留白太多，需要更紧密一点。AB、AD 不需要更紧密，保持原本排版即可。

解法是事先设定特殊组合。OpenType 支援此设定。属于 文字处理 的范畴。

另外还有一种情况，出现于阿拉伯文、泰文等等。这些语言根据语意，衔接或断开字形。

解法是剖析语意。OpenType 没有此设定，由排版引擎自行实作。属于 自然语言处理 的范畴。

未涉及的主题

因为我没有跟字型公司签技术合作，所以知道的事情有限。

一、轮廓字的编辑介面。

二、轮廓字、笔划字、点阵字之间的转换。 华康有个专利 ，演算法是 迴归 。

三、拆字组字。简化字型制作流程。

四、调字。根据环境、根据版面， 自动调整字形 。

五、手写字形。 工程师 （ 详细演算法 ）和 设计师 （ 详细流程 ）有著不同的策略。

六、压缩。减少字型档案大小。例如 Compact Table Format 和 MicroType Express。

七、列印文字。印表机韧体设计。

Font Design

这是设计师的专业。已有人写书拍片，我就不班门弄斧了。

演算法生成的字形 太过呆板 （ 例如墨字的四个点如何点 ）。目前的作业流程是：先由工程师产生大致轮廓，再由设计师调整细节。

繁体中文的笔划写法，台湾政府有订立标准。不过政府标准 不见得是好看的 ， 也不代表是正统的 。

Typeface Design / Typography Design

也许可以看看 spiro curve 、 文字云 、 笔划装饰 。

Math Rendering

画数学式子与画字形，原理相同，只是还要再解决一个问题：数学式子的资料结构为何？目前最流行的方式，是用纯文字记录一道算式，所採用的文法是 TeX 的语法。

读者可以参考 MathJax。

Web Rendering

https://en.wikipedia.org/wiki/Web_browser_engine

3D Graphics

3D Graphics

当今科技，没有任何设备可以清楚呈现 3D 物体。

退而求其次，以 2D 图片呈现 3D 物体。目前公认的做法：将 3D 模型投射到 2D 图片上面，逐一设定每个像素的 RGB 值。

3D 物体投射到 2D 图片，两种方式。

Orthogonal Projection：平行投射至图片，夹角是垂直 90 度。这个方式非常简单，却有一个严重的问题：物体不论远近都一样大，缺乏真实感。

Perspective Projection：聚焦于图片后方一点：远的物体小、近的物体大，稍微符合人类视觉观感。它是主流的方式，此处只介绍它。

聪明的读者肯定马上联想到物理课的“针孔成像”及“摄影机”。虽然 Perspective Projection 与“针孔成像”都有聚焦的概念，但是两者不尽相同。

抑或联想到美术课的“透视图”。虽然 Perspective Projection 与“一点透视图”的外观相同、原理相似，但是两者的制作方式截然不同。

Perspective Projection 细分两种实作方式：

相机到物体：穷举每一个像素，从焦点朝像素射出射线，找到对应的物体。速度极慢，用于电影动画、拟真图片。

物体到相机：穷举每一个物体，从物体射出射线至焦点，找到对应的像素。速度较快，用于电玩游戏、虚拟实境。

“ Camera ”与“ Model ”的观念，源自其他领域。

ICPC 5100

3D Graphics 相关资源

3D 绘图广泛应用于电脑游戏、电影特效、电视广告、模型设计、建筑设计、医学影像等等。像是李安引进台湾的 Rhythm & Hues Studios 公司、比如 CG Taiwaner 教学网站，都属于 3D 绘图领域。

知名的 3D 绘图函式库 ，例如 OpenGL 与 Vulkan 与 GLFW 、 Direct3D 、 PBRT 。浏览器的 3D 绘图函式库，例如 WebGL 、 three.js 。程式语言通常没有内建 3D 绘图函式库，必须另外安装。

知名的 3D 模型资料 ，例如 Infinite-Realities 。

知名的 3D 渲染软体 ，例如 Maxwell Render、LuxRender、Octane Render。

http://www.cmlab.csie.ntu.edu.tw/~ming/courses/icg/
http://www.csie.ntu.edu.tw/~cyy/courses/rendering/
http://www.raytracegroundup.com/
http://www.scratchapixel.com/
http://www.crcpress.com/p/book/9781439827376
http://graphics.csie.ntu.edu.tw/~robin/courses/gm13/
http://cs.brown.edu/courses/cs123/lectures.html
http://graphics.stanford.edu/courses/
http://graphics.csail.mit.edu/courses

Mesh Rendering: Camera to Model

Mesh Rendering

这裡再提供一个 更清楚的动画 。

Model

将物体表面简化成大量的平坦的多边形，再运用“ 多边形三角剖分 ”切割成大量的三角形，得到 Mesh。

替现实生活的物体建立 Mesh，是一套複杂的学问。所幸我们已经有 现成的模型 可以使用。例如此处的模型是 Utah Teapot 。

Mesh 由许多三角形组成。一个三角形拥有三个顶点座标（暨法向量）、正面颜色、背面颜色。

三角形的顶点顺序，决定了三角形的正面：正视三角形的正面，我们习惯让三角形顶点呈逆时针顺序。依照顶点顺序计算“ 叉积 ”，得到三角形的正面的法向量。这是大家约定俗成、心照不宣的规矩。

Mesh 的资料结构通常是：一个阵列记录每个点（暨法向量）、一个阵列记录每个三角形的三个点的编号。由于三角形经常共用顶点，因此两层式的资料结构，得以节省记忆体空间。

不过为了方便起见，以下採用笨蛋方法。

UVa 10711

Camera

替相机设定三个单位向量：长的方向、宽的方向、面对方向。

求得 Mesh 中心点，倒退一万步，作为焦点的位置。

Mesh Rendering: Illumination

Illumination

直接取用三角形的原始颜色，外观呆板，缺乏层次。真实世界，颜色缤纷，是因为光线照射。现在我们要引进一套光线系统，让三角形华丽动人、闪闪发光！

一、Light。光线的来源。

二、Optics。光线射中物体之后，物体影响光线的机制。

三、Material。光线射中物体之后，光线亮度与彩度变化。

四、Ray Tracing。追踪光线轨迹。运算量最大的地方。

五、Sampling。设定光线数量、方向，使图片外观柔顺。

这套光线系统源自物理，源自人类对于世界现象的观察。如果你熟悉物理理论、擅长物理实验，可以创造更细腻的方式。

Light

point light (omni light)：点光源。例如烛火、灯泡。
cone light (spotlight)：圆椎光源。例如聚光灯。
directional light (collimated light)：有向光源。例如遥远的太阳。

area light：区域光源。光源们组成一大片面积。
model：物体当作光源，表面发光。
environment light：环境光源。光源们组成球面，包覆在场景外围。

实际范例请见此 。数量、位置、方向（张开角度）、亮度、彩度，五个要素。光源还可进一步组成面，添增变化。

妥善设置光源，精心营造气氛。甚至可以实地拍摄天空的照片作为光源，诸如朝雾夕霞、天光云彩，营造真实感。

Optics

emission：发光。例如萤光棒。
absorption：吸收。日常生活常见物体都是。

reflect：反射。例如镜子、水中倒影。
refract：折射。例如鱼缸、晶鑽。
scatter：散射。例如叶隙光、云隙光、头髮。
diffract：绕射。很少见。

物体影响光线。或者简单想成：光线碰撞物体，产生变化。

光波有两个要素：频率（彩度）和振幅（亮度）。

一道光通常由大量频率组成，各种频率有各种振幅。物体影响光线，不会改变频率，而会改变各种频率的振幅大小、行进方向。

发光吸收是振幅大小变化，反射折射散射绕射是行进方向变化。

Optics 的数学模型

一、考虑反射角（等于入射角）、折射角（根据介质係数）。入射折射反射都在同一平面。适合当作业。

二、考虑各种反射方向、折射方向。此模型称作 BSDF = BRDF + BTDF。虽然光线遵守物理定律、光线随从明确轨迹，但是混杂了大量複杂结果，才是人类视觉观感：光线不是一条而是一束，照射处不是一点而是一块，介面不是一个平面而是很多曲折，射出不仅一个方向而是很多方向。例如 虹彩 。

三、考虑地点差异。此模型称作 BSSRDF 。光线在介质内不断散射，从别处散逸而出。光线的散射、 粒子的扩散 ，两者有著异曲同工之妙。距离交点越远，射出机率越小，近似常态分布。亦可想成表面套用 Gaussian filter。例如浊液、皮肉、头髮。

四、考虑时间差异。光线被介质吸收，缓缓射出。例如磷光、萤光。

五、考虑各种频率。白光反射时，部分频率消失（光的吸收）；白光折射时，各种频率错开（光的色散）。接近真实了。例如 dichroism 、 pleochroism 。

考虑越多，运算量、记忆量越大。四和五，当今硬体设备难以即时实现，除非取巧。

Material

人类视觉透过複杂机制，揉合振幅和频率，得到颜色。

工程师便宜行事，将光的要素，从频率和振幅，换成颜色和亮暗程度。再瞎掰出：颜色×亮暗程度=呈现颜色。儘管不切实际，但是容易计算。

工程师便宜行事，反射光、折射光，颜色不变动，亮暗程度才变动。一种入射方向，拥有多种反射方向、折射方向，每种方向各有亮暗程度。方向以经纬度表示，亮暗程度以 函数 表示。函数有形容词。

  diffuse / matte：漫射。雾面、粗糙表面。
                   反射光分散，朝不同方向。例如路面、牆壁、纸张。
specular / glossy：镜射。镜面、光滑表面。
                   反射光集中，朝同一方向。例如金属、塑胶、磁砖。

给定一种素材，有 物理仪器 可以测量函数。採用实体的测量数据，便可模仿真实世界。

除了採用实体的测量数据，亦可採用 虚拟的数学模型 。现今已有多种数学模型，各有不同视觉效果。

Ray Tracing

一、光线接触介面才有变化，产生反射折射。适用固体，例如居家摆设。演算法原理类似 状态空间搜寻 。

   ray tracing: 焦点出发。
                光学：仅考虑反射角、折射角。
  path tracing: 焦点出发（亦可焦点和光源双向出发）。
                光学：考虑各种反射方向、折射方向。
     radiosity: 光源出发，走 K 步，每步皆留下一些光子。
                焦点出发，走一步，以附近光子数量，决定像素亮度。
               （实作：每步结束后，另走一步到焦点，累加像素亮度。）
               （I^1 + I^2 + I^3 + ... + I^k）
photon mapping: 光源出发，走一步，留下一个光子。
                焦点出发，走 K 步，以附近光子数量，决定该步的光线亮度。

一、从焦点、光源出发，持续反射、折射，追踪光线轨迹。
　　每次接触介面当作一步。
二、从焦点出发时，每一步穷举所有可能的入射方向。
　　从光源出发时，每一步穷举所有可能的出射方向。
　　由于不可能完全穷举，所以採用取样，后面章节会介绍。
三、焦点、点光源仅有一点，通常瞄不准、追踪不到。
　　因此最后一步必须无视物理定律，刻意走向焦点、点光源。(global illumination)
　　区域光源则无此问题。
四、为了减低计算量，通常只走 K 步。
　　又为了减少 bias，以固定机率决定要不要走下一步。(Russian roulette)
　　又为了增加实感，累计一步、两步、……、K 步的结果。

二、光线接触介质即有变化，于介质中不断反射折射散射。适用气体液体，例如云雾、牛奶。依照浓度不同，有著各种演算法，但是皆昧于物理事实。

稀薄：视作滤心。穿过越多介质，亮暗程度变化越大。
　　　以介质厚度当作亮暗变化程度。
中等：视作粒子。气体处处都是完美漫射。光线为直线，只散射（转折）一次。
　　　穷举视线的每一个位置，尝试转折至光源。
浓稠：视作固体。光学模型：考虑入射、出射地点差异。
　　　测量 BSSRDF，套用固体的演算法。

Ray Tracing 的常见伎俩

    ambient occlusion: 遮光。挡住光线，产生阴影。
                       例如鼻翼的阴影、门缝。
subsurface scattering: 透光。光线于半透明介质内散射，深层与浅层的光线重叠。
                       例如白裡透红的肌肤、透光的窗帘、浊液、叶片、玉。

soft light/shadow: 柔光、柔影。
从交点发出大量射线，判断打中多少光源，决定亮度。
volumetric light/shadow: 光芒、阴暗。例如百叶窗散落的光、积雨云散落的阴影。
从光源发出大量光线。再从焦点发出大量射线，判断打中多少光线，决定亮度。

environment mapping: 物体周围摆放素材图片，映射在物体上。
shadow mapping: 预先计算物体阴影范围，贴上阴影图片。

电脑所能绘制的现象十分稀少。至今仍有许多 光学现象 ，绘制尚未成功，同志仍须努力。

UVa 12313

Sampling

一、反射折射：追踪光线轨迹，列举数种可能的方向。

二、发射：增加焦点射向像素的光线数量，射中的颜色们取平均值，产生平滑、模糊、抗锯齿效果。

anti-alias: 增加乱数数量，取平均值。
motion blur: 根据物体速率，决定乱数偏移量。
depth of field: 根据物体远近，决定乱数偏移量。

射线数量是一个自订常数，射线方向的偏移量是一群 二维乱数 。光线反射折射，採用球形；光线发射，採用正方形。

绘制三角形！

光源：一个点光源。光学：仅反射（入射角等于反射角）、无折射。材质：完美漫射。光线追踪演算法：Ray Tracing。无取样。

图片很阳春。如果想看更逼真的图片， 可以上网搜寻 ，或者自己动手画画看吧！

Mesh Rendering: Texture

Texture

以上介绍了光线照明系统，以下介绍表面纹路系统。

物体表面通常不是均一颜色、不是均一高低。工程师的解决之道：自订表面纹理。纹理包括了颜色、高度、法向量等类型。

Texture Generation

制造纹理的方法有：请摄影师拍摄实际照片，请设计师绘制美工图片，请工程师研发演算法。

制造纹理属于 图片处理 的范畴。原理是运用 杂讯 ，产生纹理的颜色、高度、法向量等等，营造逼真画面。读者不想自行制作纹理的话，亦可 下载现成的纹理（但是只有颜色） 。

Texture Mapping

将纹理贴上物体表面。物体表面、纹理，建立座标对应关係。请参考 这篇文章 。

简易的方式是：物体的每个三角形（四边形），各使用一片正方形纹理。直接实施三角形内插（四边形内插），得到座标对应关係。请参考 Image Warping ，属于图片处理的范畴。

Texture Mapping: Texture Coordinates

将纹理布置于物体周围。重设纹理的座标系统。

正方体：使用六片纹理，作为正方体的六个面。
圆柱体：使用一片纹理，左右衔接。（座标对应：长宽对应高度和角度）
半球体：使用一片纹理，中央凸出。（座标对应：长宽对应经纬）

Texture Mapping: Mesh Parameterization

将纹理映射至物体表面。重设物体表面的座标系统。

摊平：物体从某处剪开、摊平，得到对应关係。
　　　周界可以尽量调整成纹理形状、内界可以尽量调整成整齐网格。
中心：源自物体中心的放射线，击中表面和纹理，得到对应关係。
光学：源自焦点的射线，经由反射击中纹理，得到对应关係。

Texture Filtering

bilinear filtering：只有一张纹理。採用 image warping 改变纹理形状。
trlinear filtering：考虑相机远近，预先制作各种大小的纹理。scale transform。
anisotropic filtering：考虑相机角度，预先制作各种视角的纹理。shear transform。

二维纹理的映射当中，纹理与表面的大小形状，经常不相符，必须调整纹理的大小形状。

改变纹理的大小形状，纹理可能出现锯齿、可能失真。仿效 内插 的观念，让纹理柔顺平滑。

Texture Data Structure / Texture Atlas

   mipmap: 纹理预先缩放成各种比率，以应付各种远近距离的呈现观感。
heightmap: 附带高度资讯。

纹理的资料结构。我没有研究，请参考 这篇文章 、 Wavefront 的 obj 档案格式 。

Texture Embossing

重新设定表面法向量、表面高度，令表面凹凸不平、有立体感、有阴影，宛如 压印 。请参考 这篇文章 、 这篇文章 。

bump mapping: 表面是平面，重新设定每一处的高低。
normal mapping: 表面是平面，重新设定每一处的法向量。
displacement mapping: 三角形顶点沿法向量移动。
parallax mapping: http://exibeo.net/docs/parallax_mapping.pdf
relief mapping: http://graphics.cs.brown.edu/games/SteepParallax/index.html

Normal Interpolation

重新设定表面法向量，使其圆滑。

想得到三角形上某一点的法向量：

一、求得三角形的正面的法向量。三个顶点叉积，即得。

二、求得三角形的三个顶点的法向量。一个顶点有许多个相邻的三角形。相邻三角形的法向量相加之后，当作该顶点的法向量。然而模型本身多半已经提供精准的顶点的法向量，可以省略这两步骤。

三、求得三角形的任意一点的法向量。想要求得内插比重，直觉的方式是：将线性内插重新表示成线性变换矩阵，然后求反矩阵──然而当三角形与原点共平面，反矩阵就不存在了。推荐的方式是“ Barycentric Interpolation ”，三块小三角形的面积，就是内插比重。

法向量们方向渐层改变。打光后，三角形表面彷彿圆滑凸起。

形状看似改变了，但是实际位置没变。物体边缘会产生破绽。

Normal Encoding

将一个法向量重新表示成一个浮点数，节省储存空间。请参考 这篇文章 。

Mesh Rendering: Model to Camera

Perspective Projection

如何计算三维空间的一个点，在图片上对应的 XY 座标呢？

先以“ 点积 ”求得三个方向的投影量、即是真实距离 x y z。

再以“相似三角形边长成比例”的原理，藉由 z 和 depth 的比例，求得投影距离 x' y'。x z 构成的三角形，缩小为 depth/z 倍，得到 x'；y z 构成的三角形，缩小为 depth/z 倍，得到 y'。

注意到，真实距离和投影距离都是以图片中心为基准，距离可以是负值。最后我们调整投影距离成为图片座标。

绘制空心三角形！

此处的模型是 台大资讯系 。

穷举每个三角形，把三角形三个顶点投射到图片上，求得图片座标。运用 OpenGL 画出每个三角形的外框，最后形成了“线框（wireframe）图”。

Volume Rendering

Volume Rendering（Voxel Rendering）

Voxel

“像素 Pixel”和“体素 Voxel”两者概念相仿，二维与三维的差别而已。

像素数值，通常代表 RGB 颜色；体素数值，通常代表物质密度。物质密度越高，体素数值越高。

替现实生活的物体建立体素，是一套複杂的学问。所幸网路上已经有 电脑断层扫描的资料 。此处使用的 CTHead 是 8bit TIFF 图片档案，图片一张张叠起来，像素成了体素。

这份资料中，皮肉密度低、体素数值低，骨骼密度高、体素数值高。我不清楚物质密度与体素数值 是否恰好成正比 。

Isosurface Rendering

Isosurface Rendering

Isosurface（Implicit Surface）

isosurface: f(x,y,z) = t , f(x,y,z) - t = 0 , g(x,y,z) = 0
g(x,y,z) > 0: point (x,y,z) is outside
g(x,y,z) = 0: point (x,y,z) is coincide
g(x,y,z) < 0: point (x,y,z) is inside

“等值表面”和“体素”概念相仿，连续与离散的差别而已。

订立一个连续函数，让空间中每个地点皆有数值。再订立一个临界值，做为表面。请参考 这篇文章 。

临界值移项，使右式为零。左式的正、负、零，恰好代表该地点位于表面的外部、内部、上面。

找到射线与表面的交点，有两种方式：一、钩勒直线演算法，一步一步走，随时判断内外。二、解联立方程式，二分法求根。

另外，记得订立场景范围，让射不中物体的射线停止行进。

找到表面的法向量：使用梯度当作法向量，如同体素。

Distance Field（Signed Distance Field）

distance field: f(x,y,z) = signed distance from point (x,y,z) to surface

union        of f and g: min(f, g)
intersection of f and g: max(f, g)
complement   of f      : -f
difference   of f and g: f - g

“距离场”。等值表面究极进化。函数值恰是输入座标点到表面的最短距离！请参考 这篇文章 的参考文献、 这篇文章 的模型范例。

当模型是距离场，多个模型的联集、交集、差集非常好算！联集：最小值。交集：最大值。补集：负值。差集：减法。

找到射线与表面的交点：当前位置代入函数，得到当前最短距离。走一步，步伐是当前最短距离，顶多碰到表面，而不会穿越表面。就算因为浮点数误差穿越表面也无妨，下一步会得到负的距离，依旧持续接近表面。反覆行走，直到足够靠近表面，或者直到超出场景范围。

找到表面的法向量：使用梯度当作法向量，如同体素。

Ray Marching（Ray Casting）

当模型是距离场，射线与表面的交点，计算过程比较特别。

朝向表面：最短距离越来越小，迅速逼近。偏离表面：起初最短距离越来越小，掠过表面之后，最短距离越来越大，迅速远离。

当表面平滑柔顺，最短距离越来越小，逼近速度大致稳定。

当表面凹凸起伏，最短距离忽大忽小，逼近速度不稳定。

利用逼近速度，可以制做粗糙的 ambient occlusion。当逼近速度不稳定，表示该处附近有物体凸出，迫近射线，遮挡交点。

沿著射线小步小步走，累计每一步当中，理想的、实际的最短距离的差值，作为阴影强度。

范例：Blobby Surface

范例：Fractal Surface