图形基础理论

光栅图形学算法

• 像素点是离散的，每个像素点按行列式排布。
• 像素点坐标都是整数。
• 以下代码是示意代码，未验证

直线段扫描转换

P0(x0,y0) P_0(x_0,y_0)P0(x0,y0)`、`Pi(xi,yi)P_i(x_i,y_i)Pi(xi,yi)

=> y=kx+b y = kx + by=kx+b k=(yi−y0)(xi−x0)(xi≠x0) k = \frac{(y_i-y_0)}{(x_i-x0)} (x_i \neq x_0)k=(xi−x0)(yi−y0)(xi\\=x0) (截距式)

=> Pn=(xn,math.ceil(yn)) P_n = (x_n,math.ceil(y_n))Pn=(xn,math.ceil(yn))

    private Vector2[] BaseLine(int x0, int y0, int xi, int yi)
    {
        var dx = xi - x0;
        //这里忽略了 k = 0,Length = 0的情况;
        var k = (double)(yi - y0) / (dx);
        var b = y0 - x0 * k;

        var linePoints = new Vector2[dx + 1];

        for (int i = 0; i < dx; ++i)
        {
            //向下取整;
            linePoints[i] = new Vector2(i, (int)(k * (x0 + i) + b));
        }

        return linePoints;
    }

=> 一个乘法、一个加法、一个取整

DDA画线算法(数值微分法)

yi=kxi+b y_i = kx_i + byi=kxi+b

=> yi+1=kxi+1+b y_{i+1} = kx_{i+1} + byi+1=kxi+1+b

=> yi+1=k(xi+1)+b y_{i+1} = k(x_i+1) + byi+1=k(xi+1)+b

=> yi+1=kxi+b+k y_{i+1} = kx_i + b + kyi+1=kxi+b+k

=> yi+1=yi+k y_{i+1} = y_i + kyi+1=yi+k

这里也可以看成一个等差数列，an=a1+(n−1)×d a_n = a_1 + (n - 1) \times dan=a1+(n−1)×d，但是我们要化简计算量，所以使用 an=an−1+d a_n = a_{n -1} + dan=an−1+d

    private Vector2[] DDALine(int x0, int y0, int xi, int yi)
    {
        var dx = xi - x0;
        //这里忽略了 k = 0,Length = 0的情况;
        var k = (double)(yi - y0) / (dx);
        var b = y0 - x0 * k;

        var linePoints = new Vector2[dx + 1];
        linePoints[0] = new Vector2(x0,y0);

        double last_y = y0;
        for (int i = 1; i < dx; ++i)
        {
            last_y += k;
            linePoints[i] = new Vector2(i, (int)(last_y));
        }

        return linePoints;
    }

=> 一个加法、一个取整

中点画线法

F(x+y)=0 F(x + y) = 0F(x+y)=0

=> Ax+By+C=0 Ax + By + C = 0Ax+By+C=0 其中：A=−(Δy);B=(Δx);C=−B(Δx) A = -(\Delta y);B = (\Delta x); C = -B(\Delta x)A=−(Δy);B=(Δx);C=−B(Δx) (直线一般式方程)

• 对于直线上的点：F(x,y)=0 F(x,y) = 0F(x,y)=0
• 对于直线上方的点：F(x,y)>0 F(x,y) > 0F(x,y)>0
• 对于直线下方的点：F(x,y)<0 F(x,y) < 0F(x,y)<0

=> Pi(xi,yi),Pu(xi+1,yi+1),Pd(xi+1,yi),Pm(xi+1,yi+0.5) P_i(x_i,y_i) , P_u(x_i + 1,y_i + 1),P_d(x_i + 1,y_i),P_m(x_i + 1,y_i + 0.5)Pi(xi,yi),Pu(xi+1,yi+1),Pd(xi+1,yi),Pm(xi+1,yi+0.5)，其中 Pu,Pd P_u,P_dPu,Pd 是下一个像素点的可能值,Pm P_mPm 是 Pu,Pd P_u,P_dPu,Pd 的中点。

=> di=F(xm,ym)=F(xi+1,yi+0.5)=A(xi+1)+B(yi+0.5)+C d_i = F(x_m,y_m) = F(x_i + 1,y_i + 0.5) = A(x_i + 1) + B(y_i + 0.5) + Cdi=F(xm,ym)=F(xi+1,yi+0.5)=A(xi+1)+B(yi+0.5)+C

=> Axi+Byi+C+A+0.5B Ax_i + By_i + C + A + 0.5BAxi+Byi+C+A+0.5B

• d < 0, y={y+1(d<0)y(d≥0) y = \begin{cases} y + 1 (d < 0) \\ y (d \geq 0) \end{cases}y={y+1(d<0)y(d≥0)
• d > 0,M在线上方， y=Pd y = P_dy=Pd
• d = 0,M在线上， y=Pd y = P_dy=Pd 或 y=Pu y = P_uy=Pu 均可。

=> di+1=di+? d_{i+1} = d_i + ?di+1=di+? => ∵ \because∵ d 是 x,y 的线性函数 ∴ \therefore∴ 可以采用增量计算的方式

=> ∵ \because∵ di=Axi+Byi+C+A+0.5B d_i = Ax_i + By_i + C + A + 0.5Bdi=Axi+Byi+C+A+0.5B 且 Pi(xi,yi) P_i(x_i,y_i)Pi(xi,yi) 直线上, ∴Axi+Byi+C=0 \therefore Ax_i + By_i + C = 0∴Axi+Byi+C=0

=> di=A+0.5B d_i = A + 0.5Bdi=A+0.5B

=> 因为只需要判断 d_i 的符号，所以可以用 2di 2d_i2di 来判断符号。

private Vector2[] MidPointLine(int x0, int y0, int xi, int yi)
    {
        //Ax+By+C=0 & A^2+B^2≠0;
        var A = -(yi - y0);
        var B = xi - x0;
        var C = -B ^ 2;

        var linePoints = new Vector2[B];
        linePoints[0] = new Vector2(x0, y0);

        double last_d = A * (x0 + 1) + B * (y0 + 0.5) + C;
        for (int i = 1; i < B; ++i)
        {
            if (last_d >= 0)
            {
                last_d += A;
                linePoints[i] = new Vector2(linePoints[i - 1].x + 1,linePoints[i- 1].y);
            }
            else
            {
                last_d += A + B;
                linePoints[i] = new Vector2(linePoints[i - 1].x + 1, linePoints[i - 1].y + 1);
            }
        }
        return linePoints;
    }

Bresenham算法

提高更广的适用范围

假设每次 x+1 x+1x+1 ,y的递增量为 0 或 1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为 0.5。

=> 误差项的 d0=0 d_0 = 0d0=0，d=d+k d = d+kd=d+k,一旦 d≥1 d \geq 1d≥1 就把它减去1，保证 d dd 的区间在[0,1)。

=> {xi+1=xi+1yi+1={yi+1(d>0.5)yi(d≤0.5) \begin{cases} x_{i+1} = x_i + 1 \\ y_{i+1} = \begin{cases} y_{i} + 1 (d > 0.5) \\ y_{i} (d \leq 0.5) \end{cases} \end{cases}⎩⎨⎧xi+1=xi+1yi+1={yi+1(d>0.5)yi(d≤0.5)

• 改进_1

令 e=d−0.5 e = d - 0.5e=d−0.5 ( e0=0.5 e_0 = 0.5e0=0.5) => {xi+1=xi+1yi+1={yi+1(e>0)yi(e≤0) \begin{cases} x_{i+1} = x_i + 1 \\ y_{i+1} = \begin{cases} y_{i} + 1 (e > 0) \\ y_{i} (e \leq 0) \end{cases} \end{cases}⎩⎨⎧​xi+1​=xi​+1yi+1​={yi​+1(e>0)yi​(e≤0)​​

• e>0 e > 0e>0 ,y yy 方向递增1 11
• e<0 e < 0e<0 ,y yy 方向不递增
• e=0 e = 0e=0 ,y yy 可选取上、下光栅点显示
• {ei=e0+k(i>0)k=ΔyΔx \begin{cases} e_i = e_0 + k(i > 0) \\ k = \frac {\Delta y} {\Delta x} \end{cases}{ei=e0+k(i>0)k=ΔxΔy , if (e > 0) then e -= 1;

• 改进_2

由于算法中知用用到误差项的符号，于是可以令 e=2eΔx e = 2 e \Delta xe=2eΔx

• e0=−Δx e_0 = - \Delta xe0=−Δx
• 每走一步有 e=e+2Δy e = e + 2 \Delta ye=e+2Δy
• if (e > 0) then e -= 2Δx 2 \Delta x2Δx ;

算法步骤

1. 输入直线的两端点 P0(x0,y0),P1(x1,y1)P_0(x_0,y_0), P_1(x_1,y_1)P0(x0,y0),P1(x1,y1);
2. 计算初始值 Δx,Δy,e=−Δx,x=x0,y=y0 \Delta x , \Delta y , e = - \Delta x , x = x_0 , y = y_0Δx,Δy,e=−Δx,x=x0,y=y0;
3. 绘制 (x,y);
4. e更新为 e+2Δy e + 2\Delta ye+2Δy,判断e的符号。如 e>0 e > 0e>0,则 (x,y) 更新为 (x+1,y+1),同时将e更新为 e−2Δx e - 2 \Delta xe−2Δx;否则 (x,y) 更新为 (x+1,y);
5. 当直线没有画完时，重复步骤3和4，否则结束。

private Vector2[] BresenhamLine(int x0, int y0, int xi, int yi)
    {
        var dx = xi - x0;
        var dy = yi - y0;
        var e = -dx;
        var x = x0;
        var y = y0;

        var linePoints = new Vector2[dx];
        linePoints[0] = new Vector2(x, y);

        for (int i = 1; i < dx; i++)
        {
            e += 2 * dy;
            x = x + 1;
            if (e > 0)
            {
                y = y + 1;
                e -= 2 * dx;
            }
            linePoints[i] = new Vector2(x,y);
        }

        return linePoints;
    }