12月16, 2018

基本图形生成技术——直线

图形的生成:是在指定的输出设备上,根据坐标描述构造二维几何图形。 图形的扫描转换:在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。

直线段的扫描转换算法

数值微分(DDA)

假定直线的起点、终点分别为:(x0,y0), (x1,y1),且都为整数。

alt

基本思想

    已知过端点P0 (x0, y0), P1(x1, y1)的直线段L

    y=kx+b

    直线斜率为

    K=(y1-y0)/(x1-x0)

    计算yi+1= kxi+1+b
           = kxi+b+k△x
           = yi+k△x 
    当△x=1;     yi+1 = yi+k 
    即:当x每递增1,y递增k(即直线斜率);
    注意上述分析的算法仅适用于|k| ≤1的情形。在这种情况下,x每增加1,y最多增加1。
    当|k| > 1时,必须把x,y地位互换

    增量算法:在一个迭代算法中,如果每一步的x、y值是用前一步的值加上一个增量来获得,则称为增量算法。
    DDA算法就是一个增量算法。
    这种方法直观,但效率太低,因为每一步需要一次浮点乘法和一次舍入运算。
void DDALine(int x0,int y0,int x1,int y1,int color) {
    int x;
    float dx, dy, y, k;
    dx = x1-x0; dy=y1-y0;
    k=dy/dx; y=y0;
    for (x=x0; xx1; x++) {
      drawpixel (x, int(y+0.5), color);
      y=y+k;
    }
}

中点画线法

原理:假定直线斜率0<K<1,且已确定点亮象素点P(Xp ,Yp ),则下一个与直线最接近的像素只能是P1点或P2点。设M为中点,Q为交点

alt

1.当M在Q的下方-> P2离直线更近更近->取P22.M在Q的上方-> P1离直线更近更近->取P1
3.M与Q重合, P1P2任取一点。

alt

问题:如何判断M与Q点的关系?

假设直线方程为:ax+by+c=0
其中a=y0-y1, b=x1-x0, c=x0y1-x1y0
由常识知:

alt

∴欲判断M点是在Q点上方还是在Q点下方,只需把M代入F(x,y),并检查它的符号。
构造判别式:
    d=F(M)=F(xp+1,yp+0.5) 
     =a(xp+1)+b(yp+0.5)+c
    1.当d<0,M在直线(Q点)下方,取右上方P2;
    2.当d>0,M在直线(Q点)上方,取右方P1;
    3.当d=0,选P1或P2均可,约定取P1;
若d>=0则M在直线上方->取P1;
此时再下一个象素的判别式为
    d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c
      = a(xp +1)+b(yp +0.5)+c +a =d+a;
增量为△d1=a
若d<0则M在直线下方->取P2;
此时再下一个象素的判别式为
     d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c
         = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ; 增量为△d2=a+b

画线从(x0, y0)开始,d的初值
    d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0  +0.5)+c
      = F(x0, y0)+a+0.5b = a+0.5b 
由于只用d 的符号作判断,为了只包含整数运算, 
可以用2d代替d来摆脱小数,提高效率。
void Midpoint Line (int x0,int y0,int x1, int y1,int color){   
    int a, b, d1, d2, d, x, y;
    a=y0-y1; b=x1-x0; d0=2*a+b;
    d1=2*a; d2=2* (a+b);
    x=x0; y=y0;
    drawpixel(x, y, color);
    while (x<x1){ 
        if (d<0) {
            x++; 
            y++; 
            d+=d2; 
        } else {
            x++; 
            d+=d1;
        }
        drawpixel (x, y, color);
    }  /* while */
} /* mid PointLine */

本文链接:https://www.opsdev.cn/post/scanningline.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。