27. Алгоритм Робертса. Формирование матрицы тела. Удаление нелицевых граней. - p1xelse/CG GitHub Wiki

Этап 0. Подготовка исходных данных.

Формирование матрицы тела

Для каждого тела сцены должны быть сформирована матрица тела. Пусть V - матрица тела, которая имеет размерность 4*n где n – кол во граней.

Каждый столбец матрицы представляет собой 4 коэффициента уравнения плоскости, проходящей через очередную грань тела.

Общий вид уравнения плоскости: ax + by + cz + d = 0

Сначала нужно найти коэффициенты уравнений каждой плоскости, проходящий через каждую грань тела. Поскольку 4 неизвестных, то вроде бы нужно знать координаты 4 точек расположенных в одной плоскости, но мы знаем, что однозначно плоскость задается тремя точками не лежащих на одной прямой, значит можно это уравнение нормировать. Поделив на d отличный от нуля. Получим 3 неизвестных, а свободный член будет равен единице. a’x+b’y+c’z+1=0

PS: Про то как находить значения коэффициентов Куров не рассказывал, но в Роджерсе и у ребят со старших курсов это есть:

Или можно через определитель получить уравнение плоскости:

Матрица тела должна быть сформирована корректно, то есть любая точка, расположенная внутри тела, должна располагаться по положительную сторону от каждой грани тела. Если для очередной грани это условие не выполняется, то соответствующий столбец матрицы надо умножить на -1.

Для проверки корректности матрицы тела следует взять точку, расположенную внутри тела. Координаты такой точки можно получить усреднением координат всех вершин тела или взяв полусумму максимальной и минимальной координат. S – вектор координат точки. Находим произведение вектора S на матрицу тела. В полученном векторе надо найти отрицательные элементы, они соответствуют некорректно сформированным уравнениям плоскостей. Соответствующий столбец надо умножить на -1.

Удобно использовать прямоугольный параллелепипед, у которого каждая грань отсекает +1 или -1 на соответствующей оси. х = -1, х = 1, у = -1, у = 1, z = -1, z = 1

Координаты однородной точки расположенный в начале системы = (0, 0, 0, 1).

Результат умножения вектора S на матрицу тела будет совпадать с последней строкой матрицы.Видим, что 2, 4, 6 столбцы сформированы некорректно, значит их надо умножить на -1.

Для получения матрицы преобразованного тела надо матрицу исходного тела слева умножить на обратную матрицу преобразования.

Если спросит вот вывод всего этого дела:

Этап 1. Удаление ребер, экранируемых самим телом (Удаление нелицевых граней тела).

Должны понимать, что нелицевые ребра расположены в нелицевых гранях тела или по другому говорят, что нелицевые ребра образуется пересечением невидимых нелицевых граней тела.
Для решения задачи надо указать расположение наблюдателя и направление его взгляда.

Наблюдатель располагается в +бесконечности на оси Z и смотрит в сторону начала координат.

E = (0, 0, -1, 0) = вектор взгляда наблюдателя.

С одной стороны, E - вектор взгляда наблюдателя, с другой стороны - это вектор однородных координат точки, расположенной в -бесконечности по оси Z.

Для определения невидимых граней следует вектор Е умножить на матрицу тела V. Отрицательные компоненты полученного вектора будут соответствовать невидимым граням.
Невидимые ребра образуются пересечением невидимых граней.

Итоги этапа:

1. Если тело в сцене одно, то решив задачу поставленную на этом этапе мы решим и всю задачу целиком. Работа алгоритма закончится.
2. Решенную задачу можно интерпретировать и по-другому, чтобы определить видимые или невидимые грани достаточно найти скалярное произведение вектора взгляда на вектор внутренней нормали грани. Этот подход используется для построения реалистичных изображений, то есть когда мы должны закрашивать грани тел, поверхностей, в данном случаем многогранников.