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

Л.Г.Робертс был аспирантом Линкольновской лаборатории МИТ, работал по теме «Техническое зрение роботов». Опубликовал описание алгоритма в 1963-1964 гг. в изданиях МИТ.

Этот алгоритм позволяет определить, какие рёбра или части рёбер объектов сцены видимы, а какие заслонены гранями других объектов. Он работает в объектном пространстве и использует проекции объектов на картинную плоскость для анализа видимости.

Чтобы алгоритм Робертса работал корректно, необходимо выполнение следующих предварительных условий:

1. Тело ограничено плоскостями.
2. Тело выпукло.
3. Нормали всех граней направлены внутрь тела.

Основные Формулы

Уравнение произвольной плоскости в трёхмерном пространстве имеет вид:

Если точка S(xs, ys, zs) лежит на плоскости, то:

Если точка S не лежит на плоскости, знак выражения показывает, с какой стороны от плоскости находится точка. Предполагается, что точки, лежащие внутри тела, дают положительное значение выражения.

Нахождение Вектора Нормали

Пусть F1, F2, ..., Fn - грани многогранника. Для одной из граней, имеющей вершины V1, V2, ..., Vk, вектор нормали вычисляется через векторное произведение двух смежных рёбер V1V2 = [x1, y1, z1] и V2V3 = [x2, y2, z2]:

            ni = [V1V2, V2V3] = |i   j   k |
                                |x1  y1  z1|
                                |x2  y2  z2| =
            = (y1 * z2 - y2 * z1)i + (z1 * x2 - z2 * x1)j + (x1 * y2 - x2y1)k
 

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

Значение D вычисляется с помощью точки на плоскости (x1, y1, z1):

Так как многогранник выпуклый, коэффициенты Ai, Bi, Ci выбираются так, чтобы ni(Ai, Bi, Ci) был внешней нормалью. Например, можно использовать барицентр многогранника:

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

Алгоритм

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
    грань невидима
 

Оптимизация и Производительность

Количество сравнений ребра с гранью зависит от количества исходных граней N. Количество рёбер составляет O(N), и каждое ребро необходимо сравнить с каждой гранью, что даёт O(N^2) сравнений. В худшем случае, если каждое ребро разделяется на N частей, количество сравнений может достигать O(N^3).

Производительность можно повысить, запоминая невидимые интервалы ребра в отдельном массиве. После сравнения со всеми гранями границы интервалов сортируются, и выделяются видимые части ребра. Сортировка границ потребует O(N·logN) времени, что приводит к общему времени O(N^2·logN).

Использование Иерархии Оболочек

Производительность алгоритма можно улучшить, используя когерентность в пространстве. Объекты сцены, такие как здания, машины и люди, обычно состоят из множества граней, расположенных рядом. Вокруг таких объектов можно описать простые геометрические тела – оболочки, например, прямоугольники на экране. Сначала сравниваются оболочки объектов: если они не пересекаются, грани одного объекта не могут заслонять рёбра другого.

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

Пример на JavaScript

Ниже приведён пример реализации алгоритма Робертса на JavaScript, иллюстрирующий проверку видимости граней куба относительно точки наблюдения:

const vertices = [
    {x: 1, y: 1, z: 1},
    {x: -1, y: 1, z: 1},
    {x: -1, y: -1, z: 1},
    {x: 1, y: -1, z: 1},
    {x: 1, y: 1, z: -1},
    {x: -1, y: 1, z: -1},
    {x: -1, y: -1, z: -1},
    {x: 1, y: -1, z: -1}
];
 
const faces = [
    [0, 1, 2, 3],
    [4, 5, 6, 7],
    [0, 4, 7, 3],
    [1, 5, 6, 2],
    [0, 1, 5, 4],
    [3, 2, 6, 7]
];
 
function vectorSubtraction(v1, v2) {
    return {x: v1.x - v2.x, y: v1.y - v2.y, z: v1.z - v2.z};
}
 
function vectorCrossProduct(v1, v2) {
    return {
        x: v1.y * v2.z - v1.z * v2.y,
        y: v1.z * v2.x - v1.x * v2.z,
        z: v1.x * v2.y - v1.y * v2.x
    };
}
 
function vectorDotProduct(v1, v2) {
    return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
}
 
function isFaceVisible(face, observer) {
    const vec1 = vectorSubtraction(vertices[face[1]], vertices[face[0]]);
    const vec2 = vectorSubtraction(vertices[face[2]], vertices[face[1]]);
    const normal = vectorCrossProduct(vec1, vec2);
 
    const D = -vectorDotProduct(normal, vertices[face[0]]);
    const sign = -Math.sign(vectorDotProduct(normal, {x: 0, y: 0, z: 0}) + D);
 
    normal.x *= sign;
    normal.y *= sign;
    normal.z *= sign;
 
    return vectorDotProduct(normal, observer) + D > 0;
}
 
const observer = {x: 0, y: 0, z: 5};
faces.forEach(face => {
    if (isFaceVisible(face, observer)) {
        console.log(`Face ${face} is visible.`);
    } else {
        console.log(`Face ${face} is not visible.`);
    }
});
 

Этот пример иллюстрирует базовую проверку видимости граней куба относительно точки наблюдения, находящейся в координате {x: 0, y: 0, z: 5}.