В компьютерной графике рисование линий является фундаментальной операцией. Независимо от того, работаете ли вы над простой 2D-игрой или над сложным механизмом 3D-рендеринга, эффективные алгоритмы рисования линий необходимы для создания плавной и визуально привлекательной графики. В этой статье мы рассмотрим несколько методов, обычно используемых для рисования линий, используя разговорный язык и примеры кода для иллюстрации каждого подхода.

Метод 1: Алгоритм цифрового дифференциального анализатора (DDA)
Давайте начнем с алгоритма DDA, который представляет собой простой и интуитивно понятный метод рисования линий. Идея DDA заключается в определении положения пикселей вдоль линии путем пошагового увеличения координат x и y. Вот пример реализации на C++:

void lineDDA(int x0, int y0, int xEnd, int yEnd) {
    int dx = xEnd - x0;
    int dy = yEnd - y0;
    int steps = std::max(abs(dx), abs(dy));
    float xIncrement = dx / (float)steps;
    float yIncrement = dy / (float)steps;
    float x = x0;
    float y = y0;
    for (int i = 0; i <= steps; i++) {
        plot(round(x), round(y));
        x += xIncrement;
        y += yIncrement;
    }
}

Метод 2: алгоритм линий Брезенхема
Другим популярным алгоритмом рисования линий является алгоритм линий Брезенхэма, известный своей эффективностью. Он вычисляет положения пикселей вдоль линии, используя целочисленную арифметику, и устраняет необходимость в операциях с плавающей запятой. Вот упрощенная реализация:

void lineBresenham(int x0, int y0, int xEnd, int yEnd) {
    int dx = abs(xEnd - x0);
    int dy = abs(yEnd - y0);
    int sx = (x0 < xEnd) ? 1 : -1;
    int sy = (y0 < yEnd) ? 1 : -1;
    int err = dx - dy;
    while (x0 != xEnd || y0 != yEnd) {
        plot(x0, y0);
        int err2 = 2 * err;

        if (err2 > -dy) {
            err -= dy;
            x0 += sx;
        }

        if (err2 < dx) {
            err += dx;
            y0 += sy;
        }
    }
}

Метод 3: линейный алгоритм Сяолиня Ву
Линейный алгоритм Сяолиня Ву — это расширение алгоритма Брезенхэма, которое использует субпиксельную точность для рисования сглаженных линий, что приводит к более плавной и визуально привлекательной графике. Вот упрощенная реализация:

void lineXiaolinWu(int x0, int y0, int xEnd, int yEnd) {
    int dx = abs(xEnd - x0);
    int dy = abs(yEnd - y0);
    bool steep = dy > dx;
    if (steep) {
        std::swap(x0, y0);
        std::swap(dx, dy);
    }
    if (x0 > xEnd) {
        std::swap(x0, xEnd);
        std::swap(y0, yEnd);
    }
    float gradient = (float)dy / dx;
    float y = y0 + gradient;
    for (int x = x0 + 1; x <= xEnd - 1; x++) {
        if (steep)
            plot(round(y), x);
        else
            plot(x, round(y));

        plot(x, (int)y);
        plot(x, (int)y + 1);
        y += gradient;
    }
}

В этой статье мы исследовали три популярных метода рисования линий в компьютерной графике: алгоритм DDA, линейный алгоритм Брезенхема и линейный алгоритм Сяолиня Ву. Каждый метод имеет свои сильные стороны и недостатки с точки зрения простоты, эффективности и визуального качества. Понимая эти методы, разработчики могут выбрать наиболее подходящий алгоритм для своих конкретных потребностей в рендеринге графики.