BSP-дерево и его применение в трехмерной графике

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

Обзор      Binary Space Partitioning (BSP) Tree - стандартное бинарное дерево, используемое для сортировки и поиска многоугольников и многогранников в n-мерном пространстве. Взятое в целом BSP-дерево представляет собой все пространство, а каждый его узел ограничивает выпуклое подпространство. Каждый из узлов дерева хранит информацию о "гиперплоскости", делящей пространство узла на 2 части (переднюю и заднюю, что определяется направлением вектора нормали этой плоскости), а также ссылки на два новых узла, представляющих эти части. Заодно в узлах может храниться информация об одном или нескольких полигонах, лежащих в этой "гиперплоскости".      Хотя обычно BSP-деревья используются для представления двух- и трехмерных пространств, однако по определению эти структуры не ограничены тремя измерениями. Пример      Очень несложно разобраться с BSP-деревом, если ограничить нашу дискуссию двумя измерениями. Еще проще нам будет, если мы предположим, что используются только линии, параллельные осям X и Y, и что мы будем делить пространство на равные части для каждого узла. Рассмотрим такой пример (довольно стандартный): у нас есть квадрат где-то в плоскости XY. Мы производим первый раздел (который будет узлом нашего дерева). Разобьем квадрат пополам в направлении оси X. Для каждого рассечения мы будем изменять направление линии раздела на противоположное, т.о. второй "разрез" будет произведен над оставшимися секторами в направлении оси Y. Этот процесс можно продолжать рекурсивно, пока не будет достигнута "точка останова". Результат можно изобразить таким образом: .

Как построить BSP-дерево

Обзор      Итак, уйдем от двухмерности: дано несколько полигонов в трехмерном пространстве. Задача: построить BSP-дерево, которое бы содержало их все. На данный момент нас не интересуют особенности построения дерева для каких-то специфических нужд. Алгоритм построения дерева очень прост: 1. Выбрать делящую плоскость. 2. Разделить полигоны (сцену или один объект) этой плоскостью, переслав многоугольники, находящиеся в полупространстве нормали делящей плоскости в положительную ветвь (предположим, правую), а остальные - в отрицательную (левую). 3. Рекурсивно повторить для обоих получившихся узлов. Выбор делящей плоскости      Обычно эта плоскость выбирается в зависимости от того, как будет использовано дерево. Для некоторых целей лучше выбирать делящую плоскость из входящего списка полигонов (такой метод "у них" называется autopartition, у нас, наверно, авторазделение). Однако многие приложения могут только выиграть от выбора делящих плоскостей, параллельных осям. Разделение полигонов      Разделение списка полигонов делящей плоскостью производится путем определения положения каждого полигона из списка относительно плоскости. Если многоугольник полностью находится по одну сторону делящей плоскости, то он не модифицируется, а просто добавляется к одному из двух новых узлов дерева в зависимости от расположения этого полигона относительно плоскости (если он справа - то добавляется в правую ветвь и наоборот). Если же многоугольник пересекается делящей плоскостью, то он делится на две части, и каждая из них добавляется в свой узел (правая половинка - в правый, левая - в левый). Когда остановиться      Собственно, есть несколько критериев оценки необходимости завершения построения дерева (ого, как загнул!): оценка количества полигонов в узле, "прогон" всех многоугольников в дерево, достижение максимальной глубины дерева - в любом случае, выбор условия завершения зависит только конкретно от ваших и вашего приложения нужд. Псевдокод      Ну вот мы и подобрались к самому интересному - псевдокоду рекурсивной функции для создания трехмерного Quake-подобного BSP-дерева. Но сначала рассмотрим две структуры, которые понадобятся нам в дальнейшем. Первая из них определяет узел BSP-дерева, а вторая представляет собой описание полигона: struct BSP_Node { Polygon3D partition_face; // делящая грань Vector3D normal; // нормаль делящей грани float plane_param; // параметр D плоскости разделения BSP_Node *front; // передний (правый) узел BSP_Node *back; // задний (левый) узел } class Polygon3D { int count; // количество точек полигона Vector3D normal; // нормаль Point3D points[MAX_POINTS]; // данные о вершинах Polygon3D (Point3D, int); }      Не забудьте, что эти определения мы будем использовать для всех примеров. Для первой прикидки предположим, что в списке принадлежащих плоскости полигонов всегда только один многоугольник: тот самый, по которому мы и вычисляем делящую плоскость для этого узла дерева. Метод-конструктор для этой структуры должен инициализировать указатели на дочерние узлы в NULL: BSP_Node Build_BSP_Tree (const list &polygons) { BSP_Node *root = new BSP_Node; Polygon3D *part = (Polygon3D*)polygons[0]; // импользуем для // разделения первую // грань из списка list front, back; Polygon3D *p1, *p2; root->partition_face = part; root->normal = part->normal; root->plane_param = part->normal & part->points[0]; for (int i=1; i<polygons.count; i++) { Polygon3D *p = (Polygon3D*)polygons[i]; switch (Classify_Polygon(root, p)) { case CL_PLANE: // можно кидать в любую ветвь case CL_POSITIVE: back.add(p); break; case CL_NEGATIVE: front.add(p); break; default: // надо делить грань Split_Polygon(root, p, &p1, &p2); back.add(p1); front.add(p2); break; } } root->back = (back.count>0 ? Build_BSP_Tree(back) : NULL); root->front = (front.count>0 ? Build_BSP_Tree(front) : NULL); return root; } int Classify_Polygon(BSP_Node *node, Polygon3D &p) { int positive = 0; int negative = 0; for (int i=0; i<p.count; i++) { float res = p.points[i] & node->normal - node->plane_param; if (res > THRESHOLD) positive++; else if (res < THRESHOLD) negative++; } if (positive > 0 && negative == 0) return CL_POSITIVE; else if (positive == 0 && negative >0) return CL_NEGATIVE; else if (positive == 0 && negative == 0) return CL_PLANE; else return CL_SPLIT; }      Первая функция рекурсивно конструирует BSP-дерево. Она берет первый полигон из входящего списка и использует его для деления оставшихся. Потом процедура рекурсивно вызывает сама себя для деления обеих получившихся частей. Эта реализация алгоритма предполагает, что все многоугольники - выпуклые.      Вторая функция определяет положение грани относительно узла дерева.      Процедуру Build_BSP_Tree теоретически можно улучшить только одним способом - выбирать делящую плоскость более интеллектуально. Но... это уже совсем другая история. .

А как мне разделить полигон плоскостью?..

Обзор      Разделение полигона плоскостью в основном заключается в определении по какую сторону он находится от секущей плоскости. Эта процедура обычно называется front/back test и производится путем проверки положения каждой вершины многоугольника относительно плоскости. Если все точки лежат по одну сторону, то весь полигон находится по эту сторону и нет необходимости его делить. Если же некоторые точки лежат по разные стороны плоскости, то многоугольник требует деления на две (или более) частей.      Простейший алгоритм заключается в последовательном прохождении всех сторон полигона и поиске тех, вершины которых лежат по разные стороны плоскости. Потом вычисляются точки пересечения этих сторон с плоскостью и полученные значения используются как вершины для результирующих многоугольников. Заметки по созданию алгоритма Определение положения точки относительно плоскости производится простой подстановкой координат точки (x,y,z) в уравнение плоскости Ax+By+Cz+D = 0. Результатом этой операции будет расстояние от точки до плоскости. Оно будет положительным, если точка находится по ту сторону плоскости, в которую указывает вектор нормали и отрицательным, если по другую. Если же результат равен 0, то точка лежит на плоскости. Если вы ноль в математике и "уравнение плоскости" для вас - непроходимый лес, я поясню, что A, B, и C - это координаты вектора нормали, а D может быть заранее рассчитано подстановкой точки с координатами (x,y,z), лежащей в этой плоскости.      Вообще выпуклые полигоны гораздо проще делить чем невыпуклые, так как первые всегда делятся на две выпуклых же части, а со вторыми иметь дело очень сложно, особенно если они имеют самопересечения. Псевдокод Вот очень простая (но действующая) функция для разделения полигона плоскостью. Прошу заметить, что именно на эту функцию ссылается наш предыдущий пример: void Split_Polygon(BSp_Node *node, Polygon3D &p, Polygon3D **p1, Polygon3D **p2) { Point3D points1[MAX_POINTS]; Point3D points2[MAX_POINTS]; Vector prevP = p.points[p.count-1]; float prevF = prevP & node->normal - node-> plane_param; int count1 = 0; int count2 = 0; for (int i=0; i<p.count; i++) { Vector curP = p.points[i]; float curF = curP & node->normal - node->plane_param; if (curF >= 0 && prevF <= 0) points1[count1++] = curP; else if (curF < 0 && prevF >= 0) points2[count2++] = curP; else if (curF < 0 && prevF > 0) { float t = -curF / (prevF - curF); Point3D sp = curP + t * (prevP - curP); points1[count1++] = sp; points2[count2++] = sp; points2[count2++] = curP; } else if (curF > 0 && prevF < 0) { float t = -curF / (prevF - curF); Point3D sp = curP + t * (prevP - curP); points1[count1++] = sp; points2[count2++] = sp; points1[count1++] = curP; } prevP = curP; prevF = curF; } *p1 = new Polygon3D(points1, count1); *p2 = new Polygon3D(points2, count2); } Вы, я думаю, уже заметили подвох в этом коде и вообще в алгоритме. Эта процедура делит треугольник не на два треугольника, а на треугольник и четырехугольник. Ну что же, если для вас важно сохранить все примитивы в своем мире треугольными, то есть следующие предложения по модернизации этой процедуры: 1. В параметрах передавать указатель не на одну часть полигона а на списки, например: void Split_Polygon (BSP_Node *node, Polygon3D &p, list &polygons1, list &polygons2) 2. Для данного случая (см.рис.) если вершины треугольника передавались в порядке их следования по часовой стрелке (то есть A,B и C), то процедура выдаст следующий результат: outpts[] = E, A, D inpts[ = E, D, B, C 3. Таким образом простейшим способом деления четырехугольника на треугольники с сохранением заданной ориентации будет выборка 1-й, 2-й и 3-й вершин для первого треугольника и 1-й, 3-й и 4-й вершин для второго треугольника, то есть в нашем случае по одну сторону от плоскости будет лежать треугольник EAD, а по другую - треугольники EDB и EBC. 4. Также необходимой будет и модификация основной процедуры Build_BSP_Tree() для того, чтобы она могла принимать несколько полигонов для добавления в узлы из функции Split_Polygon(). .

Применение BSP-дерева для удаления скрытых поверхностей

Обзор      Возможно самым частым применением BSP-деревьев является удаление скрытых поверхностей в трех измерениях. Эти структуры данных обеспечивают быстрый и "безболезненный" метод отбора и сортировки полигонов путем рекурсии по дереву. Этот факт мы сейчас и используем "пересмотрев" методы удаления невидимых граней и расширив их при помощи BSP-дерева. Оптимизация алгоритма художника      BSP-деревья идеально подходят для реализации алгоритма художника, так как процесс разделения полигонов есть изначальный процесс создания BSP-дерева. Все что остается сделать после создания сцены и ее BSP-дерева - это рекурсивно пройти его "от передних ветвей к задним" (back-to-front traversal). Делается это так: 1. Начав с корневого узла дерева, определить положение точки обзора (eye point) относительно делящей плоскости этого узла. 2. Прорисовать сначала противоположную ветвь, потом полигоны, принадлежащие делящей плоскости, ну и наконец ветвь, в которой находится камера. 3. Повторять этот процесс рекурсивно для каждого узла дерева. Z-буфер, scanline-метод      Эти методы используют другой подход - им требуется прорисовка от передних плоскостей к задним, что также возможно при помощи BSP-дерева, только называется это front-to-back traversal. Делается так: 1. Начав с корневого узла дерева, определить положение точки обзора(eye point) относительно делящей плоскости этого узла. 2. Прорисовать сначала ветвь, в которой находится камера, потом полигоны, принадлежащие делящей плоскости, ну и наконец противоположную ветвь. 3. Повторять этот процесс рекурсивно для каждого узла дерева Замечания      При построении BSP-дерева для удаления невидимых поверхностей делящие плоскости почти всегда выбираются из входящих в сцену полигонов. Однако, любая плоскость может быть использована как делящая, и наверняка интеллектуальный выбор плоскости приведет к положительному скачку производительности генератора BSP-дерева и программы в целом. Псевдокод      Вот небольшой пример рекурсивного прохода дерева от задних ветвей к передним (back-to-front): void Draw_BSP_Tree (BSP_Node *tree) { // не забудьте о Vector3D eye - положении наблюдателя if ((tree->normal & eye) > tree->plane_param { if (tree->front != NULL) Draw_BSP_Tree(tree->front); Draw_Polygon(tree->partition_face); if (tree->back != NULL) Draw_BSP_Tree(tree->back); } else { if (tree->back != NULL) Draw_BSP_Tree(tree->back); Draw_Polygon(tree->partition_face); if (tree->front != NULL) Draw_BSP_Tree(tree->front); } }      Если камера находится на делящей плоскости, то теоретически порядок прорисовки ветвей неясен. В этом случае мы не выводим на экран полигоны, принадлежащие плоскости, потому что их все равно не будет видно.      Можно улучшить этот пример, если представлять камеру как направленный вектор: тогда мы сможем определять видимость отдельных ветвей, что в некоторых случаях даст 50%-й прирост скорости. Ветви, находящиеся позади камеры, можно будет просто не выводить на экран, а также поможет нам решить проблему выбора нужной ветви при нахождении игрока на делящей плоскости.      Эта процедура легко переделывается под front-to-back traversal - достаточно просто поменять местами 4 строки: Какие? Если вы поняли, о чем велась речь, это не составит для вас труда. (Подсказка: поменяйте местами обработку левого и правого поддеревьев в обоих местах). Дополнительные благодарности Спасибо книге «Компьютерная графика: полигональные модели» за то, что развеяла все мои сомнения насчет принципов работы BSP-деревьев и объяснила то, что я не понимал. Примеры, которые вы видите здесь, являются почти точной копией примеров из книги – так уж получилось, сложно придумать что-нибудь более качественное =). Поэтому я и решил заменить свой код на этот. Copyright 2001 by AWDP