Hi,

kennt jemand einen guten und vorallem schnellen Algorithmus um zu überprüfen ob ein Strahl (Undendlich lang) einen Würfel trifft?
Wo der schnittpunkt etc ist, ist dabei völlig egal, mir reicht nen Boolean wert der sagt "getroffen" oder "nicht getroffen"

Aya~

Mit einer sphere Vortesten und anschließend den Schnittpunkt mit 3 zuzr Strahlquelle gerichtenen Flächen überprüfen. (Man kann immer nur 3 Flächen eines Würfels gleichzeitig sehen)

Die sind eigentlich fast alles schnell, weils bei kisten recht einfach geht... Darf ich fragen, ob wir Orientierte Kisten oder Achsenparallele AABBs reden?

Hallo,

also ich hätte da einen Ansatz für einen allgemeinen Quader und einen Strahl.

Sagen wir einmal der Strahl ist gegeben durch die Gleichung f(x)=P+w*x, wobei P ein Aufpunkt des Strahls und w der Richtungsvektor ist.
Der Quader ist gegeben durch die Gleichung g(a,b,c)=Q+a*v1+b*v2+c*v3, wobei Q ein Eckpunkt ist, v1, v2 und v3 Vektoren, die den Quader vom Punkt Q aus aufspannen und a, b, c aus dem Intervall [0,1] sind.

Der Strahl schneidet den Quader, falls f(x)=g(a, b, c), also P+w*x=Q+a*v1+b*v2+c*v3

Daraus ergeben sich drei einzelne Gleichungen, jeweils für die Koordinaten x, y, z, also z.B.
P.z+w.z*x=Q.z+a*v1.z+b*v2.z+c*v3.z

Wenn man nach x umstellt bekommt man z.B.
x=((Q.z-P.z)+a*v1.z+b*v2.z+c*v3.z)/w.z

Jetzt muss man nur noch den minimalen und maximalen Wert für x berechnen.
Dazu muss man a, b und c (die immernoch aus dem Intervall [0,1] sind) so wählen, dass die rechte Seite der Gleichung minimal und maximal wird.

Für das Minimum : Falls z.B. v1.z, v2.z oder v3.z negativ sind, setzt man a=1, b=1 oder c=1, ansonsten 0
Für das Maximum : Falls z.B. v1.z, v2.z oder v3.z positiv sind, setzt man a=1, b=1 oder c=1, ansonsten 0

Man erhält dann für die drei Gleichungen drei Intervalle für x. Wenn man von diesen einen nichtleeren Durchschnitt erhält, schneidet der Strahl den Quader.

Ein Sonderfall ist noch, falls z.B. w.z=0 ist (dann ist die Division ja nicht erlaubt)
Dann lautet die Gleichung 0=x*w.z=((Q.z-P.z)+a*v1.z+b*v2.z+c*v3.z)
Man berechnet wieder Minimum und Maximum für die rechte Seite.
Gilt dann Minimum<=0<=Maximum ist alles ok, ansonsten ist ein Schnitt nicht möglich.

Viele Grüße
dj3hut1

Hi,

hab es hinbekommen
Hab nen PDF über nen schnellen effektiven Algo gefunden~

Aya~

PS: Es ging um Axis-Aligned Boxen