Detección de colisiones punto-triángulo en 3D

Question

¿Cómo corrijo el error de punto flotante en la siguiente simulación física?

• Punto original (x, y, z),
• Punto deseado (x', y', z') después de aplicar las fuerzas.
• Dos triángulos (A, B, C) y (B, C, D), que comparten arista BC

Estoy usando este método para la detección de colisiones:

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

El problema que tengo es que a veces el punto cae en el área gris de las matemáticas de punto flotante donde está tan cerca de la línea BC que no logra chocar con ninguno de los triángulos, aunque técnicamente siempre debería chocar con uno u otro ya que comparten una ventaja.Cuando esto sucede, el punto pasa justo entre los dos triángulos que comparten bordes.He marcado una línea del código con (!) porque creo que ahí es donde debería hacer un cambio.

Una idea que funciona en situaciones muy limitadas es omitir las pruebas de borde.Convirtiendo efectivamente los triángulos en planos.Esto sólo funciona cuando mis mallas son cascos convexos, pero planeo crear formas convexas.

Estoy usando específicamente el producto escalar y las normales del triángulo para todas mis pruebas de adelante hacia atrás.

Answer 1

Este es un problema inevitable cuando se dispara un solo rayo contra alguna geometría con aristas y vértices.¡Es sorprendente cómo las simulaciones físicas parecen buscar las más pequeñas imprecisiones numéricas!

Algunas de las explicaciones y soluciones propuestas por otros encuestados no funcionarán.En particular:

• La inexactitud numérica realmente puede hacer que un rayo "caiga por el espacio".El problema es que cortamos el rayo con el plano ABC (obteniendo el punto P, digamos) antes de compararlo con la línea BC.Luego cortamos el rayo con el plano BCD (obteniendo el punto Q, digamos) antes de compararlo con la línea BC.P y Q están representados por la aproximación de punto flotante más cercana;no hay razón para esperar que estos se encuentren exactamente en los planos en los que se supone que deben estar, por lo que es muy posible que tenga tanto P a la izquierda de BC como Q a la derecha de BC.

• Usar una prueba de menor o igual no ayudará;el problema es la inexactitud en la intersección del rayo y el plano.

• Las raíces cuadradas no son el problema;puede realizar todos los cálculos necesarios utilizando productos escalares y división de punto flotante.

Aquí hay algunas soluciones genuinas:

• Para mallas convexas, puede simplemente probar con todos los planos e ignorar los bordes y vértices, como usted dice (evitando así el problema por completo).

• No cruces el rayo con cada triángulo por turno.En su lugar, utilice el triple producto escalar.(Este método realiza exactamente la misma secuencia de cálculos para el rayo y la arista BC al considerar cada triángulo, asegurando que cualquier inexactitud numérica sea al menos consistente entre los dos triángulos).

• Para mallas no convexas, dé algo de ancho a los bordes y vértices.Es decir, coloque una pequeña esfera en cada vértice de la malla y coloque un cilindro delgado a lo largo de cada borde de la malla.Intersecta el rayo con estas esferas y cilindros así como con los triángulos.Estas figuras geométricas adicionales impiden que el rayo pase por los bordes y vértices de la malla.

Déjame recomendar encarecidamente el libro. Detección de colisiones en tiempo real por Christer Ericson.Hay una discusión sobre este problema exacto en las páginas 446–448, y una explicación del enfoque del producto triple escalar para intersectar un rayo con un triángulo en las páginas 184–188.

Answer 2

Parece que no incluyes la prueba si está EN el borde (estás escribiendo "Dentro de los bordes del triángulo").Intente cambiar el código a "menor o igual" (dentro o superpuesto).

Answer 3

Me parece algo improbable que su rayo caiga exactamente entre los triángulos de manera que la precisión del punto flotante surta efecto.¿Estás absolutamente seguro de que este es realmente el problema?

En cualquier caso, una posible solución es en lugar de disparar sólo un rayo disparar tres que estén muy cerca uno del otro.Si uno cae exactamente en el medio, se garantiza que al menos uno de los otros dos caerá en un triángulo.

Esto al menos le permitirá probar si el problema es realmente un error de punto flotante o algo más probable.

Answer 4

@Declaración:De hecho, ya estoy usando una comparación "mayor o igual que" en mi código, gracias por la sugerencia.+1

Mi solución actual es agregar una pequeña cantidad de empujón a la prueba de borde.Básicamente, cuando se prueba cada triángulo, sus bordes se empujan hacia afuera en una cantidad muy pequeña para contrarrestar el error en punto flotante.Algo así como probar si el resultado de un cálculo de punto flotante es menor que 0,01 en lugar de probar la igualdad con cero.

¿Es esta una solución razonable?

Answer 5

Si estás midiendo distancias, ten cuidado con las raíces cuadradas.Tienen la mala costumbre de tirar medio de tu precisión.Si acumula algunos de estos cálculos, puede meterse en grandes problemas rápidamente.Aquí hay una función de distancia que he usado.

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

Como la última operación no es una raíz cuadrada, ya no se pierde precisión.

Descubrí esto en un proyecto en el que estaba trabajando.Después de estudiarlo y descubrir qué hacía, localicé al programador que pensé que era el responsable de felicitarlo, pero no tenía idea de lo que estaba hablando.