Алгоритм Робертса. Основные этапы и математические предпосылки.
Алгоритм удаления невидимых линий в объектном пространстве. Работает только с выпуклыми телами. Сортировка тел по мере их удалённости от наблюдателя. Сложность ~N2
Основные этапы
- Подготовка исходных данных
- Удаление линий, экранируемых самим телом
- Удаление линий, экранируемых другими телами
- Удаление линий пересечения тел, экранируемых самими телами, связанными отношением протыкания и другими телами
Формирование матрицы Уравнение произвольной плоскости в трехмерном пространстве имеет вид aх + by + cz + d = 0. В матричной форме [x y z 1][P]T = 0, где [P]T = [a b c d] представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е. 
Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают отрицательное скалярное произведение, т. е. нормали направлены наружу. 
Алгоритм Робертса. Формирование матрицы тела. Удаление нелицевых граней.
Алгоритм Робертса. Удаление отрезков, экранируемых другими телами.
Тело, рёбра которого проверяются – пробный объект, с которым проверяются – пробное тело.
- Отсортировать все тела по максимальному z тела. Наиболее удалённое тело – более экранируемое.
Zminр>Zmaxт – тело не может загораживать ребро. (Xmaxр<Xminт) v (Xminр>Xmaxт) v (Ymaxр<Yminт) v (Yminр>Ymaxт) – тело экранировать ребро не будет.
|
|
|
Удаление экранируемых участков отрезка
P1P2 – исследуемый отрезок. P(t)=P1+(P2-P1)t – параметрическое уравнение. 𝑣 = 𝑠 + 𝑡 𝑑. Нужно найти t, при котором изменяется видимость отрезка. Параметрически зададим отрезок от точки 𝑣 до 𝑔 – точки, где находится наблюдатель: 𝑄(𝛼, 𝑡) = 𝑣 + 𝛼𝑔, 0 ≤ 𝛼. Наблюдатель в +∞, а не -∞. g=[0,0,1,0]. 𝑄(𝛼, 𝑡) = 𝑠 + 𝑡 𝑑 + 𝛼𝑔 – фактически уравнение плоскости.
Скалярное произведение любой точки, расположенной внутри объекта и матрицы объекта, положительно (это утверждение справедливо и для преобразованной матрицы объекта). Точка, находящаяся внутри объекта, невидима. Следовательно, для проверки на экранирование вектор текущей точки отрезка умножают поочередно на матрицу каждого объекта и определяют положительное решение, соответствующее прохождению отрезка внутри объекта: 𝐻=(𝑠+𝑡𝑑+ 𝛼𝑔) 𝑉 > 0.
После определения частично видимых или полностью невидимых отрезков определяют пары объектов, связанных отношением протыкания (в случае протыкания объектов сцены ищутся решения на границе 𝛼 = 0), и вычисляют отрезки, которые образуются при протыкании объектами друг друга. Эти отрезки проверяют на экранирование всеми прочими объектами сцены. Видимые отрезки образуют структуру протыкания.
|
|
|
Таким образом, алгоритм подразделяется на следующие этапы.
Дата добавления: 2019-01-14; просмотров: 481; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!