Skip to main content

Блог инженера

Блог о минимализме, инжинерии и программировании.



Черим линию из точек. Часть 1

  | #Форт#программирование#unfinished

Библиотека

Превращаем точки в линии

Когда научился ставить точки - самое время перейти к линиям. Линия состоит из точек, так ведь? Всё должно быть просто. Когда я приступал к этому, я даже не представлял себе, сколько сложности кроется за простой операцией рисования линии из отдельных точек.

Алгоритм Брезенхэма

Первое же гугление привело меня к описанию алгоритма Брезенхэма в Википедии. Я намеренно дал ссылку на английский раздел, там приведены более подходящие примеры программ. Они написаны на языке напоминающем Си, но это не Си. Думаю, это просто попытка дать код на этаком мета-языке программирования, чтобы его потом было просто перевести в любой другой язык программирования. Перевести наиболее понравившийся мне пример в Си и правда было несложно.

void plotBresenhamLine( UINT x0, UINT y0, UINT x1, UINT y1, BMP* bmp, int color) 
{
    int dx, sx, dy, sy, err, e2;
    dx =  abs(x1-x0);
    sx = x0<x1 ? 1 : -1;
    dy = -abs(y1-y0);
    sy = y0<y1 ? 1 : -1;
    err = dx+dy;  /* error value e_xy */

    while(x0 != x1 && y0 != y1)   /* loop */
    {
        e2 = 2*err;
        if (e2 >= dy)  /* e_xy+e_x > 0 */
        {
            err += dy;
            x0 += sx;
        }
        if (e2 <= dx)  /* e_xy+e_y < 0 */
        {
            err += dx;
            y0 += sy;
        }
        BMP_SetPixelIndex( bmp, x0, y0, color );
    }
}

Пример немного модифицирован. Раница во вкусе. К сожалению, у алгоритма Брезенхэма оказалась неприятная особенность. Он отлично справляется с наклонными прямыми. Но чем ближе прямая к вертикали или горизонтали - тем хуже алгоритм работает. Наконец, он вовсе не умеет рисовать вертикальные и горизонтальные линии. Это можно было бы отрабатывать как особые случаи и чертить горизонтальные и вертикальные прямые простейшим циклом, но что делать с линиями, которые только приближаются к горизонтальным или вертикальным? Вот как это выглядит. Не обращайте внимания на психоделический фон, я эксперементировал с палитрой.

Алгоритм Брезенхэма

Хорошо видно, что чем ближе линия к горизонтальной, тем большая её часть не прорисовывается. К счастью, есть несколько реализаций алгоритма, плюс модификация Мёрфи для алгорима Брезенхэма, алгоритм DDA-линии и ещё несколько разных алгоритмов. Я попробую разные на различных примерах, сравню их скорости и выясню, что же имеет смысл использовать. Хотя, скорость меня волнует очень мало, если честно. Идеально быстрые алгоритмы рисования линий - это те, которые выполняются графическим ускорителем.

Есть довольно полезные статьи про алгоритм Брезенхэма:

Ближайшие планы - написать программу интенсивно использующую линии, чтобы сравнить по времени исполнения разные реализации алгоритма. И сделать эти разные реализации, разумеется.

About Mikhail Kiselev

Photo of Mikhail Kiselev

Приветствую в моём блоге! 😄 Меня зовут Михаил. Я инженер и программист. Живу в Сибири, работаю на Сахалине, путешествую где придётся. Я предпочитаю пост в блог посту в твиттер. Описание полезной технологии или гаджета предпочитаю описанию заката или посиделок в кафе.