Anuncios Google

Tutorial: Detección de colisiones con un terreno en 3D

Hoy en día, los juegos en 3D son muy abundantes y, con el
avance de la tecnología, son cada vez mejores en cuanto a calidad gráfica.
También, en muchos videojuegos en 3D, especialmente los de carreras, se utiliza
mucho la detección de colisiones con el terreno para poder saber la altura a la
que se tiene colocar el personaje. En este tutorial os voy a explicar cómo
hacer eso en C++ de la manera más simple que conozco.

Este es el resultado que se debería obtener:

prueba del funcionamiento

Para empezar tengo que deciros que para hacer esto hay que
saber algo matemáticas o no entenderéis algunas formulas, aunque intentaré ser lo más claro posible a la hora de explicar.

Lo primero que tenemos que saber es lo que queremos conseguir.
Tenemos que cumplir este pequeño paso para poder hacer el código. En nuestro caso, lo que queremos es detectar las colisiones de un personaje sobre un terreno para poder conseguir la altura a la que se debería situar.

El segundo paso es elaborar el código que queremos ejecutar. Primero
tenemos que buscar el triangulo sobre el que está situado nuestro personaje.
Para eso podemos usar esta función:

bool PuntoEnTriangulo2D (float x1, float z1, float x2, float z2, float x3, float z3, float tx, float tz) {
 
     float orientacion, abt, bct, cat;
 
     //calculamos la orientación del triangulo
     orientacion = (x1 - x3) * (z2 - z3) - (z1 - z3) * (x2 - x3);
 
     //ahora calcularemos la orientación de los triángulos que tengan como uno de los vértices el //punto del personaje, los triangulos serían ABT, BCT y CAT donde T es el punto del personaje
     abt = (x1 – tx) * (z2 – tz) - (z1 – tz) * (x2 – tx);
     bct = (x2 - tx) * (z3 - tz) - (z2 - tz) * (x3 - tx);
     cat = (x3 - tx) * (z1 – tz) - (z3 – tz) * (x1 – tx);
 
     //si la orientación del triángulo y la de los demás triángulos es igual a cero o mayor, el punto está dentro del triángulo
     if (orientacion >= 0 && abt >= 0 && bct >= 0 && cat >= 0) {
                     return 1;
                     }
 
     //si la orientación del triángulo y la de los demás triángulos es menor que cero, el punto también está dentro del triángulo
     if (orientacion < 0 && abt < 0 && bct < 0 && cat < 0) {
                     return 1;
                     }
 
     //si no se cumple ninguna de los requerimientos anteriores, el punto está fuera del triángulo
     return 0;
     }
 

En esta función (x1, z1), (x2, z2) y (x3, z3) son las
coordenadas del triángulo. Por otra parte, tx y tz son la posición del personaje(punto T de la imagen).

Triangulo en 2D

La función calcula la orientación de la cara (ABC) y la compara con las orientaciones de los triangulos que tienen como uno de los vértices el punto del personaje, es decir, ABT, BCT y CAT, siendo T el punto del personaje. Si todas las orientaciones son iguales quiere decir que el punto está dentro del triangulo, si no lo son quiere decir que está fuera.

Cuando sepamos que el punto está dentro del triángulo, solo
necesitamos encontrar la altura a la que está situado el personaje. Para esto
también se necesitan “mates” pero para facilitar el trabajo a los que no sepan
esto, os lo explico. Para calcular la altura usaremos esta función:

float AlturaDeLaIntersecciónConElTriangulo(float x1, float y1, float z1, float x2, float y2, float z2, float x3, float y3, float z3, float tx, float tz) {
 
      float A, B, C, D, puntoY;
 
      //A, B y C son la normal del plano del triangulo
      A = y1 * (z2 - z3) + y2 * (z3 - z1) + y3 * (z1 - z2);
      B = z1 * (x2 - x3) + z2 * (x3 - x1) + z3 * (x1 - x2);
      C = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
      D = -(x1 * (y2 * z3 - y3 * z2) + x2 * (y3 * z1 - y1 * z3) + x3 *(y1 * z2 - y2 * z1));
 
      //Ahora ponemos el valor de B a un número cercano a cero si su valor original es cero para que no de errores a la hora de hacer la división
      if (B == 0) {B = 0.01;}
 
      //calculamos la altura del punto
      puntoY = -(D + A * tx + C * tz) / B;
 
      //devolvemos la altura del punto
      return puntoY;
      }

En esta función (x1, y1, z1), (x2, y2, z2) y (x3, y3, z3) son
las coordenadas del triangulo y tx y tz son la posición del personaje. En la imagen de abajo la atura que queremos conseguir sería la altura del punto en el que la linea toca el triángulo (la intersección):

Intersección con un triangulo en 3D

En este caso, la función calcula la normal del plano del triángulo y luego usa la fórmula que se ve al final del código para determinar la altura del punto del personaje.

Ahora, podemos empezar a hacer el código, gracias a estas
funciones tan útiles. Lo primero será ver si el personaje esta dentro del
modelo. Esto es opcional, pero si el personaje puede salirse del modelo, va a
hacer que se use menos CPU, por lo tanto, el rendimiento del juego
incrementará. Para esto tenemos que ver si el personaje está dentro del área
del modelo, que se puede conseguir usando seis variables: las coordenadas XYZ
más grandes y las más pequeñas. Esto deberíamos hacerlo mientras cargamos el
modelo del terreno para no tener que hacerlo luego.

Después, tenemos que buscar el triángulo sobre el que está
situado nuestro personaje. Esto lo haremos con la función PuntoEnTriangulo2D()
dándole las coordenadas del triángulo con el que estamos trabajando y las
coordenadas X y Z del personaje. Luego tenemos que conseguir la altura del
punto. La función AlturaDeLaIntersecciónConElTriangulo() está para eso (os
recomiendo cambiarle el nombre por uno más corto porque este es muy largo xD).

Cuando hayamos conseguido la altura tenemos que ver si la
altura es la más cercana al personaje (y que esté debajo de él claro).

Para resumir todo esto, en lenguaje C++ esto es más o menos
lo que deberíamos conseguir:

Nota importante: este código está hecho especialmente para los modelos con formato *.obj. Puede que tengais que modificarlo para que os funcione.

float Altura (float tempx, float tempy, float tempz, DatosModelo &mod, float escala) { // He puesto &mod para que funcione más rápido
 
      float altura = 99999999, alturaTemporal = 99999999, x1, y1, z1;
      int cara = 1, a = 0, b = 0, c = 0;
 
      //Una cosa buena de este código es que puedes escalar el modelo(no el que se va a dibujar sino el que se va a procesar)
      x1 = tempx / escala;
      y1 = tempy / escala;
      z1 = tempz / escala;
 
      //Mirar si el punto está dentro de la bounding box del modelo (si no lo está devuelve 0)
      //maxx, maxy y maxz son los puntos máximos y minx, miny y minz son los mínimos
      if (x1 > mod.maxx || x1 < mod.minx || y1 > mod.maxy || y1 < mod.miny || z1 > mod.maxz || z1 < mod.minz) {return 0;}
 
      //Buscar el triangulo en el que las coordenada x y z están localizadas.
      for (cara = 1; cara <= mod.numCaras; cara++) {
          //indices de la cara (vertices)
          a = mod.st_caras[curFace].cara[0]; //número del primer vértice del triangulo
          b = mod.st_caras[curFace].cara[3]; //número del segundo vértice del triangulo
          c = mod.st_caras[curFace].cara[6]; //número del tercer vértice del triangulo
 
          //Mirar si el punto (solo se tienen en cuenta las coordenadas  x, z) está dentro de este triangulo (si no, pasar al siguiente)
          if (PuntoEnTriangulo2D(mod.st_vertice[a].vertx, mod.st_vertice[a].vertz, mod.st_vertice[b].vertx, mod.st_vertice[b].vertz, mod.st_vertice[c].vertx, mod.st_vertice[c].vertz, x1, z1)) {
                                                    //conseguimos la altura de la intersección
                                                    alturaTemporal = AlturaDeLaIntersecciónConElTriangulo(mod.st_vertice[a].vertx, mod.st_vertice[a].verty, mod.st_vertice[a].vertz, mod.st_vertice[b].vertx, mod.st_vertice[b].verty, mod.st_vertice[b].vertz, mod.st_vertice[c].vertx, mod.st_vertice[c].verty, mod.st_vertice[c].vertz, x1, z1); //asignamos la altura actual a una variable para luego compararla con la anterior
                                                    //esto sirve para conseguir la altura más cercana al personaje
                                                    if (abs(y1 - altura) > abs(y1 - alturaTemporal)) {
                                                                   altura = alturaTemporal; //si la altura anterior es más lejana a la altura temporal, actualizamos el valor de la altura
                                                                   }
                                                   }
          }
 
      if (altura == 99999999) {
             altura = 0;
             }
 
      return altura * escala; //devuelve la altura conseguida
      }

En este código st_caras es donde están los índices a los normals, coordenadas de textura y vértices. Por ejemplo, mod.caras_st[0].cara[0] tendría el número de uno de los tres vértices que usará la cara. cara[0] = vértice, cara[1] = coordenada de textura, cara[2] = normal, cara[3] = vértice, cara[4] = coordenada de textura, cara[5] = normal, etc. También tengo que decir que st_vertice es donde está la informacion sobre los vértices del modelo. Por ejemplo, mod.st_vertice[número de vertice].vertx sería el valor del eje X del vértice.

Nota: en este tutorial solo se necesitan las caras y los vértices.

Usando estas dos estructuras podemos saber los datos exactos del eje X del vértice cero de la cara actual de esta manera: mod.st_vertices[mod.st_caras[número de la cara actual].cara[0]].vertx.

Espero que este tutorial os haya ayudado y no dudéis en comentar, saludos a todos.


PC: i5-2500K @ 4.2GHz, ATI HD 6870 1GB GDDR5 (975MHz core, 1150 MHz memory 1.176V), 8GB DDR3, 750 GB HDD, 128 GB SSD Crucial M4, 750W PSU, Win7 x64, Kubuntu x64

Avatar creado por JeyZee


Anuncios Google

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

...

Tengo una duda , En verdad es increible y logré entender muy bien las formulas y cada linea de codigo, a final de cuentas es algebral lineal, pero por ejemplo en Mario Kart, como determino las colisiones laterales de la pista? o como pudiese comprobar que el jugador esta dentro de la rampa o esta fuera de ella...

Imagen de koldo52

He hecho algo parecido a lo

He hecho algo parecido a lo que ha dicho joserc, primero verifico la distancia desde el personaje al triangulo y luego roto los triangulos en la dirección en la que mira el personaje. Finalmente, verifico si el punto donde ocurre la colisión está lo suficientemente cerca del personaje como para que haya ocurrido una colision.


PC: i5-2500K @ 4.2GHz, ATI HD 6870 1GB GDDR5 (975MHz core, 1150 MHz memory 1.176V), 8GB DDR3, 750 GB HDD, 128 GB SSD Crucial M4, 750W PSU, Win7 x64, Kubuntu x64

Avatar creado por JeyZee

Imagen de joserc87

Comprobaciones.

No soy koldo, pero me voy a tomar la libertad de responder. Espero que se entienda, pero si no se entiende o me equivoco en algo koldo me puede corregir. Además, no voy a dar fórmulas, solo voy a explicar más o menos como se haría:

Lo de las colisiones laterales, si tienes el polígono que define el lateral de la pista (ya sea una verja, un muro o lo que sea) sería calcular la distancia del jugador al polígono. Si la distancia es mayor que 0 no hay colisión, pero si es 0 o "menor" sí hay colisión (en rigor la distancia no puede ser menor que 0, pero si es negativo en el sentido de la normal, indicaría que está al otro lado del polígono). Para ser más preciso habría que comprobar las 4 coordenadas de las ruedas en lugar de la coordenada del jugador. Por último, para saber el polígono en el que comprobar la colisión, haríamos lo mismo que se hace en PuntoEnTriangulo, solo que en lugar de mirar en la proyección de la coordenada Y (desde arriba), miraríamos en la dirección de la normal del polígono (generalmente de frente). La forma más sencilla y general que se me ocurre a estas horas de la noche es aplicar una rotación a los puntos para que la normal coincida con el eje Y y luego aplicar PuntoEnTriangulo como si nada.

Por otra parte, lo de "comprobar que el jugador esta dentro de la rampa o esta fuera de ella", si es lo que creo que es, tienes ya el código en el tutorial xD.

 


Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

...

Carajo, tengo que aprender programacion el C+ urgentemente... He tenido ganas de hacer un juego 2.5D o 3D, por los graficos no hay problema, pero la programacion es algo tediosa, seria grandioso trabajar con alguien, pero eso no funciona nunca... Asi que... Gracias por la ayuda, me sera muy util... :)

 

Otra opcion es usar el Unreal Engine 4, pero tambien necesito aprender a programas... Ah, ya sera con tiempo.... De cualquier forma si a alguien le interesa este es mi correo:

 

editadoatgmail [dot] com

 

Y algunos de mis trabajos estan aqui:

 

http://bhvampire.newgrounds.com/art/

Y aqui http://bhvampire-bh.deviantart.com/

 

Para un juego solo pido que sea estilo Cyberpunk Post-Apocaliptico, de ahi en fuera cualquier idea es aceptada XD

 

Pero bueno... Ya sera despues, saludos :)


Editado: Postear direcciones de correo electrónico en el foro público incumple las Normas de la Comunidad. Puede remitir su e-mail mediante mensajes privados, pinchando en el nick del usuario. Antes de volver a postear por favor revise las normas. | AORV

Imagen de IRONSISTEM

no pues si esta chida tu

no pues si esta chida tu galeria de diseños, aunque un poco sombrios jejeje. De que parte de mexico eres? igual y si vivimos cerca podemos hacer algun juego sencillito jejeje....porque yo se programar ahi mas o menos pero lo que es diseño desde 0 nomas no XD.

y se puede

y se puede saber que le has hecho tu a esas fotos? estan dibujadas por ti desde 0? o las has editado? 

Desde Cero Men ^_^   Poligono

Desde Cero Men ^_^

 

Poligono por Poligono, Textura por Textura... :)

Imagen de koldo52

Pufff... Ya me gustaría ser

Pufff... Ya me gustaría ser así de bueno. Con lo que me cuesta a mí manejar modelos y cosas así.

Imagen de joserc87

Está muy bien.

Además, me alegro de que lo compartas para que así el próximo que tenga que hacer algo del estilo no tenga que empezar de nuevo. Yo también tuve que hacer algo muy parecido a esto, para detectar si un avión chocaba con el terreno. La única diferencia es que en mi caso el terreno estaba compuesto de triángulos con coordenadas en el plano eran fijas y solo cambiaba la altura, por lo que podias saber en todo momento el triángulo en el que está sin necesidad de buscarlo.

Si me permites una mejora, buscar entre todas las caras es MUY costoso ya que el número de polígonos puede ser bastante grande. Para mejorarlo, se me ocurren 2 opciones: o utilizar una tabla hash, o hacer un BSP (partición del espacio) de forma que puedas buscar el polígono en un arbol. La primera opción posiblemente sea la más rápida, pero la segunda creo que es más sencilla.

Por si te interesa, te explico brevemente el BSP. Se trata de clasificar los polígonos en grupos. Por ejemplo, si todos los polígonos están en el rango [0,100] de X y [0,200] de Z, dividir los polígonos que tienen coordenada x<50 de los que tienen x>=50. El primer grupo a su vez lo divides en los que tienen z<100 de los que z>=100. Estos a su vez x<25 de x>25 etc. Así, si tienes, digamos, 1.048.576 polígonos, con tu método tendrías que hacer los cálculos para más de un millón de polígonos, mientras que con el BSP haces solo 20 comprobaciones:) (Logaritmo en base 2 de 1048576=20). Si tuvieses mil millones de polígonos, serían 30.

EDIT: Añado una aclaración. Para implementar el BSP no tienes que tocar en absoluto como tienes almacenadas las caras del terreno. El BSP sería un árbol aparte que almacena los índices de las caras para buscarlas mejor. No se si me ha quedado la explicación muy clara. Si tienes alguna pregunta y algo no lo he explicado bien, dilo (si te interesa lo del BSP, claro).

Saludos!


Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Imagen de koldo52

¡Muchísimas gracias! El uso

¡Muchísimas gracias! El uso del procesador que requería leer todas las caras me preocupaba. Creo que intentaré hacer el BSP que no parece muy difícil.

Saludos.


PC: i5-2500K @ 4.2GHz, ATI HD 6870 1GB GDDR5 (975MHz core, 1150 MHz memory 1.176V), 8GB DDR3, 750 GB HDD, 128 GB SSD Crucial M4, 750W PSU, Win7 x64, Kubuntu x64

Avatar creado por JeyZee

Imagen de joserc87

Es verdad, no es nada dificil.

De hecho, creo que se podría hacer en una tarde, y si dominas las clases en C++ puedes hacerlo muy genérico. Además, el tema de la eficiencia es bastante importante porque para cada coche tendrás que buscar la altura de cada rueda, para saber la inclinación y que el movimiento sea suave entre polígonos (y eso para cada uno de los jugadores).

Aún así, si tienes alguna duda o te quedas atascado, ya sabes :). Me gustaría ver como te queda el juego :)

Saludos.


Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Imagen de koldo52

He hecho una prueba en mi

He hecho una prueba en mi juego, he hecho que lo ejecute 240 veces con 500 polígonos y el uso del procesador era bastante parecido (y eso que tengo un pentium 4), aunque ya estoy implementando eso del BSP y sólo me falta que el cargador de modelos escriba en una estructura los índices a las caras. Algún día de estos, cuando el juego sea estable y tenga algún circuito, lo subiré para que podais decirme en qué se puede mejorar o para que lo probéis.

Salu2.


PC: i5-2500K @ 4.2GHz, ATI HD 6870 1GB GDDR5 (975MHz core, 1150 MHz memory 1.176V), 8GB DDR3, 750 GB HDD, 128 GB SSD Crucial M4, 750W PSU, Win7 x64, Kubuntu x64

Avatar creado por JeyZee

Imagen de joserc87

A que te refieres?

Dices que el uso del procesador es bastante parecido. ¿Te refieres a la versión original VS la optimización? Si es eso, realmente no me extraña demasiado. Buscar entre 500 polígonos no es tanto. Prueba a meterle 500.000 y me dices si se nota la diferencia :).


Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Imagen de koldo52

Sí se nota mucho la

Sí se nota mucho la diferencia, pero en mi juego no voy a usar tantos. Usaré unos 30.000, que mi tarjeta gráfica no anda rapido con 500.000. Aun así intentare implementar el BSP (que me está costando, no se por qué).

Editado: ya me funciona sin problemas


PC: i5-2500K @ 4.2GHz, ATI HD 6870 1GB GDDR5 (975MHz core, 1150 MHz memory 1.176V), 8GB DDR3, 750 GB HDD, 128 GB SSD Crucial M4, 750W PSU, Win7 x64, Kubuntu x64

Avatar creado por JeyZee

Imagen de joserc87

Me alegro!

Podrías hacer una pequeña actualización de la hebra con lo que has cambiado cuando tengas tiempo, por si a alguien le interesa. Por curiosidad, ¿has notado diferencia en velocidad? ¿Cuantos FPS tienes con y sin BSP?

Bueno, para cualquier cosa que necesites, aquí estoy :D

 

Saludos.


Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Imagen de koldo52

Intentaré hacer la

Intentaré hacer la actualización para que soporte el BSP. Además también pondré como comprobar si hay colisiones contra alguna pared(todavía estoy trabajando en ello).

De todas formas, con el BSP me funciona a más de 100 FPS y sin el BSP me funciona a 3 FPS como máximo. También le encontre un grave fallo al código en cuanto al rendimiento. Ya lo he actualizado por si acaso, porque antes cada vez que llamaba a la función, como yo no le daba el puntero, me hacía una copia del modelo entero, y si el BSP o el modelo era demasiado grande tardaba muchísimo (15 ms con el fallo y 2 ms sin él).


PC: i5-2500K @ 4.2GHz, ATI HD 6870 1GB GDDR5 (975MHz core, 1150 MHz memory 1.176V), 8GB DDR3, 750 GB HDD, 128 GB SSD Crucial M4, 750W PSU, Win7 x64, Kubuntu x64

Avatar creado por JeyZee

Imagen de joserc87

Muy interesante los FPS.

Respecto a lo de los punteros, si programas en C++ puedes poner que el objeto que le pasas es una referencia, para usarlo como un objeto más (no como un puntero), pero sin que se copie nada, es decir, que a efectos internos se comporta como un puntero. Es muy útil, sobre todo en funciones donde el objeto no se va a modificar.

Por ejemplo, si el objeto "Obj" de tipo T ocupa mucha memoria, y tienes una función tal que:

void FUNCION (T Obj);

en general se recomienda cambiarla por:

void FUNCION (const T &Obj);

siempre que Obj ocupe algo más que unos pocos bytes. Por ejemplo, si el tipo T no es más que 2 flotantes, a lo mejor no merece la pena, pero si ocupa más, pues siempre viene bien.

La implementación de la función sería exáctamente igual, aunque los métodos de T a los que se llama tienen que estár definidos como constantes.

En fin, punteros o referencias, eso ya es tu elección.

Saludos!

 


Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Imagen de Loopin

No se si interesa mucho, pero

No se si interesa mucho, pero estaría genial tener una especie de log book, del desarrollo del juego. Incluso se podría devidir en tutoriales. Solo tenemos los tutoriales 3D de pipagerardo, y creo que sería un gran contenido para la web!


Imagen de koldo52

Buena idea

Intentaré subir tutoriales 3D a la página (si se me ocurre sobre qué hacerlos).

Saludos.

Imagen de Cheleon

Otro igual...

espero que almenos él te haya entendido y le hayas ayudado, jajajaj xD

Imagen de Cheleon

._.

Guau...

No he entendido ni papa... Fantastico ;D, se ve que sabes de que hablas.

Imagen de koldo52

Gracias. Es solo para que el

Gracias. Es solo para que el personaje pueda adaptarse al terreno. Se usa en muchos juegos. Además es el mismo código que estoy usando en un Mario Kart que estoy haciendo (se ve en la primera foto).


PC: i5-2500K @ 4.2GHz, ATI HD 6870 1GB GDDR5 (975MHz core, 1150 MHz memory 1.176V), 8GB DDR3, 750 GB HDD, 128 GB SSD Crucial M4, 750W PSU, Win7 x64, Kubuntu x64

Avatar creado por JeyZee

Imagen de the dragon lives

igual

Me ha dejado sin palabras, ahora ... hay algun staff que pueda verificar esto, o almenos que sepa encuadrarlo en portada?

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.