performance - Mejora del rendimiento del trazador de rayos.

graphics raytracing (9)

Estoy escribiendo un trazador de rayos / trazador de trayectoria comparativamente sencillo en D ( http://dsource.org/projects/stacy ), pero incluso con la optimización completa todavía se necesitan varios miles de ciclos de procesador por rayo. ¿Hay algo más que pueda hacer para acelerarlo? De manera más general, ¿conoce buenas optimizaciones / enfoques más rápidos para el trazado de rayos?

Edit: esto es lo que ya estoy haciendo.

El código ya se está ejecutando altamente paralelo
los datos temporales se estructuran de manera eficiente en caché y se alinean a 16b
Pantalla dividida en 32x32-tiles
La matriz de destino está organizada de tal manera que todos los píxeles subsiguientes en un mosaico son secuenciales en la memoria
Se realizan optimizaciones básicas de gráficos de escena.
- Las combinaciones comunes de objetos (plano-plano CSG como en cuadros) se reemplazan con objetos preoptimizados
Estructura de vectores capaz de aprovechar el soporte de vectorización automática de GDC.
Los impactos subsiguientes en un rayo se encuentran a través de una evaluación perezosa; Esto evita cálculos innecesarios para CSG.
Triángulos ni apoyados ni prioritarios. Solo primitivas simples, así como operaciones de CSG y propiedades básicas del material
Se admite la delimitación

Algunas sugerencias.

Usa objetos delimitadores para fallar rápido.
Proyecte la escena en un primer paso (como hacen las tarjetas gráficas comunes) y use el trazado de rayos solo para cálculos de luz.
Paraleliza el código.

La mejora típica de primer orden de la velocidad del trazador de rayos es una especie de esquema de partición espacial. Basado solo en la página de resumen del proyecto, parece que no lo has hecho.

Probablemente el enfoque más habitual es un octárbol, pero el mejor enfoque puede ser una combinación de métodos (por ejemplo, árboles de partición espacial y cosas como el buzón). Las pruebas de cuadro / esfera delimitadoras son un método rápido y desagradable, pero debe tener en cuenta dos cosas: 1) no ayudan mucho en muchas situaciones y 2) si sus objetos ya son primitivos simples, no ganará mucho (y hasta podría perder). Puede (más que octree) implementar una cuadrícula regular para la partición espacial, pero solo funcionará muy bien para escenas que se distribuyen de manera uniforme (en términos de ubicaciones de superficie)

Mucho depende de la complejidad de los objetos que representa, su diseño interno (es decir, permite transformaciones locales, copias de objetos de referencia, superficies implícitas, etc.), así como la precisión con la que está tratando de ser. Si está escribiendo un algoritmo de iluminación global con superficies implícitas, las compensaciones pueden ser un poco diferentes que si está escribiendo un trazador de rayos básico para objetos de malla o lo que sea. No he examinado su diseño en detalle, así que no estoy seguro de qué, si alguno, de lo anterior ya ha pensado.

Al igual que con cualquier proceso de optimización del rendimiento, primero tendrá que medir para saber dónde está gastando el tiempo y luego mejorar las cosas (algorítmicamente por preferencia, luego por código) por necesidad.

Mi primera pregunta es: ¿está tratando de optimizar el rastreo de una sola pantalla fija, o se trata de optimizar el rastreo de múltiples pantallas para calcular una animación?

Una cosa es optimizar la optimización para un solo disparo. Si desea calcular fotogramas sucesivos en una animación, hay muchas cosas nuevas en las que pensar / optimizar.

No sé D en absoluto, por lo que no puedo mirar el código y encontrar optimizaciones específicas, pero puedo hablar en general.

Realmente depende de sus necesidades. Una de las optimizaciones más simples es reducir el número de reflexiones / refracciones que puede seguir cualquier rayo en particular, pero luego comienza a perder el "resultado perfecto".

El trazado de rayos también es un problema "vergonzosamente paralelo" , por lo que si tiene los recursos (como un procesador de varios núcleos), podría calcular múltiples píxeles en paralelo.

Más allá de eso, es probable que solo tengas que hacer un perfil y descubrir qué es exactamente lo que está tardando tanto, y luego intentar optimizarlo. ¿Es la detección de intersección? Luego, trabaja en la optimización del código para eso, y así sucesivamente.

Primero debe asegurarse de usar algoritmos muy rápidos (implementarlos puede ser un verdadero problema, pero qué quiere hacer y cuánto quiere que vaya y qué tan rápido debería ser, eso es una especie de intercambio).

Algunas sugerencias más de mi parte: no utilice técnicas de correo electrónico, en los documentos se discute a veces que no se ajustan tan bien a las arquitecturas reales debido a la sobrecarga de conteo. No utilice BSP / Octtrees, son relativamente lentas. - no use la GPU para Raytracing, es demasiado lento para efectos avanzados como la reflexión y las sombras y la refracción y el mapeo de fotones, etc. (lo uso solo para sombrear, pero esta es mi cerveza)

Para una escena estática completa, los árboles-kd son imbatibles y para las escenas dinámicas hay algoritmos inteligentes que se escalan muy bien en un quadcore (no estoy seguro del rendimiento anterior).

Y, por supuesto, para obtener un rendimiento realmente bueno, necesita usar mucho código SSE (con, por supuesto, no demasiados saltos), pero no para un rendimiento "tan bueno" (estoy hablando de un 10 a un 15% tal vez). para implementar tus cosas SSE.

Y algunos documentos decentes sobre algunos algoritmos de los que estaba hablando:

"Rayos rápidos / Caja delimitadora alineada con el eje: Pruebas de superposición que utilizan Ray Slopes" (prueba de impacto AABB-Ray paralelisizable (SSE) Ray muy rápida) (tenga en cuenta que el código del documento no es todo el código, solo busque el título de Google el papel, lo encontraras

http://graphics.tu-bs.de/publications/Eisemann07RS.pdf

"Ray Rastreo de escenas deformables utilizando jerarquías de volumen de límite dinámico"

http://www.sci.utah.edu/~wald/Publications/2007///BVH/download//togbvh.pdf

Si sabes cómo funciona el algoritmo anterior, este es un algoritmo mucho mayor:

"El uso de grupos de triángulos precomputados para el trazado acelerado de rayos en escenas dinámicas"

http://garanzha.com/Documents/UPTC-ART-DS-8-600dpi.pdf

También estoy usando la prueba pluecker-test para determinar la rapidez (no es precisa, pero bueno, no se puede tener todo) si golpeo un polígono, funciona muy bien con SSE y superior.

Así que mi conclusión es que hay tantos artículos excelentes sobre tantos temas que se relacionan con el trazado de rayos (cómo construir árboles rápidos y eficientes y cómo sombrear (modelos BRDF) y así sucesivamente), es una realidad increíble e interesante campo de "experimentación", pero también es necesario tener mucho tiempo libre porque es muy complicado pero divertido.

Raytrace cada otro píxel. Consigue el color intermedio por interpolación. Si los colores varían mucho (estás en el borde de un objeto), raya el píxel que se encuentra en el medio. Es trampa, pero en escenas simples casi puede duplicar el rendimiento mientras se sacrifica algo de calidad de imagen.

Renderiza la escena en GPU, luego vuelve a cargarla. Esto te dará el primer golpe de rayo / escena a velocidades de GPU. Si no tiene muchas superficies reflectantes en la escena, esto reduciría la mayor parte de su trabajo a una representación simple y antigua. Desafortunadamente, la representación de CSG en GPU no es completamente sencilla.

Lee el código fuente de PovRay para inspirarte. :)

Tú podrías

utilizar una jerarquía de volumen de límite optimizada por SAH ...
... eventualmente usando el recorrido de paquetes,
introducir muestreo de importancia,
acceder a los mosaicos ordenados por el código Morton para una mejor coherencia de caché, y

Mucho más, pero esas fueron las sugerencias que se me ocurrieron de inmediato. En mas palabras

Puede crear una jerarquía optimizada basada en estadísticas para identificar rápidamente los nodos candidatos cuando se interseca la geometría. En su caso, tendrá que combinar la jerarquía automática con la jerarquía de modelado, es decir, restringir la compilación o hacer que finalmente se clone la información de modelado.

"Recorrido de paquetes" significa que usa las instrucciones SIMD para calcular 4 escalas paralelas, cada una de un rayo propio para atravesar la jerarquía (que suele ser el punto caliente) con el fin de exprimir al máximo el rendimiento del hardware.

Puede realizar algunas estadísticas por rayo para controlar la frecuencia de muestreo (número de rayos secundarios tomados) en función de la contribución al color de píxel resultante.

El uso de una curva de área en el mosaico le permite disminuir la distancia de espacio promedio entre los píxeles y, por lo tanto, la probabilidad de que su rendimiento se beneficie de los resultados de caché.

Una cosa que aprendí con mi trazador de rayos es que muchas de las reglas antiguas ya no se aplican. Por ejemplo, muchos algoritmos de trazado de rayos hacen muchas pruebas para obtener una "salida temprana" de un cálculo computacionalmente costoso. En algunos casos, encontré que era mucho mejor eliminar las pruebas adicionales y ejecutar siempre el cálculo hasta su finalización. La aritmética es rápida en una máquina moderna, pero una predicción de rama perdida es costosa. Obtuve algo como una aceleración del 30% en mi prueba de intersección de polígono de rayos reescribiéndolo con un mínimo de ramas condicionales.

A veces el mejor enfoque es contraintuitivo. Por ejemplo, descubrí que muchas escenas con algunos objetos grandes se ejecutaban mucho más rápido cuando las dividía en una gran cantidad de objetos más pequeños. Dependiendo de la geometría de la escena, esto puede permitir que su algoritmo de subdivisión espacial arroje muchas pruebas de intersección. Y seamos sinceros, las pruebas de intersección se pueden hacer tan rápido. Tienes que eliminarlos para conseguir una aceleración significativa.

Los volúmenes delimitadores jerárquicos ayudan mucho, pero finalmente arreglé el árbol kd y obtuve un GRAN aumento de velocidad. Por supuesto, construir el árbol tiene un costo que puede hacer que sea prohibitivo para la animación en tiempo real.

Esté atento a los cuellos de botella de sincronización.

Tienes que hacer un perfil para asegurarte de centrar tu atención en el lugar correcto.

¿Hay algo más que pueda hacer para acelerarlo?

D, dependiendo de la implementación y el compilador, presenta un rendimiento razonablemente bueno. Como no ha explicado qué métodos de rastreo de rayos y optimizaciones está usando, no puedo brindarle mucha ayuda allí.

El siguiente paso, entonces, es ejecutar un análisis de tiempo en el programa, y recodificar el código más usado o el código más lento que impacta el rendimiento más en el ensamblaje.

Más generalmente, echa un vistazo a los recursos en estas preguntas:

Realmente me gusta la idea de usar una tarjeta gráfica (una computadora masivamente paralela) para hacer algo del trabajo.

Hay muchos otros recursos relacionados con el trazado de rayos en este sitio, algunos de los cuales se enumeran en la barra lateral de esta pregunta, la mayoría de los cuales se pueden encontrar en la raytracing .