|
Wednesday, 11 February 2004 |
Los K-d 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). Aquí tenemos una lista de enlaces con tutoriales y descripción de los algoritmos:
A tutorial on kd-trees
es un completo tutorial que nos explica muy detenidamente que es, y como se construye, a de mas de varias tecnicas de optimizacion. Muy bueno si vamos a empezar a trabajar con ellos.
interactive demo en java que nos muestra un kdtree en construccion. Tambien incluye un simple pseudocodigo para terminar la implementacion.
Quick KD-Tree Tutorial Uno de los tutoriales mas raro sque he visto. El autor ha tardado mas en hacer el fondo que en hacer el tutorial.
FlipCode como no, esta web tambien tiene una introduccion a estos arboles, y comenta su relacion con los octrees.
Octrees and 3DDDA es un hilo de discusion en google que aplica el algoritmo 3dda para recorrer un octree. Tambien podemos sacar algunas ideas para recorrer el kd-tree
Kd-Trees es una definicion del algoritmo, y una lista de implementaciones.
Presentacion en PowerPoint del algoritmo de los KDtrees y los BSP's(version HTML)
|
Noticias 
