Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Ein kd-Tree ist ein binärer Suchbaum in Dimensionen.

Man verwendet beim Photon Mapping einen binären Suchbaum, weil dieser speichereffizient ist und die Nearest Neighbor Suche, die für den Radiance Estimate benötigt wird sehr effizient ist.

Erzeugung:

• Suche die Raumachse mit der größten Ausdehnung
• Entlang dieser Achse werden alle Photonen sortiert
• Das mittlere Photon wird ein neuer Knoten im Baum
• Alle kleineren Photonen kommen in den linken Teilbaum, alle größeren in den rechten
• Rekursive Anwendung auf beide Teilbäme