Как вы рисуете прямую линию между двумя точками в растровом изображении?

17

Я играю с картами высот (растровыми изображениями), пытаюсь создать свои собственные в моей игре, и для этого мне нужно реализовать некоторые базовые методы рисования. Я быстро понял, что рисование прямых линий не так просто, как я думал.

Это просто, если ваши точки имеют общие координаты X или Y, или если они выровнены, так что вы можете нарисовать идеально диагональную линию. Но во всех остальных случаях это сложнее.

Какой алгоритм вы используете, чтобы определить, какие пиксели нужно раскрасить, чтобы он стал «прямой» линией?

c++ rasterization Фредрик Бостон Вестман
источник

Ответы:

25

Я думаю, что вам нужен линейный алгоритм Брезенхэма .

Из того, что я помню, он используется для определения того, какая точка должна быть окрашена, а не насколько каждая точка должна быть окрашена.

Vaillancourt
источник
21

Алгоритм линии Брезенхэма можно использовать для определения точек в растровой сетке для построения соответствующей визуальной аппроксимации отрезка линии.

Алгоритм охватывает растеризацию линии, определяемой началом координат и конечными точками в координатном пространстве, где начало координат находится слева вверху. Предполагается, что целочисленные координаты сопоставляются с центрами пикселей. Примечательно, что базовая форма алгоритма охватывает только один октант круга: тот, в котором линия имеет увеличивающиеся координаты X и Y, но отрицательный наклон с абсолютным значением меньше 1. Все остальные октанты могут быть получены как простые преобразования этого основной октант.

В psuedocode эта базовая форма выглядит так:

void DrawLine(Point origin, Point endpoint, Bitmap surface) {
    deltaX = endpoint.X - origin.X
    deltaY = endpoint.Y - origin.Y
    error = 0

    // Note the below fails for completely vertical lines.
    deltaError = absoluteValue(deltaY / deltaX)

    Y = origin.Y
    for (X from origin.X to endpoint.X) {
        surface.PlotPixel(X, Y)
        error = error + deltaError 
        if (error >= 0.5) {
            ++Y;
            error -= 1.0
        }
    }
}

На веб-сайте Rosetta Code есть коллекция конкретных реализаций на разных языках .

Вы также можете быть заинтересованы в строковом алгоритме Ву , который допускает сглаживание.

Кен Уильямс
источник
3
Просто хочу предупредить прохожих, чтобы они не вынимали включенный псевдокод из контекста, поскольку он не будет работать из коробки. Это работает только для определенного октанта (прочитайте остальную часть ответа). Если вы ищете код для копирования / вставки, попробуйте ссылку на веб-сайт Rosetta Code.
congusbongus
1
Для тех, кто хочет проверить версию строкового алгоритма У, я хотел бы предупредить вас, что он неполон. В _dla_changebrightness при изменении яркости вы должны изменить его из: to->red = br * (float)from->red;к этому следующее: to->red = (br * (float)from->red) + ((1-br) * (float) to->red);. Сделайте то же самое для зеленого и синего соответственно
Фредрик Бостон Вестман
2

Вот чрезвычайно простой способ рисования линий. Функция может быть легко изменена для использования в проектах.

void draw_line(float x0, float y0, const float& x1, const float& y1)
{
    float x{x1 - x0}, y{y1 - y0};
    const float max{std::max(std::fabs(x), std::fabs(y))};
    x /= max; y /= max;
    for (float n{0}; n < max; ++n)
    {
        // draw pixel at ( x0, y0 )
        x0 += x; y0 += y;
    }
}
cppxor2arr
источник