Алгоритмы трёхмерной графики Алгоритмы трёхмерного отсечения, алгоритм плавающего горизонта. - презентация

1 Алгоритмы трёхмерной графики Алгоритмы трёхмерного отсечения, алгоритм плавающего горизонта

2 Трёхмерное отсечение многоугольника Отсечение прямоугольным параллелепипедом Отсечение усечённой пирамидой Побитовое представление расположение точки

3 Трёхмерное отсечение многоугольника Отсечение выпуклой многогранной областью Выпуклый многогранник = пересечение полупространств, образованных гранями многогранной области Алгоритм Сазерленда-Ходгмана { p[1..n]– многоугольник, sp – полупространство, inp(p,sp)– лежит ли точка p в полупространстве sp, add – добавление вершины в новый многоугольник} p[0]:=p[n]; ci := inp(p[n],sp); for i:=1 to n do begin nci := inp(p[i],sp); if nci ci then begin newp:=intersect(p[i-1],p[i],sp); add(newp); end; if nci then add(p[i]); ci := nci; end;

4 Алгоритм плавающего горизонта Удаление невидимых линий трёхмерного представления функции, описывающих поверхность в виде F(x, y, z) = 0 Изображение поверхности сводится к изображению последовательности секущих при постоянных значениях z. F(x, y, z) = 0 приводится к виду y=f(x,z) или x=g(y,z) Удаление невидимой линии: Если для текущего значения z, при некотором x значение y больше значений y для всех предыдущих кривых при том же x, то текущая кривая видима в точке (x, y), иначе – не видима. Добавляется «нижний» горизонт

5 Алгоритм плавающего горизонта Плавающий горизонт – два массива (по значениям x), задающих минимальное и максимальное значения y при различных z. Зазубренные боковые рёбра. Чтобы их избежать, добавляют мнимые боковые рёбра

6 Алгоритм Робертса На входе – n тел. Требуется отрисовать их с удалением невидимых линий 1.Определение нелицевых граней для каждого тела. Из каждого тела удаляются те рёбра и грани, которые экранируются самим телом. 2.Определение и удаление невидимых рёбер. Каждое из видимых рёбер каждого тела сравнивается с каждым из оставшихся тел для выделения видимой части. Сложность алгоритма растёт как квадрат от количества тел. Работает в объектном пространстве. Требуется, чтобы все тела были выпуклы. Тело представляется набором плоскостей – своих граней.

7 Алгоритм Робертса Грани задаются коэффициентами уравнения a x + b y + c z + d = 0. Всё тело – матрицей размера 4 x n.

8 Алгоритм Кэтмула Работает в пространстве изображения. Использует z-буфер.