Baum numerisch stabil traversieren

[Nai]

Hallo liebes Forum!

Ich will einen Baum wie folgt entlang eines Strahls traversieren:

while(true)
{
Finde dasjenige Blatt in dem der Strahlenursprung ist von der Wurzel aus
Führe Schnittpunktberechnungen mit Blattinhalt aus
Berechne das Austrittsskalar des Strahls aus der Bounding Box des Blatts
Strahlenursprung += Austrittsskalar * Strahlenrichtung
}

Während die ersten beiden Schritte schon gut funktionieren so stellen micht die letzten beiden Schritte vor ein Problem. Denn auf Grund von numerischen Ungenauigkeiten kommt es oft vor, dass der neue Strahlenursprung wieder im selben Blatt liegt und der Algorithmus wieder beim nächsten Schleifendurchlauf das selbe Blatt findet oder noch schlimmer sich sogar fängt und immer das selbe Blatt findet. Mein bisheriger Fix hierfür war zuerst das Austrittskalar auf den Wertebereich >= 0 zu beschränken, da es auch auf Grund von numerischen Ungenauigkeiten negativ werden kann, und anschließend einen kleinen Wert draufzuaddieren um sicher zu stellen, dass der neue Strahlenursprung wegen numerischen Ungenauigkeiten nicht wieder im selben Blatt liegt. Die Wahl des kleinen Werts ist jedoch problematisch: Wähle ich ihn zu groß so verpasse ich Knoten, wähle ich ihn zu klein, so riskiere ich, dass sich der Algorithmus fängt.
Deswegen bin ich mit dieser Lösung unzufrieden, weshalb ich euch um euren Rat bitten würde, wie ihr das Problem möglichst performant lösen würdet.

MfG Nai

 

[Killkrog]

Kommt natürlich drauf an, um welche Datenmengen es geht, aber wäre es in deinem Fall möglich, eine Liste der bereits besuchten Blätter zu speichern? Solltest du mehrere Blätter pro Suchlauf finden, kannst du ggf eines wählen, welches zuvor noch nicht bearbeitet wurde. Wenn du keines findest, kannst du den Suchbereich erweitern.

Ich muss auch sagen, ich habe dein Problem noch nie bearbeitet, ich schieße also nur ins Blaue.

 

[DjNDB]

Ohne Code ist es schwierig etwas sinnvolles zu sagen, und du schreibst auch nicht worum es geht, auf welchem System es läuft, und welche Programmiersprache eingesetzt wird.
So in's Blaue ratend:
Handelt es sich um Raytracing?
Könnten die Ungenauigkeiten behoben werden, wenn Fließkommazahlen höherer Genauigkeit verwendet werden?
Wäre es alternativ eventuell möglich/sinnvoll die Zahlen zu skalieren um die Ungenauigkeiten zu verhindern? (z.B. Statt auf 0..1 Abbildung auf 0..1000)