Войти
ПрограммированиеФорумОбщее

AABB-tree кто делал? (2 стр)

Страницы: 1 2
#15
14:59, 14 ноя 2020

gamedevfor
>Где там 8 секунд?
>Size: 1048576
Там 2^20 элементов - т.е. как раз в 4 раза меньше.


#16
15:39, 14 ноя 2020

AlexeyLarin

Function                             Times Called  Exclusive Time  Max Recursion  Max Call Time
b2DynamicTree::Balance (80% time)     21502242         0,561654        0          0,00783223
b2DynamicTree::AllocateNode(10% time) 2097151          0,0764834       0          0,00562186
b2DynamicTree::InsertLeaf (10% time)  1048576          4,42064         0          0,0118445

Чудовищное число вызовов нужно как то инлайнить.

#17
19:19, 14 ноя 2020

gamedevfor
Попробовал добавить inline, но особо ничего не поменялось.
Скорее всего основное время идет именно на ребалансировку дерева. Не думаю что это можно исправить другой имплементацией.

Наверное нужно как-то сразу строить сбалансированное дерево на основе исходных данных. Пока не знаю как это можно грамотно сделать. В коде Box2d есть функция RebuildBottomUp (сcылка) для построения сбалансированного дерева, но она работает за куб.

#18
19:27, 14 ноя 2020

AlexeyLarin
> Попробовал добавить inline, но особо ничего не поменялось.
> Скорее всего основное время идет именно на ребалансировку дерева. Не думаю что
> это можно исправить другой имплементацией.

Конечно сама студия такое страшилище не заинлайнит но можно вручную скопипастить этот код.

#19
21:32, 14 ноя 2020

AlexeyLarin
RebuildBottomUp выглядит как то, что нужно, но странно реализованное. Обычно такое построение происходит сверху вниз (то есть ты не объединяешь ветки в одну, а выбираешь где разделить корневой AABB, и потом запускаешь ту же процедуру для полученных дочерних), алгоритмическая сложность таких построений не должна превышать квадрат. Еще по какой-то причине они вместо SAH используют эвристику по периметру. Не знаю, может это специфика физических движков.
Вообще все это очень хорошо описано в Physically Based Rendering From Theory To Implementation (юзаю третье издание), раздел 4.3.

#20
23:29, 15 ноя 2020

Как я понял, то мы можем строить дерево любым способом - главное чтобы у родителей были верно выставлены границы. Разница будет только в качестве этого дерева для поиска.

Написал вот такой алгоритм взятый отсюда. (функция splitNode)

1) У нас есть набор боксов и для них считаем бокс в который они все поместятся.
2) Далее разделяем этот бокс пополам вдоль самой широкой оси. Если не получилось разделить вдоль этой оси на два бокса, чтобы в каждом был хотя бы один элемент, то пробуем следующую ось.
3) Далее для каждого из двух полученных боксов переходим к пункту 1.

Естественно данный способ не для всех случаев будет генерировать хорошие деревья, но для моего случая вполне подойдет. Для моего теста сейчас дерево строится за 900мс, что в 10 раз быстрее чем было.

На самом деле способов построить исходное дерево довольно много. Если кому надо, то нашел несколько способов  вместе с диаграммами производительности - ссылка.

Страницы: 1 2
ПрограммированиеФорумОбщее

Тема в архиве.