¿Cómo se realiza la detección de colisión en objetos hechos de muchos triángulos pequeños?
13
Entiendo que cualquier forma puede ser creada (o aproximada) por triángulos más pequeños. Cualquier rectángulo puede ser creado por 2 triángulos más pequeños. Cualquier círculo puede ser creado por muchos triángulos delgados "rebanada de pizza". ¿Cómo se traduce esto en detección de colisión?
Entiendo cómo calcular la superposición de rectángulos usando los vértices. Entiendo cómo calcular la superposición de círculos usando el centro, los radios y la distancia.
Pero, ¿cómo se hace la detección de colisión en formas hechas de pequeños triángulos? No específicos, sino solo el concepto general ...
Pero, ¿cómo se hace la detección de colisión en formas hechas de pequeños triángulos?
Al no hacerlo.
La detección de colisión contra una colección de triángulos arbitraria (o peor, entre dos colecciones de triángulos arbitrarios) es prohibitivamente costosa.
En cambio, generalmente realizamos la detección de colecciones de forma jerárquica, comenzando primero con formas extremadamente crudas y simples (como cajas o esferas) que se aproximan (pobremente) al objeto subyacente.
Esto nos permite rechazar rápidamente la mayoría de las colisiones potenciales por "no ocurrir", que es el caso habitual. En el caso de que se apruebe una verificación tan cruda, eso indica una posible colisión real, y procedemos a realizar la verificación contra una aproximación más detallada de la forma subyacente (como una hecha de múltiples formas de cápsulas ajustadas, o muchas cuadros delimitadores alineados).
Esencialmente, la detección de colisión comienza con pruebas crudas y, a medida que pasan esas pruebas, continúa con una representación cada vez más detallada. Esta imagen, proporcionada por Shiro en un comentario a la respuesta de Alexandre , ilustra cómo un modelo complejo (un humano) puede ser representado por una serie de formas más simples:
En raras ocasiones, necesitamos realizar una colisión a nivel de triángulo individual, y cuando lo hacemos, usualmente usamos los métodos más crudos para profundizar en un conjunto muy pequeño de triángulos potenciales para probar. En ese punto, se utilizan algoritmos específicos para realizar las pruebas, al igual que probaría si se superponen dos rectángulos. Por ejemplo, puede determinar si un rayo golpea un triángulo y dónde lo hace .
Gracias. Sí, si realmente estuviera haciendo un juego, simplemente usaría algún motor existente. Pero, solo quiero entender las ideas básicas que se implementan en un motor de detección de colisiones prefabricado. En su diagrama anterior, estaría usando matemática de rectángulos para ver si algo toca CUALQUIERA de las docenas de rectángulos que componen el hombre. ¿Es esa la idea básica?
JackOfAll
Esos son cuadros delimitadores orientados (3D), no rectángulos. Pero si. Si iba a probar si un rayo (que representa, por ejemplo, una bala) colisionó con el jugador, estaría probando el rayo contra esas cajas, posiblemente después de la primera prueba contra una caja gigante que representa a todo el personaje, no contra todos triángulo de la malla de renderizado).
La idea es que puede usar una aproximación aproximada del personaje, como los cuadros delimitadores orientados que se muestran en la imagen de arriba, y probar eso primero para hacer una prueba de impacto menos costosa, y si hay una colisión, luego profundice a un nivel inferior SI ES NECESARIO, probar los triángulos individuales contenidos con el cuadro delimitador. Por lo general, puede haber varios BV diferentes utilizados jerárquicamente, siendo el exterior menos preciso pero el más rápido de probar (esfera, cuadro delimitador), y profundizar en algo más específico (k-DOP), y potencialmente profundizar aún más (triángulos )
Kik
4
La detección de colisión se basa en la geometría (primitivas como líneas, planos, esferas, cajas, cápsulas, cilindros).
Si necesita realizar una detección de colisión en formas hechas de triángulo, por ejemplo, un terreno que no es plano, debe probar contra todos los triángulos que forman la malla.
Si llegas a ese punto, te recomiendo encarecidamente que uses un motor de detección de colisiones prefabricado, ya que este tipo de cosas se vuelven bastante complejas, bastante rápidas.
¿Cómo se hace la detección de colisión en formas formadas por triángulos?
JackOfAll
@JackOfAll que ya se ha mencionado que, en su respuesta, es mediante el uso de la geometría da forma generalmente i.stack.imgur.com/CAhxn.jpg
dimitris93
@JackOfAll edité mi respuesta; y como dice Shiro, si tienes "elementos" más complejos en tu entorno (cuerpos, sillas, autos, etc.), en el desarrollo del juego, generalmente están hechos de primitivas más simples que están unidas. La detección de colisiones se realiza en las formas primitivas, pero la simulación física se realiza en todo el cuerpo.
Vaillancourt
44
No estoy literalmente tratando de hacer un juego, solo quiero entender las ideas básicas que se implementan en un motor de detección de colisiones prefabricado. Si realmente estuviera haciendo un juego, claramente no estaría reinventando la rueda, de acuerdo.
La detección de colisión se basa en la geometría (primitivas como líneas, planos, esferas, cajas, cápsulas, cilindros).
Si necesita realizar una detección de colisión en formas hechas de triángulo, por ejemplo, un terreno que no es plano, debe probar contra todos los triángulos que forman la malla.
Si llegas a ese punto, te recomiendo encarecidamente que uses un motor de detección de colisiones prefabricado, ya que este tipo de cosas se vuelven bastante complejas, bastante rápidas.
fuente