Как я могу оптимизировать свое основное средство моделирования физики?

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

alt text
[Свяжитесь с увеличенной версией]

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

Проблема:

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

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

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

alt text
[Свяжитесь с увеличенной версией]

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

Это работает отлично, кроме того, если существует слишком много шаров, минимальное расстояние перевода становится примечательным. Они начинают накладываться большим объемом и постоянно толкают друг друга в нижней части. Это ухудшается, больше я увеличиваю "силу тяжести". Давление на них увеличено и сумма, они сжаты/перекрыты друг друга увеличения.

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

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

Обнаружение коллизий -
Развертка и чернослив - (иначе. Вид и Развертка)

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

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

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

После выполнения профилировщика это вышло, который Обнаружение коллизий съедало выше на приблизительно 55% моего времени, в то время как рендеринг съедал выше на приблизительно 45%. Так, это мои два самых дорогих затрат.


Вопрос:

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


Соответствующие нормы:

Весь проект:

контроль svn http://simucal-projects.googlecode.com/svn/ballbounce/trunk/

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

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

  • Pastebin: checkCollisions () - w/Развертка и Чернослив
  • Pastebin: resolveCollision () - Дорогая истинная проверка коллизии и разрешение, если все еще не удалено Разверткой и Черносливом.
  • Pastebin: рендеринг () - один только Рендеринг съедает выше на приблизительно 45% моего времени.

33
задан Glorfindel 14 July 2019 в 07:06
поделиться

12 ответов

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

Иначе, должен разделить Ваше пространство на сетку и хранить объекты в регионах сетки. Только необходимо проверить на коллизии между объектами в смежных сетках.

13
ответ дан 27 November 2019 в 18:36
поделиться

Отслеживайте соседние шары -

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

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

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

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

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

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

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

-Adam

9
ответ дан 27 November 2019 в 18:36
поделиться

Механизмы физики ядра используют векторизацию плаваний, которая дает повышение x16 на текущих аппаратных средствах, если удачный и путь больше на специализированных аппаратных средствах. Larrabee, например, может обработать 1 024 одновременных вычисления для повышения theretocal x1024 математической обработки (но ему нужно это, потому что это - также GPU)

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

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

Также те allegded 10k коллизии не находятся на таком близком расстоянии как Вы sim, таким образом, это не непосредственно сопоставимо.

4
ответ дан 27 November 2019 в 18:36
поделиться

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

4
ответ дан 27 November 2019 в 18:36
поделиться

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

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

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

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

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

4
ответ дан 27 November 2019 в 18:36
поделиться

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

2
ответ дан 27 November 2019 в 18:36
поделиться

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

использование Бурундука структуры данных для достижения это Пространственный Хеш .

2
ответ дан 27 November 2019 в 18:36
поделиться

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

  • сила тяжести поворота к 0 так, чтобы много коллизий не происходили одновременно
  • , представляет Ваш алгоритм обнаружения коллизии - если Вы используете сортированный массив шаров и только анализируете 6 или 7, которые являются ближайшими, затем у Вас не должно быть проблем... это - только приблизительно 8000 проверок коллизии на цикл, принимающий 800 шаров, который не является очень многими
1
ответ дан 27 November 2019 в 18:36
поделиться

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

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

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

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

0
ответ дан 27 November 2019 в 18:36
поделиться

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

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

0
ответ дан 27 November 2019 в 18:36
поделиться

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

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

Делают массив BitSet. Не используйте Bitset[M][N], просто новый Bitset[M*N] - немного умножения не собирается причинять Вам боль.

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

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

Looing через потенциальные коллизии теперь легок, потому что 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();
      }
    };
  }
}

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

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;
}
1
ответ дан 27 November 2019 в 18:36
поделиться

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

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

0
ответ дан 27 November 2019 в 18:36
поделиться
Другие вопросы по тегам:

Похожие вопросы: