计算机图形学 CG:任何使用计算机创建和操作几何(2D 或 3D)的方法。
CG 的主要领域有:
- 建模: 处理几何形状和外观性质的数学规范,这些规范可被存储在计算机中。
- 渲染:继承自美术的术语,处理创建来自 3D 几何体的着色图像问题。
- 动画:是一种通过图像序列创建运动错觉的技术。
还有许多其他邻域,他们是否属于 CG 较为模糊:
- 用户交互:用户交互处理输入设备(如鼠标和平板电脑)、应用程序、对图像用户的反馈和其他感官反馈)之间的接口。
- 虚拟现实:虚拟现实试图将用户浸入 3D 虚拟世界中。这通常需要至少立体图形和对头部运动的响应。而对于真正的虚拟现实,还应该提供声音和力的反馈。
- 可视化:可视化试图让用户通过视觉显示深入了解复杂信息。
- 图像处理:处理二维图像的操作。
- 3D 扫描:三维扫描使用测距技术来创建测量的 3D 模型。
- 计算摄影学:使用 CG、CV 和图像处理方法来实现摄影捕捉对象、场景和环境的方法。
- 游戏:游戏越来越多地使用复杂的 3D 模型和渲染算法。
- 卡通:卡通通常直接从 3D 模型渲染。许多传统的 2D 卡通使用从 3D 模型渲染的背景,这允许连续移动的视点,而不需要大量的艺术家时间。
- 视效:视觉效果几乎使用所有类型的计算机图形技术。几乎每个现代电影都使用数字合成将背景与单独拍摄的前景叠加。许多电影也使用 3D 建模和动画来创建合成环境、对象甚至角色。
- 动画电影:动画电影使用了许多用于视觉效果的相同技术,但不一定针对看起来真实的图像。
- 计算机辅助设计和计算机辅助制造 CAD/CAM:这些领域使用计算机技术来设计计算机上的部分和产品,然后使用这些虚拟设计来指导制造过程。
- 模拟:模拟可以被认为是准确的视频游戏。这种模拟对于驾驶等安全关键领域的初始训练非常有用,对于体验用户的场景训练,例如过于昂贵或危险的特定消防情况,无法在物理上创建。
- 医学图像:例如,计算机断层扫描 (CT) 数据集由大量 3D 矩形密度值阵列组成。计算机图形学用于创建着色的图像,帮助医生从这些数据中提取最显着的信息。
- 信息可视化:信息可视化创建了不一定具有“自然”视觉描述的数据图像。例如,十个不同股票价格的时间趋势没有明显的视觉描述,但巧妙的图技术可以帮助人类看到此类数据中的模式。
应用程序程序接口 (API) 是执行一组相关操作的标准函数集合,图形 API 是一组函数,例如将图像和 3D 表面绘制到屏幕上。每个图形程序都需要能够使用两个相关的 API:
- 用于视觉输出的图形 API
- 用于从用户输入的用户界面 API。
目前,图形和用户界面 API 有两种主要范式:
- 集成方法,例如 Java,其中图形和用户界面工具包被集成和便携式包,这些包完全标准化并作为语言的一部分支持。
- 由 Direct3D 和 OpenGL 表示,其中绘图命令是与 C++ 等语言相关的软件库的一部分,用户界面软件是一个独立的实体,可能因系统而异。
在后一种方法中,尽管对于简单的程序编写便携式代码是成问题的,但是也可以使用便携式库来封装系统特定的用户界面代码。
几何管线是一个特殊的软件/硬件子系统,可以有效地从分别绘制 3D 原语。通常,这些系统被优化以处理具有共享顶点的 3D 三角形。管线中的基本操作将 3D 顶点位置映射到 2D 屏幕位置,并对三角形进行着色处理,使它们看起来逼真并以适当的“back-to-front”顺序出现。尽管有效的绘制顺序是 CG 中最重要的问题之一,但现在几乎使用特殊的内存缓冲区(Z-buffer)以蛮力方式解决问题。
CG 管线中使用的几何操作几乎完全可以在 4D 坐标空间中完成,该空间由三个传统的几何坐标和第四个有助于透视的齐次坐标组成。这些 4D 坐标是使用 4×4 矩阵和 4 矢量来操作的。因此,图形流水线包含了许多用于有效处理和组合这些矩阵和向量的机器。这个 4D 坐标系是计算机科学中使用的最微妙、最美丽的结构之一,它无疑是学习计算机图形学时要跨越的最大智力障碍(确实)。
渲染的速度在很大程度上取决于绘制三角形的数量。因此在许多实时应用中,人们愿意使用几何面数换渲染速度。此外,从远处查看模型,则需要更少的三角形面来维持相同的质量(LOD:Level of Detail)。
幸运的是,几乎所有现代计算机都符合 IEEE 浮点标准。这允许程序员对如何处理某些数字条件做出许多方便的假设。IEEE 浮点中只有少数特别重要的知识:
- IEEE 浮点中三个“特殊”值:
- 无穷大($\infty$):这是一个大于其他所有数字的有效数字。
- 负无穷大($-\infty$):这是一个小于其他所有数字的有效数字。
- 非数(Not a Number, NaN):这是一个无效的数字,由具有未定义后果的操作产生,例如零除以零。
IEEE 浮点的设计者做出了一些对程序员非常方便的决定。其中许多与上面的三个特殊值有关,以处理异常,例如除以零。而大多数情况下则可以忽略(例如非零实数除以无穷大)。
关于 NaN 的规则:
- 任何包含 NaN 的算术表达式都会导致 NaN
- 任何涉及 NaN 的布尔表达式都是 flase
另外,IEEE 标准最有用的部分是关于除以零的规则,有了这些规则,程序员不必再花大量精力在设置条件判断语句上,来事先检查运算的合法性,例如:
IEEE 754 标准中,为了程序的鲁棒性,除以零的操作默认返回无穷大(这里吧 0 视作无穷小)。 但在整数运算中,除以零仍然会抛出异常。
没有魔法规则使代码更高效。效率是通过仔细的权衡来实现的。程序员应该更多地关注内存访问模式而不是操作计数,因为内存的速度远不如处理器的速度。 考虑一下工作流,来使你的代码更加高效:
- 以最直接的方式编写代码。动态计算中间结果,而不是存储它们。
- 在优化模式下编译。
- 使用分析工具来查找关键瓶颈。
- 检查数据结构以寻找提高局部性的方法。尽可能使数据单元大小与目标架构上的缓存/页面大小相匹配。
- 如果分析揭示了数值计算方面上的瓶颈,则检查编译器生成的汇编代码。重写源代码以解决您找到的任何问题。
这些步骤中最重要的是第一步。大多数“你认为的优化”只使代码更难阅读,而不会加速程序执行。此外,前期优化代码所花费的时间通常更好地用于纠正错误或添加特征。另外,老式技巧(如使用整数代替浮点数)可能不会真正提升性能,因为现代计算机处理两者的速度相当。
这里介绍了常见的图形编程策略。
任何图形程序的关键都是为几何实体(如矢量和矩阵)以及图形实体(如 RGB 颜色和图像)提供良好的类或例程,这些程序应该尽可能的简洁和高效。来谈谈一些基本的类:
- vector2:二维矢量类,存储 x 和 y 分量。应该将这些组件存储在长度为 2 的数组中,以便支持索引操作符。还应该包括向量加法、向量减法、点积、叉积、标量乘法和标量除法的运算。
- vector3:
- hvector:具有四个分量的齐次向量。
- rgb:存储三个分量的 RGB 颜色。还应该包括 RGB 加法、RGB 减法、RGB 乘法、标量乘法和标量除法的操作
- transform:4 × 4 矩阵。应该包含一个矩阵乘法和应用于位置、方向和表面法向量的成员函数。
- image:带有输出操作的 RGB 像素的二维数组。
此外,您可能希望也可能不希望为区间、标准正交基和坐标框架添加 Class。
现代架构表明,降低内存使用和保持连贯的内存访问是提高效率的关键。这建议使用单精度数据。然而,为了避免数值问题,建议使用双精度算法。权衡取决于程序。
随着程序员变得越来越有经验,他们使用传统调试器的次数越来越少。一个原因是,对于复杂的程序使用这样的调试器比对于简单的程序更困难。另一个原因是,最困难的错误是概念性的错误,并且很容易浪费大量的时间来遍历变量值而无法检测到错误的情况。
- 科学的方法
在图形程序中,有一种替代传统调试的方法:我们创建一个图像,然后观察它有什么问题。然后,我们提出一个关于导致问题的原因的假设并进行测试。
这种方法有时是一种很好的实践,关键原因是我们不必发现错误值或确定我们的概念错误。相反,我们只是在实验上缩小了我们的概念错误。
大概是提出假设,然后一步步缩小错误原因的范围
- 图像作为编码调试输出 在图形程序中,最简单的输出是图像。如果您想知道针对每个像素运行的部分计算的某个变量的值,您可以临时修改您的程序,将该值直接复制到输出图像中,并跳过通常会完成的其余计算。 如果您怀疑某个特定值有时超出了它的有效范围,那么让您的程序在发生这种情况的地方写入亮红色像素。其他常见的技巧包括用明显的颜色绘制表面的背面(当它们不应该是可见的时候),用对象的 ID 号给图像上色,或者用它们计算的工作量给像素上色。
- 使用调试器
一个有用的方法是为 bug“设置陷阱”。在您怀疑不正确的代码之前添加一条语句,该语句将仅在怀疑的情况下执行。
if x = 126 and y = 247 then print("problem comes here!")
,甚至可以在 print 语句上设置断点。 在程序崩溃的情况下,传统的调试器对于精确定位崩溃的位置很有用。然后,您应该开始在程序中回溯,使用断言和重新编译,以找到程序出错的地方。这些断言应该留在程序中,以备将来可能添加的错误使用。 - 用于调试的数据可视化 通常很难理解您的程序在做什么,因为它在最终出错之前计算了许多中间结果。解决方案是相同的:制作好的图表和插图,以了解数据的含义。 例如,在光线追踪器中,你可能会编写代码来可视化光线树,这样你就可以看到什么路径促成了一个像素。 为了可视化程序的内部状态而编写代码所花费的时间也会在优化程序时更好地理解它的行为。
w 是整个场景的缩放系数
2D 三角形面积:$A = \frac{1}{2} \begin{vmatrix} x_b-x_a & x_c-x_a \ y_b-y_a & y_c-y_a \end{vmatrix}$,abc 三点逆时针排列时 A 为正,反之为负。 2D 三角形内的点:$P = \alpha a+\beta b+ \gamma c\quad where \quad \alpha+\beta+\gamma = 1 \quad \alpha, \beta, \gamma \lt 1$
重心坐标(Barycentric coordinates)和你想的不太一样。。。
对于空间三角形 P1P2P3 内任一点 P,必定唯一存在三个数 w1,w2,w3,满足:w1+w2+w3=1 P=w1P1+w2P2+w3*P3 (即 P 表示成 P1,P2,P3 的线性组合) 则(w1,w2,w3)就称为此三角形上 P 点的(归一化)重心坐标(Barycentric coordinates)。
重心坐标的分量越接近 1,表示支点 p 越远离分量的对边。
采样,采样得越多计算出来越接近积分真值。
PDF:probability density function 概率密度函数 Cumulative Distribution Function, CDF 累计分布函数
公式化打法:
- 确定采样得函数与定义域
- 确定一个随机生成采样点得算法,同时确定采样点的概率密度函数
- 计算${f(x_i)}, / ,{p(x_i)}$的均值
[!note] 蒙特卡洛积分的正确性说明
$$E(I) = E\big(\frac{1}{n}\sum_{k=1}^n \frac{f(X_k)}{pdf()X_k}\big)$$ >$$E(I) = \frac{1}{n}\sum_{k=1}^n E\big(\frac{f(X_k)}{pdf()X_k}\big)$$ >$$E(I) = \frac{1}{n}\sum_{k=1}^n E\big(\int \frac{f(x)}{pdf(x)} \cdot pdf(x),dx\big)$$ >$$E(I) = \frac{1}{n}\sum_{k=1}^n \int f(x),dx$$ >$$E(I) = \int f(x),dx$$
上式说明蒙特卡洛积分是无偏的 另外蒙特卡洛积分的方差是:$D(I)\propto \frac{1}{\sqrt{n}}$ 顺带一提,写程序的时候先置 pdf 为均匀采样,为了方便调试。