KDTree

De Codepixel

Los Kd trees son una especializacion de los arboles BSP, con la diferencia de que todos los planos son "axis aligned". Por lo tanto, están a medio camino de los BSP's y de los Octree's. Nos permiten pasar rapidamente los polígonos que tienen intersección con un rayo (como hace el mental ray) o para encontrar que puntos tenemos cerca (como el photon mapping).

Hablar de Kd trees es hablar de Vlastimil Havran, y sus abundantes estudios publicados sobre la eficiencia de esta estructura.

Se ha demostrado que, en una CPU, es la estructura más rápida para consultar la intersección rayo/triangulo, pero para que se cumpla, tenemos que aplicar un proceso de construcción muy costoso, por lo que en la práctica, no es la estructura más usada (descartado en escenas dinámicas).

  • Vlastimil Havran : Profunda tesis sobre los KD trees orientado a raytracing. Analiza los costes de creacion y de recorrido, y propone formas de optimizarlos.
Herramientas personales
Navegación
Herramientas