Сравнения объектов начинаются с корня. Если сравнение не дает положительного ответа, то все тела можно сразу отбросить. В противном случае проверяются все его прямые потомки, и если какой-либо из них не дает положительного ответа, то все объекты, содержащиеся в нем, сразу же отбрасываются. При этом уже на ранней стадии проверок отсечение основного количества объектов происходит достаточно быстро, ценой всего лишь нескольких проверок.
Иерархические структуры можно строить и на основе разбиения пространства (картинной плоскости): каждая клетка исходного разбиения разбивается на части (которые, в свою очередь, также могут быть разбиты, и т. д. При этом каждая клетка разбиения соответствует узлу дерева).
Иерархии (как и разбиение пространства) позволяют достаточно легко и просто производить частичное упорядочение граней. В результате получается список граней, практически полностью упорядоченный, что дает возможность применить специальные методы сортировки.
Помимо упорядочения граней иерархические структуры позволяют производить быстрое и эффективное отсечение граней, не удовлетворяющих каким-либо из поставленных условий.
10.3. Удаление невидимых линий.
10.3.1. Алгоритм Робертса Первым алгоритмом удаления невидимых линий был алгоритм Робертса, требующий, чтобы каждая грань была выпуклым многоугольником. Опишем этот алгоритм.
Сначала отбрасываются все ребра, обе определяющие грани которых являются нелицевыми (ни одно из таких ребер заведомо не видно).
Следующим шагом является проверка на закрывание каждого из оставшихся ребер со всеми лицевыми гранями многогранника. Возможны следующие случаи: грань ребра не закрывает (рис. 10.18);
10. Удаление невидимых линий и поверхностей
грань полностью закрывает ребро (тогда оно удаляется из списка рассматриваемых ребер ) (рис. 10.19, а);
грань частично закрывает ребро (в этом случае ребро разбивается на несколько частей, видимыми из которых являются не более двух; само ребро удаляется из списка, но в список проверенных ребер добавляются те его части, которые данной гранью не закрываются).