Buena estructura de aceleración para pruebas de esfera de rayos con esferas que se mueven

Question

Estoy buscando la estructura de aceleración adecuada para hacer las pruebas de intersección de rayos y esferas (en un juego). se aplican las siguientes condiciones:

-hay cerca de 100 esferas y 100 rayos para poner a prueba uno contra el otro por trama

-las esferas se mueven en cada trama, también lo hacen los rayos

-hay pueden ser rayos/esferas añadido/borrado en cada cuadro (pero la mayoría de ellos será la misma entre dos marcos, simplemente se movió ligeramente)

cosa -whole está en 3D

una KD-Tree es muy bueno para la intersección Ray pruebas, pero desde las esferas mover, tendría que reconstruir el árbol KD en cada cuadro, que es costoso

un árbol Oct es más fácil de mantener, pero muy ineficaz para las pruebas de intersección de rayos.

no parece

100 rayos contra 100 esferas a ser mucho, pero estoy de codificación de recursos muy bajos, así que estoy buscando un poco de aceleración para que

alguien me puede dar algunas pistas sobre eso?

Answer 1

100x100 = 10k, una fuerza bruta optimizada no parece incoherente, especialmente esa prueba de intersección de rayos/esferas implica solo agregar/multiplicar. Siempre puede calcular previamente todos los vectores de rayos normalizados antes del ciclo principal.

Si hace la suposición de que vive en un universo delimitado y la densidad espacial de esferas y rayos es relativamente uniforme, puede usar una cuadrícula espacial fija (octárbol fijo) --algo como una grilla de celdas de 16x16x16, o más--, y:

• calcular previamente para cada células esfera de intersección (fácil de calcular, sólo implican unos pocos añade y comparaciones), almacenar en cada célula de la lista de esferas de intersección,
• para cada rayo, en un ciclo:
  • calcule la lista de celdas y cruces (un método basado en un algoritmo de Bresenham podría hacer el truco)
  • hacer la prueba de intersección para todas las esferas en esta lista de células.

De esa manera usted no tiene que almacenar cualquier rayo en cualquier árbol, sólo esferas. La eficiencia de este método depende del tamaño de la celda de relación/tamaño de la esfera, si no tiene demasiada dispersión en el tamaño de la esfera, puede ser una buena pista.

Si esferas no se cruzan entre sí y esfera tamaño de tener un mínimo, incluso se puede acotar la lista de esfera en la lista de celdas (número apropiado se deja como exercice al lector ...)

HTH