光栅算法
多数计算机图形图像，是通过光栅显像显示给用户的。这种系统将图像作为像素阵列进行显示，像素即图像元素。这些像素采用RGB颜色空间。
一、光栅显像
台式机和投影显示器的显示技术有多种。这些显示器的分辨率和物理尺寸各不相同。编程人员通常假设像素排成矩形阵列，又称为光栅。
像素
光栅显示器上可显示元素称为像素。在显示器上，通常用有序对(i,j)来表示像素的索引，即表示该像素所在的行和列。如果一台显示器具有m行，n列像素，则左下角的元素是像素(0,0),右上角的元素是像素(m-1,n-1)。
我们需要用实际的二维屏幕坐标来表示像素的位置。随着API的不同，这些系统在细节上会有所不同，但是最常使用的是用整数点阵作为像素中心，如下图中4X3屏幕所示。由于像素占据一定的空间，所以距离像素中心具有0.5个单位的过冲。
物理像素，就是硬件上实际可显示的元素。不同的显示系统采用不同的物理像素，多数显示系统的像点呈水滴状或者呈方形。水滴状像点，即在像素中间密度最大，向边缘方向密度逐渐减小；方形像点，几乎都是正方形，并且各正方形之间有一段小间隙，这样可使控制电路获得像素信息。
二、显示器的亮度和γ值
现代显示器采用数字信号输入方式，接收的是数字信号表示的像素"值"，然后将其转化为亮度值。断电后显示器的亮度实际上不是零，因为屏幕能够反射环境管线。不过我们可以认为此时显示器呈"黑色"，显示器完全打开是呈"白色"。对像素颜色用0到1的数值来表示。黑色为0，白色为1，介于黑白中间的中间灰色为0.5。注意这里"中间"指的是从像素发出光线的强度，而不是指观察到的亮度。
为了在显示器上产生图像，要明白两个关键问题。第一，显示器输入信号的处理是非线性的。对于多数显示器，一般利用γ值来近似表示其非线性，具体数值公式如下：
显示亮度=(最大亮度)pow(α，γ) (1)
其中α是介于0到1之间的输入亮度值。如显示器的γ值为2.0，输入值α=0.5，则显示亮度是最大亮度的1/4。用γ值表示显示器的非线性知识一阶近似，实际中在估计设备的γ值时不需要很高的精度。一种度量非线性的直观方法是，找到能产生黑白之间的中间亮度的α值，即下式中的α值：
0.5=pow(α，γ) (2)
如果能找到满足上式的α值，则能够求出γ值：
γ=ln(0.5)/lnα (3)
一旦知道了γ值，就可以对输入进行伽马校正，使得输入值α=0.5可以在屏幕上显示出介于黑白中间的灰度效果。变换方法为：
α=pow(α，1/γ) (4)
把该式带入(1)式可得：
显示亮度=γ*(pow(α,1/γ))*(最大亮度)=α*(最大亮度)
实际显示器的另一个重要特征是，输入值通常经过了量化处理。因此，我们能够在浮点范围[0,1]内处理亮度值。输入显示器的信息一般是大小固定的非负整数，取值范围一般是0-255，可采用8位二进制数存储。
三、RGB颜色
计算机图形学中，多数显示效果都有RGB颜色空间确定。RGB颜色空间比较简单，经转换能够直接控制多数计算机屏幕的显示。下面我们将从用户观察的角度讨论RGB颜色空间，RGB颜色空间的基本思想是，将红、绿、蓝三种基色光混合产生新的颜色。对于RGB加性颜色空间，我们有下列混合效果：
红色 + 绿色 = 黄色
绿色 + 蓝色 = 青色
蓝色 + 红色 = 紫红色
红色 + 绿色 + 蓝色 = 白色
“青色”是一种蓝绿色，“紫红色”是一种紫色。
如果让基色光的强度有最小到最大变化，就能在RGB显示器上显示所有的颜色。根据惯例，把单色的最亮状态表示为1，则颜色值为0-1的分数。这样就产生出一种三维RGB颜色立方体，红、绿、蓝为坐标轴，坐标值由0-1变化。 
四、α通道
我们经常想只覆盖像素的部分内容。最常见的是，在合成图像时，我们想在背景上面插入一幅前景图片。对于前景中不透明的像素，我们只需要用它们替换相应位置的背景像素即可，对于完全透明的前景像素，背景像素不再改变。而对于半透明的像素，当前景图片中有像玻璃这样的半透明区域时，或者在前景图片中有子像素孔洞时，就会出现半透明的像素。在有像素孔洞这样的情况下，为了将前景与背景混合，就要权衡像素作为前景的分数。该像素用α表示。如果想把前景色cf与背景色cb混合，并且被前景覆盖的像素的分数为α，那么就可以采用下面的公式：
c = α*cf + (1-α)*cb
其中，需要注意的是，图中的α图像可以存储为RGB图像，也可以存储为单通道的灰度图。
利用上式合成图像的示例，实际上在前景图与背景图混合之前，先经过α通道进行了修剪处理。
五、直线绘制
多数图形软件都包含直线绘制命令，即捕捉屏幕上的两个点的坐标，并在它们之间画一条直线。对一般的屏幕坐标点(x0,y0)和(x1,y1)，常规做法是在它们之间画出合适的像素点集，这些点近似一条直线。为了简化处理，x0、x1、y0、y1的值经常规定为整数(像素中心)，因为直线本身就比较粗略，要求子像素精度并不合适。我们基于直线方程进行直线绘制，有两种类型的方程可供选择：隐式方程和参数方程。
1、基于隐式方程绘制直线
基于隐式方程绘制直线最常用的算法是中点算法。中点算法结束时绘制的直线和Bresenham算法的结果一样，只是中点算法更加直接。
首先找到直线的隐式方程：
f(x,y) ≡ (y0-y1)*x + (x0-x1)y + x0*y1-x1*y0 = 0
假设x0≤x1。若不满足该条件，交换点的顺序使之成立。直线的斜率为：
m = (y1-y0)/(x1-x0)
在下面的讨论中都假设m∈(0,1]。类似的，可以推出m∈(-∞,-1]、m∈(-1,0]和m∈(1,∞)时的结果。这四种情况覆盖了所有的可能情况。
当m∈(0,1]时，直线在x轴上的变化速度大于在y轴上的变化速度。我们可以忽略对于y轴向下的坐标系，可以不考虑几何上的"升"和"降"，因为两种情况的代数表示都是一 样的。中点算法的重要假设是，我们能绘制出没有间隔的最细的直线，两对角像素之间的连接被认为没有间隔。
绘制直线时，从左端点向右端点进行。只有两种可能：绘制一像素时，和左边所绘像素高度一样，或者高出一个像素。在两端点之间每一列，总是只有一个像素。没有 像素就意味着有间隔，有两个像素就意味着太粗。就我们现在讨论的情况来看，同一行上可以有两个像素，因为直线更接近于水平，因此其走势是向右或者向上。这种认识 如图所示：
针对m∈(0,1]情况中的中点算法，首先建立最左边的像素，以及最右边像素的列号(x值)，然后沿水平方向循环建立每个像素的行号(y值)。该算法的基本形式如下：
y = y0
for x = x0 to x1 do
draw(x,y)
if(condition) then
y += 1
其中x,y都是整数。简单的说就是从左至右不断绘制像素，在该过程中有时需要向y轴正向有所偏移。关键是如何确定if
一种有效的方法是，参考两候选点之间的中点位置。更具体地说，对于刚绘制的像素点(x,y)，它在屏幕上的坐标为(x,y)，下面要绘制的候选像素为(x+1,y)和(x+1,y+1)。两 个候选点之间的中点为(x+1,y+0.5)。如果直线通过中点的下方，就绘制下面的像素，如果直线通过中点的上方，就绘制上面的像素，如图所示：
判断直线是通过点(x+1,y+0.5)的上方还是下方，可以通过直线方程f(x+1,y+0.5)的值来判断。在计算机图形学的数学知识中讨论过，位于直线上的点(x,y),满足f(x,y)=0；位于直线一边的点满足f(x,y)>0;位于直线另一边的点满足f(x,y)<0。由于-f(x,y)和f(x,y)=0都可以作为直线的方程，所以很难利用f(x,y)的正负来快速判断(x,y)究竟位于直线的上方还是下方。但是在直线方程中的关键项是关于y的项(x1-x0)*y。要注意(x1-x0)肯定为正数，因为x1>x0。这就意味着随着y的增大，(x1-x0)*y项的值将变大。因此f(x,+∞)肯定为正，并且位于直线的上方，也就是说直线上方的点都是正的。另一种判断方法是，由于梯度向量中的y分量是正的，因此在直线的上方y可以任意增加，f(x,y)也就肯定是正的。于是我们可以把语句中的条件写具体，代码更明确了：
if f(x+1,y+0.5)<0 then
y += 1
对于有适当斜率(介于0和1之间)的直线，上面的代码非常有效。
如果希望有更高的效率，就使用增量方法。增量方法利用上一步计算的结果，是循环更高效。在上述中点算法中，主要步骤是计算f(x+1,y+0.5)的值。可以看出，在循环内部，经过第一次迭代，我们已经算出f(x-1,y+0.5)或者f(x-1,y-0.5)的值。顾存在以下关系：
f(x+1,y) = f(x,y)+(y0-y1)
f(x+1,y+1)=f(x,y)+(y0-y1)+(x1-x0)
于是就有了如下增量算法的代码：
y = y0
d = f(x0+1,y0+0.5)
for x = x0 to x1 do
draw(x,y)
if d < 0 then
y += 1
d = d + (y0-y1)+(x1-x0)
else
d = d + (y0-y1)
与非增量算法相比，该增量算法需要的额外调整很少，因此具有更高的运行效率，但是对于长直线来说，由于包含很多次加法运算，会存在一定的数值误差。
在程序中，如果只有整数参加运算，算法执行起来会更快。由于已经规定x0、x1、y0、y1位整数，上面的算法也就是整数运算了。但是，初始化时还是要用到d=f(x+1,y+0.5)。将该表达式进行扩展得到：
f(x0+1,y0+0.5)=(y0-y1)*(x0+1)+(x1-x0)*(y0+0.5)+x0*y1-x1*y0
其中y0+0.5不是整数运算，结果是非整数之间做乘法运算。我们已经知道如果f(x,y)=0是直线方程，那么2f(x,y)=0也是同一直线方程。因此，我们可以用2f(x,y)代替f(x,y)，于是d的表达式就变成：
2f(x0+1,y0+0.5)=2*(y0-y1)*(x0+1)+(x1-x0)*(2y0+1)+2*x0*y1-2*x1*y0
上面的所有项都成了整数项，算法代码变为：
y = y0
d =2*(y0-y1)*(x0+1)+(x1-x0)*(2y0+1)+2*x0*y1-2*x1*y0
for x = x0 to x1 do
draw(x,y)
if d < 0 then
y += 1
d = d + 2*(y0-y1)+2*(x1-x0)
else
d = d + 2*(y0-y1)
注意：在执行上面的全整数运算代码之前，必须检查m∈[0,1)是否满足，我们可以用下式来判断：
(y1>=y0)&&((x1-x0)>(y1-y0)) ≡ m∈[0,1)
2、基于参数方程绘制直线
我们在计算机图形学的数学知识中讨论过，过两点p0 = (x0,y0)和p1 = (x1,y1)的直线参数方程为：
(x,y) = (x0+t*(x1-x0),y0+t*(y1-y0))
等价向量为：
p = p0 + t*(p1-p0)
如果直线斜率m∈[-1,1]，那么for循环就可以沿x轴继续执行，而且代码很简洁。对于[-1,1]之外的m，可以得到类似的算法。因为t是沿直线推进固定的长度，直线的x和y分量也一样，这样就可以把t看做x的函数：
t=(x-x0)/(x1-x0)
得到的代码为:
for x = x0 to x1 do
t=(x-x0)/(x1-x0)
y = y0+t*(y1-y0)
draw(x,round(y))
该算法的一个优点是不论x1-x0>0是否成立，算法都能够正常运行。可以看出基于直线参数方程的代码非常简洁，但是不能将代码设计为只处理整数。在很多计算机语言中，从浮点数到整数都是采用的截断处理，因此，round(y)项可以作为(y+0.5)的取整结果。
因为在每次迭代中t和y的变化都是一个常量，因此可采用增量算法：
△y = (y1-y0)/(x1-x0)
y = y0
for x = x0 to x1 do
draw(x,round(y))
y += △y
有时用两端点的RGB颜色c0和c1来确定直线的颜色。我们希望沿着直线颜色能够均匀的改变。如果想根据t∈[0,1]对线段参数化，则可用下面的公式：
c = (1-t)*c0 + c1
这样就能算出每个像素的颜色。
六、三角形光栅化
在屏幕坐标系中，我们经常会想到绘制一个过二维点p0=(x0,y0)、p1=(x1,y1)和p2=(x2,y2)的二维三角形。与绘制直线一样，希望能够根据顶点的数值插入颜色或者其他性质。如果存在重心坐标系，就可以直接计算插入值。例如，假设顶点的颜色值为c0、c1、c2，在重心坐标为(α，β，γ)的三角形内部，某点的颜色值为：
c=α*c0 + β*c1 + γ*c2
这种颜色插值方法在图形学中称为Gouraud插值法。
光栅化三角形的另一个特别之处是，我们通常对具有公共顶点和公共边的那些三角形进行光栅化。这就意味着要光栅化的是相邻三角形，因此没有空隙。可以使用中点算法画出每个三角形的轮廓，然后填入内部像素，从而实现三角形光栅化。因此，相邻三角形在邻边出都绘制了相同的像素。如果相邻三角形的颜色不同，则图形将由两个三角形的绘制顺序决定。为了避免顺序问题并且消除空隙，最常用的三角形光栅化方法是利用下面的约定：当且仅当一个像素的重心位于三角形内部时，才绘制该像素。也就是说，像素中点的重心坐标都在区间(0,1)内。关键结论在于：当我们根据顶点插入颜色时，利用重心坐标系可以确定是否该绘制一个像素，以及该像素是什么颜色。于是问题变为如何能快速找到像素中心的重心坐标。蛮力光栅化算法如下：
for all x do
for all y do
compute(α，β，γ) for (x, y)
if (α∈(0, 1)) && (β∈(0, 1)) && (γ∈(0, 1)) then
c=α*c0 + β*c1 + γ*c2
drawpixel(x, y) whith color c
算法的其余部分把外部循环限制在更小的候选像素集，使重心计算快速有效。
寻找三顶点的包围矩形，只对该矩形内的候选像素执行循环，这样就能提高算法效率。利用β=fac(x,y)/fac(xb,yb)来计算重心坐标。于是算法变为：
xmin = floor(xi)
xmax = ceil(xi)
ymin = floor(yi)
ymax = ceil(yi)
for y = ymin to ymax do
for x = xmin to xmax do
α = f12(x,y)/f12(x0,y0)
β = f20(x,y)/f20(x1,y1)
γ = f01(x,y)/f01(x2,y2)
if (α > 0 && β >0 && γ > 0) then
c = α*c0 + β*c1 + γ*c2
drawpixel(x, y) whith color c
其中fij是根据适当顶点，通知直线方程确定的：
f01(x,y) = (y0 - y1)*x + (x1 - x0)*y + x0*y1 - x1*y0
f12(x,y) = (y1 - y2)*x + (x1 - x2)*y + x1*y2 - x2*y1
f20(x,y) = (y2 - y0)*x + (x2 - x0)*y + x2*y0 - x0*y2
其中我们用α>0代替了α∈(0,1)是因为α+β+γ=1,如果它们三个都大于0的话，它们三个必然都是小于1的。同样我们可以只算出重心坐标的两个，然后利用它们的关系求出第三个。与绘制直线的算法类似，这时的算法同样也可以使用增量算法，每次计算α、β、γ，也就是计算f(x,y)=A*x+B*y+C的值。在内部循环中，只有x变化，每次变化1.要注意f(x+1,y) = f(x,y) + A，这是增量算法的基础。在外部循环中，由计算f(x,y)变成计算f(x,y+1)，因此计算效率类似。由于在循环中(α，β，γ)的变化增量是固定的，颜色c的变化也一样，因此该算法也可以变为增量算法。三角形颜色插值的实例如下图所示：
处理三角形边上的像素
我们还没有讨论如何处理那些中心位于三角形边上的像素。如果一个像素正好落在三角形边上，那么它同时还位于相邻三角形的边上。没有明确的方式来确定该像素属于哪个三角形。最坏的决定就是不绘制该像素，这时两个三角形之间就会出现一个空隙。如果在两个三角形上都绘制该像素，情况会好一点，但这仍然不是最好的解决方式。如果三角形是透明的，就会出现重复绘制。
屏幕外的任何一点肯定位于要绘制的公共边的一侧。对两个互不重叠的三角形来说，不在公共边的顶点位于公共边的相对两侧。这些顶点中正好有一个与屏幕外的点处在同一侧。
f01(x,y) = (y0 - y1)*x + (x1 - x0)*y + x0*y1 - x1*y0
七、简单反走样技术
前面讲过的直线绘制和三角形绘制算法，普遍存在锯齿现象。如果允许像素值变低或变高一些，则可以减轻这种视觉上的不足。例如，对于白色背景上的一个黑色三角形，如果一个像素的中心几乎位于该三角形的内部，则可以将该像素设为黑白之间的颜色。在实际应用中，这种模糊化处理可以改进视觉效果，尤其是在动画制作中。
构造"无锯齿"图像的最直接方法就是采用盒式滤波器，将像素设置为盒式区域的平均颜色值。这就意味着，要把所有可绘制的实体都看做已经明确定义的区域。像中点算法产生的锯齿状直线这样的现象，是走样造成的结果。因此，通过认真选择像素值来避免锯齿现象的技术，称为反走样技术。盒式滤波器可以满足多数情况的需要，适用于对视觉质量要求不是特别高的场合。
实现盒式滤波器反走样最容易的办法是，先建立高分辨率图像，然后进行下采样。例如，我们要处理一幅256X256的图像，其中直线宽度为1.2个像素。可以在1024X1024的屏幕上，对宽度为4.8像素的直线段构成的矩形区域进行光栅化处理，然后对像素进行4X4的平均，得到256X256的压缩图像。这是对实际图像的近似盒式滤波，如果目标和对于像素间距不是特别小的话，这种党阀的效果还是非常好的。
八、图像捕捉与存储
1.扫描仪和数码摄像机
扫描仪和数码摄像机使用某些类型的光感芯片来记忆光能。其核心技术是CCD和CMOS阵列。这些阵列可以感测所有波长的光强。要获得彩色图像，一种方法是将光线分成三路，然后经红、绿、蓝三片滤光器进行滤光，经同一硅片的三个滤光器之后就生成了红、绿、蓝三色光。另一种方法是，在硅片的各个传感器上分别覆盖不同的彩色滤光层。
2.图像存储
在多数RGB图像格式中，红、绿、蓝通道各占8位二进制数，因此存储一幅百万像素的元素图像大约需要3MB。为减少所需的存储空间，多数图像格式都进行某种形式的压缩。这种压缩分为无损压缩和有损压缩。在无损压缩中 信息不会丢失；有损压缩中会丢失部分信息，而且是不可恢复的丢失。常见的图像存储格式包括：
gif：有损压缩格式，只能表示出256种可能的颜色。图像质量取决于这256种颜色的选择。这种格式适用于自然图像。
jpeg：有损压缩格式，以人类视觉系统的阈值为基础。适用于自然图像。
tiff：无损压缩格式，每个像素通常占24位的常用压缩格式，虽然存在很多其他的可选格式。
ppm：无损压缩格式，每个像素通常占24位的常用未压缩格式，虽然存在很多其他的可选格式。
png：无损格式的集合，具有很好的开放源码管理工具。