Растеризация линий

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

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

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

Две растрированные линии. Цветные пиксели показаны кружками. Вверху: монохромная растеризация; внизу: сглаживание Гупта-Спроулла, идеальная линия здесь рассматривается как поверхность.

Монохромный полутон

Одноцветная растеризация рисует линии с одним цветом переднего плана на фоне. Он подходит для устройств с монохромным дисплеем, например для лазерных принтеров .

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

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

Наивный метод скрининга с помощью округления

Самый простой способ растеризовать - напрямую реализовать уравнение, определяющее линию. Если ( х , у ) является точка начала и ( х _е , у _е ) конечная точка линии, точки на линии удовлетворяют уравнение прямой линии , то где наклон . ${\ Displaystyle у = м (х-х_ {а}) + у_ {а}}$${\ displaystyle \ textstyle m = {\ frac {\ Delta y} {\ Delta x}} = {\ frac {y_ {e} -y_ {a}} {x_ {e} -x_ {a}}}}$

Линия рисуется путем вычисления соответствующего значения в цикле для каждого значения от до в соответствии с этой формулой и округления его до ближайшего целого числа. Затем окрашивается пиксель ( x , y ). ${\ displaystyle x}$${\ displaystyle x_ {a}}$${\ displaystyle x_ {e}}$${\ displaystyle y}$

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

${\ Displaystyle у_ {я + 1} -у_ {я} \!}$	${\ displaystyle = (m (x_ {i + 1} -x_ {a}) + y_ {a}) - (m (x_ {i} -x_ {a}) + y_ {a}) \!}$
	${\ Displaystyle = м (х_ {я + 1} -х_ {я}) \!}$
	${\ Displaystyle = м \!}$.

Соответственно, достаточно , чтобы начать с ( х , у ) и увеличение на каждый раз , когда цикл выполняется через . Этот метод также известен как цифровой дифференциальный анализатор (DDA). ${\ displaystyle y}$${\ displaystyle m}$

Поскольку округление до ближайшего целого числа соответствует округлению , также может использоваться дополнительная управляющая переменная , которая инициализируется значением 0,5 и добавляется при каждом проходе цикла . Каждый раз, когда управляющая переменная достигает или превышает 1,0, она увеличивается на 1 и вычитает 1,0 из управляющей переменной. Это означает, что округление больше не требуется. Этот метод можно перефразировать, чтобы использовать только более быстрые целочисленные операции, и его можно элегантно реализовать на языке ассемблера . Однако вначале по- прежнему необходимо медленное деление ( ), которое нельзя компенсировать быстрым циклом в случае коротких строк. ${\ displaystyle y}$${\ displaystyle y + 0 {,} 5}$${\ displaystyle m}$${\ displaystyle y}$ ${\ displaystyle \ Delta y / \ Delta x}$

Обобщение в любом направлении

Растеризация любых линий с использованием свойств симметрии. Допустимая область исходной процедуры показана цветом; три изменения алгоритма также открывают другие области.

Только что описанные методы работают только с наклонами линий от 0 до 1, что соответствует углу от 0 ° до 45 ° к горизонтали. На других склонах линия не нарисована или проведена неправильно. Однако достаточно описать алгоритм только для уклонов от 0 до 1, поскольку другие линии могут отображаться правильно с помощью симметрии. Это делается посредством следующих трех изменений:

1. Различают два случая в зависимости от того (по сумме) или наоборот. В первом случае цикл выполняется, как и раньше, и вычисляется в теле цикла , в противном случае он выполняется и вычисляется с использованием.${\ displaystyle \ Delta x> \ Delta y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle x}$
2. В теле цикла, или не увеличивается на 1, но в зависимости от знака из или, значения +1 или -1 добавляется.${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle \ Delta y}$${\ displaystyle \ Delta x}$
3. Если или , цикл должен проходить в обратном направлении.${\ displaystyle \ Delta x <0}$${\ displaystyle \ Delta y <0}$

Применяя эти обобщения, можно создать следующую таблицу для лучшего обзора:

Где i для m <= 1 значений от 0 до и для m> 1 значений от 0 до . Линии, параллельные оси X или Y, также включены в эту таблицу, и их не нужно рассматривать отдельно. Указанное направление относится к графику справа, предполагая, что x увеличивается вправо, а y увеличивается вверх. x1 и y1 - координаты начальной точки линии, а x2 и y2 - координаты конечной точки. ${\ displaystyle \ Delta x}$${\ displaystyle \ Delta y}$

Кроме того, следующий псевдокод может быть создан только путем изменения знака, который охватывает все восемь описанных случаев:

  signX = 1;
  signY = 1;

  if x1 > x2
      signX = -1;

  if y1 > y2
      signY = -1;

  if m <= 1
      for i=0; i <= deltaX; i++
          drawPixel( ceil(x1 + i * signX), ceil(y1 + i * m * signY) )
  else
      for i=0; i<= deltaY; i++
          drawPixel( ceil(x1 + i / m * signX), ceil(y1 + i * signY) )

Где ceil () - это функция для округления, а drawPixel может быть любой функцией для установки пикселя.

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

Самые старые опубликованные алгоритмы растеризации линий относятся к началу 1960-х годов. Они использовались для управления цифровыми плоттерами , в которых перо могло перемещаться только по горизонтали, вертикали или диагонали по сетке с фиксированными интервалами. Это также включало алгоритм Брезенхема, представленный Джеком Брезенхэмом в 1963 году , который использует только целочисленные вычисления. Питтвей дал эквивалентный вывод этого алгоритма, который имеет преимущество перед довольно геометрической формулировкой Брезенхема, заключающейся в том, что его можно применять не только к линиям, но и к кривым. Результирующий алгоритм, иногда называемый «алгоритмом средней точки», точно такой же, как в статье Брезенхэма.

Выбор следующего пикселя в алгоритме Брезенхема

Идея алгоритма Брезенхема состоит в том, чтобы выбирать между двумя пикселями справа («восток») и вверху справа («северо-восток») от последнего пикселя, нарисованного на каждом шаге. Выбирается пиксель, который ближе к идеальной линии. Чтобы сделать это, посмотрите на средней точке между пикселями в рецептуре нейтрали и : если она выше идеальной линии, это ближе, в противном случае . ${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle NO}$${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle NO}$

Чтобы найти положение противоположной линии, используется другая форма уравнения прямой линии: ${\ displaystyle M}$

${\ Displaystyle F (x, \, y) = ax + by + c = \ Delta y \ times x- \ Delta x \ times y + c = 0}$.

F ( x, y ) равен 0 для точек на прямой, положительным для точек ниже и отрицательным для точек над линией. Если в это уравнение ввести координаты, получается значение ${\ displaystyle M}$

${\ displaystyle \ textstyle d_ {i} = F (x_ {i} +1, \, y_ {i} + {\ frac {1} {2}}) = \ Delta y (x_ {i} +1) - \ Delta x (y_ {i} + {\ frac {1} {2}}) + c}$.

В зависимости от знака этой управляющей переменной выбирается пиксель или . ${\ displaystyle d_ {i}}$${\ displaystyle O}$${\ displaystyle NO}$

Чтобы получить эффективный алгоритм, управляющая переменная вычисляется постепенно, то есть увеличивается шаг за шагом. То, как вы меняете его между двумя последовательными шагами, зависит от того, были ли выбраны пиксели или . Для каждого из этих случаев рассмотрите разницу между значением управляющей переменной для следующего, но одного и следующего пикселя: ${\ displaystyle O}$${\ displaystyle NO}$

${\ displaystyle {\ begin {align} \ textstyle \ Delta _ {O} & = \ textstyle d_ {i + 1} -d_ {i} = F (x_ {i} +2, \, y_ {i} + { \ frac {1} {2}}) - d_ {i} = \ Delta y \\\ textstyle \ Delta _ {NO} & = \ textstyle d_ {i + 1} -d_ {i} = F (x_ {i } +2, \, y_ {i} + {\ frac {3} {2}}) - d_ {i} = \ Delta y- \ Delta x \\\ конец {выровнено}}}$

С каждым шагом управляющая переменная увеличивается на выбранный пиксель или зависит от него . Если , то находится над прямой линией, поэтому она выбрана, в противном случае . ${\ displaystyle \ Delta _ {O}}$${\ displaystyle \ Delta _ {NO}}$${\ displaystyle d_ {i} \ leq 0}$${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle NO}$

Начальное значение управляющей переменной также можно эффективно вычислить, если начальная точка линии находится точно в пикселе: ${\ displaystyle d}$${\ Displaystyle F (x_ {a}, \, y_ {a}) = 0}$

${\ displaystyle \ textstyle d_ {0} = F \ left (x_ {a} +1, \, y_ {a} + {\ frac {1} {2}} \ right) = \ \ underbrace {\ Delta y \ cdot x_ {a} - \ Delta x \ cdot y_ {a} + c} _ {= F (x_ {a}, \, y_ {a}) = 0} \, + \, \ Delta y - {\ frac {\ Delta x} {2}} = \ Delta y - {\ frac {\ Delta x} {2}}}$

Чтобы исключить деление на 2, все значения управляющей переменной удваиваются; решающий знак сохраняется. Таким образом, алгоритм Брезенхема для линий с градиентом от 0 до 1 может быть выражен в следующем псевдокоде . Алгоритм требует только дополнений внутри цикла; простые умножения вне цикла также могут быть реализованы путем сложения.

Изменение управляющей переменной в алгоритме Брезенхема

d = 2×Δy – Δx
ΔO = 2×Δy
ΔNO = 2×(Δy − Δx)
y = ya
Pixel (xa, ya) einfärben
Für jedes x von xa+1 bis xeWenn d ≤ 0
        d = d + ΔO
    ansonsten
        d = d + ΔNO
        y = y + 1
    Pixel (x, y) einfärben

Другая интерпретация алгоритма предполагает, что растрированная линия содержит горизонтальные и диагональные шаги. Чтобы «смешать» эти два типа шагов, каждый шаг либо вычитается из управляющей переменной, либо добавляется. Выполняется соответствующий тип шага, в котором результирующая величина управляющей переменной меньше. Это также видно из приведенного выше рисунка, на котором управляющая переменная всегда находится как можно ближе к нулевой оси. Томпсон описал алгоритм, основанный на этой формулировке в 1964 году, но не обсудил выбор правильного начального значения для контрольной переменной. До Брезенхема Фред Стоктон опубликовал алгоритм растеризации линий в 1963 году, который также использует только целочисленные вычисления, но является излишне сложным.${\ displaystyle m = \ Delta x- \ Delta y}$${\ displaystyle n = \ Delta y}$${\ displaystyle m}$${\ displaystyle n}$

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

Ряды пикселей

Хотя алгоритм Брезенхема довольно эффективен, он рисует только один пиксель за итерацию, и для этого требуется дополнение. Метод, который рисует все пиксели в «строке», то есть пиксели с одинаковой координатой y, был впервые разработан Реджиори. Отдельно обрабатывались строки с одним пикселем. Позже Брезенхэм представил более общий алгоритм, который обходился без тестов для этого частного случая.

В алгоритме строки пикселей Брезенхема он не увеличивается постепенно, но . Конец текущей строки рассчитывается для каждого . Это делается путем рассмотрения точек, в которых идеальная линия пересекает горизонталь, проходящую через среднюю точку между двумя соседними по вертикали пикселями. Конец строки пикселей - это округленное значение координаты x этого пересечения: ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$

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

В самом внутреннем цикле нового алгоритма Брезенхема никаких дополнений не требуется, потому что все пиксели в строке окрашиваются одновременно. Однако для инициализации требуется деление. Фунг заменил его процедурой поиска и произвел дальнейшую оптимизацию.

N- шаговый метод

Четыре возможных шаблона пикселей в методе двойного шага

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

Чтобы иметь возможность различать четыре возможных шаблона в двухэтапном методе, сначала исследуется последний столбец пикселей в шаблоне. Если растеризуемый пиксель находится внизу или вверху, шаблоны 1 или 4 могут быть выведены тривиальным способом. Если, с другой стороны, пиксель находится посередине, необходима дополнительная проверка среднего столбца, чтобы иметь возможность выбирать между шаблонами 2 и 3.

Эти испытания упрощаются тем фактом, что при уклоне m  ½ образец 4 и при m  ½ образец 1 не может возникнуть. Подобно алгоритму Брезенхема, управляющая переменная для тестов также может быть вычислена постепенно с помощью двухшагового метода. В конце концов, алгоритм обходится только сложениями и простым умножением, которое можно реализовать с помощью быстрого сдвига битов .

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

Двунаправленный скрининг

Вверху: линия, растеризованная слева направо с использованием алгоритма Брезенхема; внизу: двунаправленное экранирование. Полые кружки указывают пиксели, которые будут окрашены, когда другой пиксель будет выбран при d = 0.

Чтобы еще больше увеличить скорость растеризации, имеет смысл рисовать линию двунаправленно, то есть одновременно от начальной и конечной точки до центральной точки. Здесь цикл проходит только над половиной строки; на каждом шаге два задействованных пикселя окрашиваются с каждой стороны линии. Таким образом можно модифицировать как алгоритм Брезенхема, так и другие методы.

Однако следует отметить, что линия, растеризованная с помощью обычных методов, сама по себе не обязательно является точечно-симметричной . Это связано с тем, что при растеризации возникают неоднозначные ситуации, когда идеальная линия проходит точно через центр двух вертикально смежных пикселей, между которыми вы можете свободно выбирать. Алгоритм Брезенхема, перечисленный выше, например, в таких случаях всегда выбирает пиксель с меньшей координатой y ( ) . С другой стороны, при рисовании справа налево пиксель с большей координатой y выбирается из-за использования симметрии . Если линия проводится двунаправленно или справа налево, внешний вид может измениться по сравнению с обычным алгоритмом, при условии, что неоднозначные случаи не проверяются отдельно. ${\ displaystyle d = 0}$

Другие техники

периодичность

Можно показать , что значения управляющей переменной в алгоритме Bresenham повторить раз, где а является наибольший общий делитель из и . Это означает, что значения управляющей переменной должны быть рассчитаны только для части линии и затем могут быть применены к другим частям. Однако для этого необходимо рассчитать НОД. Этот метод также можно комбинировать с двунаправленным скринингом. ${\ displaystyle \ Delta x}$${\ displaystyle \ Delta y}$

Строки пикселей первого, второго и третьего порядка

Иерархические ряды пикселей

Длина строк пикселей в растрированной строке соответствует определенному шаблону. Розенфельд доказал, что длина всех строк пикселей, кроме, возможно, первого и последнего, отличается не более чем на один пиксель. Он также обнаружил, что последовательность строк пикселей сама по себе имеет такую ​​структуру, как и последовательность этих последовательностей и так далее. Растеризованные строки иерархически структурированы из строк « n-го порядка», каждая из которых может принимать только определенную длину. Стивенсон описал работоспособные алгоритмы, которые могут рисовать линию из строк любого высокого порядка, а также рекурсивный алгоритм, который начинается с наивысшего возможного порядка. Это обобщает как алгоритм Брезенхэма, так и алгоритм строки пикселей. Алгоритм для строк «нулевого порядка», в котором строки пикселей игнорируются, соответствует обычному алгоритму Брезенхема.

Структурные алгоритмы

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

Например, алгоритм Бронса представляет растеризованную линию строкой из нулей и единиц, где 0 означает горизонтальный шаг, а 1 - диагональный шаг. Алгоритм предполагает символьную строку, которая представляет собой первое приближение линии, объединяет последовательности нулей и единиц и распределяет их равномерно. Тот же процесс применяется к получившейся последовательности. Это повторяется до тех пор, пока не удастся добиться дальнейшего улучшения. Однако растрированная таким образом линия не является оптимальной; чтобы получить ту же линию, что и в алгоритме Брезенхема, необходимы дополнительные настройки.

Свойства и сравнение

Хотя было обнаружено множество алгоритмов, которые менее сложны, чем алгоритм Брезенхема, их практическое преимущество в скорости невелико. Это связано с тем, что инструкции по раскрашиванию пикселей на современном оборудовании очень медленные по сравнению с выполнением самого растрового алгоритма. Однако некоторые графические карты предоставляют несколько более быстрые функции для одновременного окрашивания нескольких пикселей, например, функция rectwrite в системах SGI . Это преимущество для алгоритмов строки пикселей, которые могут сразу же быстро нарисовать такую ​​строку.

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

Еще один фактор при выборе алгоритма - длина программы. Производители графических процессоров, которые реализуют растеризацию непосредственно на аппаратном уровне и поэтому нуждаются в экономии места, предпочитают короткие алгоритмы, такие как алгоритм Брезенхема. В программных реализациях этот фактор менее критичен.

Проблемы

Разная яркость в зависимости от наклона

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

Различная яркость

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

Стили линий

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

Вырезка

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

Сглаживание

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

Метод Гупты и Спроулла

Иллюстрация конического сглаживающего ядра. Интенсивность пикселя пропорциональна объему V.

При сглаживании цветное значение пикселя может быть определено путем размещения так называемого ядра сглаживания или фильтра восстановления поверх пикселя. Гупта и Спроул предложили в качестве сглаживающего ядра конус радиусом в один пиксель. Значение цвета пикселя пропорционально объему той части конуса, которая перекрывает линию, подлежащую растрированию (в данном случае прямоугольник, подлежащий растрированию). Этот объем, в свою очередь, зависит от расстояния между центральной линией прямоугольника и пикселем. ${\ displaystyle D}$

Три возможных пикселя, окрашенных толщиной линии в один пиксель.

Алгоритм Гупта-Спроула основан на алгоритме Брезенхема, но также рассчитывает для каждого из пикселей, ядро ​​сглаживания которых перекрывает линию. При ширине линии в один пиксель это максимум три пикселя на столбец. Из соображений эффективности расстояния не рассчитываются точно, учитываются только 24 возможных расстояния. Значения интенсивности, соответствующие этим расстояниям, были рассчитаны заранее и сохранены в таблице ( справочной таблице ), чтобы их можно было быстро вызвать. ${\ displaystyle D}$

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

Алгоритм Гупта-Спроулла подходит для линий с любой толщиной линии, хотя таблица поиска также меняется. Если ширина линии больше одного пикселя, необходимо отметить, что ядра сглаживания более трех пикселей могут перекрывать линию.

Проблема с алгоритмом Гупта-Спроулла заключается в том, что экранированные линии часто имеют разную яркость в разных местах. Такой «канатоподобный» вид в основном связан с неадекватностью конуса в качестве сглаживающего стержня.

Метод Ву

Расчет интенсивностей в антиалиасинге Wu

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

Алгоритм Брезенхема пытается аппроксимировать идеальную линию, минимизируя «ошибку», то есть расстояние между идеальной линией и двумя возможными пикселями. Ву предложил другую меру погрешности, которую можно применить к любой кривой. Ошибка в смысле этой меры погрешности может быть полностью устранена, если разрешены любые значения цвета. Для этого два пикселя, которые находятся непосредственно над и под идеальной линией, должны принимать значения цвета, пропорциональные вертикальному расстоянию до идеальной линии.

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

Другие техники

Различные методы сглаживания на примере модели проволочной сетки САПР . Слева направо: без сглаживания (Брезенхэм), Гупта-Спроул, сканирование невзвешенной области и Ву.

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

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

В дополнение к процессам сглаживания, специально оптимизированным для линий, также могут использоваться общие процессы, такие как метод Уиттеда, в котором растровая графика с высоким разрешением перемещается как «кисть» вдоль линии.

Специальные оптимизации

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

Метод аппроксимации

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

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

Простой метод распараллеливания монохромной растеризации позволяет различным алгоритмам работать параллельно, каждый из которых слегка смещен и рисует несколько пикселей с определенными интервалами. Другая возможность - разделить строку на несколько примерно равных частей, каждая из которых назначается процессору для растеризации. Каждая часть визуализируется с использованием алгоритма Брезенхема; основная проблема - это вычисление правильных начальных значений переменных. Также возможно, чтобы несколько процессоров вычисляли координаты конечной точки строк с использованием алгоритма строки пикселей Брезенхема. Также были представлены алгоритмы для векторных компьютеров, массово работающих параллельно с более чем 1000 процессорами. Каждый пиксель растровой графики назначается процессору, который решает, должен ли этот пиксель быть окрашен или нет.

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

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

4-х звенная сетка. Квадраты, выбранные в дополнение к 8-соединенной сетке, показаны заштрихованными.

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

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

литература

• Джеймс Д. Фоли, среди прочего: Компьютерная графика: Принципы и практика в C . Аддисон-Уэсли, Рединг (Массачусетс) 1995, ISBN 978-0-201-84840-3 . (Охватывает алгоритм Брезенхэма, проблемы растеризации и сглаживание Гупта-Спроулла) 

Отдельные статьи:

Этот список является избранным; подробная библиография включена в диссертацию Стивенсона.

1. ↑ См. Образец кода на http://www.crbond.com/papers/newline.pdf (250 КБ)
2. ^ Алгоритм компьютерного управления цифровым плоттером. IBM Systems Journal 4, 1 (1965): 25-30, ISSN  0018-8670 ( PDF, 220 кБ ). Уже представлен в августе 1963 года в качестве лекции на Национальной конференции ACM в Денвере.
3. ↑ Майк Л.В. Питтуэй: Алгоритм рисования эллипсов или гипербол с помощью цифрового плоттера. Компьютерный журнал 10, 3 (ноябрь 1967): 282-289, ISSN  0010-4620
4. ^ JR Томпсон: Переписка: прямые линии и графопостроители. Компьютерный журнал 7, 3 (август 1964): 227
5. ↑ Фред Г. Стоктон: Алгоритм 162: построение графика XYmove. Сообщения ACM 6, 4 (апрель 1963 г.): 161, ISSN  0001-0782
6. ↑ Джованни Б. Реджиори: цифровые компьютерные преобразования для нерегулярных штриховых рисунков. Технический отчет 403-22, Нью-Йоркский университет, Нью-Йорк, апрель 1972 г.
7. ^ Джек Э. Брезенхэм и др.: Срезы длины серии для добавочных линий. Бюллетень технических раскрытий IBM 22-8B (1980): 3744-3747, ISSN  0018-8689
8. ↑ ^{a b} Кхун Йи Фунг: Алгоритм рисования длинных отрезков без операций деления. Форум компьютерной графики 11, 3 (1992): 267-277, ISSN  0167-7055
9. ↑ Сяолинь Ву, Джон Г. Рокне: Двухшаговая пошаговая генерация линий и кругов. Компьютерное зрение, графика и обработка изображений 37,3 (март 1987 г.): 331-344, ISSN  0734-189X
10. ↑ Фил Грэм, С. Ситхарама Айенгар: Двойная и тройная пошаговая пошаговая генерация линий. В ACM CSC '93 Proceedings: 384-389. ACM Press, Индианаполис 1993, ISBN 0-89791-558-5
11. ^ Пол Бао, Джон Г. Рокне: Генерация линии в четыре шага. Компьютеры и графика 13, 4 (1989): 461-469, ISSN  0097-8493
12. ^ Грэм У. Гилл: N-шаговые инкрементные алгоритмы прямой линии. IEEE Computer Graphics and Applications 14, 3 (май 1994): 66-72, ISSN  0272-1716
13. ↑ ^{a b} Джулио Кашиола: Основные концепции для ускорения алгоритмов построения линий. Компьютеры и графика 12, 3/4 (1988): 489-502.
14. ^ Азриэль Розенфельд: сегменты цифровых прямых линий. Транзакции IEEE на компьютерах C-23, 12 (декабрь 1974 г.): 1264-1269, ISSN  0018-9340
15. ^ ^{A b} Питер Стивенсон: Структура оцифрованной линии: с приложениями для рисования линий и трассировки лучей в компьютерной графике. Докторская диссертация, Университет Джеймса Кука в Северном Квинсленде, Австралия, 1998 г. ( онлайн ( памятная записка от 5 сентября 2007 г. в Интернет-архиве ))
16. ^ Рейер Бронс: лингвистические методы описания прямой линии на сетке. Компьютерная графика и обработка изображений 3 (1974): 48-62, ISSN  0146-664X
17. ^ Джим X. Чен: Анализ и статистика распределения линий. IEEE Computer Graphics and Applications 22, 6 (ноябрь / декабрь 2002 г.): 100-107
18. ^ Евгений П. Кузьмин: алгоритм генерации линии Брезенхэма со встроенным отсечением. Форум компьютерной графики 14, 5 (1995): 275-280
19. ↑ Сатиш Гупта, Роберт Ф. Спроул: Фильтрация краев для полутоновых дисплеев. В ACM SIGGRAPH '81 Proceedings: 1-5. ACM Press, Даллас 1981, ISBN 0-89791-045-1
20. ^ А. Р. Форрест: Сглаживание на практике. В RA Earnshaw (ed.): Fundamental Algorithms for Computer Graphics (= NATO ASI Series F.17): 113-134. Springer, Берлин 1985, ISBN 3-540-13920-6
21. ↑ Сяолинь Ву: эффективная техника сглаживания. В ACM SIGGRAPH '91 Proceedings: 143-152. ACM Press, Нью-Йорк 1991, ISBN 0-89791-436-8
22. ↑ См., Например, Винсент Бойер, Жан-Жак Бурден: Дискретный анализ сглаженных линий. Краткая презентация, Eurographics 2000 ( PDF, 230 kB )
23. ↑ Николас А. Диакопулос, Питер Д. Стивенсон: Сглаживание линий с использованием масок прогона. Форум компьютерной графики 24, 2 (июнь 2005 г.): 165-172
24. ^ Тернер Уиттед: рисование линий со сглаживанием с использованием выдавливания кисти. В ACM SIGGRAPH '83 Proceedings: 151-156. ACM Press, Детройт 1983, ISBN 0-89791-109-1
25. ↑ Винсент Бойер, Жан-Жак Бурден: Fast Lines: Span by Span Method. Форум компьютерной графики 18, 3 (1999): 377–384 ( PDF, 400 kB )
26. ^ Роберт Ф. Спроул: Использование программных преобразований для получения алгоритмов рисования линий. Транзакции ACM на графике 1,4 (октябрь 1982 г.): 259-273, ISSN  0730-0301
27. ^ Уильям Э. Райт: Распараллеливание алгоритмов линии и круга Брезенхема. IEEE Computer Graphics and Applications 10, 5 (сентябрь 1990 г.): 60-67
28. ↑ Иво Поважан, Томаш Груз: Параллельная линия: единое решение. In WSCG '97 Proceedings: 60-67. Университет Западной Богемии, Пльзень 1997, ISBN 80-7082306-2 ( онлайн )
29. ↑ Алекс Т. Панг: Алгоритмы рисования линий для параллельных машин. IEEE Computer Graphics and Applications 10, 5 (сентябрь 1990 г.): 54-59
30. ↑ См., Например, Pere Marès Martí, Antonio B. Martínez Velasco: Архитектура памяти для параллельного рисования линий, основанная на инкрементальном алгоритме. В: Euromicro 2000 Proceedings: Vol. 1, 266-273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8
31. ↑ См., Например, Роберт Макнамара и др.: Предварительно отфильтрованные сглаженные линии с использованием функций полуплоскостного расстояния. В HWWS 2000 Proceedings: 77-85. ACM Press, Нью-Йорк 2000, ISBN 1-58113-257-3
32. ↑ Chengfu Yao, Jon G. Rokne: Подход с интегральной линейной интерполяцией к разработке алгоритмов инкрементных линий. Журнал вычислительной и прикладной математики 102, 1 (февраль 1999 г.): 3-19, ISSN  0377-0427
33. ^ Митчелл А. Харрис, Эдвард М. Рейнгольд: рисование линий, високосные годы и Евклид. ACM Computing Surveys 36, 1 (март 2004 г.): 68–80, ISSN  0360-0300 ( PDF, 270 кБ ( памятная записка от 16 декабря 2006 г. в Интернет-архиве ))

веб ссылки

• Алгоритм Брезенхема (Словарь алгоритмов и структур данных NIST) - Предпосылки к алгоритму Брезенхема с исходным исходным кодом
• Растеризация линий, окружностей, эллипсов (Магдебургский университет, Институт моделирования и графики) - Java-апплет для понимания алгоритма Брезенхема
• Проект: Статистика линий (Лаборатория компьютерной графики Университета Джорджа Мейсона) - Исследование распределения длин линий и наклона
• Красота алгоритма Брезенхема - простая реализация для рисования линий, окружностей, эллипсов и кривых Безье

Эта статья была добавлена в список отличных статей 4 мая 2007 года в этой версии .