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

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

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

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

Декартово уравнение пересечения наклона для прямой: $Y\; =\; mx\; +\; b\; \{\backslash \; displaystyle\; Y\; =\; mx\; +\; b\}$, где m представляет наклон линии и b как пересечение оси y. Учитывая, что две конечные точки линейного сегмента указаны в позициях $(x\; 1,\; y\; 1)\; \{\backslash \; displaystyle\; (x1,\; y1)\}$и $(x\; 2,\; y\; 2)\; \{\; \backslash \; displaystyle\; (x2,\; y2)\}$, мы можем определить значения для наклона m и точки пересечения оси y b с помощью следующих вычислений: $m\; =\; (y\; 2\; -\; y\; 1)\; /\; (x\; 2\; -\; Икс\; 1)\; \{\backslash \; Displaystyle\; м\; =\; (y2-y1)\; /\; (x2-x1)\}$так, $b\; =\; y\; 1\; -\; m\; \ast \; x\; 1\; \{\backslash \; displaystyle\; b\; =\; y1-m\; *\; x1\; \}$.

Линии с использованием алгоритма Сяолинь Ву, показывающие "липкий" вид.

Ниже приводится частичный список алгоритмов рисования линий:

• наивный алгоритм
• Цифровой дифференциальный анализатор ( графический алгоритм) - Подобен простому алгоритму рисования линий, с небольшими вариациями.
• Линейный алгоритм Брезенхэма - оптимизирован для использования только сложений (то есть без делений или умножений); он также позволяет избежать вычислений с плавающей запятой.
• Линейный алгоритм Сяолинь Ву - может выполнять пространственное сглаживание, выглядит "нечетким" из-за того, что яркость меняется по длине линии

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

Самый простой метод растрирования - это прямое рисование уравнения, определяющего линию.

dx = x2 - x1 dy = y2 - y1 для x от x1 до x2 do y = y1 + dy × (x - x1) / dx plot ( x, y)

Именно здесь точки уже упорядочены так, чтобы $x\; 2>x\; 1\; \{\backslash \; displaystyle\; x\_\; \{2\}>x\_\; \{1\}\}$. Этот алгоритм отлично работает когда $dx>=\; dy\; \{\backslash \; displaystyle\; dx>=\; dy\}$(т.е. наклон меньше или равен 1), но если (т.е. наклон больше 1), Строка становится довольно разреженной с большим количеством пробелов, и в предельном случае $dx\; =\; 0\; \{\backslash \; displaystyle\; dx\; =\; 0\}$произойдет исключение деления на ноль.

Наивный алгоритм рисования линий неэффективен и поэтому медлителен на цифровом компьютере. Его неэффективность связана с количеством операций и использованием вычислений с плавающей запятой. Вместо этого предпочтительны алгоритмы рисования линий, такие как Bresenham или Wu.

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