Алгоритмы вывода графических примитивов. Прямое вычисление координат

Алгоритмы машинной графики можно разделить на два уровня: нижний и верхний. Группа алгоритмов нижнего уровня предназначена для реализации графических примитивов (линий, окружностей, заполнений и т.п.).

Среди алгоритмов нижнего уровня можно выделить следующие группы:

· Простейшие в смысле используемых математических методов и отличающиеся простотой реализации. Такие алгоритмы не являются наилучшими по объему выполняемых вычислений или требуемым ресурсам памяти.

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

· К третьей группе следует отнести алгоритмы, которые могут быть без больших затруднений реализованы аппаратно (допускающие распараллеливание, рекурсивные, реализуемые в простейших командах). В эту группу могут попасть и алгоритмы, представленные в первых двух группах.

· Наконец, к четвертой группе можно отнести алгоритмы со специальным назначением (например, для устранения лестничного эффекта).

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

или

Для того чтобы свести к минимуму вычисления в цикле, все операции над константами выносятся из тела цикла:

В цикле вычисляется

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

+ Простота, ясность построения алгоритма;

+ Возможность работы с нецелыми значениями координат отрезка.

- Использование операций с дробными числами или целочисленных операций умножения и деления обуславливает малую скорость;

- При вычислении координат путем добавления приращений может накапливаться ошибка.

Алгоритмы вывода прямой линии:
Рассмотрим растровые алгоритмы для отрезков прямой линии. Предполо­жим, что заданы координаты (x 1,y 1 - х2,у2) концов отрезка прямой. Для вывода линии необходимо закрасить в определенный цвет все пикселы вдоль линии. Для того чтобы закрасить каждый пиксел, необходимо знать его ко­ординаты.

Наиболее просто нарисовать отрезок горизонтальной линии:

Вычисление текущих координат пиксела здесь выполняется как приращение по х (необходимо, чтобы х1 <-х2), а вывод пиксела обеспечивается функцией Пиксел(). Поскольку в языке С, C++ для названия функции нельзя использо­вать кириллицу, то будем дальше использовать ее как комментарий.

Аналогично рисуется отрезок вертикали:

Как видим, в цикле выполняются простейшие операции над целыми числа­ми — приращение на единицу и проверка на "< =". Поэтому операция рисо­вания отрезка выполняется быстро и просто. Ее используют как базовую операцию для других операций, например, в алгоритмах заполнения плоско­сти полигонов.

Можно поставить такой вопрос: какая линия рисуется быстрее — горизон­таль или вертикаль? На первый взгляд — одинаково быстро. Если учитывать только математические аспекты, то скорость должна быть одной и той же при одинаковой длине линий, поскольку в обоих случаях выполняется равное количество идентичных операций. Однако если кроме расчета координат анализировать также вывод пикселов, то могут быть отличия. В растровых системах рисование пиксела обычно означает запись одного или нескольких бит в память, где сохраняется растр. И здесь уже не все равно — по строкам или по столбцам заполняется растр. Необходимо учитывать логическую ор­ганизацию памяти компьютера, в которой хранятся, биты или байты растра.

Даже для компьютеров одного типа (например, персональных компьютеров) для различных поколений процессоров и памяти скорость записи по сосед­ним адресам может существенно отличаться от скорости записи по не сосед­ним адресам [40]. В особенности это заметно, когда для растра используется виртуальная память с сохранением отдельных страниц на диске и (или) в оперативной памяти (RAM). При работе графических программ в среде опе­рационной системы Windows часто случается так, что горизонтали рисуются быстрее вертикалей, поскольку в страницах памяти хранятся соседние байты. А может быть, что RAM достаточно, но скорости рисования все же различны.

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

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