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

Ответ 1

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

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

Ответ 2

Следите за соседними шарами -

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

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

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

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

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

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

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

-Adam

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

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

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

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

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

Ответ 9

Попробуйте следующее:

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

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

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

Запустите квадраты. Для каждой пары шаров в каждой квадратной метке эта пара является потенциальным столкновением. Для этого создайте битсет и - учитывая, что у вас есть H-шары, а шары A и B занимают один и тот же квадрат - устанавливают биты A + BH и AH + 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();
      }
    };
  }
}

И это будет приятно отслеживать ваши потенциальные столкновения. Тогда 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;
}

Ответ 10

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

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

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

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

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

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

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

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

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

Спасибо.

Ответ 11

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

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

Ответ 12

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

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

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

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

Ответ 13

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

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