图形系统与基本图形生成

本节导读

计算机图形学大纲分四个部分：图形学和图形系统基本知识；基本图形生成和几何变换；三维物体的表示与显示处理；真实感图形绘制技术。本课用三节讲：本节讲第一部分和第二部分中的直线、二次曲线（以圆为主）的生成、字符和区域填充；第 30 节讲几何变换、窗口视图变换、裁剪和投影；第 31 节讲曲线曲面、三维物体表示和真实感图形。

按常见资料的说法，图形学的题型是判断、填空和问答。本节能出计算的是帧缓存容量和画线、画圆算法的逐步推演，要会列表写出每一步的判别量和像素。

计算机图形学与图形系统

计算机图形学研究怎样用计算机表示、生成、处理和显示图形。图形一般指由点、线、面等几何要素和颜色等属性描述的对象（矢量表示），图像指由像素点阵描述的画面；光栅显示时图形最终也要转成像素。应用领域有计算机辅助设计、科学计算可视化、虚拟现实、计算机动画、游戏和图形用户界面等。

图形系统由硬件和软件组成。光栅扫描显示器把屏幕看成像素阵列，帧缓存（显示存储器）为每个像素保存颜色值，显示控制器按扫描顺序反复读帧缓存来刷新屏幕；帧缓存容量 = 水平分辨率 × 垂直分辨率 × 每像素位数 ÷ 8（字节），每像素 $n$n 位时可同时显示 $2^n$2n 种颜色。采用颜色查找表时，帧缓存只存表的索引。随机扫描（矢量）显示器则按显示文件直接画线段。

图形软件的标准有 GKS（第一个国际二维图形标准）、PHIGS（支持三维和层次结构）、CGI（设备接口）、CGM（图元文件格式）等。OpenGL 是与硬件和窗口系统无关的图形程序接口，按状态机方式工作：顶点数据经变换、裁剪、视口变换后光栅化成片元，再经纹理、深度测试等处理写入帧缓存。

直线生成算法

画直线就是确定最接近理想直线的像素。下面都以斜率 $0 \le k \le 1$0≤k≤1 为例，其余情况利用对称性处理。

算法	思想	特点
DDA（数值微分法）	$x$x 每步加 1，$y$y 每步加 $k$k，再取整	简单，但有浮点运算和取整
中点画线法	用直线方程判断两候选像素的中点在直线上方还是下方	只用整数加法
Bresenham 算法	用误差项判断下一个像素取 $y$y 还是 $y + 1$y+1	只用整数加法，应用最广

Bresenham 算法：设 $\Delta x = x_1 - x_0$Δx=x1​−x0​，$\Delta y = y_1 - y_0$Δy=y1​−y0​，判别量初值 $p_0 = 2\Delta y - \Delta x$p0​=2Δy−Δx。每步 $x$x 加 1：若 $p < 0$p<0，$y$y 不变，$p \leftarrow p + 2\Delta y$p←p+2Δy；否则 $y$y 加 1，$p \leftarrow p + 2\Delta y - 2\Delta x$p←p+2Δy−2Δx。中点画线法的思路相同：直线写成 $F(x, y) = ax + by + c$F(x,y)=ax+by+c，判别中点代入后的符号，结果与 Bresenham 一致。光栅化的直线会出现锯齿（走样），可以用提高分辨率、超采样或区域采样等反走样方法减轻。

圆的生成算法

圆具有八分对称性：算出圆心在原点的圆上一点 $(x, y)$(x,y)，就能直接得到 $(\pm x, \pm y)$(±x,±y)、$(\pm y, \pm x)$(±y,±x) 共 8 个点，所以只需计算从 $(0, R)$(0,R) 到 $x = y$x=y 的八分之一圆弧。

中点画圆法：从 $(0, R)$(0,R) 开始，每步 $x$x 加 1，在正右方和右下方两个候选像素中选一个。判别式 $d$d 是两候选像素的中点代入 $F(x, y) = x^2 + y^2 - R^2$F(x,y)=x2+y2−R2 的值，初值 $d_0 = 1.25 - R$d0​=1.25−R。若 $d < 0$d<0，中点在圆内，取正右方像素，$d \leftarrow d + 2x + 3$d←d+2x+3；否则取右下方像素，$d \leftarrow d + 2(x - y) + 5$d←d+2(x−y)+5，这里的 $x$x、$y$y 是当前像素的坐标。$d_0$d0​ 也可以取 $1 - R$1−R，对整数半径结果相同。椭圆等二次曲线可以用类似的中点算法生成。

区域填充

扫描线多边形填充按扫描线逐条处理：求扫描线与多边形各边的交点，按 $x$x 排序，两两配对，填充每对交点之间的像素。为了提高效率，用边表（ET）和活性边表（AET）保存边的信息，利用相邻扫描线交点的连贯性增量计算交点。扫描线经过顶点时：若顶点是局部极值点（相邻两边在扫描线同一侧），计为两个交点；否则只计一个交点。