Prüfen, ob eine Linie durch einen Würfel geht.

  • VB.NET
  • .NET (FX) 4.0

Es gibt 29 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Prüfen, ob eine Linie durch einen Würfel geht.

    Also ich würde gerne eine Hitbox machen, die überprüft, ob eine Linie durch sie hindurch geht. Es ist ein Würfel (wovon alle Koordinaten verfügbar sind (der ecken, Mittelpunkt, Abstand zur Wand, Normals)) und bei der Linie wären es dann die Länge und beide Punkte.
    Mir ist leider nichts dazu eingefallen und google hat auch nicht viel geholfen. Ich hab schonmal sowas ähnliches mit einer For...Next schleife gemacht aber es hat dann eine andere Hitbox am Rand der einen ausgewählt. (und die Schleife ging in 1-er abständen, und man kann sie ja nicht unendlich klein machen, da es sonst bei 60x pro Sekunde laggen würde.)

    00yoshi schrieb:

    Es ist ein Würfel
    Ohne mich jetzt ganz tief einzudenken:
    Schnittpunkte von Gerade und Kugel lassen sich elementar lösen: Kürzester Abstand einer Geraden zu einem Punkt.
    Wenn die Gerade die Um-Kugel des Würfels nicht schneidet => kein Schnittpunkt.
    Wenn die Gerade die In-Kugel des Würfels schneidet => Schnittpunkt.
    Wird die Um-Kugel geschnitten und die In-Kugel nicht, musst Du weiterrechnen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Ich würde so vorgehen:
    1. Schnittpunkt der Geraden mit einer der Ebenen, auf denen die Würfelseiten liegen, berechnen (wirst du mit Google schnell was finden).
    2. Diesen Punkt nun in 2D bringen und mittels Point-in-Polygon-Algorithmen prüfen, ob der Punkt in dem Bereich der Würfelseite liegt.

    WhitePage schrieb:

    Was ist

    WhitePage schrieb:

    Eine Linie ist immer unendlich (mit einer Gleichung).
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    WhitePage schrieb:

    Was ist ein
    Projektion in eine Ebene.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    WhitePage schrieb:

    3D-Linie
    Linie mit (x,y,z) im Raum ist 3D.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    nein, eine Gerade ist im R3 nie ein 2D-Objekt. Es gibt grundsätzlich zwei Möglichkeiten, wie du das verstehen könntest:
    1. Die Anzahl der Dimensionen des Raumes, in dem sich die Gerade befindet -> wäre in dem Fall 3 also ist die gerade auch dreidimensional
    2. Die Dimension des abstrakten Objektes selber ohne Berücksichtigung irgend eines Raumes -> damit wäre ne Gerade ein eindimensionales Objekt (unendlich viele Punkte, also nulldimensionale Objekte, hintereinander)
    Ich würde vorschlagen, ihr einigt euch erst einmal auf einheitliche Bezeichnungen. Hier herrscht teilweise ein ziemliches Durcheinander darüber, was nun eine Linie, eine Gerade, eine Ebene, eine Fläche und was ein leckeres saftiges Steak ist... ;)

    Da der TE am Anfang von einer Linie sprach, ging ich unmissverständlich von einer Strecke aus, die eine gerade Verbindung von zwei Punkten darstellt. Dabei ist es übrigens egal, ob die Punkte im R2, R3 oder Rn liegen. Hier kann man wohl der Einfachheit halber annehmen, dass es sich um Punkte im R3 (also dem Raum mit drei Dimensionen) handelt.
    Eine Gerade hingegen ist für mich eine unendliche "Linie" (hust) die ebenfalls im Rn liegt und meist durch zwei Punkte, die "irgendwo" auf ihr liegen oder einen Punkt und einen Richtungsvektor eindeutig definiert ist. Die Kombination "Punkt" und "Richtung" ist übrigens gleichbedeutend mit der sog. "Geradengleichung". Diese wird man wohl tatsächlich für die Aufgabe benötigen, aber das sollte eigentlich kein Problem sein, schließlich kann man aus den zwei Endpunkten der Linie(!) bequem die Gleichung der Geraden herleiten, auf der diese Linie liegt.

    Zum Problem selbst:
    Ich würde zunächst für beide Punkte (Start- und Endpunkt der Linie) testen, ob mind. einer davon innerhalb des Würfels liegt. Das sollte nicht so schwer sein und oben gab es bereits einen Link, wo eine Lösung aufgeführt war.
    Dummerweise kann es halt vorkommen, dass beide Punkte außerhalb des Würfels liegen, die Linie aber dennoch durch den Würfel geht.
    Mithilfe der Flächennormalen des Würfels muss man dann für jede Seite prüfen, ob die Z-Positionen beider Punkte in Bezug auf die jeweilige Fläche unterschiedliche Vorzeichen haben. Ist das der Fall, dann schneidet die Linie mindestens die Ebene(!), in der die Würfelfläche liegt. Dann muss man tatsächlich den Umriss des Würfels in diese Ebene projizieren (was aber angesichts der Geometrie eines Würfels wirklich nicht kompliziert sein dürfte) und dann überprüfen, ob der Schnittpunkte der Geraden(!) mit der Ebene(!) innerhalb des Quadrats liegt, das bei der Projektion entsteht.
    Gibt es einen Treffer, kann man abbrechen, ansonsten muss man das für alle sechs Würfelflächen durchlaufen, bevor man sichergehen kann, dass die Linie an keiner Stelle den Würfel schneidet oder berührt.

    Naja... die Berechnungen an sich musst du jetzt selbst durchführen. Aber ich glaube, wenn man mit Vektoren und Matrizen schonmal zu tun hatte, sollte das nicht mehr so schwer sein... :D

    PS: *klugscheißmodus an*
    Im obigen Link wurde auch erklärt, wie man testet, ob zwei "Boxen" (also Quaderförmige Körper) sich irgendwo überschneiden. Dort wurde behauptet, man müsse nur testen, ob mind. einer der Punkte der einen Box innerhalb der anderen läge - und umgekehrt. Leider ist diese Lösung falsch. Denn auch hier fällt mir mindestens ein Beispiel ein, bei dem jeweils jeder Eckpunkt jedes Quaders nicht innerhalb des jeweils anderen Quaders liegt, die Körper sich aber dennoch überschneiden.
    Weltherrschaft erlangen: 1%
    Ist dein Problem erledigt? -> Dann markiere das Thema bitte entsprechend.
    Waren Beiträge dieser Diskussion dabei hilfreich? -> Dann klick dort jeweils auf den Hilfreich-Button.
    Danke.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Arby“ ()

    Ich würde vorschlagen den Würfel in folgender Form zu definieren.
    s + r * [1;0;0] + t * [0;1;0] + d * [0;0;1]
    = [s + r; s + t; s + d]
    Wobei gelten muss: {r,t,d} < k (Kantenlänge)
    Nun kann man die Gleichung des Würfels mit der der Geraden gleichsetzten.
    Ist nur eine Idee. Weiß nicht ob das klappt :)
    st aber dann wahrscheinlich nicht eindeutig lösbar, weil man 3 Gleichungen, aber 4 Unbekannte hat.
    @WhitePage
    Folgender Code, den ich da gefunden hab, ist ein bisschen zu kompliziert, finde ich.
    Spoiler anzeigen
    function PunktinEllipse(p: TD3DXVector3; x, y, z: single; matWorld: TD3DXMatrix);
    var matScale : TD3DXMatrix;
    newposition : TD3DXVector3;
    begin
    D3DXMatrixScaling(matScale, x, y, z);
    D3DXMatrixMultiply(matScale, matScale, matWorld);
    D3DXMatrixInverse(matScale, nil, matScale);

    D3DXVec3TransFormCoord(newposition, p, matScale);

    result := sqr(newposition.x) + sqr(newposition.y) + sqr(newposition.z) < 1;
    end;

    p ist der zu überprüfende Punkt. x, y und z die
    Radien der Ellipse und matWorld die Worldmatrix der Ellipse.

    4. Punkt in 3D Box

    Jetzt kommen die wirklich geilen Algorithmen :) Der folgende Algorithmus soll
    nun zeigen, wie man einen beliebigen Punkt mit einer beliebigen Box
    überprüfen kann. Dabei spielt die Lage der Box absolut keine Rolle.
    Jede Position ist möglich. Das Verfahren ist recht simple. Über den
    Normalvektor einer jeder Fläche schauen wir einfach, ob der Punkt vor oder
    hinter der Fläche liegt. Liegt er davor, dann ist er außerhalb der
    Box und man braucht erst garnicht weiter zu machen. Hier mal ein kleines Bild
    dazu:

    Auf dem Bild erkennt ihr eine Box. Die Pfeile sind
    die Normalvektoren. Der Punkt liegt in diesem Fall außerhalb der Box,
    weil er bei mindestens einer Seite außerhalb liegt. Die
    Überprüfung würde nun so aussehen, das man jede Seite mit dem
    Normalvektor durchgeht und schaut, ob der Punkt davor oder dahinter liegt. Doch
    dafür brauchen wir erstmal eine Struktur, die eine Box darstellt. Wir
    haben dafür folgende genommen.

    type
    TD3DBox8 = record
    point: array [1..8] of TD3DXVector3;
    end;

    Eine Box ist also einfach nur eien Struktur aus 8 Punkten.
    Welcher Punkt wo liegt, das könnt ihr an dem oberen Bild ablesen. Eine
    fertige Funktion sieht nun so aus. Dabei wird der zu überprüfende
    Punkt und die zu überprüfende Box übergeben:

    function PunktinBox(p: TD3DXVector3; box: TD3DBox8): boolean;

    //Dies ist nur eine Hilfsfunktion um 2 Vektoren zu Subtrahieren
    function vectorsub(v1, v2: TD3DXVector3): TD3DXVector3;
    begin
    result.x := v1.x - v2.x;
    result.y := v1.y - v2.y;
    result.z := v1.z - v2.z;
    end;

    var normal: TD3DXVector3;
    collision: boolean;
    begin
    //Sobald der Punkt auch nur bei einer Ebene außerhalb ist findet
    //KEINE Kollision statt

    collision := true;

    //Plane unten
    D3DXVec3Cross(normal, VectorSub(box.point[2], box.point[1]),
    VectorSub(box.point[3], box.point[1]));
    if D3DXVec3Dot(normal, vectorsub(p, box.point[1])) >= 0 then collision := false;

    //Plane oben
    if collision then
    begin
    D3DXVec3Cross(normal, VectorSub(box.point[7], box.point[5]),
    VectorSub(box.point[6], box.point[5]));
    if D3DXVec3Dot(normal, vectorsub(p, box.point[5])) >= 0 then collision := false;
    end;

    //Plane vorne
    if collision then
    begin
    D3DXVec3Cross(normal, VectorSub(box.point[7], box.point[3]),
    VectorSub(box.point[4], box.point[3]));
    if D3DXVec3Dot(normal, vectorsub(p, box.point[3])) >= 0 then collision := false;
    end;

    //Plane hinten
    if collision then
    begin
    D3DXVec3Cross(normal, VectorSub(box.point[5], box.point[1]),
    VectorSub(box.point[2], box.point[1]));
    if D3DXVec3Dot(normal, vectorsub(p, box.point[1])) >= 0 then collision := false;
    end;

    //Plane rechts
    if collision then
    begin
    D3DXVec3Cross(normal, VectorSub(box.point[6], box.point[2]),
    VectorSub(box.point[3], box.point[2]));
    if D3DXVec3Dot(normal, vectorsub(p, box.point[2])) >= 0 then collision := false;
    end;

    //Plane links
    if collision then
    begin
    D3DXVec3Cross(normal, VectorSub(box.point[4], box.point[1]),
    VectorSub(box.point[5], box.point[1]));
    if D3DXVec3Dot(normal, vectorsub(p, box.point[1])) >= 0 then collision := false;
    end;

    result := collision;
    end;

    also ich benutze, um zu überprüfen, ob ein punkt in einer box liegt meist folgenden code:

    VB.NET-Quellcode

    1. Public Function CheckForCollision(point2 As Point2) As Boolean
    2. If point2.X >= Bounds(0).X AndAlso point2.X <= Bounds(1).X AndAlso point2.Y >= Bounds(0).Y AndAlso point2.Y <= Bounds(1).Y Then
    3. Return True
    4. Else
    5. Return False
    6. End If
    7. End Function
    8. 'kürzer (ist mir grad eingefallen) :
    9. Public Function CheckForCollision(point2 As Point2) As Boolean
    10. return point2.X >= Bounds(0).X AndAlso point2.X <= Bounds(1).X AndAlso point2.Y >= Bounds(0).Y AndAlso point2.Y <= Bounds(1).Y end function