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

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

Трёхмерное отсечение многоугольника Отсечение выпуклой многогранной областью Выпуклый многогранник = пересечение полупространств, образованных гранями многогранной области Алгоритм Сазерленда-Ходгмана { 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;

Алгоритм плавающего горизонта Удаление невидимых линий трёхмерного представления функции, описывающих поверхность в виде 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), иначе – не видима. Добавляется «нижний» горизонт

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

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

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

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