Деревья BSP

Что такое дерево BSP?

BSP расшифровывается как двоичное разделение пространства. Формально оно представляет из себя структуру данных, которая используется для упорядочения объектов в пространстве (или на плоскости). С точки зрения компьютерной графики, такие деревья являются полезными инструментами для удаления скрытых поверхностей полигонов и рейтрейсинга (моделирование световых эффектов). Чтобы создать такое дерево, обычно пользуются рекурсией. Рекурсивно вызывается процедура, которая анализирует каждый полигон. Одним из параметров этой процедуры является секущая плоскость. Перед началом рекурсии эта плоскость выбирается произвольно. Итак, эта процедура создает очередной узел дерева. У каждого узла есть два дочерних узла. Процедура же должна анализировать пространство и распределить полигоны на “левые” и “правые” относительно выбранной плоскости. Так может продолжаться до бесконечности, однако вопросы о точках останова уже давно решены и их можно узнать, прочитав список часто задаваемых вопросов из BSP-Faq.


Ваш браузер не поддерживает апплеты Java. Загрузите с сайта Microsoft виртуальную машину Java.

Как пользоваться апплетом?

Вы можете рисовать сегменты линий в первом окне. Первая нарисованная вами линия потребует некоторого времени для инициализации внутренних классов Java, но все остальные линии должны обрабатываться нормально. Сегменты линий, которые вы можете рисовать, имеют номера. Если линии пересекаются, то выполняется их разделение по следующему принципу. Допустим, какая-то линия 1 пересекает линию 2. Следовательно, линия 1 будет формировать секущую плоскость для линии 2. Поэтому, вторая линия разделяется на два сегмента, на левый и правый, или, как еще говорят, на задний и передний. В данном примере используется терминология “задний и передний”, поэтому при пересечении двух линий на одной из них будет происходить разделение на части с последующим их именованием с добавлением букв “b” (для задней части) и “f” (для передней).

Вы можете перемещать и менять направление сиреневой стрелки, которая представляет направление взгляда смотрящего на иерархию сегментов. Этим вы изменяете картину трехмерного визуализатора, расположенного ниже. Одновременно, направление и точка приложения вектора взгляда отображается в окне с деревом BSP.

Вы можете применять операцию скроллинга для всех окон, если это необходимо. Это можно сделать, если нажать и удерживать в нажатом положении мышь, перемещая её по окну.

Для получения исчерпывающей информации читайте BSP-FAQ.

Эта страница была переведена Прядкиным Дмитрием. E-mail: pryadkin@inbox.ru