Как я могу оптимизировать свой базовый симулятор физики?

Question

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

альтернативный текст http://i41.tinypic.com/2zr0oic.png
[Ссылка на увеличенную версию]

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

Проблема:

Прямо сейчас моя программа задыхается, если вы добавляете слишком много шаров (на моей машине она не может обрабатывать более 800). Если вы это сделаете, симуляция больше не будет реалистичной, и все шары перекрывают друг друга на дне.

Проблема в обнаружении столкновений. В наиболее наивном случае обнаружение столкновений является проблемой O (N ^ 2). Каждый шар проверяет каждый второй. Это очень быстро снижает производительность (даже после 100 шаров вы будете делать 10 000 проверок столкновений за цикл).

Если вы посмотрите здесь, вы можете увидеть скриншот, где я добавил несколько сотен шаров. Симулятор не может идти в ногу, и они начинают перекрывать друг друга.

альтернативный текст http://i41.tinypic.com/2nsnuqd.png
[Ссылка на увеличенную версию]

В настоящее время я обнаруживаю столкновения, ища перекрывающиеся шары. Если я нахожу два шарика, которые перекрывают друг друга, я разделяю их по минимальному расстоянию перевода (MTD) или раздвигаю их. Затем я использую простое физическое уравнение, чтобы скорректировать их импульсные векторы, и после столкновения они движутся в разных направлениях.

Это прекрасно работает, за исключением случаев, когда слишком много шаров, минимальное расстояние перевода становится заметным. Они начинают перекрывать друг друга в больших количествах и постоянно толкают друг друга на дне. Чем хуже я увеличиваю «гравитацию», тем хуже. Давление на них увеличивается, а количество сжимаемых / перекрывающих друг друга элементов увеличивается.

Опять же, у меня нет проблем, пока я не наберу значительное количество N шаров.

Текущий метод оптимизации :

Обнаружение столкновения -
Очистка и удаление - (иначе. Сортировка и очистка)

Я использую сортировку вставки на своих шарах каждый цикл цикла вдоль их оси x. Из-за характера сортировки вставок я могу использовать временную когерентность моего симулятора. Кадр за кадром, позиции шаров меняются незначительно, так что сортировке не нужно много работать. Это приводит к тому, что время линейной сортировки амортизируется во время O (N) или линейно, а не в среднем времени O (N ^ 2).

Поскольку шары отсортированы, я делаю пару предварительных проверок во втором цикле перед проверкой столкновений. Теперь мне нужно только проверить шары рядом друг с другом (потому что они отсортированы вдоль оси x), и я вырываюсь из второй петли каждый раз, когда проверяю шар против другого шара, xmin которого больше, чем xmax текущего шара , Так что он пропускает тысячи проверок.

Когда я это реализовал, это принесло огромное улучшение скорости. Тем не менее, я все еще хотел бы иметь возможность обрабатывать более 600-800 мячей. Я читал о Physics Engines, которые легко справляются с обнаружением столкновений между 10k объектами одновременно, поэтому я хотел бы думать, что я смог бы достичь 1-2k с небольшой работой.

После запуска profiler выяснилось, что Collision Detection потреблял около 55% моего времени, а рендеринг - около 45%. Итак, это мои две самые дорогие расходы.

---

Вопрос:

Можете ли вы придумать какие-нибудь лучшие алгоритмы или методы, которые позволили бы моему симулятору обрабатывать больше шаров?

---

Соответствующий код:

Весь проект:

svn checkout http://simucal -projects.googlecode.com / svn / ballbounce / trunk /

или нажмите здесь , чтобы просмотреть файлы вручную в браузере.

Разделы интересов:

• Pastebin: checkCollisions () - w / Sweep and Prune
• Pastebin: resolCollision () - дорогостоящая проверка и разрешение коллизий, если они еще не удалены Sweep and Prune.
• Pastebin: render () - Один только рендеринг съедает около 45% моего времени.

Answer 1

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

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

Answer 2

Я сделал что-то очень похожее на iPhone, и он использует акселерометр, позволяющий наклонять шары, и сенсорный экран, чтобы добавлять и удалять шары. Он может выдержать не менее 30 шаров, прежде чем он начнет заметно тормозить.

Одна из оптимизаций, которую я сделал на ранних этапах, - это математическая математика. Первоначально у меня был отдельный «векторный» класс, и он мог обрабатывать только 10-12 шаров, прежде чем превратился в слайд-шоу. Профилирование показало, что оно тратит много времени на выделение и освобождение векторов.

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

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

Answer 3

Я думаю, что пришло время измерить производительность, чтобы проверить, где на самом деле узкое место. Вам не нужно было делать измерения раньше, потому что была очевидная проблема алгоритма. Теперь еще есть возможности для улучшения алгоритма, но вы уверены, что это самая большая проблема? Измерьте, сколько сравнений вы делаете за мяч сейчас. Это что-то маленькое? Если это так, то алгоритмические изменения могут быть не лучшим следующим шагом.

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