АЛГОРИТМЫ РАСТРОВОЙ ГРАФИКИ
Алгоритмы развертки, применяемые при построении растрового изображения, вызывается очень часто – при каждом создании или модификации изображения. Поэтому алгоритмы должны давать не только хорошее изображение, но и делать это как можно быстрее.
Основные критерии алгоритмов:
¾ скорость,
¾ качество изображения.
Но обычно предпочтение отдается быстродействию.
Преобразование отрезков из векторной
Формы в растровую.
Главной задачей алгоритма развертки отрезков является вычисление координат пикселов на двумерной растровой сетке. При решении этой задачи будем предполагать, что конечные т. отрезков имеют целые координаты. Простой алгоритм заключается в пошаговом x, вычислении и высвечивании в т. . Вычисление произведения требует и замедляет процесс разложения в растр.
Пошаговый алгоритм
Операцию умножения можно устранить, если заметить, что при сводится к , т.е. изменение на 1 приводит к изменению на (тангенс угла наклона).
Т.о. если , то
,
т.е. последующие значения т. отрезка определяются, исходя из предыдущих.
Рис. 3.1
Если , тот шаг по будет приводить к шагу по . Поэтому надо и поменять местами - на 1, а на . После вычисления очередной т. происходит округление ее координат до ближайших целых.
Алгоритм Брезенхэма
Трудности применения предыдущего метода состоят в том, что округление до целого значения требует времени, и кроме того, и должны быть вещественными числами.
Более привлекателен в этом отношении алгоритм Брезенхэма, т.к. в нем используется только целая арифметика. Вещественные переменные не используются совсем, и, значит, округление не нужно.
Рис. 3.2
Суть метода: В алгоритме используется управляющая переменная , которая на каждом шаге пропорциональна разности между и . Так для т. надо определить, какой из будет выбран: и ? Если , то ближе к отрезку, в противном случае ближе будет .
Т.е. если
.
А теперь рассмотрим алгоритм подробнее.
Есть отрезок — . Пусть 1-я т. находится ближе к началу координат, тогда перенесем обе точки при помощи так, чтобы начальная точка отрезка стала (0,0), а конечная — , или .
Уравнение прямой будет иметь вид: .
Обозначим координаты после переноса т. через . Тогда координаты:
Найдем разность:
Величина , поэтому можно использовать в качестве проверки условия.
Обозначим: , имеем:
.
Т.к.
, ,
то
(1)
Прибавляя 1 к каждому индексу:
Вычитая из :
Но
(2)
Т.е. вначале вычисляется .
Если , выбирается , тогда
и
.
Если , выбирается , тогда
и
.
Т.о. мы получили итерактивнй способ вычисления по предыдущему значению и выбора между и .
Начальное значение находят из выражения (1) при , : .
Дата добавления: 2016-07-18; просмотров: 2325;