Формы в растровую.

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

Пошаговый алгоритм

Операцию умножения можно устранить, если заметить, что при сводится к , т.е. изменение на 1 приводит к изменению на (тангенс угла наклона).

Т.о. если , то

,

т.е. последующие значения т. отрезка определяются, исходя из предыдущих.

Рис. 3.1

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

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

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

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

Рис. 3.2

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

Т.е. если

.

А теперь рассмотрим алгоритм подробнее.

Есть отрезок — . Пусть 1-я т. находится ближе к началу координат, тогда перенесем обе точки при помощи так, чтобы начальная точка отрезка стала (0, 0), а конечная — , или .

Уравнение прямой будет иметь вид: .

Обозначим координаты после переноса т. через . Тогда координаты:

Найдем разность:

Величина , поэтому можно использовать в качестве проверки условия.

Обозначим: , имеем:

.

Т.к.

, ,

то

(1)

Прибавляя 1 к каждому индексу:

Вычитая из :

Но

(2)

Т.е. вначале вычисляется .

Если , выбирается , тогда

и

.

Если , выбирается , тогда

и

.

Т.о. мы получили итерактивнй способ вычисления по предыдущему значению и выбора между и .

Начальное значение находят из выражения (1) при , : .