Иерархические и регулярные сетки
Иерархическая сетка представляет из себя дерево (обычно небольшой глубины, но зато очень широкое), в узлах которого лежат относительно небольшие регулярные сетки. Причем, каждый кубик в регулярной сетке является узлом. Он может быть либо пуст, либо это может быть лист, содержащий геометрию, либо указатель на сетку, разбивающую данный узел. Иерархическая сетка призвана устранить недостатки регулярной, а именно главный ее недостаток - проблему чайника на стадионе.
Рассмотрим здесь один из возможных алгоритмов траверса иерархических сеток (самый простой), а потом посмотрим, как его можно улучшить. Будем работать в 2D пространстве. Все, что нам нужно сделать, это модифицировать алгоритм траверса в регулярной сетке так, чтобы мы могли перемещаться от одной сетке к другой.
Описание структуры дерева
Введем еще одно ограничение (не существенне, но полезное). Будем считать, что дерево расположено в памяти в виде линейного массива. И вместо указателей на узлы, будем сохранять смещения относительно начала массива.
struct GridCell
{
// разумно используе память - 31 бит на смещение + 1 бит на флаг = 32 бита
unsigned int leftOffset: 31;
unsigned int leaf : 1; // если leaf == 1 то это лист
};
Для простоты будем считать, что количество узлов в сетке - константа CELL_NUMBER. Также не будем усложнять себе жизнь и сохраним координаты ограничивающего бокса для каждого узла. В последствии мы увидим, что это на самом деле может дать некоторый прирост производительности.
struct HGridNode
{
HGridNode()
{ upOffset = -1;}
bool Root() const // эта функция возвращает true если узел является корнем.
{ return upOffset < 0;}
void Draw();
GridCell GetVoxel(int x, int y) const
{
ASSERT(x >= 0);
ASSERT(y >= 0);
return grid[x + y*CELL_NUMBER];
}
AABB2f m_box;
int upOffset; // используется просто как флаг, в теории можно сохранить здесь смещение до верхнего узла
GridCell grid[CELL_NUMBER*CELL_NUMBER];
};
Алгоритм траверса в иерархической сетке
Рассмотрим здесь безстековый алгоритм. Суть такова: пользователь может играть лесными эльфами, охраной дворца и злодеем... нет это по-моему не отсюда, вот что нам нужно: Траверсим сетку до тех пор, пока не нашли в одном из ее кубиков (вокселей) внутреннюю сетку. Тогда мы берем ограничивающий бокс для этого воксела и входим внутрь, выполняя заново инициализирующую часть алгоритрма траверса в регулярной сетке. Траверсим внутреннюю сетку. Чтобы обойтись без стека и при этом не усложнять себе жизнь, при выходе из внутренней сетки во внешнюю, сделаем рестарт. Что это значит? Это означает что ели мы хотим выйти во внешний узел, мы должны "подвинуть" origin луча на t_max узла, из которого мы вышли и начать поиск с корня дерева. Алгоритм аналогичен kd-tree restart. Можно подумать, что это будет неэффективно. Однако, в случае небольшой глубины дерева restart потребует почти столько же операций, сколько и выход во внешний узел. Более того, рестарт будет производиться относительно нечасто, так как лучи, дошедшие до глубоких узлов дерева скорее всего найдут пересечение в вокселах и их вообще не нужно больше траверсить.
Вот так это выглядит:
Первая модификация в алгоритме для регулярной сетки такова: поставим метку NEXT_GRID в самом начале алгоритма. Это плохой стиль программирования, но в данной ситуации это лучшее решение, так как нам потребуется один неструктурированный переход из середины цикла. Не хотелось бы вводить дополнительные флаги. Еще нам теперь понанобится сохранть t_max пересечения с боксом, чтобы делать рестарт по нему.
float t_min, t_max;
debugRestartTimes = 0; // Нужно только, чтобы посчитать количество раз, которое луч делает рестарт
NEXT_GRID:
if(!IntersectRay2fBox2f(ray, *pBox, t_min, t_max))
return;
Затем, нам придется немного изменить цикл траверса регулярной сетки. Вместо NextVoxel(x,y,box) поместим этот код:
GridCell voxel = node->GetVoxel(x,y);
if(voxel.leaf)
NextVoxel(x, y, *pBox);
else
{
node = root + voxel.leftOffset;
pBox = &node->m_box;
goto NEXT_GRID;
}
И в заключении, добавим после основного цикла проверку следующего вида: Если текущая сетка не корневая, необходимо сделать рестарт с сохраненным t_max.
if (!node->Root())
{
node = root;
pBox = &node->m_box;
ray.pos += ray.dir*(t_max*1.0001f);
debugRestartTimes++; // DEBUG посчитаем, сколько всего раз луч сделает рестарт
goto NEXT_GRID;
}
Возможные модификации могут быть следующими:
-
Выходить в верхний узел вместо того чтобы делать рестарт.
-
Если мы сохраняем ограничивающий бокс в узле, то его можно перерасчитывать для геометрии которая попала в этот узел. В таком случае если луч не пересекается с боксом, можно вообще не входить в узел. Более того, это улучшит характеристики сетки, так как она будет более плотно прилегать к геометрии. Однако, это может усложнить алгоритм траверса.
-
Низкоуровневая оптимизация кода, например, замена делений на умножения. Так как для луча можно один раз посчитать значение 1.0f/ray.dir.x() и 1.0f/ray.dir.y(), то все деления на ray.dir.x() и ray.dir.y() можно заменить на умножения (Это относится и к функции пересечения бокса с лучем).
-
Вы конечно можете использовать рекурсию или стек, чтобы не делать рестарт. Стек для tMaxX и tMaxY на CPU наверное будет лучшим решением.
-
Можно убрать goto, если режет глаза. Но не факт, что это упростит код.
Реализацию алгоритма в 2D с визуализацией можно скачать по следующей ссылке.
http://ray-tracing.ru/upload/sources/Hierarchical_grid_01_March_2009.zip |
