Для работы рендерера все секторы разбиваются на выпуклые части, называемые SubSector.
При построении изображения происходит упорядочение всех SubSector'oB по мере их удаления (front-to-back) и последовательный вывод.
Для построения такого разбиения и упорядочения SubSector используется специальный вариант BSP-деревьев.
Компьютерная графика. Полигональные модели Замечание. На самом деле используется еще структура равномерного разбиения плоскости (ВЬОСКМАР), но она применяется не для рендеринга, а для определения возможности перемещения игрока (проверок на пересечение со стенами). В данной структуре весь лабиринт разбивается на одинаковые квадратные клетки и для каждой такой клетки хранится список всех пересекающих ее отрезков (ЫпеОе/).
Рассмотрим несколько простейших сцен.
Пусть сцена (рис. 13,15) состоит всего из одного сектора, но он невыпуклый. Разобьем его на две части прямой /, проходящей через вершины 3 и 2. В результате появится одна дополнительная вершина 7 и сектор будет разбит на две выпуклые части (0-1-2-7-6 и 2-3-4-5-7), они и станут ЗиЬБесгог. По результатам разбиения построим двоичное дерево, узлами которого являются разбивающие плоскости, а листьями - 8иЬ8есюг. Получившееся в результате дерево изображено на рис. 13.16. Сцена с рис. 13.13 состоит уже из двух выпуклых секторов, поэтому узлом (корнем) дерева будет пря мая, проходящая через разделяющий их отрезок.
Для сцены, приведенной на рис. 13.17, одного разбиения недостаточно, так как одна из частей, которые получились после разбиения прямой, проходящей через отрезок 11-10, по-прежнему является невыпуклой. Разобьем ее еще раз, приходя тем самым к дереву, представленному на рис. 13.18.
В общем случае процедура разбиения выглядит следующим образом: выбирается некоторая прямая (обычно проходящая через один из отрезков) и все секторы, через которые она проходит, разбиваются ею на части. Получаем два множества
13. Элементы виртуальной реальности Многоугольников - лежащих справа от прямой, производящей разбиение, и лежащих слева от этой прямой.