Назад | Оглавление | Домой | Далее
Разбиение картинной плоскости можно производить не только прямыми, параллельными координатным осям, но и по границам проекций граней. В результате получается точное решение задачи.
Предлагаемый метод работает с проекциями граней на картинную плоскость.
В качестве первого шага производится сортировка всех граней по глубине (front-to-back).
Затем из списка оставшихся граней берется ближайшая грань A и все остальные грани обрезаются по этой грани. Если проекция грани B пересекает проекцию грани A, то грань B разбивается на части так, что каждая часть либо содержится в грани A, либо не имеет с ней общих внутренних точек.
Таким образом, получаются два множества граней: Fin – грани, проекции которых содержатся в проекции грани A (сюда входит и сама грань A), и Fout – грани, проекции которых не имеют общих внутренних точек с проекцией грани A.
Множество Fin обычно называют множеством граней, внутренних по отношению к A.
Однако во множестве Fin могут быть грани, лежащие к наблюдателю ближе, чем сама грань A (это возможно, например, при циклическом наложении граней). В этом случае каждая такая грань используется для разбиения всех граней из множества Fin (включая исходную грань A). Когда рекурсивное разбиение завершится, то все грани из первого множества выводятся из набора оставшихся граней (их уже ничто не может закрывать). Затем из набора оставшихся граней Fout берется очередная грань и процедура повторяется.
Рассмотрим простейший случай для двух граней A и B (рис. 5.18).
Рис. 5.18. Пример разбиения граней
Будем считать, что грань A расположена ближе, чем грань B. Тогда на первом шаге для разбиения используется именно грань A. Грань B разбивается на две части. Часть B1 попадает в первое множество Fin и, так как она лежит дальше грани A, удаляется.
После этого выводится грань A и в списке оставшихся граней остается только грань B2. Так как кроме нее других граней не осталось, то эта грань выводится, и на этом работа завершается.
Назад | Оглавление | Домой | Далее