para name metatags keywords google etiquetas ejemplos description crear content optimization physics collision-detection

optimization - name - ¿Cómo puedo optimizar mi simulador básico de física?



meta name keywords (13)

He escrito un modelador de física simple que me permite rebotar bolas alrededor de la pantalla. Puede hacer clic y arrastrar para lanzar una pelota, o puede generar bolas de cientos a la vez y verlos interactuar entre sí.

texto alternativo http://i41.tinypic.com/2zr0oic.png
[Enlace a una versión más grande]

Ha sido un pequeño programa divertido para trabajar y quiero llevarlo más lejos si puedo. Sé que dicen que la optimización pre-madura es la raíz de todos los males, pero estoy empezando a tocar las barreras de rendimiento reales y quiero saber si alguien con experiencia en el desarrollo de juegos / simuladores puede ayudarme.

Problema:

En este momento, mi programa se ahoga si agrega demasiadas bolas (parece que no puede manejar más de 800 en mi máquina). Si lo haces, la simulación ya no es realista y todas las bolas se superponen entre sí en la parte inferior.

El problema está en la detección de colisiones. En el caso más ingenuo, la detección de colisión es un problema O (N ^ 2). Cada bola controla cada otra bola. Esto obtiene un rendimiento pobre bastante rápido (después de incluso 100 bolas, harás controles de colisión de 10k por ciclo de bucle).

Si miras aquí, puedes ver una captura de pantalla de donde he agregado varios cientos de bolas. El simulador no puede mantener el ritmo y comienzan a superponerse entre sí.

texto alternativo http://i41.tinypic.com/2nsnuqd.png
[Enlace a una versión más grande]

Actualmente, detecto colisiones buscando bolas superpuestas. Si encuentro dos bolas superpuestas, las separo por su distancia de traducción mínima (MTD) o las aparto. Luego utilizo una ecuación física simple para ajustar sus vectores de impulso y luego van en diferentes direcciones después de la colisión.

Funciona muy bien, excepto si hay demasiadas bolas, la distancia mínima de traducción se hace notable. Comienzan a superponerse en grandes cantidades y se empujan constantemente en la parte inferior. Se pone peor cuanto más aumento la "gravedad". La presión sobre ellos aumenta y la cantidad que se comprimen / se superponen entre sí aumenta.

De nuevo, no tengo problemas hasta que golpeé una cantidad considerable de N bolas.

Método de optimización actual :

Detección de colisiones -
Barrer y podar - (también conocido como ordenar y barrer)

Utilizo un tipo de inserción en mis bolas cada ciclo de bucle a lo largo de su eje x. Debido a la naturaleza de Insertion Sort, puedo aprovechar la coherencia temporal de mi simulador. Cuadro a cuadro, las posiciones de las bolas cambian solo ligeramente, por lo que el tipo no tiene mucho trabajo por hacer. Esto hace que el tiempo de ejecución amortiguado de Linear Sorts sea O (N) o lineal en lugar de su tiempo de ejecución promedio de O (N ^ 2).

Como las bolas están clasificadas, hago un par de comprobaciones previas en mi segundo ciclo antes de verificar las colisiones. Ahora solo tengo que comprobar las bolas cerca unas de otras (porque están ordenadas a lo largo del eje x), y salgo del segundo ciclo cada vez que miro una bola contra otra bola cuyo xmin es mayor que el xmax de la bola actual . Por lo tanto, omite miles de comprobaciones.

Cuando implementé esto, trajo una gran mejora de velocidad. Sin embargo, aún me gustaría poder manejar más de 600-800 bolas. He leído sobre los motores de física que manejan fácilmente la detección de colisión entre objetos de 10k simultáneamente, así que me gustaría pensar que podría alcanzar 1-2k con un poco de trabajo.

Después de ejecutar un generador de perfiles , descubrí que la detección de colisiones consumía aproximadamente el 55% de mi tiempo, mientras que el procesamiento se comía un 45%. Entonces, estos son mis dos costos más caros.

Pregunta:

¿Puedes pensar en algoritmos o técnicas mejores que permitan que mi simulador sea capaz de manejar más bolas?

Código relevante:

Proyecto entero:

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

o haga clic http://simucal-projects.googlecode.com/svn/ballbounce/trunk/ para buscar los archivos manualmente en su navegador.

Secciones de interés:

A menos que me haya perdido algo, las bolas superpuestas son el resultado de un error, no de un código ineficiente. Un código ineficiente simplemente provocaría que la animación se ejecute lentamente.

Sugeriría que el problema se deba al enfoque iterativo de la detección de colisión de bola a bola. Actualmente parece que solo estás considerando el resultado de una colisión de bola a bola. Cuando varias bolas tocan una sola bola, los resultados parecen indefinidos, y las posibilidades de que esto ocurra aumentan con la gravedad o el número de bolas.

Creo que es hora de medir el rendimiento para verificar dónde está realmente el cuello de botella. No fue necesario hacer la medición antes porque había un problema de algoritmo obvio. Ahora todavía hay espacio para mejorar el algoritmo, pero ¿está seguro de que ese es el mayor problema? Mida cuántas comparaciones hace por pelota ahora. ¿Es algo pequeño? Si es así, los cambios algorítmicos pueden no ser el mejor paso siguiente.

Compare cuánto tiempo lleva determinar la posición de cada bola en comparación con el tiempo que lleva dibujarlas. Podría ser el último es ahora el cuello de botella, y debe centrar sus esfuerzos en el código de representación en lugar del motor de física.

Está empezando a sonar casi como un fluido ligeramente compresible en un campo gravitacional en este punto. Las ideas de dinámica de fluidos computacionales, usando un punto de vista euleriano, podrían ayudar. Si crea una cuadrícula con una escala tal que solo una bola a la vez pueda ocupar cada celda, puede escribir la conservación de la masa, el momento y los balances de energía para cada celda y rastrear el movimiento de las bolas de esa manera.

He estado siguiendo el desarrollo de Chipmunk desde su inicio y, desde mi entendimiento, la respuesta a la optimización está en las estructuras de datos. (¿no es así siempre?) ...

La estructura de datos que Chipmunk usa para lograr this es un Spacial Hash .

He hecho algo muy parecido a esto en el iPhone, y usa el acelerómetro para permitirle inclinar las bolas, y la pantalla táctil para agregar y eliminar bolas. Puede manejar al menos 30 bolas antes de que empiece a atascarse notablemente.

Una optimización que hice al principio es alinear las matemáticas. Originalmente tenía una clase de "vector" separada, y solo podía manejar 10-12 bolas antes de que se convirtiera en una presentación de diapositivas. La creación de perfiles demostró que dedicaba mucho tiempo a asignar y desasignar vectores.

Además, no separé las bolas una vez que golpean, simplemente reboto los vectores. Parece que nunca se superponen, y cuando lo hacen es bastante obvio que es porque todos se atascaron en la parte inferior.

Todavía no estoy listo para lanzar el código, tengo que pulir algo y luego lo pondré en la tienda.

La forma más simple es no probar colisiones Objeto vs Objeto, llenar una matriz con el punto central de cada bola. Luego, desde cada centro escanee un cuadrado de tamaño 4 * radio centrado en ese punto (puede optimizarlo un poco al no usar un cuadrado, a expensas de hacer que el código sea más complejo). Si hay otro centro en este cuadrado, solo entonces verifica si están dentro de un radio de 2 * uno del otro (y por lo tanto colisionan). Puede optimizar aún más esto reduciendo la resolución y redondeando la posición de la bola, reduciendo la cantidad de controles que debe hacer.

Otra forma es dividir el espacio en una cuadrícula y almacenar los objetos en las regiones de la cuadrícula. Solo necesita comprobar las colisiones entre objetos en cuadrículas adyacentes.

Los motores de física de núcleo duro usan vectorización de flotadores, lo que da un impulso x16 en el hardware actual si tiene suerte, y mucho más en hardware especializado. Larrabee, por ejemplo, puede manejar 1024 cálculos simultáneos para un impulso a la x1024 en el procesamiento matemático (pero lo necesita porque también es GPU)

Todavía no he mirado el código, pero ¿está utilizando optimizaciones matemáticas como la raíz cuadrada rápida y los absolutos binarios, o el cambio de signo de bit a bit? Estas cosas por sí solas no ayudan, pero cuando se mezclan grandes cantidades de datos, estas técnicas redirigen algunas operaciones matemáticas a la CPU principal, liberando la FPU, lo que básicamente le proporciona un mayor rendimiento.

Además, la generación de código SIMD de GCC literalmente es una mierda, he visto un aumento de hasta 16 veces usando VC o IntelCompiler, es decir, si has prestado atención, ¡ese GCC no estaba usando ninguna instrucción SIMD en absoluto!

Además, esas llamadas colisiones de 10k no están tan cerca como tú, por lo que no es directamente comparable.

Mantenga un registro de las bolas cercanas -

Al igual que el tipo de inserción es óptimo debido al cambio mínimo por fotograma, puede usar la misma propiedad para mantener el seguimiento de los "vecinos" de la pelota.

Cada pelota solo puede interactuar con otras 6 bolas como máximo. Probablemente pueda ejecutar un algoritmo cada 10 fotogramas aproximadamente para saber qué vecinos tiene cada bola, y luego usar esa información para los siguientes diez cuadros para calcular las colisiones reales.

También puede seguir los vectores de cada bola, dibujar líneas virtuales y ver qué líneas se cruzan en los siguientes 3 a 5 cuadros y solo calcular las colisiones posibles (aunque pocas sucederán debido al tiempo).

Del mismo modo que clasificaste por el eje x, puedes agrupar bolas en subdivisiones dentro de la ventana principal. Cuando una bola está dentro de una subdivisión por al menos un diámetro de bola, solo necesita mirar las bolas en la misma subdivisión. Si está más cerca de uno o dos bordes, necesita mirar una o dos subdivisiones más, pero debería haber menos cálculos.

Además, esas subdivisiones se pueden ubicar dinámicamente, por lo que la subdivisión promedio tiene solo 100 bolas, no es necesario tener subdivisiones del mismo tamaño con diferentes números de bolas.

Dependiendo de qué tan concurrida esté una subdivisión (bolas por unidad cuadrada), puede probar diferentes algoritmos: una caja escasamente llena solo necesita cálculos vectoriales para predecir colisiones, mientras que una subdivisión densamente compacta solo necesita algún tipo de cálculo hexagráfico optimizado. Las cajas dispersas pueden no necesitar detección de colisión para muchos marcos (ya que la superposición no se notará tanto como en los cuadros densamente poblados).

La densidad de energía de una caja determinada se puede determinar: una caja muy dispersa con bolas de baja energía necesita menos cálculos de colisión que una caja dispersa con mucha energía.

-Adán

Prueba esto:

Divida su rectángulo en cuadrados N * M, de modo que los cuadrados sean ligeramente más anchos que el radio de una bola. Puede ser una buena idea hacer que los cuadrados se superpongan a los bordes de su rectángulo, en lugar de encajar perfectamente dentro de él.

Haz una matriz de BitSet. No use un Bitset [M] [N], solo un Bitset nuevo [M * ​​N] - una pequeña multiplicación no le hará daño.

Identifica cada pelota con un número. Cuando coloque una bola en un lugar, coloque el bit en el conjunto de bits para ese cuadrado y los 8 cuadrados a su alrededor (para hacerlo más fácil, extienda su matriz de cuadrados de modo que se extiendan uno más allá del borde del rectángulo; de esa manera no tiene que cortar)

Corre a través de los cuadrados. Para cada par de bolas en cada cuadrado, marque ese par como una posible colisión. Para hacer esto, crea un conjunto de bits y, dado que tienes H bolas y las bolas A y B ocupan el mismo cuadrado, establece los bits A + B H y A H + B.

Perder las potenciales colisiones es ahora fácil, porque BitSet incluye un método que dice "encuéntrame el siguiente bit después de este que está configurado". Recuerde que cada bit se cuenta doblemente, de modo que cuando se detecta que el bit Q está siendo configurado, asegúrese de desactivar el bit (Q%H)*H + (Q/H) - que es el otro bit del par.

Alternativamente: puede colapsar ese conjunto de colisiones con bastante facilidad. Una colisión entre A y B, dado que A> B puede marcarse configurando el bit A * (A-1) / 2 + B Esto tiene la ventaja de que no necesita preocuparse por el número total de bolas.

En realidad: olvídalo. solo use esta clase que escribí como ejercicio:

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(); } }; } }

Y eso hará un buen seguimiento de tus posibles colisiones. El psudeocode es entonces

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; }

Simucal. Me doy cuenta de que estoy respondiendo aproximadamente un año y medio demasiado tarde, pero aún me gustaría escribir mis pensamientos.

Hace poco escribí una pregunta sobre el mismo problema que la superposición de bolas , que en realidad utilizaba el mismo algoritmo que usaste. No vi tu pregunta cuando la envié, así que es malo.

Ante todo,

La optimización : utilizo un sistema de partición de cuadrícula simple donde toda la pantalla se divide en celdas que tienen el ancho y la altura del diámetro de la bola más grande. La grilla hace un seguimiento de la celda en la que se encuentra cada bola, así que cuando necesita una prueba de colisión, uso una función nearBy () que llena una lista de las ID de cada bola que está en las celdas adyacentes a la que estoy revisando .

El método de cuadrícula funciona muy bien, y puedo tener hasta 2000 bolas antes de rezagarme. Sin embargo, quitar y agregar bolas a la grilla es un poco doloroso, pero así es como lo implementé (la grilla se basa en gran medida en una lista de bolas y en la posición de índice de cada bola).

En el futuro, me gustaría buscar otros métodos de particionar y optimizar las verificaciones de colisión.

La superposición : muchas de las respuestas aquí y en otros lugares sugieren que se corrigen recursivamente las colisiones en cada cuadro. Esto realmente funcionó para mí hasta cierto punto. Con una optimización lo suficientemente buena, podría salirse con 2 o 3 cheques por cuadro, lo que parece prevenir algunos de los problemas superpuestos. Sin embargo, no es perfecto. Sospecho que mejorar la precisión (con palabras elegantes como la interpolación y una mejor integración) puede ayudar con el tintineo y la superposición.

Pensé en ordenar los controles de colisión en función de la prioridad (los más altos son los que tocan las paredes, luego los que tocan los que están un paso abajo en la lista de prioridades, etc.), y tener esto en cuenta en la distancia de traducción mínima. MyPhysicsLab habla sobre el manejo de múltiples colisiones simultáneas, pero todavía tengo que investigar eso.

Si alguna vez encuentras algo, ¡por favor actualiza! Estoy trabajando en exactamente los mismos problemas, y los simuladores de bolas parecen ser bastante populares. Este tipo de experiencia puede ser útil si tuviéramos que pasar a la física corporal rígida.

Gracias.

Su principal problema es el algoritmo de resolución de colisiones: puede acelerar el dibujo y la detección de colisiones, pero eso no evitará que sus bolas se colapsen entre sí. El problema que tiene es mucho más difícil de resolver limpiamente de lo que parece; sin embargo, es posible hacerlo bien.

En su caso, en la configuración que falla (big bin-o''-balls) sus objetos realmente deberían deslizarse uno contra el otro, sin rebotar. El deslizamiento es una restricción continua, que es diferente del tipo de restricciones basadas en impulsos que maneja su implementación.

Lo más simple que puede hacer para evitar el colapso es volver a verificar todos los objetos en colisión para asegurarse de que no se están interpenetrando después de la manipulación de la colisión, lo que puede iterar tantas veces como sea necesario hasta que ninguno viole las restricciones. Por supuesto, esto llevará más tiempo, posiblemente mucho más tiempo (e incluso plantea la posibilidad de un ciclo infinito, aunque tal vez no en esa situación particular ...).

Existen buenos algoritmos que harán que su simulación se comporte, pero son más complicados que su sistema basado en impulsos. En general, implican considerar cuerpos mutuamente interactivos (como las bolas en el contenedor) como un todo, y ajustar su configuración colectiva para satisfacer sus limitaciones mutuas.

Debe buscar trabajos (libros, documentos, sitios web) sobre la simulación multicuerpo . No puedo decir cuál es la más útil para sus propósitos; si yo fuera usted, comenzaría visitando una buena biblioteca de la universidad y mirando los libros que tienen sobre el tema. Deberías estar preparado para algunas matemáticas serias; si términos como "multiplicadores de Lagrange" te hacen explotar en colmenas, mira hacia afuera 8 ^). Básicamente, si sigues esta ruta, es probable que aprendas muchas matemáticas y no poca cantidad de física.

Tal vez el problema es que hay tantas interacciones como las bolas "se acumulan". Si estuviera haciendo esto, probaría lo siguiente:

  • cambia la gravedad a 0 para que muchas colisiones no estén ocurriendo simultáneamente
  • perfila tu algoritmo de detección de colisión - si estás utilizando una matriz ordenada de bolas y solo analizas las 6 o 7 que están más cercanas, entonces no deberías tener ningún problema ... eso es solo 8000 o más controles de colisión por ciclo asumiendo 800 bolas, que no es muy muchos

Una vez que una pelota está completamente rodeada por otras bolas, deténgala para detectar colisiones. Solo al mirar su captura de pantalla parece que solo se deben considerar las bolas "superficiales". ¿Por qué comprobar la pelota de 6 bolas de profundidad con la que nada puede colisionar? Esto reduciría en gran medida el número de posibles colisiones.