Алгоритм Робертса. Это алгоритм типичный пример решения задачи в лоб, методом грубой силы

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

· Грань не закрывает ребро (либо их проекции не пересекаются, либо ребро находится ближе чем грань);

· Грань полностью закрывает ребро – ребро удаляется из списка видимых ребер;

· Грань частично закрывает ребро (либо ребро лежит под гранью, но не полностью, либо пересекает ее) – ребро разбивается на несколько частей, и они заносятся вместо него в список ребер;

Такой алгоритм требует O(N²) времени. Его можно немного ускорить, если описать вокруг граней некоторые ограничивающие тела (обычно это либо параллелепипеды (в картинной плоскости– прямоугольники), с ребрами параллельными осям координат, AABB (Axis Aligned Bounding Box), либо сферы (в картинной плоскости – окружности)). Тогда достаточно сначала проверить пересечение этих тел, и только если они пересекаются, проверять пересечение ребра с гранью. Можно ограничивать не только отдельные ребра или грани, но и их группы (например, объекты), и проверять сначала пересечение тел для групп, и только если они пересекаются – для отдельных объектов. Таким образом, можно построить целую иерархию ограничивающих тел.