Структура данных

А как же углы вращения? Или они все вдоль осей?

Можно начать с более простой задачи - проиндексировать аналогичным образом список одномерных интервалов.

Все вдоль осей

Во первых как ты проверяешь принадлежность кубу? Через x > x0 && x < x1 & ... или через манхеттенское расстояние до центра? Второе будет быстрее.

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

1. разбить пространство на области, при каждом сдвиге куба размещать указатель на наего в те области, которые он пересекает. Тогда при проверке точки ты будешь смотреть уже не все кубы, а только закешированный участок. Но это не будет работать, если все кубы будут в одной области.
2. сделать sqlite базу в оперативке и закинуть туда данные кубов. Звучит как адовый оверхед, но если кубов прям много, то алгоритмы индексирования при правильных запросах могут дать увеличение скорости над проходом в ручную

1. какой характерный объем куба?

2. сколько кубов?

3. какая доля пространства не относится ни к одному кубу?

4. размерность пространства тройка?

Да вроде ничего нового - octree, rtree, а учитывая дискретность пространства ещё и обычный хэш по клеточкам. Выбор зависит от заполненности пространства, размера кубов, количества перекрытий, диапазонов координат.

Размерность пространства тройка. Характерная длина ребра куба не больше 20-30. Но сами значения координат ограничены лишь int. Кубов в районе тысячи. Проверки точек гораздо чаще модификации кубов.

Вариантов дофига, напр. сетка Верле. Вводим равномерную сетку с шагом больше единицы (сколько именно - надо оценивать), в каждой ячейке лежит список цепляющих ее кубов. Шаг сетки такой что бы сетка хорошо лезла в память, а лучше в хэш. Дальше сразу находим ячейку сетки, а в ячейке уже прямой перебор.

Нужно больше информации о задаче.

Характерная длина ребра куба не больше 20-30. Но сами значения координат ограничены лишь int.

А насколько кучно расположены кубы и насколько они пересекаются? Можно какой то небольшой вмещающий куб построить, или несколько?

В одномерном случае гораздо проще жить, там естественное упорядочение есть.

Предлагаю посмотреть https://en.wikipedia.org/wiki/R-tree

В том и дело, там проще, но сложности уже вылезают. Если сначала решить их, то 3-мерное будет не так неподъёмно смотреться.

Если кубов 1000 то просто массив с центрами и размерами, быстрее всё посчитать чем городить, что-то.

Если их миллион и нужны только те что наблюдаются (есть камера?) то массив с отсечением того что не видно через фруструм.

Если их миллион и важны не те что видны, а все наверное типа такого https://habr.com/ru/post/473066/ только в 3D

Ты выбираешь точку для проверки, определяются те кубы что входят в «клетку» и проверяются только они.

А так, просто массив или несколько массивов, например назбить весь мир на 8 больших кубов. То есть 8 массивов (или один разбитый на 8 частей) с данными кубиков. Ты выбираешь точку определяешь в каком из кубов мира она и проверяешь только те кубики которые живут в этом кубе, при трансформации кубиков и их перемещении проверяешь не переселился ли кубик в другой мировой куб ну и просто данные копируешь из одного элемента массива в другой.

Короче что угодно что позволит отсекать то что в принципе не нужно считать.

Похоже на R-дерево, оптимизированное под конкретную задачу.

Похоже на модифицированную задачу с обнаружением столкновений. Погуглите по ключевым «collision detection».

Из подходов могу предложить разбить трёхмерное пространство на некоторое количество частей так, чтобы в каждой части было не больше n кубов. И уже в этих получившихся кусках пространства отсматривать на коллизии.

Сложностей там не так много, нужны упорядоченные массивы/мапы отдельно для левых и правых границ интервалов и затем поиск пересечения двух множеств.

Уже в 2D такое не прокатит.

Этот самый «поиск пересечения» и есть главная проблема.

А для 2д тоже нужно пересечение, но не двух а четырёх множеств.

Для 1000 элементов поиск пересечения двух множеств это 20 операций с 64х битными числами. Для 3D 8 множеств, это уже на порядок сложнее. Но в целом - это может быть для ТС рабочим вариантом - просто, делается на коленке и наверное будет все же быстрее (по крайней мере в разы) чем прямой перебор.

Правда ТС не сказал насчет параллельности алгоритма поиска, это отдельная история.

Как раз в такой формулировке разницы вообще нет - оно получается O(N) и там и там, то есть то же самое что полный перебор, только коэфициент поменьше. Только вот в моём понимании индексирование подразумевает что вместо O(N) должно получаться хотя бы O(sqrt(N)). Ну, если знать что кубов не больше 1000 то может и вариант.

Вот тут как бэ то место, где теория алгоритмов вдребезги разбивается о суровую действительность;-)

С т.з. практики все эти O(…) неважны, а важны времена работы. И O(N^2) с маленьким коэффициентом будет до некоторого N лучше чем O(N) с большим коэффициентом.

Я уж не говорю про конвейр, векторизацию, вред ветвлений, обращения к менеджеру памяти и тд и тп.

Так то, для 1000 кубов, все это больше смахивает на преждевременную оптимизацию. Сначала надо сделать прямой перебор, профилирование, а потом уже, если выясниться что это узкое место, думать над изощренными структурами данных.

R-tree

Запросы на принадлежность точек происходят чаще, чем сдвиги кубов.
Какая структура данных лучше всего для этого подходит?

три координатных вектора, и один мутекс. любой запрос на движение куба в нитку. куб shared_ptr. всё.

самое главное забыл - пишу софт за деньги)