2025年计算机图形学笔记 -- 基本图形的扫描转换

大家好，我是讯享网，很高兴认识大家。

图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。1. 确定有关像素；2. 对像素进行写操作。

一、直线的扫描转换

直线的扫描转换是在屏幕像素点阵中确定**逼近于理想直线的像素点集的过程。
常用算法：数值微分算法DDA；中点Bresenham画线算法。

数值微分算法（DDA）：增量思想

$\large y_{i+1}= y_{i}+k$
讯享网

中点Bresenham画线算法

Jack Elton Bresenham是IBM的科学家，他最知名的一项创新就是Bresenham直线算法。
算法原理

设给定直线起点坐标为 $\large p_{0}\left ( x_{0},y_{0} \right )$ ，终点坐标为 $\large p_{1}\left ( x_{1},y_{1} \right )$

则直线的隐函数方程为： $\large F(x,y)=y-kx-b=0$

直线斜率为： $k=\frac{\Delta y}{\Delta x}=\frac{y_{1}-y_{0}}{x_{1}-x_{0}}$

直线在水平方向上的位移： $\Delta x=x_{1}-x_{0}$

直线在垂直方向上的位移： $\Delta y=y_{1}-y_{0}$

假定： $0\leq k\leq 1$ ，则确定x方向为主位移方向

每次在主位移方向上移动，另一个方向则根据中点误差项的值决定是否移动

$\large {\color{Golden} }d_{i}=y_{i}+0.5-k\left ( x_{i} +1\right )-b$

$\large y_{i+1}=y_{i}+1,\left ( d_{i}<0 \right )$ $\large y_{i+1}=y_{i},\left ( d_{i}\geq 0 \right )$

递推公式

当 $\large d_{i}< 0$ 时： $\large d_{i+1}=d_{i}+1-k$

当 $\large d_{i+1}\geq 0$ 时:： $\large d_{i+1}=d_{i}-k$

中点误差项的初始值 $d_{0}$ ,第一个中点坐标是M( $x_{0}+1,y_{0}+0.5$ )，则 $\large d_{0}$ 为：

$\large d_{0}=0.5-k$

总结

首先，确定主位移方向；
计算 $\large d_{0}$ ；
计算 $\large d_{i}$ 的递推公式；

二、圆的扫描转换

圆的扫描转换是在屏幕像素点阵中确定**逼近于理想圆的像素点集的过程。
算法原理

圆心在原点，半径为R的圆方程的隐函数表达式为： $F\left ( x,y \right )=x ^{2}+y^{2}-R^{2}=0$

根据圆的对称性，可以用四条对称轴 x=0, y=0, x=y, x=-y 把圆分成8等份。

绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八分法画圆算法。

$x\in \left [ 0,\frac{R}{\sqrt{2}} \right ]$

构造中点误差项 $d=\left ( x_{i}+1 \right )^{2}+\left ( y_{i}-0.5 \right )^{2}-R^{2}$

因此， $y_{i+1}=y_{i} (d<0)$ , $y_{i+1}=y_{i}-1 (d\geq 0)$

递推公式

当 $d_{i}<0$ 时， $d_{i+1}=d_{i}+2x_{i}+3$

当 $d_{i}\geq 0$ 时， $d_{i+1}=d_{i}+2(x_{i}-y_{i})+5$

$d_{0}=1.25-R$

void CTestView::MBCircle(double R,CDC *pDC) { double x,y,d; d=1.25-R;x=0;y=R; for(x=0;x<=y;x++) { CirclePoint(x,y,pDC); //调用八分法画圆子函数 if(d<0) d+=2*x+3; else { d+=2*(x-y)+5; y--; } } } void CTestView::CirclePoint(double x,double y,CDC *pDC) //八分法画圆子函数 { //圆心坐标 CP2 pc=CP2((p0.x+p1.x)/2.0,(p0.y+p1.y)/2.0); //定义圆的边界颜色 COLORREF dr=RGB(0,0,255); pDC->SetPixelV(Round(x+pc.x),Round(y+pc.y),clr);//x,y pDC->SetPixelV(Round(y+pc.x),Round(x+pc.y),clr);//y,x pDC->SetPixelV(Round(y+pc.x),Round(-x+pc.y),clr);//y,-x pDC->SetPixelV(Round(x+pc.x),Round(-y+pc.y),clr);//x,-y pDC->SetPixelV(Round(-x+pc.x),Round(-y+pc.y),clr);//-x,-y pDC->SetPixelV(Round(-y+pc.x),Round(-x+pc.y),clr);//-y,-x pDC->SetPixelV(Round(-y+pc.x),Round(x+pc.y),clr);//-y,x pDC->SetPixelV(Round(-x+pc.x),Round(y+pc.y),clr);//-x,y }

讯享网

三、反走样技术

走样（Aliasing）：由离散量表示连续量引起的失真；走样是理想直线扫描转换后的必然结果，不可避免，只能减轻。

反走样/抗锯齿（Anti-Aliasing,AA）：用于减轻走样现象的技术。一类是硬件技术，一类是软件技术。

硬件技术：提高显示器分辨率，不是理想的反走样技术；

软件技术：加权区域采样

Wu反走样算法：根据像素和理想直线的距离对响铃两个像素的亮度等级进行调节。