4. Разложение в растр отрезков прямых.

   1. Разложение на основе параметрического уравнения прямой

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

Горизонтальные и вертикальные линии легко построить. Также и прямоугольники со сторонами параллельными границам экрана. Их рассматривать не будем. Это частные случаи построения отрезка. Надо построить отрезок общего положения на плоскости.

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

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

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

Вернёмся к прямым общего положения – слайд 7. Здесь изображён растровый экран как бы в увеличенном виде и где мы видим каждый пиксел.

Если взять параметрическое уравнение прямой линии

x

t = где N – число всех пикселов экрана,

= x₁∙(1-t) + x₂∙t

y = y₁∙(1-t) + y₂∙t

и по этому уравнению вывести на экран примитив прямой, то его вид будет таким, как показан на экране выше – с большим количеством артефактов, лестничным эффектом, уплотнёнными и разряженными узлами. Алгоритм не учитывает, что экран дискретный. За счет аппаратного или программного округления координат точек возможны либо наслоения точек, либо пропуски их при отрисовке на экране. Идеально в зоне 2х2 должно быть не больше двух точек. Визуально, восприятие такой информации не комфортно. То же можно отметить и на отрисовке окружности. Эти артефакты, как отмечено выше, связаны с округлением результатов расчёта точки по алгоритму. Возникает вопрос – как от этого избавиться?

2. 1-ый классический алгоритм

Рассмотрим 1-ый классический алгоритм. Он и получил название пошаговый алгоритм аппроксимации прямой.

Требуется построить отрезок прямой, заданной координатами начальной точки (x₁, y₁) и конечной - (x₂, y₂). Изображение отрезка на слайде 8.

Перенесём прямую в начало координат (на “-b”). Тогда имеем уравнение прямой –

y = kx,

где k = = = .

При увеличении x на 1, значение k = сводится к k = , т. е. изменение x на 1 приводит к изменению y на k. Следовательно, алгоритм итерации можно записать так:

– алгоритм итерации.

Дальше, значение y округляют до целого ближайшего!, т. е. принимают y_i = (round(y_i)). Последующие точки вычисляют на основе полученных предыдущих значений.

Если k>1, то шаг по х приведёт к смещению “y” более чем на 1 пиксел. Появится разреженность точек в непрерывном отрезке. Поэтому, при k>1 x и y меняют местами: задают y = 1 ед., а x = = единиц.

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

Текст программы – слайд 11.