Render Pipeline - Line

常用的直线生成算法有DDA和Bresenham

DDA

DDA的主要核心思想是利用微分增量来计算下一个点的位置(求出总步长及斜率后,根据起点及终点就能算出步长内的各点的位置)

float dx = endX - startX;
float dy = endY - startY;

// 总步长
float steps = std::max<float>(std::abs(dx), std::abs(dy));

// 每次步长的微分增量(斜率)
float increx = dx / steps;
float increy = dy / steps;

float xi = startX;
float yi = startY;

for (int i = 0; i < steps; i++)
{
    drawPixel(std::round(xi), std::round(yi), color);
    xi += increx;
    yi += increy;
}

Bresenham

Bresenham的主要核心思想也是微分增量,是DDA的一种改进,避免了浮点运算。

int dx = endX - startX;
int dy = endY - startY;

int ux = (dx > 0) ? 1 : -1;
int uy = (dy > 0) ? 1 : -1;

int xi = startX;
int yi = startY;

int eps = 0.0f;
dx = std::abs(dx);
dy = std::abs(dy);

if (dx > dy)
{
    for (; xi != std::round(endX); xi += ux)
    {
        drawPixel(xi, yi, color);
        eps += dy;
        if ((eps << 1) >= dx)
        {
            yi += uy;
            eps -= dx;
        }
    }
}
else
{
    for (; yi != std::round(endY); yi += uy)
    {
        RenderDevice::getSingletonPtr()->drawPixel(xi, yi, color);
        eps += dx;
        if ((eps << 1) >= dy)
        {
            xi += ux;
            eps -= dy;
        }
    }
}