Я бы использовал для этого фиксированную сетку NxN, главным образом потому, что вокруг каждого кадра перемещается слишком много точек, чтобы извлечь выгоду из рекурсивной природы подразделения дерева квадрантов. Это тот случай, когда прямая структура данных с правильно настроенными представлениями данных и расположением памяти может изменить мир к лучшему.
Главное, что я бы сделал для Java, — это фактически избегал моделирования каждой частицы как объекта. Это должны быть необработанные данные, такие как простые старые данные, такие как числа с плавающей запятой или целые числа. Вы хотите иметь возможность работать с гарантиями непрерывности для пространственной локальности с последовательной обработкой и не платить за заполнение и 8-байтовые накладные расходы на экземпляр класса. Отделите холодные поля от горячих полей.
Например, вам не обязательно знать цвет частицы, чтобы перемещать ее и применять физику. В результате здесь вам не нужно представление AoS, которое должно загружать цвет частицы в строки кэша во время последовательного прохода физики только для того, чтобы исключить его, а не использовать. Втисните как можно больше релевантной памяти, используемой вместе, в строку кэша, отделив ее от нерелевантной памяти для конкретного прохода.
Каждая ячейка в сетке должна просто хранить индекс в частице, при этом каждая частица хранит индекс для следующей частицы в ячейке (односвязный список, но навязчивый, который не требует выделения узлов и просто использует индексы в массивы) . -1 можно использовать для обозначения конца списка, а также пустых ячеек.
Чтобы найти столкновения между интересующими частицами, просмотрите ту же ячейку, что и частица, которую вы тестируете, и вы можете сделать это параллельно, когда каждый поток обрабатывает одну или несколько ячеек с частицами.
Сетка NxN должна быть очень тонкой, учитывая количество движущихся частиц, которые вы можете иметь в каждом кадре. Поиграйте с тем, сколько ячеек вы создаете, чтобы найти что-то оптимальное для ваших входных размеров. У вас может быть даже несколько сеток. Если определенные частицы не взаимодействуют друг с другом, не помещайте их в одну сетку. Не беспокойтесь об использовании памяти в сетке. Если каждая ячейка сетки просто хранит 32-битный индекс для первой частицы в ячейке, то сетка 200x200 занимает всего 160 килобайт с 32-битным индексом next на каждую частицу.
Я сделал что-то подобное несколько лет назад на языке C, используя описанную выше технику (но не с таким количеством интересных взаимодействий частиц, как в демо-игре), которая могла обрабатывать около 10 мл частиц, прежде чем она начала опускаться ниже 30 кадров в секунду, а на старом оборудовании всего лишь 2 ядра. Он использовал C, а также SIMD и многопоточность, но я думаю, что вы можете получить очень быстрое решение на Java, обрабатывающее кучу частиц одновременно, если вы сделаете вышеописанное.
Структура данных: 
Когда частицы перемещаются из одной ячейки в другую, все, что вы делаете, — это манипулируете парой целых чисел, чтобы переместить их из одной ячейки в другую. Ячейки не «владеют памятью» и не выделяют ее. Это просто 32-битные индексы.
Чтобы выяснить, какую ячейку занимает частица, просто выполните:
cell_x = (int)(particle_x[particle_index] / cell_size)
cell_y = (int)(particle_y[particle_index] / cell_size)
cell_index = cell_y * num_cols + cell_x
... гораздо более дешевая операция с постоянным временем, чем обход древовидной структуры и необходимость перебалансировать ее по мере движения частиц.
person
Community
schedule
10.12.2017
