¿Cómo manejar la detección de colisión con píxeles perfectos con rotación?

8

¿Alguien tiene alguna idea de cómo lograr la detección de colisión rotatoria de píxeles perfectos con Bitmaps en Android? ¿O en general para el caso? Actualmente tengo matrices de píxeles, pero no sé cómo manipularlas en función de un número arbitrario de grados.

SECADO
fuente

Respuestas:

11

No estoy familiarizado con Android, así que no sé qué herramientas tiene a su disposición, pero puedo decirle una forma de implementar esto en términos generales. Lo fácil que será dependerá de lo que Android le proporcione. Necesitarás matrices o al menos simplificarán mucho los cálculos.

Para empezar, haga una verificación de colisión en el cuadro delimitador y regrese de inmediato si no colisionan para evitar nuevos cálculos. Eso es lógico porque si los cuadros delimitadores no chocan, se garantiza que tampoco habrá píxeles colisionando.

Luego, si se necesita una verificación de colisión perfecta de píxeles, entonces el punto más importante es que debe realizar esa verificación en el mismo espacio . Esto se puede hacer tomando cada píxel del sprite A, aplicando una serie de transformaciones para llevarlos al espacio local del sprite B, y luego verifica si choca con algún píxel en esa posición en el sprite B. Se produce una colisión cuando ambos píxeles marcados son opacos.

Entonces, lo primero que necesitas es construir una matriz mundial para cada uno de los sprites. Probablemente hay tutoriales en línea que le enseñan cómo crear uno, pero básicamente debería ser una concatenación de algunas matrices más simples en el siguiente orden:

Translation(-Origin) * Scale * Rotation * Translation(Position)

La utilidad de esta matriz es que al multiplicar un punto en el espacio local, y, por ejemplo, si obtiene los píxeles utilizando un método como bitmap.getPixelAt(10,20)10,20 se define en el espacio local, la matriz mundial correspondiente lo moverá al espacio mundial:

LocalA * WorldMatrixA -> World
LocalB * WorldMatrixB -> World

Y si invierte las matrices, también puede ir en la dirección opuesta, es decir, transformar los puntos del espacio mundial en cada uno de los espacios locales del sprite, según la matriz que haya utilizado:

World * InverseWorldMatrixA -> LocalA
World * InverseWorldMatrixB -> LocalB

Entonces, para mover un punto desde el espacio local del sprite A al espacio local del sprite B , primero lo transforma usando la matriz mundial del sprite A, para obtenerlo en el espacio mundial, y luego usando la matriz del mundo inverso del sprite B , para ingresarlo espacio local del sprite B:

LocalA * WorldMatrixA -> World * InverseWorldMatrixB -> LocalB

Después de la transformación, verifica si el nuevo punto cae dentro de los límites del sprite B, y si lo hace, verifica el píxel en esa ubicación al igual que lo hizo con el sprite A. Por lo tanto, todo el proceso se convierte en algo así (en pseudocódigo y no probado) :

bool PixelCollision(Sprite a, Sprite B)
{
    // Go over each pixel in A
    for(i=0; i<a.Width; ++i)
    {
        for(j=0; j<a.Height; ++j)
        {
            // Check if pixel is solid in sprite A
            bool solidA = a.getPixelAt(i,j).Alpha > 0;

            // Calculate where that pixel lies within sprite B's bounds
            Vector3 positionB = new Vector3(i,j,0) * a.WorldMatrix * b.InverseWorldMatrix;

            // If it's outside bounds skip to the next pixel
            if(positionB.X<0 || positionB.Y<0 || 
               positionB.X>=b.Width || positionB.Y>=b.Height) continue;

            // Check if pixel is solid in sprite B
            bool solidB = b.getPixelAt(positionB.X, positionB.Y).Alpha > 0;

            // If both are solid then report collision
            if(solidA && solidB) return true;
        }
    }
    return false;
}
David Gouveia
fuente
1
Me gusta porque es elegante, pero el uso de matrices como esta, multiplicando una matriz de 3x3 por píxel por fotograma, introducirá algunas penalizaciones de rendimiento bastante serias para cualquiera, excepto los mapas de bits más pequeños, especialmente en la mayoría de los dispositivos Android.
3Dave
2
@DavidLively De hecho, será un proceso costoso computacionalmente. Y creo que incluso con los cálculos de la matriz que se desenrollan en cálculos regulares con trigonometría, posiblemente omitiendo la escala si no se usa, seguiría siendo más o menos lo mismo. Puede haber otras soluciones, pero no se me ocurre ninguna. En última instancia, la mejor solución sería considerar si la detección de colisión perfecta de píxeles es realmente necesaria. Y algunos juegos que usan colisiones de píxeles perfectos (como los primeros juegos de Sonic) abstraen a los personajes en una serie de puntos de colisión.
David Gouveia
buen punto; Estoy arruinando mi cerebro tratando de encontrar una solución alternativa que no implique restar mapas de bits y buscar picos. Probablemente haya una oportunidad para un artículo en esto en alguna parte. :) Mantra: óptimo vs suficiente ... óptimo vs suficiente ..
3Dave
Muchas gracias, esa es una gran explicación. Actualmente tengo configurada la detección de colisión del cuadro delimitador y, si eso ocurre, verifico la superposición de píxeles entre los dos mapas de bits, pero solo en el rectángulo superpuesto. Todo esto funciona muy bien y no requiere demasiado procesador. El problema ocurre cuando giro la imagen. Los píxeles en sí no se giran en el mapa de bits. Solo estoy dibujando una imagen rotada. Entonces, cuando continúo verificando la colisión de píxeles, todavía está usando los píxeles antiguos. Me gusta lo que dijiste sobre la asignación de píxeles a coordenadas mundiales. Esto puede muy bien ser lo que necesito hacer. ¡¡¡Gracias!!!
DRIFTy
+1 Siempre me he preguntado cómo funciona el algoritmo, gracias @DavidGouveia
Vishnu
2

Si bien la respuesta de David Gouveia parece correcta, no es la mejor solución desde el punto de vista del rendimiento. Hay varias optimizaciones importantes que debes hacer:

  1. clasifique y evite verificaciones innecesarias verificando primero con una simple colisión circular: para obtener el centro y el radio de sus sprites en cualquier rotación, obtenga las coordenadas mínimas y máximas x e y de los 4 vértices (ya rotados): luego puede construir Un círculo que se cierra en el sprite por:

    centro = max_x-min_x / 2, max_y-min_y / 2

    radio = max (max_x-min_x, max_y-min_y)

  2. ahora no debería tener demasiados candidatos para verificar rasterizando las imágenes ya transformadas (rotadas) básicamente utilizando un algoritmo de mapeo de textura afín simple . Básicamente, realiza un seguimiento de 4 líneas por sprite rasterizado: 2 líneas que van desde el vértice a hasta los siguientes vértices de su caja girada (byc) 2 líneas que van en "espacio de mapa de bits" desde el vértice u1 / v1 hasta los siguientes vértices u2 / v2 y u3 / v3: Nota: busqué en Google esta imagen y muestra un triángulo, sus cajas son solo dos triángulos. Es vital para este algoritmo dibujar líneas horizontales (es por eso que se llama " rasterizador ") para evitar "agujeros" dentro del mapa de bits debido a errores de redondeo. Al calcular las líneas con un algoritmo de Bresenham, necesita para cada píxel solo 4 adiciones y 4 comparaciones (y, a veces, dos adiciones adicionales, dependiendo de la pendiente). Lo que debe hacer es escribir su propio mapeador de texturas poligonales, sin la costosa (y difícil de optimizar) corrección 3d. mapa de texturas afines

  3. puede reducir fácilmente la resolución de los mapas de bits de colisión (por ejemplo, por el factor 2) y ahorrar aún más tiempo. Una verificación de colisión en la mitad de la resolución debe ser imperceptible.

  4. Si está utilizando aceleración de gráficos, podría ser posible usar algún tipo de verificación de Buffer acelerado por HW (¿plantilla?) Para evitar codificar el rasterizador usted mismo.

El problema principal es: Java no es muy rápido para acceder a los datos de mapa de bits almacenados en una matriz 2D. Recomendaría almacenar los datos en una matriz unidimensional para evitar al menos 1 comprobación indexOutOfBounds para cada acceso. Utilice también las dimensiones de potencia de 2 (como 64x64, 128x128, etc. Con esto puede calcular el desplazamiento a través de desplazamiento de bits y no multiplicación). ¡También puede optimizar el segundo acceso de textura para realizarlo solo si el primero tiene valor! = 0 (transparente)

Todos estos problemas se resolvieron en los motores de representación de software, podría ser útil analizar el código fuente

Peter Parker
fuente