PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : BSP Tree, Sichtbarkeitstest zwischen 2 Punkte ohne die in den BSP tree aufzunehmen?

SimonX
2003-06-12, 00:44:20
Wenn ich einen statischen BSP Tree habe, ist es dann möglich festzustellen, ob zwei Punkt direkte Sichtbarkeit haben ohne diese Punkte in den BSP Treee auf zu nehmen?
Demirug
2003-06-12, 10:34:09
Ja das sollte eigentlich gehen. Ich hoffe ich bekomme das ganze noch richtig aus dem Kopf zusammen.

Man geht mit beiden Punkten gleichzeitig durch den Baum. Solange beide Punkte auf der gleichen Seite liegen wandert man diesen Zweig nach unten. Kommt man so bis zum Ende des Baums liegt kein Hinderniss zwischen den beiden Punkten.

Findet man nun aber eine Node bei der die Punkte nicht mehr auf der gleichen Seite liegen hat man möglicherweise ein Hinderniss gefunden. Nun muss man für alle Flächen die unterhalb dieser Node liegen noch eine genaue Prüfung durchführen.
KiBa
2003-06-12, 10:58:10
Original geschrieben von SimonX
Wenn ich einen statischen BSP Tree habe, ist es dann möglich festzustellen, ob zwei Punkt direkte Sichtbarkeit haben ohne diese Punkte in den BSP Treee auf zu nehmen?
jo, einfach mit der linie, welche aus den zwei punkten gebildet wird, den bsp-baum durchlaufen. bei jedem node splittest du die linie an der ebene. landest du bei dieser rekursion irgendwann in einem back-leaf, gibt es keine direkte sichtverbindung.
geht meist sehr schnell dieser algorithmus, ist eine viel genutzte anwendung von bsp-bäumen...