2014-02-12
577
Это аналог алгоритма Аппеля. Список активных ребер сортируется вдоль оси х. Он просматривается слева направо, при встрече левого ребра спан заносится в список активных спанов ActiveSpans, а при встрече правого – удаляется. Таким образом, в списке активных спанов находятся все спаны, закрывающие точку в данный момент, они отсортированы по глубине. В начале этого списка находится ближайший к наблюдателю (видимый) спан, для него количественная невидимость равна нулю, для остальных – она равно положению в списке. Если задать условие, что объекты не пересекаются, то список изменяется только на ребрах, принадлежащих контуру. При добавлении спана в список достаточно определить глубину его начала относительно спанов в списке и вставить его в нужное место. При удалении спана – он просто удаляется из списка. Если пересекается ребро, не принадлежащее контуру, то новый спан просто заносится на место предыдущего.
0:
A:AC
B:AC,BD
C:CG,BD
D:CG,DF
E:EI,CG,DF
F:EI,CG,FH
G:EI,FH
H:EI
I:
Алгоритм можно значительно ускорить, если не заносить в список ребер не принадлежащие контурам ребра, эти ребра можно получать из текущего спана, его правое ребро одновременно является левым для следующего. Кроме того, нет необходимости сортировать ребра каждый раз, можно использовать отсортированный список с предыдущей строки. При добавлении ребра в список активных нужно вставлять его сразу на правильное место. А при изменении координаты x ребра следить за сохранением порядка и, при необходимости, переставлять ребро.
|
|
|
Этот алгоритм позволяет выводить и полупрозрачные полигоны.
Метод потенциально видимых множеств PVS (Potentially Visible Set)
Для многих сцен, особенно для закрытых помещений, количество видимых на экране объектов значительно меньше общего количества объектов в сцене. Для быстрого отсеивания большей части невидимых объектов в статических, неизменных, сценах и применяется этот метод. Пространство сцены разбивается на выпуклые объемы, например комнаты. Для каждого объема определяется, какие объекты могут быть видимы хотя бы из одной точки этого объема. При отображении сцены определяется объем, в котором находится наблюдатель, а затем выводятся все объекты, которые он может увидеть. Основным недостатком PVS является потребность в больших объемах памяти, ведь для каждого объема нужно хранить карту всех, видимых из него, объектов. Как правило, хранят не карту видимых объектов, а карту видимых объемов, это добавляет объектов при отрисовке, но значительно уменьшает требования к памяти. Но доже в этом случае, размер PVS растет квадратично с увеличением количества объемов. Тем не менее, метод PVS является очень эффективным и используется во многих приложениях.
