В подобных задачах сцену можно достаточно легко разбить на набор выпуклых областей, например комнат, и для каждой из таких областей составить список iex граней, которые могут быть видны из данной области. Подобный список называется
10. Удаление невидимых линий и поверхностей
pVS (Potentially Visible Set) и для каждой из областей на этапе препроцессинга обычно строится заранее. PVS позволяет получить достаточно быструю визуализацию постоянной сцены из различных точек наблюдения, хотя и требует больших затрат на этапе препроцессирования.
Для удаления невидимых граней из PVS и их частей используется один из традиционных методов удаления невидимых поверхностей (например, метод z-буфера).
10.5.2. Метод порталов Существует подход, позволяющий строить PVS прямо на ходу. Разобьем сцену на набор выпуклых областей и рассмотрим, как эти области соединены между собой. Те соединения, через которые можно видеть (окна, дверные проемы), называются порталами.
Ясно, что все грани, принадлежащие той ячейке, в которой находится наблюдатель, могут быть видны и поэтому автоматически попадают в PVS. Рассмотрим порталы, соединяющие данную ячейку с соседними. Если какие-то грани и могут быть видны» w только через эти порталы. Поэтому выделим области, соединенные с текущей областью порталами, и в них те грани, которые видны через соединяющие их порталы. Далее для областей, соседних с начальной, рассмотрим соседние области. Они также могут быть видны только через соединяющие порталы. Поэтому выделим те грани, которые могут быть видны (теперь уже через два последовательных портала), и т. д. Подобным путем можно легко построить некоторое множество граней, потенциально видимых из данной точки. Возможно, этот список окажется несколько избыточным, но тем не менее он будет заметно меньше, чем общее число граней.
Рассмотрим сцену, представленную на рис. 10.47. Порталы обозначены пунктирными линиями.
Пусть наблюдатель находится в комнате 0-1-2-27-28. Очевидно, что он видит все лицевые грани в этой комнате. Кроме того, через портал 3-26 он видит комнату 3-4-25-26, а через портал 4-25 - комнату 4-5-6-7-