TFT LCD Draw Line or Circle Arithmetic Analysis

Author: Apenper
Email: [e-mail]
QQ: 1005450581

Drawing a straight line in the TFT LCD is to determine a series of coordinations after the linear gating, and display in the LCD lattice, somebody calls this linear rasterizer. The linear rasterizer`s arithmetic contains mid-points line method \ DDA arithmetic(Numberical differentiation) \ Symettric algorithms and Bresenham algorithms. The following fig is the progress:


DDA algorithms:
DDA算法是一种增量算法，在一个迭代算法中，每一步的x 、y值是用前一步的值加一个增量来获得的。

Bresenham algorithms:
Bresenham可以说是DDA算法的简化版，DDA算法是某一个长的方向，每一次变化一个单位或者一个单位像素，另外一个方向的变化量可以通过浮点运算和四舍五入计算得到。而Bresenham算法对于下一个点的坐标的取值，则是通过判断一个反复迭代的误差因数是否大于零，而在迭代的计算误差因数的时候，只用到了整形数的加法和移位操作，计算量非常小，是最高效的单步画线算法。

The following fig is Bresenham algorithms progress:


由于Bresenham算法仅用到了整形数的加法和移位操作，大大减少了系统的运算量，便于在小型处理器利用应用。
Bresenham算法的实现与优化过程：
（1）原始模型
假定直线段的0<=k<=1，则有如下表达式：
x(i+1) = x(i) + 1;
y(i+1) = y(i) + 1, when d > 0.5;
y(i+1) = y(i), when d <= 0.5.
其中，d为误差项，d的初始值为0，每走一步，d = d + k（k为要画的线的斜率），一旦y方向上走上一步，d = d - 1.
算法步骤：
1）输入直线的两端点p0(x1, y1), p1(x2, y2);
2）计算初始值△x、△y, d = 0, x = x0, y - y0;
3）绘制点(x, y);
4）d更新为d + k，判断d的值，若d > 0.5, x = x + 1, y = y + 1, d = d - 1; 否则, x = x + 1, y = y;
5）当线未画完，则重复执行3）和4）.

第一次改进模型：
令e = d - 0.5, 则有如下公式：
x(i+1) = x(i) + 1;
y(i+1) = y(i) + 1, when e > 0;
y(i+1) = y(i), when e <= 0.
其中，e的初值为-0.5, 每走一步有e = e + k, 若e > 0, 则e = e - 1.
算法步骤：
1）输入直线的两端点p0(x1, y1), p1(x2, y2);
2）计算初始值△x、△y, e = -0.5, x = x0, y - y0;
3）绘制点(x, y);
4）e更新为e + k，判断e的值，若d > 0, x = x + 1, y = y + 1, e = e - 1; 否则, x = x + 1, y = y;
5）当线未画完，则重复执行3）和4）.

Bresenham算法的最后改进：
算法步骤：
1）输入直线的两端点p0(x1, y1), p1(x2, y2);
2）计算初始值△x、△y, e = -△x, x = x0, y - y0;
3）绘制点(x, y);
4）e更新为e + 2△y，判断e的值，若d > 0, x = x + 1, y = y + 1, e = e - 2△x; 否则, x = x + 1, y = y;
5）当线未画完，则重复执行3）和4）.

程序示例：
/***
 draw a pixel, color is from VD[0:23] --> [x x x x x NC NC NC x x x x x x NC NC x x x x x NC NC NC]
***/

void PutPixel(UINT32 x, UINT32 y, UINT32 color)

{

    UINT8 red, green, blue;

    switch (bpp){

        case 16: {

            UINT16 *addr = (UINT16 *)fb_base_addr + (y * xsize + x);

            red   = (color >> 19) & 0x1f;

            green = (color >> 10) & 0x3f;

            blue  = (color >>  3) & 0x1f;

            // convert to 565 format    
            color = (red << 11) | (green << 5) | blue;     // 格式5:6:5

            *addr = (UINT16) color;

            break;

        }

        

        case 8: {

            UINT8 *addr = (UINT8 *)fb_base_addr + (y * xsize + x);
            // color is 8bits index value in the palette

            *addr = (UINT8) color;

            break;

        }

        default:

            break;

    }

}

/***
   color value: for 16BPP, color`s format is 0xAARRGGBB(AA是透明度), need to convert to 565 format
                     for 8BPP, color is palette index value
 ***/     

void DrawLine(int x1, int y1, int x2, int y2, int color)

{

    int dx, dy, e;

    dx=x2 - x1; 

    dy=y2 - y1;

    

    if(dx >= 0) {

        if(dy >= 0) {     // dy>=0

            if(dx >= dy) {     // 1/8 octant

                e = dy - dx / 2;

                while(x1 <= x2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){
                        y1 += 1;
                        e -= dx;
                    }   

                    x1 += 1;

                    e += dy;

                }

            } else {        // 2/8 octant

                e = dx - dy / 2;

                while(y1 <= y2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){ x1 += 1; e -= dy; }   

                    y1 += 1;

                    e += dx;

                }

            }

        } else {               // dy<0
            dy = -dy;           // dy=abs(dy)

            if(dx >= dy) {        // 8/8 octant

                e = dy - dx / 2;

                while(x1 <= x2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){ y1 -= 1; e -= dx;}   

                    x1 += 1;

                    e += dy;

                }

            } else {        // 7/8 octant

                e = dx - dy / 2;

                while(y1 >= y2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){x1 += 1; e -= dy;}   

                    y1 -= 1;

                    e += dx;

                }

            }

        }   

    } else {    //dx<0

        dx = -dx;     //dx=abs(dx)

        if(dy >= 0) {    // dy>=0

            if(dx >= dy) {    // 4/8 octant

                e = dy - dx / 2;

                while(x1 >= x2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){ y1 += 1; e -= dx; }   

                    x1 -= 1;

                    e += dy;

                }

            } else {      // 3/8 octant

                e = dx - dy / 2;

                while(y1 <= y2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){x1 -= 1; e -= dy;}   

                    y1 += 1;

                    e += dx;

                }

            }

        } else {              // dy<0

            dy = -dy;       // dy=abs(dy)

            if(dx >= dy) {    // 5/8 octant

                e = dy - dx / 2;

                while(x1 >= x2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){y1 -= 1;e -= dx;}   

                    x1 -= 1;

                    e += dy;

                }

            } else {       // 6/8 octant

                e = dx - dy / 2;

                while(y1 >= y2) {

                    PutPixel(x1, y1, color);

                    if(e > 0){x1 -= 1;e -= dy;}   

                    y1 -= 1;

                    e += dx;

                }

            }

        }   

    }

}

void Mire(void)

{

    UINT32 x,y;

    UINT32 color;

    UINT8 red,green,blue,alpha;

    for (y = 0; y < ysize; y++) {

        for (x = 0; x < xsize; x++){

            color = ((x-xsize/2)*(x-xsize/2) + (y-ysize/2)*(y-ysize/2))/64;

            red   = (color/8) % 256;

            green = (color/4) % 256;

            blue  = (color/2) % 256;

            alpha = (color*2) % 256;

            color |= ((UINT32)alpha << 24);

            color |= ((UINT32)red   << 16);

            color |= ((UINT32)green << 8 );

            color |= ((UINT32)blue       );

            PutPixel(x,y,color);

        }
    }

}

The following algorithmetics is another format of Bresenham algorithmetic:

void LCD_DrawLine(u16 x1, u16 y1, u16 x2, u16 y2)

{

    u16 t; 

    int xerr=0, yerr=0, delta_x, delta_y, distance; 

    int incx,incy,uRow,uCol; 

    delta_x=x2-x1; //计算坐标增量 

    delta_y=y2-y1; 

    uRow=x1; 

    uCol=y1; 

    if(delta_x>0) incx=1; //设置单步方向 

    else if(delta_x==0) incx=0;//垂直线 

    else {incx=-1;delta_x=-delta_x;} 

    if(delta_y>0)incy=1; 

    else if(delta_y==0)incy=0;//水平线 

    else{incy=-1;delta_y=-delta_y;} 

    if( delta_x>delta_y)distance=delta_x; //选取基本增量坐标轴 

    else distance=delta_y; 

    for(t=0;t<=distance+1;t++ )//画线输出 

    {  

        LCD_DrawPoint(uRow,uCol);//画点 

        xerr+=delta_x ; 

        yerr+=delta_y ; 

        if(xerr>distance) 

        { 

            xerr-=distance; 

            uRow+=incx; 

        } 

        if(yerr>distance) 

        { 

            yerr-=distance; 

            uCol+=incy; 

        } 

    }  

}    

The following code is a type of algorithmetic of draw circle:

void Draw_Circle(u16 x0,u16 y0,u8 r)

{

    int a,b;

    int di;

    
    a=0; b=r;  

    di=3-(r<<1);             //判断下个点位置的标志

    while(a<=b)

    {

        LCD_DrawPoint(x0+a,y0-b);          //5

        LCD_DrawPoint(x0+b,y0-a);          //0           

        LCD_DrawPoint(x0+b,y0+a);         //4               

        LCD_DrawPoint(x0+a,y0+b);         //6 

        LCD_DrawPoint(x0-a,y0+b);          //1       

        LCD_DrawPoint(x0-b,y0+a);             

        LCD_DrawPoint(x0-a,y0-b);           //2             

        LCD_DrawPoint(x0-b,y0-a);           //7             

        
        a++;

        //使用Bresenham算法画圆     

        if(di<0)di +=4*a+6;  

        else

        {

            di+=10+4*(a-b);   

            b--;

        }    

    }

}