Superficie infinita del cono * Prueba de intersección AABB

Question

Estoy tratando de descubrir un algoritmo más rápido para probar si un conical surface alineado con el eje intersecta el volumen de un cuadro delimitador alineado con el eje.

El algoritmo actual he desarrollado es el siguiente:

• x = 0
• Para cada uno de los 4 bordes paralelos de la AABB:
  • Intersect su línea con el cono
  • Si el punto de intersección está dentro de la AABB:
    • Volver cierto.
  • Si el punto de intersección está en un lado específico de la AABB:
    • x + = 1
• Si x == 0 o x == 4 (todo el las intersecciones estaban en un lado de la AABB):
  • Devolver falso.
• Devuelve verdadero.

¿Alguien puede pensar en uno más eficiente? Esto parece hacer mucho trabajo extra al computar cada intersección de línea.

EDIT:

encima algoritmo es malo, por ejemplo:

El cono puede cortar un solo borde de la caja de manera que todas las intersecciones del eje de la línea son de una sola lado, por lo que el algoritmo anterior no funciona a menos que todos los bordes sean probados o los bordes a ser probados sean inteligentemente elegidos (¿quizás los bordes más cercanos al cono?).

EDITAR EDITAR: Vea a continuación mi propia respuesta para la solución que descubrí más tarde, que me parece casi óptima.

Answer 1

encontré otro, solución posiblemente óptima:

Antecedentes: La ecuación para un derecho abertura del cono unidad a lo largo del eje -z + es x^2 + y^2 - z^2 = 0

Encuentre el máximo y mínimo de x^2 + y^2 - z^2 sobre el AABB. Sugerencia: para x^2, el mínimo es abrazadera (0, xmin, xmax)^2 y el máximo es máximo (xmin^2, xmax^2).

• Si el intervalo resultante es completamente negativo, la caja está completamente dentro del cono.
• Si el intervalo resultante contiene 0, el cuadro se cruza con la superficie del cono.
• Si el intervalo resultante es completamente positivo, la caja está completamente fuera del cono.

Answer 2

En cuanto a parece que no hay una prueba de intersección cono/AABB conocida. ¡Así que estás solo, me temo!

Puede comenzar con el artículo de David Eberly "Intersection of a Triangle and a Cone" y ver cuánto de eso se puede adaptar a su situación. (En el peor de los casos, un AABB se compone de 12 triángulos, pero espero que pueda hacerlo mejor que eso.)

Answer 3

El link to the David Eberly article de @Gareth Rees es bueno, pero si divide todo en triángulos, Terminaré revisando vértices y bordes redundantes.Creo que esto va a funcionar bien:

1. (Opcional) comprobar si la AABB es enteramente en el lado opuesto del plano perpendicular al eje del cono. Si es así, no hay intersección.

2. Compruebe cada uno de los 8 vértices para ver si está dentro del cono. Si hay un vértice, el cono y la AABB se cruzan. Esto es bastante directo, pero se explica en la página 4 del enlace.

3. Compruebe cada uno de los 12 bordes para ver si se cruzan con el cono. Si lo hace cualquier borde, el cono y AABB se cruzan. Esto está en las páginas 4-5 del enlace.

4. Compruebe cada una de las 6 caras para ver si se cruzan con el cono. Si lo hace cualquier borde, el cono y AABB se cruzan. Es suficiente para el rayo de comprobación formado por el eje del cono contra el AABB; esta es una prueba de intersección bastante estándar.

En realidad, puede ser mejor cambiar el orden de la cara y el borde; Esperaría que los controles de la cara sean más rápidos que los de borde, por lo que es posible que pueda salir antes.

Probablemente hay algunas oportunidades agradables para optimizaciones SIMD ya que el número de vértices y aristas son ambos múltiplos de 4 y el cono es el eje alineados, pero eso es más allá del alcance de esta respuesta :)

Answer 4

he encontrado una mejor solución con la ayuda de piman en #gamedev:

Realice una prueba de círculo recto entre las caras superior e inferior de la AABB a lo largo del eje del cono con el círculo que el cono hace en su plano.

Si ambos rectángulos están afuera, el AABB está fuera del cono.

Answer 5

Se me ocurrió un algoritmo para resolver el caso general de un cono y un aabb arbitrarios, pero todavía maneja su caso específico de manera eficiente.

he descrito en otro hilo: Detect if a cube and a cone intersect each other?