图形：计算机图形学（CG [Computer Graphics]）简介

super1

计算机图形学（CG [Computer Graphics]）是当代计算机显示的基础科学。其代指一系列，以数学算法对虚拟场景下二维或三维图形的矩阵和位姿进行处理，将抽象物体转化为可由挂载显示器输出的栅格化数据，的方法论。它是一门复合学科，衍变自影像学（Photography），成形于人工智能（AI）和人机交互（HCI）研究中对图形数字化处理的探索。
早期的探索与积累

影像学（Photography）是人们在图像处理方面的早期探索。
1888年，托马斯·爱迪生（Thomas Edison，1847 - 1931）在万博会上首次展示了，由他的爱迪生实验室雇员，发明家威廉·肯尼迪·迪克森（William Kennedy Dickson，1860 - 1935）发明的活动影像观察镜（Kinetoscope）原型机 [4]。该机器将一系列有时序的图片，装配到了可由铰链驱动的链式齿轮组上，并于设备顶部开设了光源入口和观察口。借由转动齿轮组的驱动轴，使用者可以从观测口看到机器内部的时序图片，在快速运动下形成的动态影像 [1] [2] [3]。这极大的启发随父亲一起受邀参加了活动的奥古斯特·卢米埃尔（Auguste Lumière，1862 - 1954）和路易斯·卢米埃尔（Louis Lumière，1864 - 1948）两兄弟。



图1 活动影像观察镜（Kinetoscope）原型机草图 [2]

1895年，卢米埃尔兄弟（Lumière Brothers），在活动影像观察镜（Kinetoscope）的基础上，研发出了可以将影像画面投影至画布的黑白电影放映机（Cinematograph）。这个伟大的发明，让电影正式登上了历史舞台 [5]。此后，电影业进入了快速发展阶段。这期间有关图形存储和射影几何的理论积累，为数字影像学（Digital Photography）提供了极大帮助。



图2 卢米埃尔兄弟的电影放映机（Cinematograph）原型机草图 [6]

计算机图形学的诞生

20世纪，计算机技术在冷战背景下得到了快速发展，小型化和运算能力的提升成为了趋势，为计算机图形学的诞生提供了摇篮。而真正促成计算机图形学产生的关键事件，则是“电子游戏之父”史蒂夫·罗素“不顾正业”的使用了科研设备开发《太空大战》（Spacewar!），和“计算机图形学之父”伊凡·苏泽兰发明了划时代的 “画板”（Sketchpad）系统。这两个程序让人们分别看到了计算机图形处理技术在商业上的潜力，和开发更为便利的人机交互系统上的可能。
1958年，当时还在麻省理工（MIT）任教的“人工智能之父” 约翰·麦卡锡（John McCarthy，1927 - 2011）在研究逻辑式编程（Logic Programming）的过程中发现，可以抽象原始递归函数（Primitive Recursive Function）的逻辑运算过程为单独的象征性符号（Symbolic Expressions）来简化整个计算机处理过程中的同类表达范式 [7]。基于这一发现，麦卡锡博士开始了初代 Lisp 语言的研发工作，并于 1960年将研究成果汇总发布到了美国计算机学会（ACM [Association for Computing Machinery]）的月刊《美国计算机学会通讯》（Communications of the ACM）上 [7]。
1961年，就在 Lisp 语言因为估值器函数（Evaluator Function）抽象问题陷入了停滞之时，麦卡锡的学生史蒂夫·罗素（Steve Russell，1937 - Present）根据导师的论文，提出了“可以将通用函数的概念应用在 Lisp 的估值器函数设计上，使得经过抽象的估值器逻辑运算过程，能够用计算范式（Evaluate Lisp Expressions）统一表示”的观点 [8]，解决了 Lisp 语言的解释执行问题。为了证明理论可行，罗素在一台 IBM 704 大型主机（Mainframe Computer）用 Lisp 语言编写了首个可执行的 Lisp 程序，这个程序就是最初的 Lisp 直译器（Lisp Interpreter）。这一段经历，为罗素接下来要干的事提供了足够的想法和技术能力。
1961年同年 9月，由于协助 Lisp 语言开发的功劳外加麦卡锡的社团教授身份，史蒂夫·罗素所在的麻省理工火车模型技术俱乐部（TMRC [Tech Model Railroad Club]）得到了校方提供的一台来自美国数字设备公司（DEC [Digital Equipment Corporation]）捐赠的 PDP-1 计算机的使用权。这部计算机在当时可谓是划时代的产品，创造性的使用了阴极射线管显示器，并首次配备了可用于和计算机直接互动的交互输入设备（在这之前，人们和计算机交互都需要通过打卡机实现）。



图3 MIT 的 PDP-1 照片

有了 PDP-1 设备使用权后，整个 TMRC 上下非常兴奋。罗素和几位社团社员迫不及待的用这台设备做了游戏史上第一个图形化的游戏《太空大战》（Spacewar!）[9]。如此灵感让大家意识到，计算机图形化在商业上的潜力。《太空大战》的全代码开源，让所有想要在此领域有所建树的人能够一探究竟。DEC 公司的工程师们，更是将此程序做为诊断程序（Diagnostic Program）预装到了每一台发售的 PDP-1 机器上从而使《太空大战》广为人知，进一步激发了人们对计算机图形处理的兴趣。
紧跟《太空大战》发布之后的 1963年1月，伊凡·苏泽兰（Ivan Sutherland，1938 - Present）在麻省理工林肯实验室的 TX-2 机器上完成了 “画板”（Sketchpad）系统的开发，并发表了著名论文《画板：人机图形通信系统》（Sketchpad: A man-machine graphical communication system） [10]。整部系统的开发仅用了3年时间，苏泽兰甚至还为论文答辩抽空制作了一部介绍短片。



图4 扩展存储器（MEMEX [Memory Extender]）说明原稿

受启发自范内瓦·布什（Vannevar Bush，1890 - 1974）在《诚如所思》（As We May Think）中所提到的扩展存储器（MEMEX [Memory Extender]），“画板”（Sketchpad）系统使用电容笔作为输入设备，并首次在计算机系统上引入了“光标”（Cursor）的概念 [11]。通过这根电容笔，用户能够指挥“光标”直接在显示器上绘制图形。这种创造性的交互方式，开创了用户图形界面（GUI [Graphical User Interface]）的先河。而系统中的动态图形、实时协调系统等概念，更是深远影响了当今计算机系统的人机交互体系。



图5 短片中，苏泽兰演示“画板”（Sketchpad）系统的使用

近现代技术爆发

《太空大战》和 “画板”系统的出现让科研工作者们爆发出了无比的热情，使得整个学科领域得到了大量的关注与投入。所有关注的目光中，就包括一些大型企业和集团。他们更感兴趣于计算机图形技术带来的不可估量的商业价值。于是，在科学界将计算机图像处理的重心放在工业 3D 模型电脑辅助设计（CAD [Computer Aided Design]）和头戴立体显示器（HMD [Head Mounted Display]）时，首台基于苏泽兰思想开发的，搭载有光栅显示器（CRT [Cathode Ray Tube]）、配套图像显示单元（Graphics Display Unit）、GUI 超文本编辑系统 (HES [Hypertext Editing System]) 的实时交互商用图形计算机 IBM 2250 在 1964年 面世，悄然实现了可交互操作系统的商业化。
不过，大量的实践也使得人们发现了当下阻碍图形学更进一步的两个关键问题：图形可视化（Visualization）和图形着色（Colorization）。尤其是图形可视化，直接决定了计算机是否能够具有更为出色的模型效果。
随后的几年间，IBM 在计算机图形可视化方面进行了攻坚，贡献了大量突破性算法。这其中就包括了经典的用于绘制直线与中点圆的布雷森汉姆直线算法（Bresenham's Line Algorithm）[12] 和由亚瑟·埃佩尔（Arthur Appel）提出的首个光线投影算法（Ray Casting Algorithm）[13]。而其他的一些研究机构，如 ACM 和 IEEE，也发表了扫描线算法（Scan Line Algorithm）[14]、高氏渲染（Gouraud Shading）[15] 等经典算法。这些算法缓解了图形可视化问题在当时的需求。



图6 埃佩尔论文中的光线投影算法草图 [13]

而图形着色方面，则由当时正受教于由伊凡·苏泽兰和大卫·埃文斯（David C. Evans， 1924 - 1998）指导的犹他大学（The University of Utah）先进计算机图形班（Advanced Computer Graphics Class）的艾德文·卡特姆（Edwin Earl Catmull，1945 - Present），在 1974年 发表的《一种用电脑显示曲面的细分算法》（A subdivision algorithm for computer display of curved surfaces）中，率先引入了纹理映射（Texture Mapping）和深度缓存（Depth Buffer）的处理方式初步解决 [16]。
至此，图形可视化（Visualization）和图形着色（Colorization）的基础理论得以确立。随之而来，计算机图形学迎来了技术爆发：



图7 计算机图形学关键理论年鉴（1970 - 1995）

到1995年为止，现在我们所了解的计算机图形学基本成形了。而之后3D图形引擎因游戏行业的发展开始被重视，从为我们带来了以CG为理论的基础图形驱动如 OpenGL、DirectX等，和封装了物理引擎的游戏图形引擎如 Unity、CryEngine等。

【参考文献】
[1] Hendricks (1961), pp. 4, 10–12; Musser (1994), pp. 49–53, 62. Robinson (1997) states that "Edison and Dickson were almost certainly in the audience" on February 25 (p. 23);
[2] Quoted in Robinson (1997), p. 23. The caveat was written on October 8 and filed on October 17. Hendricks (1961), pp. 14–16.
[3] "Origins of Motion Pictures: The Kinetoscope". Inventing Entertainment: The Early Motion Pictures and Sound Recordings of the Edison Companies. Library of Congress. Retrieved November 24, 2022.
[4] Hendricks, Gordon (1966). The Kinetoscope: America's First Commercially Successful Motion Picture Exhibitor. New York: Theodore Gaus' Sons. Reprinted in Hendricks, Gordon (1972). Origins of the American Film. New York: Arno Press/New York Times. ISBN 0-405-03919-0
[5] Mannoni, Laurent (2000). The great art of light and shadow : archaeology of the cinema. Richard Crangle. Exeter, Devon: University of Exeter Press. ISBN 0-85989-665-X. OCLC 44562210.
[6] Louis Lumière, The Lumière Cinematograph. In:Fielding, Raymond (1979). A technological history of motion pictures and television: an anthology from the pages of the Journal of the Society of Motion Picture and Television Engineers. University of California Press. pp. 49–51. ISBN 0-520-03981-5.
[7] McCarthy, John (1960). "Recursive Functions of Symbolic Expressions and Their Computation by Machine". Communications of the ACM. 3 (4): 184–195. CiteSeerX 10.1.1.322.5235. doi:10.1145/367177.367199. S2CID 1489409.
[8] Stoyan, Herbert (1984-08-06). Early LISP history (1956–1959). LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming. Association for Computing Machinery. p. 307. doi:10.1145/800055.802047. Archived from the original on 2005-04-05.[9] Graetz, Martin (August 1981). "The origin of Spacewar". Creative Computing. Vol. 7, no. 8. pp. 56–67. ISSN 0097-8140.
[10] Sutherland, Ivan Edward (January 1963). "Sketchpad: A man-machine graphical communication system (courtesy Computer Laboratory, University of Cambridge UCAM-CL-TR-574 September 2003)". Massachusetts Institute of Technology. Retrieved 2006-12-26.
[11] Sears, Andrew; Jacko, Julie A. (19 September 2007). The Human–Computer Interaction Handbook: Fundamentals, Evolving Technologies and Emerging Applications, Second Edition. CRC Press. p. 5. ISBN 978-1-4106-1586-2. Retrieved 1 March 2013
[12] Joy, Kenneth. "Bresenham's Algorithm" (PDF). Visualization and Graphics Research Group, Department of Computer Science, University of California, Davis. Retrieved 20 December 2016.
[13] Appel, Arthur (April 30, 1968), "Some techniques for shading machine renderings of solids" (PDF), AFIPS '68 (Spring) Proceedings of the April 30--May 2, 1968, Spring Joint Computer Conference: 37–45, doi:10.1145/1468075.1468082, S2CID 207171023.
[14] Bouknight, W. J. (1970). A procedure for generation of three-dimensional half-tone computer graphics presentations. Communications of the ACM.
[15] Gouraud, H. (1971). Computer display of curved surfaces. IEEE Transactions on Computers20 (6), 623–629.
[16] Catmull, Edwin Earl (1974). A subdivision algorithm for computer display of curved surfaces (PDF) (PhD thesis). University of Utah. Archived (PDF) from the original on September 26, 2020.

【推荐书目】
1、《数字信号处理 原理、算法与应用 第4版》，作者：[美] John G.Proakis / [美] Dimitris G.Manolakis，译者：方艳梅 / 刘永清，出版社: 电子工业出版社，ISBN: 9787121238680
2、《数字图像处理 第4版》，作者：[美] Rafael C. Gonzalez / [美] Richard E. Woods，译者: 阮秋琦 / 阮宇智，出版社: 电子工业出版社，ISBN: 9787121377471