Простейшим вариантом является равномерное разбиение пространства на набор равных прямоугольных клеток (рис. 2.11).
Очень эффективным является использование разбиения картинной плоскости, когда каждой клетке разбиения ставится в соответствие список тех объектов, проекции которых данную клетку пересекают. Для отыскания
всех объектов, которые закрывают рассматриваемый объект при проектировании, определяются объекты, попадающие в те же клетки картинной плоскости, в которые попадает и проекция данного объекта, и на закрывание проверяются только они.
Для сцен с неравномерным распределением объектов имеет смысл использовать неравномерное (адаптивное) разбиение пространства или плоскости (рис. 2.12).
Иерархические структуры (Hierarchies)
При работе с большими объемами данных весьма полезными могут оказаться различные древовидные (иерархические) структуры. Стандартными формами таких структур являются восьмеричные, тетрарные и BSP-деревья, а также деревья ограничивающих тел.
Одной из сравнительно простых структур является иерархия ограничивающих тел (Bounding Volume Hierarchy). Сначала ограничивающее тело описывается вокруг всех объектов. На следующем шаге объекты разбиваются на несколько компактных групп и вокруг каждой из них описывается свое ограничивающее тело. Далее каждая из групп снова разбивается на подгруппы, вокруг каждой из них строится ограничивающее тело и т. д. В результате получается дерево, корнем которого является тело, описанное вокруг всей сцены. Тела, построенные вокруг первичных групп, образуют первичных потомков, вокруг вторичных - вторичных и т. д.
Сравнения объектов начинаются с корня. Если сравнение не дает положительного ответа, то все тела можно сразу отбросить. В противном случае проверяются все его прямые потомки, и если какой-либо из них не дает положительного ответа, то все объекты, содержащиеся в нем, сразу же отбрасываются. При этом уже на ранней стадии проверок отсечение основного количества объектов происходит достаточно быстро, ценой всего лишь нескольких проверок.