Построение треугольника

Алгоритм Брезенхема построения растрового образа отрезка был изначально разработан для графопостроителей, но он полностью подходит и для растровых дисплеев. В процессе работы в зависимости от углового коэффициента отрезка изменяется на единицу либо x, либо y, а изменение другой координаты (на ноль или на единицу) зависит от расстояния между действительным положением точки и ближайшей точкой растра, называемое ошибкой. Алгоритм построен так, что анализируется лишь знак этого смещения. На рис. 2 это иллюстрируется для отрезка в первом октанте, то есть для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0, 0) больше чем 1/2, то его пересечение с прямой x = 1 будет расположено ближе к прямой y = 1, чем к прямой y = 0. Следовательно, точка растра (1, 1) лучше аппроксимирует ход отрезка, чем точка (1, 0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента, равного 1/2, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1, 1).

(рис. 2)

Не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется на рис. 3, где отрезок с тангенсом угла наклона 3/8 сначала проходит через точку растра (0, 0) и последовательно пересекает три пикселя. Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселями. Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной -1/2. Таким образом, если угловой коэффициент отрезка больше или равен 1/2, то величина ошибки в следующей точке растра с координатами (1, 0) может быть вычислена как

e = e + m,

где m -- угловой коэффициент. В нашем случае при начальном значении ошибки -1/2 e = -1/2 + 3/8 = -1/8.

(рис. 3)

Так как e отрицательно, отрезок пройдет ниже середины пикселя. Следовательно, пиксель на том же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому у не увеличивается. Аналогично вычисляем ошибку e = -1/8 + 3/8 = 1/4 в следующей точке растра (2, 0). Теперь e положительно, а значит, отрезок пройдет выше средней точки. Растровый элемент (2, 1) со следующей по величине координатой y лучше аппроксимирует положение отрезка. Следовательно, y увеличивается на единицу. Прежде чем рассматривать следующий пиксель, необходимо откорректировать ошибку вычитанием из нее единицы. Имеем e = 1/4 - 1 = -3/4.

Заметим, что пересечение вертикальной прямой x = 2 с заданным отрезком лежит на 1/4 ниже прямой y = 1. Если же перенести отрезок 1/2 вниз, мы получим как раз величину -3/4. Продолжение вычислений для следующего пикселя дает e = -3/4 + 3/8 = -3/8.

Так как e отрицательно, то y не увеличивается. Из всего сказанного следует, что ошибка -- это интервал, отсекаемый по оси y рассматриваемым отрезком в каждом растровом элементе (относительно -1/2).

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

(рис. 4)

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

Функция Line аппроксимирует отрезок с начальными координатами X1, Y1 и конечными координатами X2, Y2 по общему алгоритму Брезенхема.

Функция Triang объединяет три матрицы с координатами точек каждой стороны треугольника.

Далее выводим средствами Mathcad результат работы функции Triang для заданных координат вершин треугольника:

 
< Пред   СОДЕРЖАНИЕ   Скачать   След >