Gerade Bewegung in einem Quader

Hallo,

ich habe ein Objekt, welches sich anhand einer Gerade durch einen Quader bewegt. Wenn das Objekt den Quader verlässt soll es gelöscht und am anderen "Ende" der Gerade durch den Quader wieder auftauchen.
Das Problem dabei ist, dass mir keine effiziente Lösung einfällt um das umzusetzen. Das logisch einfachste ist, anhand der geschnittenen Ebene am Rand des Quaders auszurechnen, welche Ebene auf der anderen Seite geschnitten wird und für diese dann den Schnittpunkt mit der Geraden ausrechnen. Allerdings kommt mir das für drei Dimensionen extrem aufwändig vor, da man zig Fallunterscheidungen treffen muss.
Gibt es da irgendwelche einfachereren Tricks? Ich hoffe ich konnte halbwegs verständlich erklären, was mein Problem überhaupt ist

Ist der Quader frei im Raum orientiert oder in der Basis des Koordinatensystems?

Der Quader wird durch einen Punkt P und einem Vektor (X,Y,Z) beschrieben. Dabei erstreckt er sich von P aus in alle Richtungen um den jeweiligen Richtungsbetrag des Vektors. Die Eckpunkte sind also

P+X+Y+Z
P+X+Y-Z
P+X-Y+Z
P+X-Y-Z
P-X+Y+Z
P-X+Y-Z
P-X-Y+Z
P-X-Y-Z

rapso

klingt nach derselben basis wie das koordinatensystem, in dem fall hast du 6 simple moeglichkeiten wo sich das objekt ausserhalb des quaders befinden kann (p+x,p-x,p+y,p-y,p+z oder p-z) und wenn du das feststellst, dann musst du es entsprechend die doppelte entfernung in die gegenrichtung bewegen 2*(-x,+x,-y,+y,-z oder +z).

Wenn ich das richtig verstanden habe sagst du, dass wenn das Objekt über eine xy-Kantenebene hinaus ist und im P im Ursprung liegt, dass ich den z-Wert einfach negieren müsste. Wenn man das ganze jetzt mal einfacher halber im zweidimensionalen betrachtet:
Ich habe eine Quadrat mit der Kantenlänge 4. In der Mitte des Quadrats liegt der Punkt (0,0). Jetzt bewegt sich mein Objekt entlang der Gerade (0,0)+t*(2,1). Das Objekt wird die x=2 Kante im Punkt (2,1) schneiden. Wenn ich jetzt aber einfach nur den x-Wert negiere, dann ist das Objekt aber plötzlich im Punkt (-2,1) und bewegt sich entlang der Geraden (-2,1)+t*(2,1), was eine andere Gerade ist. Korrekt wäre in diesem Fall, dass das Objekt in den Punkt (-2,-1) verschoben wird. Aber wie ich das effizient für drei Dimensionen und beliebige Quader hinbekomme ist mir noch rätselhaft.

rapso

ach das meinst du mit 'anderes "ende"'.
ich nahm an damit hattest du das andere ende vom quader gemeint (also die spiegelnde seite).

wenn deine gerade mit o+r*m beschrieben ist (o ursprung,r richtung, m schritt).

in deinem fall gibt es ja nur 2 punkte die du kennen musst, du kannst das objekt beim initialisieren von o aus in +r und in -r laufen lassen bis es den quader an irgend einer achsen-ebene verlaesst. anschliessend teilst du die laenge zwischen den zwei punkten durch die schrittweite (also vectorlaenge r,|r|) um die schrittmenge n zu erhalten.

anschliessend musst du nur noch, immer wieder, m von 0 bis n inkrementieren und die position deines objektes ist entsprechend dem oberen.

falls dich das alles eigentlich nicht interesiert und deine frage nur ist wie du die schnittpunkte aus 3d wuerfel und strahl errechnest, dann ist das quasi "standard" verfahren: http://www.cs.utah.edu/~awilliam/box/

Finnegan

Flash der Blitz schrieb:

Wenn ich das richtig verstanden habe sagst du, dass wenn das Objekt über eine xy-Kantenebene hinaus ist und im P im Ursprung liegt, dass ich den z-Wert einfach negieren müsste. Wenn man das ganze jetzt mal einfacher halber im zweidimensionalen betrachtet:
Ich habe eine Quadrat mit der Kantenlänge 4. In der Mitte des Quadrats liegt der Punkt (0,0). Jetzt bewegt sich mein Objekt entlang der Gerade (0,0)+t*(2,1). Das Objekt wird die x=2 Kante im Punkt (2,1) schneiden. Wenn ich jetzt aber einfach nur den x-Wert negiere, dann ist das Objekt aber plötzlich im Punkt (-2,1) und bewegt sich entlang der Geraden (-2,1)+t*(2,1), was eine andere Gerade ist. Korrekt wäre in diesem Fall, dass das Objekt in den Punkt (-2,-1) verschoben wird. Aber wie ich das effizient für drei Dimensionen und beliebige Quader hinbekomme ist mir noch rätselhaft.

Mir ist etwas unklar wohin sich die bisherige Diskussion bewegt, vielleicht habe ich auch etwas falsch verstanden. Nach meinem Verständnis benötigst du die Schnittpunkte (Eintritts- und Autrittspunkt) einer Geraden mit einem (beliebigen?) Quader (?). Das zu Berechnen benötigt schon eine gewisse menge an Fallunterscheidungen, nach meinem Wissen gibt es da kein "geniales" Verfahren, das mit ein oder zwei Zeilen Code auskommt

Ich würde das Problem (das ich hoffentlich richtig verstanden habe) folgendermassen angehen:

Man kann der Einfachheit halber annehmen dass der Quader im Nullpunkt zentriert ist und (falls du das überhaupt benötigst) keine Rotation hat. Das nenne ich mal das lokale Koordinatensystem des Quaders. Für beliebige Quader kannst du die Gerade in das Quader-Koordinatensystem transformieren, indem für den Stützvektor der Geraden die inverse Quader-Transformation durchführst (negative Verschiebung und umgekehrte Rotation) und für den Richtungsvektor der Geraden die umgekehrte Rotation.
Wenn du keine Rotation hast, bedeutet das lediglich den Punkt P des Quaders vom Stützvektor der Geraden zu subtrahieren, um den Stützvektor der Geraden in Quader-Koordinaten zu erhalten. Alle folgenden Berechnungen werden dann in Quader-Koordinaten gemacht, wodurch das Ganze relativ simpel wird (Quader-Mittelpunkt ist [0, 0] und alle Seitenflächen des Quaders sind parallel zu den Koordinatenachsen).

Nun berechnest du für alle Ebenen in denen die Seitenflächen den Quaders liegen die Schnittpunkte mit der Geraden (ich denke du weisst wie du das machst). Wenn sich die Gerade in allgemeiner Lage befindet (also nicht parallel zu einer der Koordinatenachsen liegt) erhältst du 6 Schnittpunkte, die aber nicht zwangsläufig auch auf dem Quader liegen müssen, da du die Schnittpunkte für Ebenen mit unendlicher Ausdehnung berechnet hast. Wenn die Gerade parallel zu einer Koordinatenachse liegt, müsstest du bei der Berechnung der Schnittpunkte auf eine Divison durch 0 stossen, was man voeher abfangen sollte. In diesem Fall gibt es keine Schnittpunkte mit den entsprechenden Ebenen oder aber unendlich viele (es kann sein dass eine Gerade genau durch eine Kante des Quaders läuft - wenn du diesen Fall behandeln willst sind die Eintritts- und Austrittspunkte genau die Eckpunkte den Quaders zwischen denen die Kante verläuft).

Für die Schnittpunkte musst du dann noch bestimmen, ob sie auf dem Quader liegen oder außerhalb: Wenn du z.B. die Schnittpunkte mit den beiden zur YZ-Ebene parallelen Quader-Ebenen berechnest hast du die X-Koordinate der Geraden vorgegeben (+X deines Ausdehnungsvektors des Quaders für die eine Ebene und -X für die andere). Diese X-Koordinate liegt auf dem durch die Quader-Ebenen begrenzten Quader. Du musst also nun für die berechneten Y- und Z-Koordinaten den Schnittpunkts noch ermitteln, ob diese auf dem Quader liegen, indem du prüfst ob diese im jeweiligen Koordinaten-Intervall für den Quader liegen ([-Y, +Y] und [-Z, +Z]).

Berechnete Schnittpunkte, die nicht auf dem Quader liegen, fallen weg (die schneiden nur die undendlich ausgedehnten Ebenen, nicht jedoch den räumlich begrenzten Quader).

Am Ende erhältst du 0, 1 oder 2 Schnittpunkte (Gerade schneidet nicht oder unendlich oft [Sonderfall-Behandlung?], Gerade schneidet genau einen Eckpunkt, Gerade hat Eintritts- und Austrittspunkt).

Für 2 Schnittpunkte hast du dann das Ergebnis, das du (nach meinem Verständnis) haben möchtest: Wenn das Objekt sich nicht innerhalb des Quaders befindet ist derjenige Punkt, der in Richtung der Bewegungsrichtung des Objektes am nächsten an der Position des Objekts befindet der Eintrittspunkt und der andere der Austrittspunkt.

Allerdings: Die Punkte sind noch in Quader-Koordinaten angegeben (die Vereinfachung am Anfang). Um die Schnittpunkte in Welt-Koordinaten zu berechnen müssen diese nochmal mit der Quader-Transformation transformiert werden, also für einen nicht-rotierten Quader einfach nochmal den Positionsvektor des Quaders P zu den Punkten hinzuaddieren.

Hoffe das war hilfreicher als es verwirrend war
Finnegan