4.3. Алгоритм Робертса

Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм прежде всего удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет теоретически как квадрат числа объектов.

В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые части. В этом алгоритме выпуклое многогранное тело с плоскими гранями должно представляться набором пересекающихся плоскостей. Уравнение произвольной плоскости в трехмерном пространстве имеет вид

aх + by + cz + d = 0

Если любая точка S(x_s, y_s, z_s) лежит на плоскости, то ax_s + by_s + cz_s + d = 0. Если же S не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают положительное скалярное произведение.

Пусть F₁, F₂, ..., F_n - грани многогранника. Рассмотрим одну из граней. Обозначим вершины, инцидентные грани, через V1, V2, ..., Vk. Найдем вектор нормали к грани, вычислив векторное произведение любых двух смежных ребер этой грани V₁V₂ = [x₁,y₁,z₁] и V₂V₃ = [x₂,y₂,z₂]:

 

ni = [V1V2,V2V3] =

i     j    k x1  y1  z1 x2  y2  z2

= (y1z2 - y2z1)·i + (z1x2 - z2x1)·j + (x1y2 - x2y1)·k = Ai·i + Bi·j + Ci·k

Тогда опорная функция грани имеет вид:

L_i(x,y,z) = A_iх + B_iy + C_iz + D

Величина D вычисляется с помощью произвольной точки на плоскости. В частности, если компоненты этой точки на плоскости (х₁,y₁,z₁), то:

D = -(ах₁ + by₁ + cz₁)

Так как многогранник выпуклый, коэффициенты A_i, B_i, C_i легко выбрать так, чтобы n_i(A_i, B_i, C_i) был вектором внешней нормали. Для этого найдем какую-либо внутреннюю точку, например, барицентр многогранника:

W = (V₁ + V₂ + ... + V_k)/k

Если скалярное произведение уравнения плоскости и этой точки меньше 0, то необходимо поменять знак уравнения этой плоскости, чтобы отразить правильное направление внешней нормали. Остается только вычислить скалярное произведение уравнения плоскости на точку, в которой находится наблюдатель. Если это скалярное произведение меньше 0, то плоскость невидима и необходимо удалить весь многоугольник, лежащий в этой плоскости. Запись этого алгоритма на псеводокоде приводится ниже.

Алгоритм Робертса
V1, V2, V3 - вершины многогранника
W - барицентр многогранника
P - точка наблюдения

 

	выделим одну из граней многогранника
	Vec1.X = V1.X - V2.X; Vec2.X = V3.X - V2.X; Vec1.Y = V1.Y - V2.Y; Vec2.Y = V3.Y - V2.Y; Vec1.Z = V1.Z - V2.Z; Vec2.Z = V3.Z - V2.Z;	/ для этой грани найдем координаты двух векторов, которые лежат в плоскости грани
	A = Vec1.Y·Vec2.Z - Vec2.Y·Vec1.Z; B = Vec1.Z·Vec2.X - Vec2.Z·Vec1.X; C = Vec1.X·Vec2.Y - Vec2.X·Vec1.Y; D = -(A·V1.X + B·V1.Y + C·V1.Z);	/ вычислим коэффициенты уравнения плоскости
	m = -Sign(A·W.X + B·W.Y + C·W.Z + D);	/ коэффициент, изменяющий знак плоскости
	A = A·m; B = B·m; C = C·m; D = D·m;	/ корректируем направление плоскости
	if A·P.X + B·P.Y + C·P.Z + D > 0 then грань видима; отобразить грань else грань невидима

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

Для каждого тела из приоритетного списка:

1. Проверить экранирование всех лицевых ребер всеми другими телами сцены. Тело, ребра которого проверяются, называется пробным объектом, а тело, относительно которого в настоящий момент производится проверка, называется пробным телом. Естественно, что нужно проверять экранирование пробного объекта только теми пробными телами, у которых ниже приоритеты.
2. Провести проверки экранирования для прямоугольных объемлющих оболочек пробного объекта и пробного тела.
3. Провести предварительные проверки протыкания, чтобы увидеть, не протыкается ли пробное тело пробным объектом и существует ли возможность частичного экранирования первого последним.