Bresenham 算法

zero0000

最近在看圣2的代码，里面有个画直线的函数Line(), 用的是Bresenham算法，我把函数单独拿出来研究，网上也找了许多关于Bresenham算法的资料，不过不是太明白，主要是几句话。
下面是源程序导读中的函数：
// 在第一象限中
void Line(HDC hdc, int left, int top, int right, int bottom, DWORD color)
{
    int delta_x, delta_y;

    delta_x = right  - left;
    delta_y = bottom - top;

    for ( int i = 0, error = 0; i < delta_x; i++ )
    {
        SetPixel(hdc, left, top, color);
  /* ------------------------------------------------------
        error += delta_y;   
        if ( error > delta_x )
        {
        error -= delta_x;
        top++;
        }
   ------------------------------------------------------ */
   // 这几句不懂， 各位高手能不能给个解释或原理，小弟谢谢先~~~~~~~

        left++;
     }
} [em7]

superdai

就是在对Y轴的偏移进行步进,你稍微跟踪以下数值的变化应该能看的出来.

hanma

这是我的，精度高，不用分象限，就是有点复杂，算是抛砖引玉，谁有更好的算法？
//        根据线段记录处于线段上的单元。
void        ComputeLineBlocks(       
                        std::vector< world_block >&        blocks,        //        用于返回位于该线段上的所有块。
                        const        Vector&                        begin,        //        线段的开始坐标。
                        const        Vector&                        end                //        线段的结束坐标。
                        )
{
        //        要求块集是空的。
        assert(        !blocks.size()        );

        //        计算方向。
        Vector        dir                        =        end        -        begin;

        //        计算第一和第二递增方向。
        int        first_x                =        (dir.x>0)?1:-1;
        int        first_y                =        (dir.y>0)?1:-1;
        int        second_x        =        (dir.x>0)?1:-1;
        int        second_y        =        (dir.y>0)?1:-1;

        if(        abs(dir.x)        >        abs(dir.y)        )        //        哪个方向长，先增加那个方向。
        {
                first_y                =        0;
                second_x        =        0;
        }
        else
        {
                first_x                =        0;
                second_y        =        0;
        }

        //
        float        k        =        0;
        if(        dir.x        !=        0        )
                k        =        dir.y        /        dir.x;
        float        b        =        begin.y        -        k * begin.x;

        //        准备启动点和结束点。
        world_block                now_block(begin.x,begin.y);
        world_block                end_block(end.x,end.y);

#ifdef        DEBUG
        int        assert_block_count        =        begin.DistTo( end )        +        2;
#endif

        //        记录开始点。
        blocks.push_back( now_block );

        //
        while(        now_block.m_x        !=        end_block.m_x        ||        now_block.m_y        !=        end_block.m_y        )
        {
                //        如果当前块等于结束块，则跳出循环。
                if(        now_block        ==        end_block        )
                        break;

                //        首要方向递增。
                if(        now_block.m_x        !=        end_block.m_x        )        now_block.m_x        +=        first_x;
                if(        now_block.m_y        !=        end_block.m_y        )        now_block.m_y        +=        first_y;

                //        如果次要方向是X，则靠拢X。
                if(        second_x )       
                {
                        //        计算次要方向的标准值。
                        int        compare_x        =        (int)(        (        now_block.m_y        -        b        )        /        k        );

                        //        如果不等于标准数值，则向标准值靠拢。
                        if(        now_block.m_x        !=        compare_x        )
                                now_block.m_x        +=        (        compare_x        >        now_block.m_x        )?1:-1;

                }

                //        如果次要方向是Y，则靠拢Y。
                if( second_y )       
                {
                        //        求次要方向的标准值。
                        int        compare_y        =        (int)(        k        *        now_block.m_x        +        b        );

                        //        如果次要方向的当前值小于标准值，则递增。
                        if(        now_block.m_y        !=        compare_y        )
                                now_block.m_y        +=        (        compare_y        >        now_block.m_y        )?1:-1;
                }

                //        如果现位置横坐标等于目的横坐标，则递增到目的坐标。
                if(        now_block.m_x        ==        end_block.m_x        )
                {
                        while(        now_block.m_y        !=        end_block.m_y        )
                        {
                                now_block.m_y        +=        (        end_block.m_y        >        now_block.m_y        )?1:-1;
                                blocks.push_back( now_block );
                        }
                }
               
                //        如果现位置纵坐标等于目的纵坐标，则递增到目的坐标。
                if(        now_block.m_y        ==        end_block.m_y        )
                {
                        while(        now_block.m_x        !=        end_block.m_x        )
                        {
                                now_block.m_x        +=        (        end_block.m_x        >        now_block.m_x        )?1:-1;
                                blocks.push_back( now_block );
                        }
                }

                //        记录。
                blocks.push_back( now_block );

#ifdef        DEBUG
                //        检查总记录数。
                assert(        blocks.size()        <=        assert_block_count        );
#endif

        };

};

hanma

我这个有特殊用途，要求精度比较高，而且要记录以便重复取这些数值进行运算。

zero0000

明白了，其实就是用加法表示 dx / dy, 谢谢楼上各位了！