Брезенхем и У на страже диагоналей



    На что вы сейчас смотрите? Если вы не из параллельной вселенной, где все сидят за векторными мониторами, то перед вами растровое изображение. Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией. Для этой цели существует целая куча всевозможных алгоритмов растеризации, но я бы хотел рассказать об алгоритме Брезенхема и алгоритме У, которые находят приближение векторного отрезка в растровых координатах.

    С проблемой растеризации мне довелось столкнуться во время работы над процедурным генератором планов зданий. Мне нужно было представить стены помещения в виде ячеек двумерного массива. Похожие задачи могут встретиться в физических расчётах, алгоритмах поиска пути или расчёте освещения, если используется разбиение пространства. Кто бы мог подумать, что знакомство с алгоритмами растеризации однажды может пригодиться?

    Принцип работы алгоритма Брезенхема очень простой. Берётся отрезок и его начальная координата x. К иксу в цикле прибавляем по единичке в сторону конца отрезка. На каждом шаге вычисляется ошибка — расстояние между реальной координатой y в этом месте и ближайшей ячейкой сетки. Если ошибка не превышает половину высоты ячейки, то она заполняется. Вот и весь алгоритм.

    Это была суть алгоритма, на деле всё выглядит следующим образом. Сначала вычисляется угловой коэффициент (y1 — у0)/(x1 — x0). Значение ошибки в начальной точке отрезка (0,0) принимается равным нулю и первая ячейка заполняется. На следующем шаге к ошибке прибавляется угловой коэффициент и анализируется её значение, если ошибка меньше 0.5, то заполняется ячейка (x0+1, у0), если больше, то заполняется ячейка (x0+1, у0+1) и из значения ошибки вычитается единица. На картинке ниже жёлтым цветом показана линия до растеризации, зелёным и красным — расстояние до ближайших ячеек. Угловой коэффициент равняется одной шестой, на первом шаге ошибка становится равной угловому коэффициенту, что меньше 0.5, а значит ордината остаётся прежней. К середине линии ошибка пересекает рубеж, из неё вычитается единица, а новый пиксель поднимается выше. И так до конца отрезка.



    Ещё один нюанс. Если проекция отрезка на ось x меньше проекции на ось y или начало и конец отрезка переставлены местами, то алгоритм не будет работать. Чтобы этого не случилось, нужно проверять направление вектора и его наклон, а потом по необходимости менять местами координаты отрезка, поворачивать оси, и, в конечном итоге, сводить всё к какому-то одному или хотя бы двум случаям. Главное не забывать во время рисования возвращать оси на место.

    Для оптимизации расчётов, применяют трюк с умножением всех дробных переменных на dx = (x1 — x0). Тогда на каждом шаге ошибка будет изменяться на dy = (y1 — y0) вместо углового коэффициента и на dx вместо единицы. Также можно немного поменять логику, «передвинуть» ошибку так, чтобы граница была в нуле, и можно было проверять знак ошибки, это может быть быстрее.

    Примерно так может выглядеть код для рисования растровой линии по алгоритму Брезенхема. Псевдокод из Википедии переделанный под C#.
    void BresenhamLine(int x0, int y0, int x1, int y1)
    {
        var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Проверяем рост отрезка по оси икс и по оси игрек
        // Отражаем линию по диагонали, если угол наклона слишком большой
        if (steep)
        {
            Swap(ref x0, ref y0); // Перетасовка координат вынесена в отдельную функцию для красоты
            Swap(ref x1, ref y1);
        }
        // Если линия растёт не слева направо, то меняем начало и конец отрезка местами
        if (x0 > x1)
        {
            Swap(ref x0, ref x1);
            Swap(ref y0, ref y1);
        }
        int dx = x1 - x0;
        int dy = Math.Abs(y1 - y0);
        int error = dx / 2; // Здесь используется оптимизация с умножением на dx, чтобы избавиться от лишних дробей
        int ystep = (y0 < y1) ? 1 : -1; // Выбираем направление роста координаты y
        int y = y0;
        for (int x = x0; x <= x1; x++)
        {
            DrawPoint(steep ? y : x, steep ? x : y); // Не забываем вернуть координаты на место
            error -= dy;
            if (error < 0)
            {
                y += ystep;
                error += dx;
            }
        }
    }
    


    У алгоритма Брезенхэма есть модификация для рисования окружностей. Там всё работает по схожему принципу, в чём-то даже проще. Расчёт идёт для одного октанта, а все остальные куски окружности дорисовываются по симметрии.

    Пример кода рисования окружности на C#.
    void BresenhamCircle(int x0, int y0, int radius)
    {
        int x = radius;
        int y = 0;
        int radiusError = 1 - x;
        while (x >= y)
        {
            DrawPoint(x + x0, y + y0);
            DrawPoint(y + x0, x + y0);
            DrawPoint(-x + x0, y + y0);
            DrawPoint(-y + x0, x + y0);
            DrawPoint(-x + x0, -y + y0);
            DrawPoint(-y + x0, -x + y0);
            DrawPoint(x + x0, -y + y0);
            DrawPoint(y + x0, -x + y0);
            y++;
            if (radiusError < 0)
            {
                radiusError += 2 * y + 1;
            }
            else
            {
                x--;
                radiusError += 2 * (y - x + 1);
            }
        }
    }
    

    Теперь про алгоритм У Сяолиня для рисования сглаженных линий. Он отличается тем, что на каждом шаге ведётся расчёт для двух ближайших к прямой пикселей, и они закрашиваются с разной интенсивностью, в зависимости от удаленности. Точное пересечение середины пикселя даёт 100% интенсивности, если пиксель находится на расстоянии в 0.9 пикселя, то интенсивность будет 10%. Иными словами, сто процентов интенсивности делится между пикселями, которые ограничивают векторную линию с двух сторон.



    На картинке выше красным и зелёным цветом показаны расстояния до двух соседних пикселей.

    Для расчёта ошибки можно использовать переменную с плавающей запятой и брать значение ошибки из дробной части.

    Примерный код сглаженной линии У Сяолиня на C#.
    private void WuLine(int x0, int y0, int x1, int y1)
    {
        var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
        if (steep)
        {
            Swap(ref x0, ref y0);
            Swap(ref x1, ref y1);
        }
        if (x0 > x1)
        {
            Swap(ref x0, ref x1);
            Swap(ref y0, ref y1);
        }
    
        DrawPoint(steep, x0, y0, 1); // Эта функция автоматом меняет координаты местами в зависимости от переменной steep
        DrawPoint(steep, x1, y1, 1); // Последний аргумент — интенсивность в долях единицы
        float dx = x1 - x0;
        float dy = y1 - y0;
        float gradient = dy / dx;
        float y = y0 + gradient;
        for (var x = x0 + 1; x <= x1 - 1; x++)
        {
            DrawPoint(steep, x, (int)y, 1 - (y - (int)y));
            DrawPoint(steep, x, (int)y + 1, y - (int)y);
            y += gradient;
        }
    }
    


    Если вам вдруг в будущем придётся работать с сетками, задумайтесь ненадолго, возможно вы изобретаете велосипед и на самом деле вы работаете с пикселями, хотя и не знаете этого. Модификации этих алгоритмов можно использовать в играх для поиска ячеек перед юнитом на карте, расчёта области поражения выстрела или красивой расстановки объектов. Или можно просто рисовать линии, как в программе по ссылкам ниже.

    Unity Web Player | Windows | Linux | Mac | Исходники на GitHub
    Левая кнопка мыши — Брезенхем, правая кнопка мыши — У, пробел — очистить, Esc — выход.
    Для пользователей Linux: Сделайте файл BresenhamWu исполняемым с помощью «chmod +x BresenhamWu» и запускайте.

    На Rosetta Code есть код на разных языках для алгоритма Брезенхема и алгоритма У. Ссылка на статью У Сяолиня
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 43

      +18
      Странно. Последнее изображение противоречит тексту. Написано, что чем ближе линия к середине пикселя, но при этом 2 пикселя ровно посередине (координаты 2:1 и 3:1) явно светлее своих «пар» (2:0 и 3:2 соответственно), хотя их центры и находятся гораздо ближе к линии
        0
        Простите за занудство. Но мне потребовалось 4 раза перечитать предложение, чтобы понять о чем вы. Так правильнее:

        Написано, что чем ближе линия к середине пикселя, тем темнее, но при этом 2 пикселя ровно посередине (координаты 2:1 и 3:1) явно светлее своих «пар» (2:0 и 3:2 соответственно), хотя их центры и находятся гораздо ближе к линии
          0
          да-да, извиняюсь, заметил уже тогда, когда редактировать поздно было…
          –1
          Опечатка в тексте, сейчас исправлю.
            0
            Это не опечатка, нужно переделывать картинку.
              0
              А, разобрался в чём дело. Я в графическом редакторе вырезал не тот кусок линии.
                +8
                Переделал иллюстрации. Морока с этим фотошопом пиксели увеличивать, всё норовит сгладить.
                  –1
                  Я обычно это принтскрином делаю, не всегда подходит, но в целом быстро и просто.
                    0
                    Увеличивайте с интерполяцией по соседним пикселям (Nearest neighbor).
              0
              Линия пересекает боковые центры этих пикселей (нижний и верхний), а не центр пикселя (геометрический).
                0
                раньше там было другое, неправильное, изображение
              +3
              В прекрасном университете ИТМО лабораторная по компьютерной графике писалась на ASM, а задание было нарисовать свою фамилию начертанием «от руки». Все, кто хотят вызубрить эти алгоритмы — Welcome to IFMO!:)

              Не для слабонервных
                +2
                По-моему, тут нет сглаживания.
                  0
                  Так монохромная картинка же. Раз на ASM-е делалось, явно проще в двух цветах работать, чем загружать свою палитру, например.
                +7
                Про самую первую картинку: мне на 100% нравится вариант слева — глаза не устают.
                  0
                  Ничего удивительного, алгоритм У Сяолиня для рисования гладких линий за двадцать с лишним лет успел устареть. На замену ему напридумывали множество других алгоритмов, в том же фотошопе линии рисуются иначе, зато он по-прежнему остаётся очень простым в реализации.
                    0
                    Сейчас происходит дополнительно утяжеление линии, для того, чтобы она не выглядела резаной. Утяжеление расширяет количество смежных пикселей на некоторое значение, которое сглаживает линию.
                  +13
                  Жуть, Брезенхем с плавающей точкой, извращение. Это целочисленный алгоритм, на кой черт там float. В той же вики есть пример на C++, целочисленный.
                    –5
                    Разумеется, но приведённый выше читается легче. Во время подготовки статьи я нашёл море разных оптимизаций, но не могу же я их все привести?
                      +7
                      Один из бонусов алгоритма Брензенхема состоит в том, что он целочисленный. Я понимаю, что сейчас это уже не актуально, но печально глядеть на то, как люди коверкают сущности.
                        0
                        Это все еще актуально. см мою недавнюю историю.
                          +1
                          Всегда можно найти задачу где применение целочисленной арифметики оправданно. Просто раньше их и искать не надо было.
                    +1
                    В статье не указанно, в чём преимущество алгороитма Брезенхема. А именно: в цикле рисования не используется умножение и деление, что было очень актуально, когда процессоры были большие и медленые.
                      +7
                      Оно и сейчас актуально.
                      +1
                      Спасибо за алгоритм сглаженной линии. Брезенхем для сеток давно использовал уже. Не хватает примеров в 100% масштабе. По увеличенным понятно, как оно должно выглядеть, но, иногда, в 100% масштабе выглядит все не так, как представляется.
                        0
                        Посмотрите на новые картинки, надеюсь, стало понятнее.
                        +1
                        (y1 — у0)/(x1 — x0)

                        А если x1=x0?
                          0
                          Тогда деление на ноль. Кроме вертикальной линии, есть ещё три других особых ситуаций: горизонтальная линия, диагональ под 45 градусов и точка. Их можно обрабатывать в начале и рисовать другими способами.
                            0
                            Тогда memset или цикл с присваиванием, что к тому же быстрее.
                              0
                              Ошибся, memset — для горизонтальной. Для вертикальной — только цикл.
                                0
                                А для диагональной — тот же цикл, но со сдвигом на 1 в обоих измерениях, а не в одном.
                                А потом можно прогнать тот же цикл около линии с каждой стороны и на 2 пикселя короче с прозрачностью, скажем, 1-sqrt(2), для сглаживания.
                                  0
                                  (1-sqrt(2))/2 даже, наверно, потому что с двух сторон.
                                    +1
                                    То есть (1-sqrt(2)/2)/2, забыл поделить корень на 2.
                            0
                            (y1 — у0)/(x1 — x0)

                            А если x1=x0?

                            Извините
                              +4
                              (y1 — у0)/(x1 — x0)

                              А если x1=x0?
                                +2
                                Нужно наверное еще гамму учитывать — код цвета пикселя вроде как нелинейно связан с его яркостью. Линии будут менять визуально толщину в зависимости от наклона.

                                Кроме того, по этому алгоритму концы отрезка получаются неправильные — скошенные по вертикали. Через это непонятно что будет на стыках двух отрезков.

                                Короче я бы все-таки взял какую-нибудь готовую библиотеку для рисования вектора, нетривиальная это задача.
                                  +2
                                  Если вы не из параллельной вселенной, где все сидят за векторными мониторами

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

                                  Бррр. Расточительный расход экранной площади.
                                    –1
                                    в виде совокупности закрашенных квадратных фигур со сторонами, параллельными краям монитора

                                    Это и есть растр.
                                      +1
                                      вот-вот. И больше ничего из него не извлечешь.

                                      Хоть векторизуй, в самом деле.
                                  • UFO just landed and posted this here
                                    • UFO just landed and posted this here
                                        +4
                                        Да вы, батенька, весельчак!
                                        +1
                                        Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией.

                                        Те у кого ретина, разглядеть не смогут как ни придвигайся. ))

                                        Only users with full accounts can post comments. Log in, please.