28. Алгоритм Робертса. Удаление отрезков, экранируемых другими телами.

Тело, рёбра которого проверяются – пробный объект, с которым проверяются – пробное тело.

• Отсортировать все тела по максимальному 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), и вычисляют отрезки, которые образуются при протыкании объектами друг друга. Эти отрезки проверяют на экранирование всеми прочими объектами сцены. Видимые отрезки образуют структуру протыкания.

Таким образом, алгоритм подразделяется на следующие этапы.

1. Определение коэффициентов уравнения плоскости каждой грани, проверка правильности знака уравнения и формирование матрицы объекта визуализации.
2. Проведение видового преобразования матрицы объекта, вычисление прямоугольной охватывающей оболочки объекта.
3. Определение нелицевых граней, удаление их из списка граней и соответствующих ребер - из списка ребер.
4. Определение списка других объектов синтезируемой сцены, которые могут быть экранированы данным объектам визуализации на основании сравнений охватывающих оболочек объектов.
5. Формирование списка протыканий на основании сравнений охватывающих оболочек объектов.
6. Определение невидимых отрезков или участков отрезков.
7. Формирование списка возможных отрезков, соединяющих точки протыкания, для пар объектов, связанных отношением протыкания.
8. Проверка видимости полученных отрезков по отношению ко всем объектам сцены в соответствии с этапами 3 и 6.
9. Визуализация изображения.