Алгоритм Робертса. Основные этапы и математические предпосылки.
Алгоритм удаления невидимых линий в объектном пространстве. Работает только с выпуклыми телами. Сортировка тел по мере их удалённости от наблюдателя. Сложность ~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), и вычисляют отрезки, которые образуются при протыкании объектами друг друга. Эти отрезки проверяют на экранирование всеми прочими объектами сцены. Видимые отрезки образуют структуру протыкания.
Таким образом, алгоритм подразделяется на следующие этапы.
- Определение коэффициентов уравнения плоскости каждой грани, проверка правильности знака уравнения и формирование матрицы объекта визуализации.
- Проведение видового преобразования матрицы объекта, вычисление прямоугольной охватывающей оболочки объекта.
- Определение нелицевых граней, удаление их из списка граней и соответствующих ребер - из списка ребер.
- Определение списка других объектов синтезируемой сцены, которые могут быть экранированы данным объектам визуализации на основании сравнений охватывающих оболочек объектов.
- Формирование списка протыканий на основании сравнений охватывающих оболочек объектов.
- Определение невидимых отрезков или участков отрезков.
- Формирование списка возможных отрезков, соединяющих точки протыкания, для пар объектов, связанных отношением протыкания.
- Проверка видимости полученных отрезков по отношению ко всем объектам сцены в соответствии с этапами 3 и 6.
- Визуализация изображения.
Дата добавления: 2019-01-14; просмотров: 491; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!