Какие технологии использовать для системы частиц с огромным спросом?

Question

У меня есть система частиц с X-частицами. Каждая частица тестирует на столкновение с другими частицами. Это дает X * X = X ^ 2 тестов столкновений на кадр. Для 60f / с это соответствует 60 * X ^ 2 обнаружению столкновений в секунду.

Каков наилучший технологический подход для этих интенсивных расчетов? Должен ли я использовать F #, C, C ++ или C # или что-то еще?

Ниже приведены ограничения

1. Код написан на C # с последним XNA
2. Может считаться многопоточным
3. Нет специального алгоритма, который проверяет столкновение с ближайшими соседями или который уменьшает проблему

Последнее ограничение может быть странным, поэтому позвольте мне объяснить. Независимо от ограничения 3, учитывая проблему с огромными вычислительными требованиями, что было бы лучшим подходом для решения проблемы. Алгоритм уменьшает проблему; все же один и тот же алгоритм может вести себя по-разному в зависимости от технологии. Рассмотрим плюсы и минусы CLR против нативного C.

Answer 1

Простой ответ - «измерить».Но взгляните на этот график (который я позаимствовал у этого вопроса - который стоит прочитать).

C ++, возможно, на 10% быстрее, чемРеализация MS C # (для этого конкретного расчета) и еще быстрее против реализации Mono C #.Но с точки зрения реального мира, C ++ не все , что намного быстрее, чем C #.

Если вы выполняете хардкорное сокращение чисел, вы можете использовать SIMD / SSE единица вашего процессора.Это то, что C # обычно не поддерживает, но Mono добавляет поддержку через Mono.Simd.Из графика видно, что использование блока SIMD значительно повышает производительность обоих языков.

(Стоит отметить, что, хотя C ++ все еще «быстрее», чем C #, выбор языка имеет лишь небольшой эффектпо производительности, по сравнению с выбором того, какое аппаратное обеспечение использовать. Как было упомянуто в комментариях - ваш выбор алгоритма окажет наибольший эффект.)

И, наконец, как отметил Джерри Коффин в его ответ , что вы также можете сделать обработку на GPU.Я полагаю, что это будет даже быстрее, чем SIMD (но, как я уже сказал, измерьте это).Использование графического процессора имеет дополнительное преимущество: процессор может свободно выполнять другие задачи.Недостатком является то, что вашим конечным пользователям понадобится разумный графический процессор.

Answer 2

Вам, вероятно, следует подумать о том, чтобы сделать это на GPU, используя что-то вроде CUDA, OpenCL или DirectX Compute Shader.

Answer 3

Sweep and prune - это широкий алгоритм обнаружения коллизий фаз, который может хорошо подходить для этой задачи.Если вы можете использовать временную когерентность, то разность местоположений от кадра к кадру, как правило, невелика, можно добиться уменьшения обработки.Хорошая книга на эту тему - «Обнаружение столкновений в реальном времени».

Answer 4

Для простого ускорения вы можете отсортировать сначала по одной оси и пройти проверку на наличие столкновений на этой оси, прежде чем выполнять полную проверку ... Для каждой частицы вам нужно только смотреть дальше в массиве, пока не найдете тот, которыйне сталкивается с этой осью, то вы можете перейти к следующей.