Различные проекции объектов, представленные в форме октодерева, можно получить, применив к представлению в форме октодерева преобразования, меняющие ориентацию объекта согласно выбранной проекции. Октанты можно затем перенумеровать так, чтобы представление в форме октодерева всегда имело на передней грани октанты 0, 1, 2 и 3.
Рис. 9.25. Этапы деления октантов области пространства и плоскость соответствующего квадранта
МЕТОД РАСЧЕТА ЛУЧА
Если рассмотреть луч, идущий от положения пикселя на плоскости наблюдения через сцену, как показано на рис. 9.26, можно определить, какие объекты на сцене (если такие есть) пересекают этот луч. После расчета всех точек пересечения луча с поверхностью видимой считается поверхность, точка пересечения с которой является ближайшей к пикселю. В данной схеме исследования видимых поверхностей используются процедуры расчета луча (ray casting), представленные в разделе 8.20. Расчет луча как средство исследования видимых поверхностей основан на методах геометрической оптики, позволяющих отследить пути лучей света. Поскольку на сцене имеется бесконечное число лучей света, а нас интересуют только те лучи, которые проходят через положения пикселей, можно отследить ход лучей света в обратном порядке - от пикселей на сцену. Отметим, что метод расчета лучей при анализе видимых поверхностей эффективен для сцен с криволинейными поверхностями, особенно сферами.
Рис. 9.26. Луч вдоль линии наблюдения от пикселя сквозь сцену
Расчет луча можно рассматривать как разновидность метода буфера глубины (раздел 9.3). В алгоритме буфера глубины поверхности обрабатываются по одной, и для всех спроектированных точек поверхности вычисляются значения глубины. Затем рассчитанные глубины поверхностей сравниваются с ранее записанными глубинами, чтобы для каждого пикселя определить видимую поверхность. В методе расчета лучей по одному обрабатываются пиксели, и для всех поверхностей, проектирующихся в этот пиксель, вычисляются глубины.
Расчет луча является частным случаем алгоритма построения хода луча (ray-tracing) (раздел 10.11), прокладывающим несколько путей луча, чтобы учесть глобальные вклады в отражение и преломление от нескольких объектов сцены. При расчете же луча луч прослеживается только от каждого пикселя до ближайшего объекта. В настоящее время разработаны эффективные формулы расчета точки пересечения луча с поверхностью распространенных объектов, например, сфер; подробно данные методы рассмотрены в разделе 10.11.
СРАВНЕНИЕ МЕТОДОВ ИССЛЕДОВАНИЯ ВИДИМЫХ ПОВЕРХНОСТЕЙ
Эффективность метода исследования видимых поверхностей зависит от характеристик конкретного приложения. Если поверхности на сцене значительно распределены вдоль направления наблюдения, и существует крайне незначительное перекрытие по глубине, часто эффективнее использовать методы сортировки по глубине или В8Р-дерева. Если проекции поверхностей на плоскость наблюдения немного перекрываются, видимые поверхности проще локализовать с использованием строк развертки или деления области.
Исходя из сказанного, можно сформулировать общее правило: если сцена содержит малое число поверхностей, крайне эффективным подходом является алгоритм сортировки по глубине или метод ВБР-дерева. Это объясняется тем, что подобные сцены обычно содержат мало поверхностей, перекрывающихся по глубине. Когда сцена содержит малое число поверхностей, хорошие результаты также дает метод строк развертки. Чтобы эффективно определить видимые поверхности для сцен, содержащих до нескольких тысяч многоугольных поверхностей, можно использовать метод строк развертки, сортировки по глубине или метод В8Р-дерева. Для сцен, содержащих более нескольких тысяч поверхностей, лучшим является метод буфера глубины или восьмеричного дерева. Для метода буфера глубины характерно почти постоянное время обработки, независимо от числа поверхностей на сцене. Это так, потому что размер областей поверхности уменьшается при увеличении числа поверхностей на сцене. Следовательно, метод буфера глубины имеет относительно невысокую производительность на простых сценах и сравнительно большую - на сложных сценах. ВБР-деревья полезны, когда соответствующие проекции требуется рассчитать для нескольких точек наблюдения. Если сцена содержит криволинейные поверхности, то, чтобы определить видимые части сцены, можно использовать метод октодерева или расчета лучей.