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