17.2.2. ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ РАЗДЕЛЕНИЯ ВИДИМЫХ И НЕВИДИМЫХ ЭЛЕМЕНТОВ СЦЕНЫ

Определения 17.1 и 17.2 предусматривают проверку всех пар граней при выявлении тех, которые загораживают другие грани. Это нереально при работе с изображениями, содержащими тысячи подобных граней, но осуществимо, если речь идет о гранях отдельного объекта. Действительно, пусть сцена содержит к объектов и число поверхностей объекта равно . В таком случае сложность полного упорядочения пропорциональна величине

а сложность процедуры сравнения поверхностей лишь одного объекта пропорциональна величине

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

а) Рассматриваются многоугольники, являющиеся проекциями граней, и с помощью какого-либо алгоритма разрезания выявляются все пересекающиеся пары многоугольников (в том числе такие пары многоугольников, в которых один полностью покрывается другим). Затем с помощью утверждения 16.1 устанавливается, какой из многоугольников пары загораживает другой многоугольник. Вместо проверки непосредственно пар можно рассматривать их пере сечение с окнами, задаваемыми правильными многоугольниками. Два многоугольника могут загораживать друг друга лишь в том случае, если они пересекаются с одним и тем же окном. Этот метод положен в основу алгоритма 17.1.

б) Рассматривается пересечение всех граней с некоторой гори зонтальной плоскостью и для полученных в результате отрезков прямых решается задача разделения видимых и невидимых элементов. Этот метод реализован в алгоритме 17.2.