Detección de colisión perfecta de píxeles en Canvas HTML5

Question

Quiero verificar una colisión entre dos Sprites en canvas HTML5. Entonces, por el bien de la discusión, supongamos que ambos sprites son objetos IMG y una colisión significa que el canal alfa no es 0. Ahora ambos de estos sprites pueden tener una rotación alrededor del centro del objeto pero ninguna otra transformación en caso de que esto lo haga cualquier más fácil.

Ahora la solución obvia que se me ocurrió que sería la siguiente:

• calcular la matriz de transformación, tanto para
• encontrar una estimación aproximada de la zona en la que el código debe probar (como desplazamiento de ambos + espacio extra calculado para la rotación)
• para todos los píxeles en el rectángulo de intersección, transforma las coordenadas y prueba la imagen en la posición calculada (redondeada al vecino más cercano) para el canal alfa. Luego abortar al primer golpe.

El problema que veo con eso es que a) no hay clases de matriz en JavaScript, lo que significa que tengo que hacer eso en JavaScript, que podría ser bastante lento, tengo que probar las colisiones cada fotograma que hace que este costoso. Además, tengo que replicar algo que ya tengo que hacer en el dibujo (o lo que el lienzo hace por mí, configurando las matrices).

Me pregunto si me falta algo aquí y si hay una solución más fácil para la detección de colisiones.

Answer 1

No soy un codificador de JavaScript, pero me imagino que los mismos trucos de optimización funcionan igual para Javascript que para C++.

Simplemente rote las esquinas del sprite en lugar de cada píxel. De hecho, estarías haciendo algo parecido al mapeo de texturas de software. Podría calcular la posición x, y de un píxel dado usando varios gradientes de información. Busque mapeo de texturas de software para más información.

Si quadtree descompuso el sprite en áreas de "golpe" y "sin golpe", entonces podría verificar efectivamente si una descomposición dada de un árbol cuádruple es "sin impacto", "todo golpe" o "posible golpe" "(es decir, contiene éxitos y píxeles sin éxito. Los primeros 2 son triviales para pasar. En el último caso, desciende al siguiente nivel de descomposición y repite la prueba. De esta forma solo verificará los píxeles que necesita y para grandes áreas de "no-hit" y "éxito" usted no tiene que hacer un conjunto tan complejo de cheques.

de todos modos eso es sólo un par de pensamientos.

Answer 2

tengo que replicar algo que ya tiene que ver en el dibujo

Bueno, se podría hacer un nuevo contexto de representación, parcela de una gira máscara blanca-fondo en la misma, fijar la operación de composición a lighter y la trama de la otra máscara girada en la parte superior en el offset dado.

Ahora, si queda un píxel no blanco, hay un golpe. Todavía tendría que getImageData y cribar a través de los píxeles para descubrirlo. Es posible que pueda reducir un poco esa carga de trabajo escalando la imagen resultante hacia abajo (confiando en el anti-aliasing para mantener algunos píxeles no blancos), pero estoy pensando que probablemente todavía sea bastante lento.

Tengo que probar las colisiones en cada cuadro, lo que hace que esto sea bastante caro.

Sí, creo que va a utilizar tablas de colisiones precalculadas. Si tiene espacio para ello, puede almacenar un hit/sin hit para cada combinación de sprite a, sprite b, rotación relativa, relative-x-normalized-to-rotation y relative-y-normalized-to-rotation . Dependiendo de cuántos sprites tienes y cuántos pasos de rotación o movimiento, esto podría ser bastante grande.

Un compromiso sería almacenar las máscaras prerrotadas de cada sprite en una matriz de JavaScript (de Número, que le da 32 bits/píxeles de fácil && -able datos, o como un personaje en un Sring, que le da 16 bits) y && cada línea de máscaras de sprites que se cruzan juntas.

O, renunciar a los píxeles y empezar a mirar, por ejemplo. caminos.

Answer 3

Mismo problema, una solución alternativa. Primero uso los datos de getImageData para encontrar un polígono que rodee el sprite. Cuidado aquí porque la implementación funciona con imágenes con fondo transparente que tienen un solo objeto sólido. Como un barco. El siguiente paso es Ramer Douglas Peucker Algorithm para reducir el número de vértices en el polígono. Finalmente, obtengo un polígono de muy pocos vértices fácil y barato de girar y verificar las colisiones con los otros polígonos para cada sprite.

http://jsfiddle.net/rnrlabs/9dxSg/

var canvas = document.getElementById("canvas"); 
var context = canvas.getContext("2d"); 
var img = document.getElementById("img"); 

context.drawImage(img, 0,0); 
var dat = context.getImageData(0,0,img.width, img.height); 
// see jsfiddle 
var startPixel = findStartPixel(dat, 0); 
var path = followPath(startPixel, dat, 0); 
// 4 is RDP epsilon 
map1 = properRDP(path.map, 4, path.startpixel.x, path.startpixel.y); 

// draw 

context.beginPath(); 
context.moveTo(path.startpixel.x, path.startpixel.x); 
for(var i = 0; i < map.length; i++) { 
    var p = map[i]; 
    context.lineTo(p.x, p.y); 
} 
context.strokeStyle = 'red'; 
context.closePath(); 
context.stroke();