Алгоритм рисования линий

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

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

Алгоритмы рисования одноцветных линий

Алгоритмы рисования одноцветных линий включают рисование линий одного цвета переднего плана на фоне. Они хорошо подходят для использования с монохромными дисплеями.

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

Простые методы

Самый простой метод рисования линии предполагает непосредственное вычисление положений пикселей по уравнению линии. Учитывая отправную точку $(x_{1},y_{1})$ и конечная точка $(x_{2},y_{2})$ , точки на прямой удовлетворяют уравнению $y=m(x-x_{1})+y_{1}$ , с $\textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}$ является наклоном линии. Затем можно провести линию, оценив это уравнение через простой цикл, как показано в следующем псевдокоде:

dx = x2 − x1
dy = y2 − y1
m = dy/dx
for x from x1 to x2 do
    y = m × (x − x1) + y1
    plot(x, y)

Здесь точки уже упорядочены так, что $x_{2}>x_{1}$ .

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

$y_{i+1}-y_{i}\!$	$=(m(x_{i+1}-x_{1})+y_{1})-(m(x_{i}-x_{1})+y_{1})\!$
	$=m(x_{i+1}-x_{i})\!$
	$=m\!$ .

Поэтому достаточно просто начать с точки $(x_{1},y_{1})$ а затем увеличить $y$ к $m$ один раз на каждой итерации цикла. Этот алгоритм известен как цифровой дифференциальный анализатор .

Потому что округление $y$ до ближайшего целого числа эквивалентно округлению $y+0.5$ вниз, округления можно избежать, используя дополнительную управляющую переменную, инициализируемую значением 0,5. $m$ добавляется к этой переменной на каждой итерации. Затем, если эта переменная превышает 1,0, $y$ увеличивается на 1, а управляющая переменная уменьшается на 1. Это позволяет алгоритму избежать округления и использовать только целочисленные операции. Однако для коротких линий этот более быстрый цикл не компенсирует дорогостоящее деление. $\textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}$ , что еще необходимо вначале.

Этот алгоритм отлично работает, когда $dx\geq dy$ (т. е. наклон меньше или равен 1), но если $dx<dy$ (т.е. наклон больше 1), линия становится весьма разреженной с множеством пропусков, и в предельном случае $dx=0$ , произойдет исключение деления на ноль.

Проблемы

В определенных ситуациях алгоритмы рисования одноцветных линий сталкиваются с проблемами:

Непостоянная яркость

При рисовании линий одинаковой длины с разным наклоном рисуется разное количество пикселей. Это приводит к тому, что более крутые линии состоят из меньшего количества пикселей, чем более плоские линии той же длины, в результате чего более крутая линия выглядит ярче, чем плоская линия. Эта проблема неизбежна на монохромных устройствах.

Обрезка

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

Сглаживание

Самая большая проблема алгоритмов рисования одноцветных линий заключается в том, что они приводят к появлению грубых и неровных линий . На устройствах, способных отображать несколько уровней яркости, этой проблемы можно избежать с помощью сглаживания . Для этого линии обычно просматриваются в двухмерном виде, обычно в виде прямоугольника желаемой толщины. Чтобы нарисовать эти линии, необходимо учитывать точки, лежащие рядом с этим прямоугольником.

Алгоритм Гупты и Спроролла

Алгоритм Гупта-Спроулла основан на линейном алгоритме Брезенхема , но добавляет сглаживание .

Оптимизированный вариант алгоритма Гупта-Спроулла можно записать в псевдокоде следующим образом:

DrawLine(x1, x2, y1, y2) {
    x = x1;
    y = y1;
    dx = x2 − x1;
    dy = y2 − y1;
    d = 2 * dy − dx; // discriminator
    
    // Euclidean distance of point (x,y) from line (signed)
    D = 0; 
    
    // Euclidean distance between points (x1, y1) and (x2, y2)
    length = sqrt(dx * dx + dy * dy); 
    
    sin = dx / length;     
    cos = dy / length;
    while (x <= x2) {
        IntensifyPixels(x, y − 1, D + cos);
        IntensifyPixels(x, y, D);
        IntensifyPixels(x, y + 1, D − cos);
        x = x + 1
        if (d <= 0) {
            D = D + sin;
            d = d + 2 * dy;
        } else {
            D = D + sin − cos;
            d = d + 2 * (dy − dx);
            y = y + 1;
        }
    }
}

Функция IntensifyPixels(x,y,r) выполняет преобразование радиальной линии и устанавливает интенсивность пикселя (x,y) со значением кубического полинома, который зависит от расстояния r пикселя до линии.

Оптимизации

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

Приблизительные методы

Бойер и Бурден представили алгоритм аппроксимации, который окрашивает пиксели, лежащие непосредственно под идеальной линией. ^[1] Линия, отображаемая таким образом, обладает некоторыми особыми свойствами, которыми можно воспользоваться. Например, в подобных случаях участки линии являются периодическими. В результате получается алгоритм, который работает значительно быстрее, чем точные варианты, особенно для более длинных строк. Ухудшение качества заметно только на линиях с очень малой крутизной.

Распараллеливание

Простой способ распараллелить растеризацию одноцветных линий — позволить нескольким алгоритмам рисования линий рисовать смещенные пиксели на определенном расстоянии друг от друга. ^[2] Другой метод предполагает разделение строки на несколько частей примерно одинаковой длины, которые затем назначаются разным процессорам для растеризации. Основная проблема – найти правильные начальные и конечные точки этих участков.

Также существуют алгоритмы для процессорных архитектур с массовым параллелизмом и тысячами процессоров. В них каждый пиксель из сетки пикселей назначается одному процессору, который затем решает, должен ли данный пиксель быть окрашен или нет. ^[3]

Для ускорения доступа к памяти во время растеризации были разработаны специальные иерархии памяти. Например, они могут разделить память на несколько ячеек, каждая из которых затем независимо отображает часть строки. ^[4] Растеризация с использованием сглаживания также может поддерживаться специальным оборудованием. ^[5]

Связанные проблемы

Линии могут быть нарисованы не только 8-связными, но и 4-связными, то есть разрешены только горизонтальные и вертикальные шаги, а диагональные шаги запрещены. Учитывая растр из квадратных пикселей, это приводит к тому, что каждый квадрат содержит часть окрашиваемой линии. Обобщение методов рисования 4-связных линий на три измерения используется при работе с сетками вокселов , например, при оптимизированной трассировке лучей , где можно определить вокселы, которые пересекает данный луч.

Алгоритмы рисования линий распределяют диагональные шаги примерно равномерно. Таким образом, алгоритмы рисования линий также могут использоваться для равномерного распределения точек с целочисленными координатами в заданном интервале. ^[6] Возможные применения этого метода включают линейную интерполяцию или понижающую дискретизацию при обработке сигналов . Существуют также параллели с алгоритмом Евклида , а также последовательностями Фарея и рядом связанных с ними математических конструкций. ^[7]

См. также

Ссылки

^ Винсент Бойер, Жан-Жак Бурден: Быстрые линии: метод промежутка. Форум компьютерной графики 18, 3 (1999): 377–384 ( Архивировано 23 апреля 2024 г. на ai.univ-paris8.fr (Ошибка: неизвестный URL-адрес архива) )
^ Роберт Ф. Спроулл: Использование программных преобразований для получения алгоритмов рисования линий. Транзакции ACM на графике 1, 4 (октябрь 1982 г.): 259–273, ISSN 0730-0301
^ Алекс Т. Панг: Алгоритмы рисования линий для параллельных машин. Компьютерная графика и приложения IEEE 10, 5 (сентябрь 1990 г.): 54–59.
^ См., например, Пере Марес Марти, Антонио Б. Мартинес Веласко: Архитектура памяти для рисования параллельных линий на основе неинкрементного алгоритма. В: Euromicro 2000 Proceedings: Vol. 1, 266–273. Издательство IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8
^ См., например, Роберт Макнамара ua: Предварительно отфильтрованные сглаженные линии с использованием функций расстояния в полуплоскости. В материалах HWWS 2000: 77–85. ACM Press, Нью-Йорк, 2000, ISBN 1-58113-257-3.
^ Ченгфу Яо, Джон Г. Рокне: Интегральный подход к линейной интерполяции при разработке алгоритмов инкрементных строк. Журнал вычислительной и прикладной математики 102, 1 (февраль 1999 г.): 3–19, ISSN 0377-0427
^ Митчелл А. Харрис, Эдвард М. Рейнгольд: Рисование линий, високосные годы и Евклид. Обзоры ACM Computing Surveys 36, 1 (март 2004 г.): 68–80, ISSN 0360-0300 ( Архивировано 16 декабря 2006 г. на emr.cs.iit.edu (Ошибка: неизвестный URL-адрес архива) )

Основы компьютерной графики, 2-е издание, AK Peters, Питер Ширли

[1] Винсент Бойер, Жан-Жак Бурден: Быстрые линии: метод промежутка. Форум компьютерной графики 18, 3 (1999): 377–384 ( Архивировано 23 апреля 2024 г. на ai.univ-paris8.fr (Ошибка: неизвестный URL-адрес архива) )

[2] Роберт Ф. Спроулл: Использование программных преобразований для получения алгоритмов рисования линий. Транзакции ACM на графике 1, 4 (октябрь 1982 г.): 259–273, ISSN 0730-0301

[3] Алекс Т. Панг: Алгоритмы рисования линий для параллельных машин. Компьютерная графика и приложения IEEE 10, 5 (сентябрь 1990 г.): 54–59.

[4] См., например, Пере Марес Марти, Антонио Б. Мартинес Веласко: Архитектура памяти для рисования параллельных линий на основе неинкрементного алгоритма. В: Euromicro 2000 Proceedings: Vol. 1, 266–273. Издательство IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8

[5] См., например, Роберт Макнамара ua: Предварительно отфильтрованные сглаженные линии с использованием функций расстояния в полуплоскости. В материалах HWWS 2000: 77–85. ACM Press, Нью-Йорк, 2000, ISBN 1-58113-257-3.

[6] Ченгфу Яо, Джон Г. Рокне: Интегральный подход к линейной интерполяции при разработке алгоритмов инкрементных строк. Журнал вычислительной и прикладной математики 102, 1 (февраль 1999 г.): 3–19, ISSN 0377-0427

[7] Митчелл А. Харрис, Эдвард М. Рейнгольд: Рисование линий, високосные годы и Евклид. Обзоры ACM Computing Surveys 36, 1 (март 2004 г.): 68–80, ISSN 0360-0300 ( Архивировано 16 декабря 2006 г. на emr.cs.iit.edu (Ошибка: неизвестный URL-адрес архива) )

[1]

[2]

[3]

[4]

[5]

[6]

[7]