Удаление невидимых поверхностей
Получившийся алгоритм реализует следующий фрагмент псевдокода:
def renderScene ( viewFrrustrum, activeCell ): for wall in activeCell.walls:
if wall.intersect ( viewingFrustrum ):
clippedWall = clipPolygon ( wall, viewFrustrum ) drawPolygon ( clippedWall )
for portal in activeCell.portals:
if portal.intersect ( viewingFrustrum ):
clippedPortal = clipPolygon ( portal, viewFrustrum ) renderScene ( viewFrustrum,
portal.adjacentCell ( activeCell ) )Так как в большинстве случаев все многоугольники являются выпуклыми, то в результате требуется процедура отсечения одного выпуклого многоугольника по другому выпуклому многоугольнику.
В классическом методе порталов вся сцена разбивается на набор выпуклых комнат - при этом все лицевые грани, видимые через портал, не могут закрывать собой другие лицевые грани в пределах той же комнаты. Тем самым в этом случае задача определения видимости полностью решена, более того, затраты на рендеринг сцены прямо пропорциональны количеству реально видимых граней, в отличие от других методов.
Разбиение сцены на набор выпуклых комнат может производиться при помощи листового BSP-дерева. Используя это же BSP-дерево, можно также построить и порталы для каждой из получающихся комнат. Рассмотрим этот процесс подробнее.
Для сцены с рис. 2.26 листовое BSP-дерево будет выглядеть следующим образом (рис. 2.27).
Рассмотрим теперь плоскость р и разобьем эту плоскость при помощи плоскостей, проходящих через грани комнат А к В. В результате мы получим портал, соединяющий эти комнаты. Обратите внимание, что плоскость должна разбиваться как при помощи всех плоскостей BSP-дерева, так и при помощи всех плоскостей, проходящих через грани данной комнаты.
Тем самым процесс построения выпуклых комнат и порталов по заданному набору граней полностью автоматизируется, но при этом количество порталов и комнат может получиться очень большим (в ряде случаев их количество оказывается даже сравнимым с. общим числом граней). Поскольку обработка портала является достаточно дорогостоящей операцией (по сравнению с обработкой обычной грани), то подобный подход не всегда применим в системах, работающих в режиме реального времени (или накладывает довольно жесткие ограничения на геометрию сцены).