kd-tree + ray"tracing"

[Pigeon]

Hallo.
Meine 3D Daten sollen in einem kd-tree repräsentiert werden. Nun kann ich leider überhaupt nicht nachvollziehen wie....

... man damit zum Beispiel ein Dreieck per Mausklick selektieren kann! Das ist ja eigendlich nichts anderes als Raytracing mit nur einem Strahl!?
Muss ich den Strahl in mehrere Teile unterteilen und dann immer wieder schauen wie nah der nächste Punkt ist oder wie funktioniert denn das?
Der kd-Baum lässt ja Suchalgorithmen a la "welche Punkte sind in diesem Rechteck enthalten", "Existiert genau dieser Punkt" oder "Wie lautet der nächste benachbartste Punkt X von Punkt Y"

... man von dem Punkt auf das Dreieck schliessen kann. Klar man kann zB in jedem Vertex eine Liste der benachbarten Dreiecke speichern oder auch andere aufwändigere topolgische Datenstrukturen entwerfen. Aber solche Details hat google mir nicht verraten können. (Sourcen überfordern mich derzeit sehr)

Ein völliges Rätzel bleibt mir jedoch das Raytracing.

BITTE nicht auf google verweisen - das habe ich heute schon über 8 Studen gemacht. Danke!

[Blue-Tiger]

Willst du wissen wie man den kd-Tree aufbaut oder wie man ihn schlussendlich traversiert ( = einen Strahl durchschickt)?

Fuers Aufbauen gibts mehrere Heuristiken. Grundsaetzlich gehts immer so:
1. Such dir eine Achse aus, an der du die Trennlinie ziehst (X, Y oder Z)
2. Such dir einen Punkt auf der Achse auf, an dem du den Raum unterteilst.
3. Speichere den Trennpunkt. Falls Abbruchbedingung (z. B. Rekursionstiefe, Anzahl Objekte in den Teilraeumen, ...) noch nicht erreicht: Gehe fuer beide Teilraeume wieder zu Punkt 1

Je nach Heuristik sehen Auswahl der Achse, Auswahl des Trennpunkts und Abbruchbedingung anders aus. Das Traversieren ist auch nicht weiter schlimm.

Einen sehr guten Ueberblick ueber die verschiedenen Heuristiken/Traversieralgors gibts z. B. hier: http://www.cgg.cvut.cz/~havran/phdthesis.html , sollte dir das nicht zu hoch sein.