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

Наиболее известные алгоритмы

Алгоритм является исторически первым. Он требует, чтобы грани были выпуклыми многоугольниками. Алгоритм переборного типа, работает с ребрами, т.е. больше подходит для каркасных изображений. Ребра, смыкающие 2 невидимые грани, не рассматриваются, т.к. они заведомо невидимы. Каждое оставшееся ребро каждого объекта анализируется на взаимоположение со всеми гранями каждого объекта. Возможны случаи:

· грань не закрывает ребро;

· грань полностью или частично закрывает ребро;

· грань и ребро пересекаются.

Первый случай наблюдается в 2 вариантах:

· ребро находится в том же полупространстве относительно грани, что и наблюдатель - рис а);

· ребро полностью расположено в полупространстве, не содержащем наблюдателя, но проекции грани и ребра не пересекаются и проекция ребра не содержится в проекции грани ( не лежит внутри) - рис. б).

а) б) в) г) д)

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

В третьем случае ребро пересекается с плоскостью, содержащей грань - рис. д). Аналогично второму случаю ребро разбивается на части, из которых видимы не более 2, далее рассматриваем только видимые подребра. Разбиение делается на 2 части по точке пересечения, рассматриваем отдельно обе части, т.е. сводим к предыдущим случаям.

Если плоскость, несущая грань, и ребро пересекаются, ребро разбивается на две части по точке пересечения, каждая часть ребра рассматривается отдельно.

Временные затраты алгоритма пропорциональны квадрату числа граней всех объектов.