Python: Алгоритм наилучшего столкновения частиц / треугольника - PullRequest
Новая
       69

Python: Алгоритм наилучшего столкновения частиц / треугольника

1 голос
/ 24 ноября 2011

Я начинаю работать над этим движком частиц для Blender в Python: http://www.youtube.com/watch?v=uoK4QV3jg58&feature=channel_video_title

Все данные обрабатываются моим сценарием, Blender просто для визуального. Моя проблема на данный момент, в видео выше, я вычисляю расстояние между каждой частицей для всех частиц, чтобы определить, сталкиваются ли они друг с другом.

Я начинаю читать о:

  • Octree
  • kdTree
  • BVHTree
  • AABBtree
  • ... и многие другие

Kdtree, кажется, очень эффективен для поиска ближайших соседей, но только для статического облака. Мои частицы всегда движутся и поэтому должны регенерировать kdTree на каждой итерации, что, я думаю, отнимает слишком много времени. Я читал много игр, использующих дерево AABB. Я немного растерялся ... Я не знаю, что выбрать. Что я хочу это:

  • Обнаружение столкновения между очень большим количеством частиц (250 000 и более)
  • Не нужно быть в реальном времени (во всяком случае, с 250 000 частиц это не реально). 20 минут на кадр для 2 миллионов частиц для меня не проблема.
  • Мои частицы - это всегда сферы
  • Обнаружение столкновения между частицами и многоугольными объектами
  • Необходим алгоритм для вычисления расстояний (избегая таких вещей, как вычисление всех частиц для каждой частицы или многоугольника, даже если они далеко)
  • Мои частицы являются динамическими, а мои объекты многоугольника могут быть динамическими или статическими.

Если кто-нибудь подскажет, что является лучшим предположением и где я могу найти документацию по Python и пример для нее.

1 Ответ

0 голосов
/ 24 ноября 2011

Если «все динамично», вы теряете преимущества структур данных с быстрым поиском и медленным вставлением.

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

Сказать, что «все движется» без каких-либо дополнительных ограничений, сродни утверждению, что данные полностьюслучайный от итерации к итерации;следовательно, ключом к вашей проблеме является определение того, можно ли повторно использовать какие-либо вычисления из предыдущей итерации.Это будет диктовать соответствующую структуру данных и алгоритм.

...