В n-D дерево BSP представляет собой структуру пространственных данных разбиения, которая рекурсивно разбивает пространство на ячейки с помощью расщепления n-D гиперплоскостей (или даже n-D гиперповерхностей).
В 2D все пространство рекурсивно разбивается на двумерные линии (в (возможно, бесконечные) выпуклые многоугольники).
В 3D все пространство рекурсивно расщепляется на трехмерные плоскости (в (возможно, бесконечные) выпуклые многогранники).
Как построить дерево BSP в 3D (от модели)
Модель изготовлена из списка примитивов (треугольники или каре, который я считаю, что вы называете прямоугольниками).
Начните с исходного корневого узла в дереве BSP, который представляет собой ячейку, покрывающую все трехмерное пространство и первоначально содержащую все примитивы вашей модели.
Вычислить оптимальную плоскость расщепления для рассматриваемых примитивов.
Целью этого шага является поиск плоскости, которая будет разделять примитивы на две группы примитивов примерно одинакового размера (одинаковые пространственные экстенты или одинаковое количество примитивов).
Простая стратегия разделения может заключаться в том, чтобы выбрать направление в случайном порядке (которое будет нормальным для вашей плоскости) для разделения. Затем отсортируйте все примитивы пространственно вдоль этой оси. И перейдите отсортированный список примитивов, чтобы найти положение, которое разделит примитивы на две группы примерно равного размера (т. Е. Просто найдет медианное положение из примитивов вдоль этой оси). С этим направлением и этим положением определяется плоскость расщепления.
Один, как правило, используется стратегия расщепления, однако:
Центр тяжести дает положение плоскости расщепления.
Собственный вектор для наибольшего собственного значения ковариационной матрицы дает нормаль плоскости расщепления, которая является направлением, где примитивы наиболее распространены (и где текущая ячейка должна быть разделена).
Разделить текущий узел, создать два дочерних узла и назначить примитивы каждому из них или текущему узлу.
Найдя подходящую плоскость расщепления в 1., трехмерное пространство можно разделить на два полупространства: один положительный, на который указывает плоскость нормальный, и один отрицательный (на другой стороне плоскости расщепления). Цель этого шага состоит в том, чтобы разрезать половину рассмотренных примитивов, присвоив примитивы полупространству, в котором они принадлежат.
Проверьте каждый примитив текущего узла относительно плоскости расщепления и назначьте его либо левому, либо правому дочернему узлу в зависимости от того, находится ли он в положительном полупространстве или в отрицательном полупространстве.
Некоторые примитивы могут пересекать плоскость расщепления. Они могут быть обрезаны плоскостью на более мелкие примитивы (и, возможно, также триангулированы), так что эти меньшие примитивы полностью находятся внутри одного из полупространств и принадлежат только одной из ячеек, соответствующих дочерним узлам. Другой вариант - просто присоединить перекрывающиеся примитивы к текущему узлу.
Примените рекурсивно эту стратегию разделения к созданным дочерним узлам (и их дочерним узлам) до тех пор, пока не будет выполнен некоторый критерий прекращения расщепления (как правило, не имеет достаточного количества примитивов в текущем узле).
Как использовать BSP дерево в 3D
Во всех случаях использования, иерархическая структура дерева BSP используется отбрасывать ненужную часть модели для запроса.
нахождением точки
Траверс дерева BSP с вашей точки запроса. На каждом узле идите влево или вправо в зависимости от того, где находится точка запроса w.r.t. к плоскости расщепления узла.
Compute луч/модель пересечению
Чтобы найти все треугольники модели, пересекающей луч (возможно, это нужно для получения вашей карты), сделать что-то похожее на 1 .. Traverse дерева BSP с вашим запрос луч. На каждом узле вычислите пересечение луча с плоскостью расщепления. Также проверьте примитивы, хранящиеся на узле (если есть), и сообщите те, которые пересекают луч. Продолжайте обход детей этого узла, чья ячейка пересечет ваш луч.
отбрасывая невидимые данные
Другим возможным использование отбрасывать части вашей модели, которые лежат вне поля зрения усеченного камеры (что, вероятно, что вы заинтересованы в здесь). Вид усечения точно ограничен шестью плоскостями и имеет 6 четырехгранников. Как и в пунктах 1. и 2., вы можете пересечь дерево BSP, проверить рекурсивно, какая ячейка перекрывается с помощью усечения и полностью отбрасывать те (и соответствующие части вашей модели), которые этого не делают. Для теста пересечения плоскости/обзора frustum вы можете проверить, пересекается ли какое-либо из 6 квадрантов усечения на плоскости, или вы можете консервативно аппроксимировать представление усечения с ограниченным объемом (рамка с ограничением по оси/оси или ориентированным ограничителем) или даже сделать комбинацию обоих.
При этом, решение вашей медленной проблемы рендеринга может быть в другом месте (вы не можете быть в состоянии отказаться от большого количества данных с деревом 3D БСП для вашей модели):
62K квадратов не так уж и много: если вы используете OpenGL, вы не должны рисовать эти квадраты индивидуально или непрерывно передавать геометрию на графический процессор. Вы можете поместить все вершины в один статический буфер вершин и нарисовать квадратики путем подготовки буфера статического индекса, содержащего список индексов для квадратов с треугольниками или (лучше) примитивов треугольников, чтобы нарисовать соответствующие квадраты в одном обратном вызове ,
Ваши данные высокая структурированная (обычная сетка с высотой). Если у вас есть больше больших наборов данных (которые даже не вписываются в память больше), то вам нужно не только пространственное разбиение (которое использует структуру 2.5D ваших данных и ее регулярность, например quadtree), но, возможно, LOD, а также (чтобы заменить части ваших данных более дешевым представлением, а не просто отбрасывать данные). Затем вам следует изучить методы LOD для рендеринга местности. This page перечисляет несколько ресурсов (документы + реализации). В качестве отправной точки можно использовать упрощенный Chunked LOD.
Не могли бы вы рассказать о том, что ваш 3D-объект: это карта с высотой? Каков его типичный размер? И почему вы думаете, что деревья BSP - это решение вашей проблемы с медленным рендерингом? – user3146587
Мой 3D-объект содержит список трехмерных квадратов (четыре точки 3D), и я думаю, что деревья BSP - это решение, потому что есть как 62000 квадратов, и он работает очень медленно. Кроме того, я хочу знать, как использовать BSP в целом. – TJR
Вы имеете в виду, что у вас простая регулярная сетка, где каждая точка имеет высоту? И вы представляете это как список квадроциклов? – user3146587