Разбор случаев для обобщённого алгоритма Брезенхема
Пересечение окружности и сетки растра
Системы координаты строк сканирования
Необходимость удаления невидимых линий
Обработка нижней стороны поверхности
Эффект зазубренного ребра
Xребра = x
Не лицевые плоскости
Схема решения относительно a и t
Простая трассировка лучей
Пересечение прямоугольной области в преобразованной системе координат
Навигация
Xребра = x
Трёхмерная компьютерная графика
103587
знаков
0
таблиц
0
изображений
1 Xребра = x
Yребра = y
return
подпрограмма определения видимости точки
Subroutine Видимость (x, y, Верх, Низ; Тфлаг)
видимость точки определяется по отношению к верхнему и нижнему плавающим горизонтам. Если точка лежит на самом горизонте, то она считается видимой.
Тфлаг = 0, если точка невидима
= 1, если она видима и выше верхнего горизонта
= -1, если она видима и ниже нижнего горизонта
x считается целой
if (y < Верх (x)) and (y > Низ (x)) then Тфлаг = 0
if y ³ Верх (x) then Тфлаг = 1
if y £ Низ (x) then Тфлаг = -1
return
подпрограмма заполнения массивов плавающих горизонтов
Subroutine Горизонт (X1, Y1, X2, Y2; Верх, Низ)
Эта программа использует линейную интерполяцию для заполнения массивов горизонтов между X1 и X2
Max (a, b) – определяет большее из a и b
Min (a, b) – определяет меньшее из a и b
проверка вертикальности наклона
if (X2 - X1) = 0 then
Верх (X2) = Max (Верх (X2), Y2)
Низ (X2) = Min (Низ (X2), Y2)
else
Наклон = (Y2 - Y1)/(X2 - X1)
for x = X1 to X2 step 1
y = Наклон * (x - X1) + Y1
Верх (x) = Max (Верх (x), y)
Низ (x) = Min (Низ (x), y)
next x
end if
return
подпрограмма вычисления пересечения текущей кривой с горизонтом
Subroutine Пересечение (X1, Y1, X2, Y2, Массив; Xi, Yi)
Эта процедура вычисляет пересечение двух отрезков прямых
Массив содержит информацию о соответствующем горизонте
Sign – функция принимающая значения -1, 0, 1, если знак её аргумента <0, =0, >0 соответственно
проверка бесконечности наклона
if (X2 – X1) = 0 then
Xi = X2
Yi = Массив (X2)
else
вычисление пересечения
обход начинается с самой левой используемой точки
пересечение считается обнаруженным, когда изменяется знак разности значений y
Наклон = (Y2 – Y1)/(X2 – X1)
Ysign = Sign (Y1 + Наклон - Массив (X1 + 1))
Csign = Ysign
Yi = Y1 + Наклон
Xi = X1 + 1
while Csign = Ysign
Yi = Y1 + Наклон
Xi = X1 + 1
Csign = Sign (Yi - Массив (Xi))
end while
выбирается ближайшее целое число
if |Yi - Наклон - Массив (X1 – 1)| £ |Yi - Наклон - Массив (X1)| then
Yi = Y1 – Наклон
Xi = X1 – 1
end if
end if
return
В приведенных выше алгоритме и примере функция у = f (x, z) рассматривалась только при z = const. Часто бывает удобно вычерчивать кривые, полагая постоянными как z, так и x. При этом возникает эффект перекрестной штриховки. На первый взгляд может показаться, что перекрестную штриховку можно получить путем наложения двух результатов, образованных плоскостями z = const и x = const. Однако это не так. Верный результат получается при обработке тех кривых из числа лежащих в плоскостях z = const и x = const, которые ближе всего к горизонтальным при обычном порядке их следования. Однако после обработки каждой кривой, самой близкой к горизонтальной, необходимо обрабатывать участки кривых, лежащих в ортогональных ей плоскостях, которые находятся между указанной кривой и кривой, следующей за ней. Разумеется, при обработке обеих последовательностей кривых нужно использовать одни и те же массивы верхнего и нижнего плавающих горизонтов. Если используется перекрестная штриховка, то не надо формировать левое и правое боковые ребра.
Алгоритм Робертса
Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий . Это математически элегантный метод, работающий в объектном пространстве. Алгоритм, прежде всего, удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет теоретически как квадрат числа объектов. Именно этот факт привёл к снижению интереса к алгоритму Робертса. Однако математические методы, используемые в этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алгоритма, использующие предварительную приоритетную сортировку вдоль оси z и простые габаритные или минимаксные тесты, демонстрируют почти линейную зависимость от числа объектов.
В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые части. В этом алгоритме выпуклое многогранное тело с плоскими гранями должно представляться набором пересекающихся плоскостей. Уравнение произвольной плоскости в трехмерном пространстве имеет вид
ах + by + cz + d = 0 (3.1)
В матричной форме это выглядит так:
или
где представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е.
где каждый столбец содержит коэффициенты одной плоскости.
Напомним, что любая точка пространства представима в однородных координатах вектором
Более того, если точка [S] лежит на плоскости, то [S]*[P]T = 0. Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают положительное скалярное произведение.
Хотя уравнение плоскости (3.1) содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы d = 1 следовательно, трех неколлинеарных точек достаточно для определения этих коэффициентов. Подстановка координат трех неколлинеарных точек (x1, y1, z1), (x2, y2, z2), (x2, y2, z2) в нормированное уравнение (3.1) дает:
ax1+ by1 + cz1 = -1
ax2+ by2 + cz2 = -1
ax3+ by3 + cz3 = -1
В матричной форме это выглядит так:
или
(3.2)
Решение этого уравнения дает значения коэффициентов уравнения плоскости:
Другой способ используется, если известен вектор нормали к плоскости, т. е.
n = ai + bj + ck
где i, j, k - единичные векторы осей x, y, z соответственно. Тогда уравнение плоскости примет вид
ax + by + cz + d = 0(3.3)
Величина d вычисляется с помощью произвольной точки на плоскости. В частности, если компоненты этой точки на плоскости (х1, y1, z1)то:
d = - (aх1+ by1 + cz1) (3.4)
Поскольку объем вычислений в алгоритмах удаления невидимых линий или поверхностей растет с увеличением числа многоугольников, для описания поверхностей выгодно использовать многоугольники с более чем тремя сторонами. Эти многоугольники могут быть как невыпуклыми, так и неплоскими. Метод, предложенный Мартином Ньюэлом, позволяет найти как точное решение для уравнений плоскостей, содержащих плоские многоугольники, так и “наилучшее” приближение для неплоских многоугольников. Этот метод эквивалентен определению нормали в каждой вершине многоугольника посредством векторного произведения прилежащих ребер и усреднения результатов. Если a, b, c, d – коэффициенты уравнения плоскости, то
(3.5)
где
if i =n then j = 1 else j = i + 1
а d вычисляется с помощью любой точки на плоскости.
Перед началом работы алгоритма удаления невидимых линий или поверхностей для получения желаемого вида сцены часто применяется трехмерное видовое преобразование. Матрицы тел для объектов преобразованной сцены можно получить или преобразованием исходных матриц тел или вычислением новых матриц тел, используя преобразованные вершины или точки.
Если [В] - матрица однородных координат, представляющая исходные вершины тела, а [Т] - матрица размером 4х4 видового преобразования, то преобразованные вершины таковы:
[ВТ] = [В][T] (3.6)
где [ВТ] - преобразованная матрица вершин. Использование уравнения (3.2) позволяет получить уравнения исходных плоскостей, ограничивающих тело:
[В][V] = [D] (3.7)
где [V] - матрица тела, а [D] в правой части - нулевая матрица. Аналогично уравнения преобразованных плоскостей задаются следующим образом:
[ВТ][VТ] = [D] (3.8)
где [VТ] - преобразованная матрица тела. Приравнивая левые части уравнения (3.7) и (3.8), получаем
[ВТ][VT] = [В][V]
Подставляя уравнение (3.6), сокращая на [В] и умножая слева на
[T]-1 имеем
[VT] = [T]-1[V]
Итак, преобразованная матрица тела получается умножением исходной матрицы тела слева на обратную матрицу видового преобразования.
Похожие работы
... Разновидности компьютерной графики Двумерная графика Двумерная компьютерная графика классифицируется по типу представления графической информации, и следующими из него алгоритмами обработки изображений. Обычно, компьютерную графику разделяют на: · векторную · растровую, · фрактальную Они отличаются принципами формирования изображения при отображении на экране монитора или при печати на ...
... в качестве реальной альтернативы системе Unix. _ 23.Платформа Intel ПК с процессором Intel продолжает оставаться наиболее распространённой платформой в сфере компьютерной графики и анимации. Главным событием, имеющим к ней непосредственное отноше- ние, стала демонстрация компанией Autodesk четвёртой версии программы 3D Studio - ...
... простыми. Большинство цветовых оттенков образуется смешением основных цветов. Способ разделения цветового оттенка на составляющие компоненты называется цветовой моделью. Существует много различных типов цветовых моделей, но в компьютерной графике, как правило, применяется не более трех. Эти модели известны под названиями: RGB, CMYK, НSB. Цветовая модель RGB Наиболее проста для понимания и ...
... прочие). В соответствии с принципами формирования изображения аддитивным или субтрактивным методами разработаны способы разделения цветового оттенка на составляющие компоненты, называемые цветовыми моделями. В компьютерной графике в основном применяют модели RGB и HSB (для создания и обработки аддитивных изображений) и CMYK (для печати копии изображения на полиграфическом оборудовании). Цветовые ...
0 комментариев