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

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

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

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

Answer 2

Следите за ближайшими шарами -

Так же, как сортировка при вставке является оптимальной из-за минимального изменения в кадре, вы можете использовать это же свойство для отслеживания «соседей» шара

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

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

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

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

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

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

-Adam

Answer 3

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

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

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

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

Вам следует искать работы (книги, статьи, веб-сайты) о многотомном моделировании . Я не могу сказать, что может быть наиболее полезным для ваших целей; Если бы я был тобой, я бы начал с посещения хорошей университетской библиотеки и просмотра любых книг по этому предмету. Вы должны быть готовы к серьезной математике; если такие термины, как «множители Лагранжа», заставляют вас вспыхнуть в ульях, обратите внимание 8 ^). По сути, если вы пойдете по этому пути, вы, вероятно, выучите много математики, а не небольшое количество физики.

Answer 4

Как только шар полностью окружен другими шарами, прекратите рассматривать его для обнаружения столкновения. Просто глядя на скриншот, кажется, что нужно учитывать только «поверхностные» шары. Зачем проверять шар на 6 шаров глубиной, с которым ничто не может столкнуться? Это значительно уменьшит количество потенциальных столкновений.

Answer 5

Физические движки с жестким ядром используют векторизацию поплавков, что дает прирост x16 на текущем оборудовании, если повезет, и намного больше на специализированном оборудовании. Например, Larrabee может обрабатывать 1024 одновременных вычисления для общего увеличения математической обработки в x1024 (но это необходимо, потому что это также GPU)

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

Кроме того, генерация SIMD-кода в GCC отстой, я видел увеличение в 16 раз при использовании VC или IntelCompiler, это означает, что, если вы обратили внимание, GCC вообще не использовал никаких SIMD-инструкций!

Кроме того, эти предполагаемые столкновения в 10 тысячах не находятся в таком тесном соседстве, как вы, сим, так что это не сравнимо напрямую.

Answer 6

Я следил за разработкой Бурундук с самого начала, и, насколько я понимаю, ответ на оптимизацию лежит в структурах данных. (разве не всегда?) ...

Структура данных, используемая Бурундуком для достижения , это является Spacial Hash .

Answer 7

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

Answer 8

Simucal. Я понимаю, что отвечаю примерно на полтора года позже, но я все же хотел бы записать свои мысли.

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

Прежде всего,

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

Метод сетки отлично работает, и у меня может быть до 2000 шаров до отставания. Удаление и добавление шаров в сетку - это немного болезненно, но я так и реализовал это (сетка, в значительной степени основанная на списке шаров и позиции индекса каждого шара).

В будущем я хотел бы рассмотреть другие методы разделения и оптимизации проверок на столкновение.

Перекрытие : множество ответов здесь и в других местах предлагают рекурсивно исправлять столкновения в каждом кадре. Это на самом деле работает для меня до некоторой степени. При достаточно хорошей оптимизации вы можете избежать 2 или 3 проверок на кадр, что, по-видимому, предотвращает некоторую путаницу. Это не идеально, хотя. Я подозреваю, что повышение точности (с такими причудливыми словами, как интерполяция и лучшая интеграция) может помочь с дрожанием и перекрытием.

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

Если вы когда-нибудь что-нибудь узнаете, пожалуйста, обновите! Я работаю над точно такими же проблемами, и симуляторы мяча кажутся довольно популярными. Такой опыт может пригодиться, если мы когда-нибудь перейдем к физике твердого тела.

Спасибо.

Answer 9

Попробуйте это:

Разделите прямоугольник на N * M квадратов так, чтобы квадраты были немного шире, чем радиус шара. Возможно, было бы неплохо, чтобы квадраты перекрывали края вашего прямоугольника, а не аккуратно помещались в нем.

Создать массив из BitSet. Не используйте набор битов [M] [N], просто новый набор битов [M * ​​N] - небольшое умножение не повредит вам.

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

Беги по квадратам. Для каждой пары шаров в каждом квадрате отметьте эту пару как потенциальное столкновение. Для этого создайте набор битов и - учитывая, что у вас H шариков, а шарики A и B занимают один и тот же квадрат - установите биты A + B H и A H + B.

Обнаружение потенциальных коллизий теперь легко, потому что BitSet включает метод, который говорит: «найди мне следующий бит после того, который установлен». Помните, что каждый бит отсчитывается дважды, поэтому, когда бит Q определяется как установленный, обязательно сбросьте бит (Q%H)*H + (Q/H), который является другим битом пары.

В качестве альтернативы: вы можете легко свернуть этот массив коллизий. Столкновение между A и B - , учитывая, что A> B можно пометить установочным битом A * (A-1) / 2 + B. Преимущество в том, что вам не нужно заботиться об общем количестве шаров.

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

import java.util.BitSet;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class PairSet extends BitSet implements
    Iterable<PairSet.Pair> {
  public static class Pair implements Comparable<Pair> {
    public final int a;
    public final int b;

    private Pair(int a, int b) {
      if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
          "Pair(" + a + "," + b + ")"); }
      if (a > b) {
        this.a = a;
        this.b = b;
      } else {
        this.a = b;
        this.b = a;
      }
    }

    public String toString() {
      return "Pair(" + a + "," + b + ")";
    }

    public int hashCode() {
      return a * (a - 1) / 2 + b;
    }

    public boolean equals(Object o) {
      return o instanceof Pair
          && hashCode() == ((Pair) o).hashCode();
    }

    public int compareTo(Pair o) {
      return hashCode() - o.hashCode();
    }

  }

  PairSet() {}

  PairSet(BitSet z) {
    or(z);
  }

  PairSet(Iterable<Pair> z) {
    for (Pair p : z)
      set(p);
  }

  public void set(Pair p) {
    set(p.a, p.b);
  }

  public void clear(Pair p) {
    clear(p.a, p.b);
  }

  public void set(int a, int b) {
    if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
        "add(" + a + "," + b + ")"); }
    if (a > b) {
      set(a * (a - 1) / 2 + b);
    } else {
      set(b * (b - 1) / 2 + a);
    }
  }

  public void clear(int a, int b) {
    if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
        "add(" + a + "," + b + ")"); }
    if (a > b) {
      clear(a * (a - 1) / 2 + b);
    } else {
      clear(b * (b - 1) / 2 + a);
    }
  }

  public Iterator<Pair> iterator() {
    return new Iterator<Pair>() {
      int at       = -1;
      int triangle = 0;
      int a        = 0;

      public boolean hasNext() {
        return nextSetBit(at + 1) != -1;
      }

      public Pair next() {
        int nextat = nextSetBit(at + 1);
        if (nextat == -1) { throw new NoSuchElementException(); }
        at = nextat;
        while (triangle <= at) {
          triangle += a++;
        }
        return new Pair(a - 1, at - (triangle - a) - 1);

      }

      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }
}

И это будет хорошо отслеживать ваши потенциальные столкновения. Тогда псевдокод

SW = width of rectangle
SH = height of rectangle
R = radius of balls + 1 // +1 is a fudge factor.

XS = number of squares across = SW/R + 4; // the +4 adds some slop
YS = number of squares hight = SH/R + 4; // the +4 adds some slop

int sx(Point2D.Float p) // the square into which you put a ball at x
   // never returns a number < 1
 := (int)((p.x-R/2)/R) + 2;

int sy(Point2D.Float p) // the square into which you put a ball at y
   // never returns a number < 1
 := (int)((p.y-R/2)/R) + 2;

Bitset[] buckets = new BitSet[XS*YS];
{for(int i: 0; i<buckets.length; i++) bukets[i] = new BitSet();}

BitSet bucket(int x, int y) {return bucket[y*XS + x]}
BitSet bucket(Point2D.Float p) {return bucket(sy(p),sx(p));}

void move(int ball, Point2D.Float from, Point2D.Float to) {
  if bucket(from) == bucket(to) return;
  int x,y;
  x = sx(from); y=sy(from);
  for(int xx==-1;xx<=1; xx++)
  for(int yy==-1;yy<=1; yy++)
  bucket(sx+xx, sy+yy).clear(ball);
  x = sx(to); y=sy(to);
  for(int xx==-1;xx<=1; xx++)
  for(int yy==-1;yy<=1; yy++)
  bucket(sx+xx, sy+yy).set(ball);
} 

PointSet findCollisions() {
    PointSet pp = new PointSet();
    for(BitSet bb: buckets) {
    int a;
    int prev_a;
    for(prev_a = -1; (a = bb.nextSetBit(prev_a+1))!=-1; prev_a=a) {
      int b;
      int prev_b;
      for(prev_b = a; (b = bb.nextSetBit(prev_b+1))!=-1; prev_b=b) {
        pp.add(a,b);
      }
    }
    return pp;
}

Answer 10

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

• повернуть гравитацию до 0, чтобы не произошло много столкновений одновременно
• профилируйте ваш алгоритм обнаружения столкновений - если вы используете отсортированный массив шаров и анализируете только 6 или 7 ближайших, то у вас не должно быть никаких проблем ... это всего лишь 8000 проверок столкновений за цикл, если 800 шаров, что не очень много