Работа с соседними ячейками в Quadtree на GPU

В этом видео от SpaceX (https://youtu.be/txk-VO1hzBY) описывается разделение региона в прямоугольники, как если бы вы использовали дерево квадрантов.

Затем они говорят о выполнении вычисления для каждой ячейки в этом предполагаемом дереве квадрантов, которое зависит от 4 соседей этой ячейки с использованием графического процессора.

Зная ограничения кода графического процессора (данные должны поступать в виде массива, и вы должны попытаться получить доступ к элементам массива в простом согласованном порядке), как передать дерево квадрантов данных в графическом процессоре в виде массива?

Существуют ли известные алгоритмы для работы с такими деревьями квадрантов?


arrays gpu quadtree
person Mizerable Mizerable    schedule 18.02.2016    source источник
comment
в этом документе инженеры SpaceX предполагают, что они использование не является деревом квадрантов. Поскольку эти высокопроизводительные симуляции, вероятно, являются частью секретного соуса SpaceX, я предполагаю, что они вряд ли раскроют точные детали.   -  person njuffa    schedule 19.02.2016
comment
Не уверен насчет деревьев квадрантов, но упомянутый вами метод (разделение области на подобласти и последующее выполнение некоторых вычислений для каждой подобласти на основе ее соседей) используется в вычислениях трафарета, а также в адаптивном уточнении сетки, оба из которых были реализованы на ГПУ. Возможно, вы захотите начать с этого.   -  person shridharama    schedule 19.02.2016
comment
Вы имеете в виду 4 субрегиона, Вы написали 4 соседа, Четырехъядерная ячейка может иметь более 4 соседних соседних ячеек.   -  person AlexWien    schedule 22.02.2016

Ответы (1)


arrow_upward
0
arrow_downward

Дерево квадрантов на основе массива называется «линейным деревом квадрантов».

см. также, например, https://xlinux.nist.gov/dads//HTML/linearquadtr.html)
(Поиск в Google даст вам несколько статей для чтения)

person AlexWien    schedule 22.02.2016