图形扫描转换概念

图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。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反走样算法：根据像素和理想直线的距离对响铃两个像素的亮度等级进行调节。

一、直线的扫描转换

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

中点Bresenham画线算法

总结

二、圆的扫描转换

三、反走样技术

知秋君

相关推荐