math - programar - funcion de colision en java

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

Question

¿Cómo corrijo el error de coma 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 el borde 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 estoy teniendo es que a veces el punto cae en el área gris de la matemática de punto flotante donde está tan cerca de la línea BC que no colisiona con ningún triángulo, aunque técnicamente siempre debe colisionar con uno u otro ya que ellos comparten una ventaja. Cuando esto sucede, el punto pasa justo entre los dos triángulos que comparten el borde. He marcado una línea del código con (!) Porque creo que es allí donde debería hacer un cambio.

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

Específicamente, utilizo el producto escalar y las normales de triángulo para todas mis pruebas frontales.

Answer 1

@Declaración: 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 empuje a la prueba de borde. Básicamente, cuando se prueba cada triángulo, sus bordes se expulsan en una cantidad muy pequeña para contrarrestar el error en el 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 2

Me resulta un tanto improbable que tu 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 solución posible es disparar un solo rayo para disparar a tres que están muy cerca el uno del otro. Si uno cae exactamente en medio de ese al menos uno de los otros dos está garantizado para caer en un triángulo.

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

Answer 3

Parece que no incluyes pruebas 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 superposición).

Answer 4

Si está haciendo mediciones de distancia, tenga cuidado con las raíces cuadradas. Tienen la desagradable costumbre de tirar la mitad de tu precisión. Si acumula algunos de estos cálculos, puede tener 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 pierde la precisión.

Lo descubrí en un proyecto en el que estaba trabajando. Después de estudiarlo y averiguar qué sucedió, localicé al programador, que me pareció responsable de felicitarlo, pero no tenía idea de lo que estaba hablando.

Answer 5

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

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

• La inexactitud numérica realmente puede causar que un rayo "caiga por la brecha". El problema es que intersectamos el rayo con el plano ABC (obteniendo el punto P, por ejemplo) antes de probar contra la línea BC. Luego intersectamos el rayo con el plano BCD (obteniendo el punto Q, por ejemplo) antes de realizar la prueba contra la línea BC. P y Q están representados por la aproximación de coma flotante más cercana; no hay ninguna razón para esperar que estos se encuentren exactamente en los planos en los que se supone que se encuentran, y por lo tanto, cada posibilidad de que pueda tener ambas P a la izquierda de BC y Q a la derecha de BC.

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

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

Aquí hay algunas soluciones genuinas:

• Para mallas convexas, puedes probar contra todos los planos e ignorar los bordes y vértices, como dices (evitando así el problema por completo).

• No cruce el rayo con cada triángulo por turno. En cambio, use el producto triple escalar . (Este método realiza exactamente la misma secuencia de cálculos para el rayo y el borde 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, dale a los bordes y vértices cierto ancho. Es decir, coloque una esfera pequeña 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 detienen el rayo que pasa a través de los bordes y vértices de la malla.

Permítanme recomendar encarecidamente el libro Real-Time Collision Detection de Christer Ericson. Hay una discusión sobre este problema exacto en las páginas 446-448, y una explicación del enfoque escalar del producto triple para intersectar un rayo con un triángulo en las páginas 184-188.