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

Это математически элегантный алгоритм.

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

Трудоемкость — .

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

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

.

В матричной форме: , или

— представляет собой плоскость.

Поэтому любое выпуклое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей:

.

Каждый столбец содержит коэффициенты одной плоскости. Любая точка пространства в однородных координатах:

.

Если точка S лежит на плоскости, то

.

Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка. Если точка внутри тела — знак «+», если вне — «–».

Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка (точка внутри тела — знак «+», точка вне тела — знак «–»).