Работа Алгоритм Робертса проходит в два этапа:
1. Определение нелицевых граней для каждого тела отдельно.
2. Определение и удаление невидимых ребер.
Пусть F — некоторая грань многогранника. Плоскость, несущая эту грань, разделяет пространство на два подпространства. Назовем положительным то из них, в которое смотрит внешняя нормаль к грани. Если точка наблюдения – в положительном подпространстве, то грань – лицевая, в противном случае – нелицевая. Если многогранник выпуклый, то удаление всех нелицевых граней полностью решает задачу визуализации с удалением невидимых граней.
Для определения, лежит ли точка в положительном подпространстве, используют проверку знака скалярного произведения (l, n), где l – вектор, направленный к наблюдателю, фактически определяет точку наблюдения; n – вектор внешней нормали грани. Если (l, n) > 0, т. е. угол между векторами острый, то грань является лицевой. Если (l, n) < 0, т. е. угол между векторами тупой, то грань является нелицевой.
Алгоритма Робертса. Получение и проверка матрицы тела. Построение матрицы тела по трем точкам.
Уравнение произвольной плоскости в трехмерном пространстве имеет вид
| aх + by + cz + d = 0 | (17.1.) |
В матричной форме этот результат выглядит так: [ x y z 1][ P ] T = 0, где [ P ] T = [ a b c d ] представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е. [ V ] = 
,где каждый столбец содержит коэффициенты одной плоскости.
Шесть плоскостей, описывающих данный куб, таковы: x 1 = 1/2,
x 2 = -1/2, y 3 = 1/2, y 4 = -1/2, z 5 = 1/2, z 6 = -1/2. Более подробно уравнение правой плоскости можно записать как x 1 + 0× y 1+ 0× z 1- (1/2) = 0 или 2 x 1 - 1 = 0
Полная матрица тела такова:
[ V ]= 
= 
.
ПРОВЕРКА МАТРИЦЫ
Экспериментально проверим матрицу тела с помощью точки, о которой точно известно, что она лежит внутри тела. Если знак скалярного произведения для какой-нибудь плоскости больше нуля, то соответствующее уравнение плоскости следует умножить на -1. Для проверки возьмем точку внутри куба с координатами x = 1/4, y = 1/4, z = 1/4. В однородных координатах эта точка представляется в виде вектора
[ S ] = [1/4 1/4 1/4 1] = [1 1 1 4]. Скалярное произведение этого вектора на матрицу объема равно
[ S ]×[ V ] = [1 1 1 4] × 
= [-2 6 -2 6 -2 6].
Здесь результаты для второго, четвертого и шестого уравнения плоскостей (столбцов) положительны и, следовательно, составлены некорректно. Умножая эти уравнения (столбцы) на -1, получаем корректную матрицу тела для куба:
[ V ] = 
.
ПОСТРОЕНИЕ ПО 3М ТОЧКМ
Хотя уравнение плоскости содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы d = 1. Следовательно, трех неколлинеарных точек достаточно для определения этих коэффициентов. Подстановка координат трех неколлинеарных точек (x 1, y 1, z 1), (x 2, y 2, z 2), (х 3, у 3, z 3) в нормированное уравнение (17.1.) дает
ax 1 + by 1 + cz 1 = -1;
ax 2 + by 2 + cz 3 = -1;
ax 3 + by 2 + cz 3 = -1.
В матричной форме это выглядит так:
| или [X][C] = [D] | (17.2.) |
Решение этого уравнения дает значения коэффициентов уравнения плоскости: [C] = [X]-1[D]. Другой способ используется, если известен вектор нормали к плоскости, т. е.
n = a i + b j + c k, где i, j, k – единичные векторы осей х, у, z соответственно. Тогда уравнение плоскости примет вид ax + by + cz + d = 0
Величина d вычисляется с помощью произвольной точки на плоскости. В частности, если компоненты этой точки на плоскости (х 1, у 1, z 1), то d = -(ax 1 + by 1 + cz 1)