Colisión De Esfera A Cubo

[Sacrifai]

 Pues resulta que estoy haciendo un arkanoid. Y me he topado con el tema de las colisiones. He probado las colisiones de caja a caja, pero en la pelota no me acaba de convencer. Sin embargo, nunca he probado colisión de esfera a caja, y no se como hacerlo exactamente. ¿ Me podríais dar alguna dirección o explicarlo un poco ?

Gracias.


PD: Es en 2D.

[Lord Trancos 2]

 http://www.gametutorials.com/download/Open...OnPlane_OGL.zip

Ahi tienes un algoritmo (en 3D) que te dice el punto mas cercano de una linea a un punto.

Yo lo que haria seria calcular los puntos mas cercanos de cada linea que forma el rectangulo y el centro de la esfera.

Si alguno de esos 4 puntos resultantes se encuentra dentro de la esfera, o bien el centro de la esfera se encuentra dentro del rectangulo, hay colision.

Imagino que debe de haber formas mas sencillas; pero esta es la que se me ha ocurrido.  :rolleyes:

Supongo que alguien por aqui tendra un algoritmo mejor ;)

[Pogacha]

 En 2d es circulo, no esfera, caja safa bastante bien, pero bue ...

Código [Seleccionar] Expand

struct Pelotita
{  
 vector2 Posicion, Velocidad;
 float Radio
}

struct Colision
{
 vector2 Posicion, Normal;
}

struct Bloque
{
 int n_Vectores;
 vector2 *Vectores; // un cuadrado o un rectangulo o un triangulo o un pentagono o lo que sea ...
};



bool Detectar_Colision(Colision &c,  Bloque &b, Pelotita &p)
{
 int i,j;

// interseccion circulo - segmento
 for(j=b.n_Vectores-1, i=0; i<b.n_Vectores; j=i++)
{
   vector2 recta= b.Vectores[i]-b.Vectores[j];
   vector2 tangente = vector2(recta.y, -recta.x);

   tangente.Normalizar();

   float dis = tangente.Punto(b.Vectores[i]);

   float d1 = tangente.Punto(b.Vectores[i]) - dis - radio;
   float d2 = tangente.Punto(b.Vectores[j]) - dis - radio;
   if(d1 < EPSILON)  continue;   // si vengo por atras no colisiono
   if(d2 > -EPSILON)  continue;    // mantengo una norma, los vectores del bloque en sentido horario
   vector2 Interseccion = p.Posicion + p.Velocidad * (d1 / (d1 - d2)) * p.Velocidad.Longitud();
   float disint=recta.Punto(Interseccion);
   if(disint < recta.Punto(b.Vectores[i]) continue; // tiene que estar sobre el segmento
   if(disint > recta.Punto(b.Vectores[j]) continue;
   c.Posicion = Interseccion;    
   c.Normal = tangente;
   return true;
}

// interseccion circulo - vertice
 for(i=0; i<b.n_Vectores; i++)
 {
      vector2 veltangente = vector2( p.Velocidad.y, -p.Velocidad.x);
      veltangente.Normalizar();
 
    float seno = veltangente.Punto(b.Vectores[i] - p.Posicion);
    if(p.Radio * p.Radio < seno * seno) continue;
    float cose =  sqrt(p.Radio * p.Radio - seno * seno );
    vector2 velnorm=p.Velocidad;
    velnorm.Normalizar();
    vector2 punto_mas_cercano= p.Posicion + seno * velnorm + coseno * veltangente;
     if( (punto_mas_cercano - b.Vectores[i]).Longitud() > p.Velocidad.Longitud() ) continue;
     c.Posicion = b.Vectores[i];
     c.Normal = punto_mas_cercano - p.Posicion;
     c.Normal.Normalizar();
     return true;
 }
 return false;
}


void Controlar_Pelotita(Pelotita &p)
{
  for(int i=0; i< n_Bloques; i++)
  {
     Colision c;
     if(Detectar_Colision(c,  Bloques[i], p))
     {
           p.Velocidad -= c.Normal * p.Velocidad.Punto(c.Normal) * 2.0f; // refleccion
            ... destruir bloque
            ... hacer ruidito
            ... sumar puntos y todo lo que sea necesario
     }
  }
}


Faltaria una deteccion caja caja para computar rejeccion trivial, ademas profundidad de colision, y control de velocidad para tiempo variable, pero para empezar tenes.

Esto lo escribí de un tirón, puede tener errores y seguramente no compile si cuto-pasteas, pero si lo estudias un poquito encontraras el camino.
Espero sirva.

Saludos.

[senior wapo]

 EDIT: se me adelantó pogacha mientras escribía  (ole)

Lo que Trancos ha explicado es colisión de caja-caja y sirve para descartar rápidamente. Si quieres colisión esfera-caja has de calcular DESPUES la distancia entre la esquina más cercana y el centro de la esfera (si es menor o igual al radio hay colisión).

La manera más rápida es guardar la caja como su centro y su "radiox" y "radioy" que vienen a ser la mitad del ancho y del alto respectivamente. Esto te permite ahorrarte sentencias IF y utilizar el bit de signo de las distancias (en X y en Y) para determinar que esquina es la potencialmente más cercana (técnicamente determinas el quadrante en el el que está la esfera).

Combinas los signos dx y dy para obtener un número entre 0-3 que es la esquina cuya distancia has de calcular con la formula:
sqrt(distanciax*distanciax + distanciay*distanciay)

Si es menor o igual al radio, hay colisión.

Esto es necesario porque si la esfera esta muy próxima a una esquina a lo largo de una diagonal de la caja, su distancia a cada uno de los lados de la caja es menor al radio, pero no hay colisión.

[Sacrifai]

 Gracias a todos por las respuestas. La verdad es que aun estoy intentando ingerir tanta fórmula  (ole)  . En cuanto saque algo de alguna lo comento  (uoh)  .

[Lord Trancos 2]

 

Lo que Trancos ha explicado es colisión de caja-caja y sirve para descartar rápidamente.

Nooo... lo que yo he explicado (si no me he equivocado en algun sitio) es para colision esfera vs caja (Y el metodo es parecido a lo que ha puesto pogacha.)

Detectar caja vs caja es mucho menos enrevesao (si estan alineadas a los ejes)

Código [Seleccionar] Expand


function RectCollision(var _r1, _r2: TRect): boolean;

begin
 Result := not ((_r1.Right  < _r2.Left) or (_r1.Bottom < _r2.Top) or
                (_r2.Right  < _r1.Left) or (_r2.Bottom < _r1.Top));
end;


Si quieres colisión esfera-caja has de calcular DESPUES la distancia entre la esquina más cercana y el centro de la esfera (si es menor o igual al radio hay colisión).

Pues eso, lo que yo decia... si alguno de los 4 puntos (1 por cada lado) mas cercanos se encuentra dentro de la esfera es que hay colision. :P

Claro que lo ideal es primero comprobar si hay colision caja vs caja q es muy rapida para ahorrar calculos. Despues yo comprobaria si el centro de la esfera esta dentro de la caja (comprobacion tb muy rapida). Y finalmente iria comprobando lados de la caja hasta que un colisionara (o hasta que no quedaran lados por comprobar).

[Minos]

 Yo reduciria el problema a la distancia entre un punto y dos rectas. El punto seria el eje de la circunferencia y las dos rectas pues las que pasan por el punto medio del cuadrado y con vectores de direccion los lados. Si la distancia es mayor que la mitad del lado mas el radio no chocan.
Si el cuadrado esta alineado a los ejes sale trivial.

No se si me explico.

[senior wapo]

 @Minos y Trancos: Lo mismo soy yo el que lo lee mal, que puede ser, pero es que ese algoritmo es lo que yo llamo caja-caja (por usar distancias alineadas con los ejes) y falla para esferas/circunferencias.

Basicamente, da falsos resultados de colisión. Si no hay colisión la respuesta es siempre acertada, claro.

Aqui os he dibujado una imagen que os lo muestra, con los 4 puntos que dice Trancos (si lo he entendido bien) y las proyecciones de las lineas que cruzan la caja por la mitad. En el caso del dibujo vuestros algoritmos indican colisión, pero NO hay colisión. Repito, si es que es eso lo que decis y no lo he entendido mal.
En el caso de Minos los 2 puntos no los he marcado por no enrevesarlo más.



Por eso la necesitad de calcular la distancia con las esquinas (vértices) si ese algoritmo preliminar devuelve que hay colisión. Por eso Pogacha calcula después contra los vértices en su código.

Lo que yo explicaba era comparar sólo un vértice aprovechando los signos de las distancias horizontal y vertical para seleccionar el quadrante/vértice.

O lo mismo me estoy liando yo solo..  :D

[vicho]

 nose si servira pero a vista rapida se me ocurrio que podias hacer un juego de trigonometria

creo que podria servir(por lo menos para lo de la imagen, se podria generalizar el metodo)

sacar el pto de la circunferencia donde intersecta el angulo formado por la pendiente de entre la circunferencia y   el vertice

las formulas serian

y=sin(180+arctg((Cy-Vy)/(Cx-Vx)))*RadioCircunferencia+Ycentrocircunferencia
x=cos(180+arctg((Cy-Vy)/(Cx-Vx)))*Radiocircunferencia+Xcentrocircunferencia

con eso sacas la cordenada en la circunferencia donde se proyecta el vertice si la cordenada y el vertice tienen el mismo valor habria colision

esto fue hecho a la rapida y es una idea general, talvez resulte

suerte

[Lord Trancos 2]

 

Aqui os he dibujado una imagen que os lo muestra, con los 4 puntos que dice Trancos (si lo he entendido bien)

No, esos no son los 4 puntos que yo decia. Yo me referia a (usando el algoritmo de gametutorials), calcular para cada lado del rectangulo el punto mas cercano al centro de la esfera/circulo. Lo que tu has puesto no es el punto mas cercado de cada linea que forma el cuadrado; sino el punto mas cercano de cada plano.

En fins,.... q creo q en realidad estamos diciendo lo mismo :P

[Buffon]

 sabiendo que al principio la pelota está fuera de cualquier tipo de caja. solo teneis que calcular para los 4 puntos de la caja la distancia al centro de la pelota, en el caso que alguno de ellos sea menor al radio, eliminais caja, pasos intermedios, y calculais nueva direccion de la pelota.

pero eso no se hace para los 4 puntos, sino para las 4 arestas.

Luego para saber que posibles cajas pueden llegar a coincidir, o haceis al principio de la direccion de la pelota, un busqueda, que es hacer 1 simple raytracing sobre un plano 2D, cual será o serán sus posibles obstáculos, cogiendo como mucho 3 de ellos, y a cada paso del bucle comprobar si se ha chocado con alguno de ellos.

es todo mucho más sencillo de lo que parece :P y con un BSP y un OCTREE se puede sacar rápido ese rayito :)

[Buffon]

 esto último lo digo, por que lo mismo hay gente que a cada paso del bucle hace la comprobacion para TODAS las cajas  :blink:

cuando si haces esa comprobacion al cambio de direccion de la pelota, lo estás haciendo 1 vez sólo, con un algoritmo poco eficiente, frente a las 100 posibles como poco que harías, y eso pensando que obligamos a 24 fps, si lo haces sin obligación, un arkanoid pasa de 100 fps, imagina cada segundo comprobar 100 veces eso oO.

[Minos]

 si, tienes razon en mi caso, no habia tenido en cuenta ese caso.  :(  

[Lord Trancos 2]

 Un octree o un BSP para un simple arkanoid....?

Una comprobacion caja vs caja es muy rápida. Yo primero haria ese tipo de comprobación aunque tuviera que hacerla contra 100 cajas; no es pa tanto :P

Y despues para cada vez que se detectara colision caja vs caja haria una prueba de caja vs circulo para confirmar la colision.

Pero weno, yo es que soy muy vago.  :rolleyes:  

[senior wapo]

 para un simple arkanoid yo haria una matriz 2D, miraria en que celda esta la pelota y comprobaria colision con máximo 3 cajas de alrededor (segun la direccion)..

Enhorabuena en secuestrar el hilo  :P