Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Schneidet eine Strecke (=Linien-Segment) eine AABB?

Werbeanzeige

BlazeX

Alter Hase

  • »BlazeX« ist der Autor dieses Themas

Beiträge: 478

Wohnort: DD

Beruf: Maschinenbau-Student

  • Private Nachricht senden

1

08.01.2011, 14:36

Schneidet eine Strecke (=Linien-Segment) eine AABB?

Hi Leute!
Ich suche wieder mal nach einem Algorithmus, um zu testen, ob eine Strecke (gegeben durch Anfangs- und Endpunkt) eine AABB (gegeben durch ihren Mittelpunkt und der Hälfte ihrer Größe/Ausdehnung). Er sollte schnell und robust sein. Natürlich im 3D-Raum.
Fällt jemandem auf Anhieb gleich etwas ein?

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

2

08.01.2011, 16:08

Separating Axis Theorem: Gibt es eine Gerade, die man zwischen die Box und die Linie legen kann? Und fuer diesen Speziall-Fall eine Hilfe, falls es eine solche Gerade gibt, gibt es auch eine Gerade, parallel zu deiner Strecke.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

3

08.01.2011, 18:06

Hatten wir das Topic nich irgendwie erst?
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

4

09.01.2011, 10:44

Das SAT braucht im R3 aber eine Ebene und keine Gerade (und wäre dann das seperate plane theorem). Es macht keinen Sinn zu sagen, dass eine AABB auf der einen Seite der Gerade liegt.

Ansonsten: Es gibt da einen schönen algorithmus von Kay-Kayjia, der sollte ganz gut passen.
Lieber dumm fragen, als dumm bleiben!

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

5

09.01.2011, 11:44

Zitat von »Jonathan_Klein«

Das SAT braucht im R3 aber eine Ebene und keine Gerade (und wäre dann das seperate plane theorem).
Und?
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

BlazeX

Alter Hase

  • »BlazeX« ist der Autor dieses Themas

Beiträge: 478

Wohnort: DD

Beruf: Maschinenbau-Student

  • Private Nachricht senden

6

09.01.2011, 11:51

SAT klingt gut. Habe ich das so hier richtig verstanden:

(Link)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

7

09.01.2011, 15:01

Berechne auf jeder Achse (x, y, z) das "t-Intervall", wo die Linie die Box auf dieser Achse schneidet (erfordert Test von Linie vs. Ebene - Test vereinfachbar für den Fall, dass die Box an den Koordinatenachsen ausgerichtet ist).
Dann kriegst Du 3 Intervalle raus, eins für jede Achse.
Wenn diese 3 Intervalle sich überlappen (= eine nicht-leere Schnittmenge haben), dann hast Du einen Schnitt. Du suchst quasi das t-Intervall, auf dem sich die Linie auf allen drei Achsen innerhalb der Box befindet.
Du kannst den Test sofort abbrechen, wenn Du siehst, dass die Linie auf einer Achse (x, y, z) die Box nicht schneidet. Das kann passieren, weil Du ja keine Gerade hast, sondern nur eine endlich lange Strecke.
Das funktioniert mit beliebigen konvexen Polyedern!
Nach jedem Test für eine der Achsen kannst Du das in Frage kommende Intervall anpassen. Du musst also nicht prüfen, ob 3 Intervalle sich schneiden, sondern nur 2 und Dir das aktuelle Schnittintervall merken. Wenn ein neu hinzugekommenes Intervall das aktuelle Schnittintervall nicht schneidet, kannst Du ebenfalls sofort abbrechen.

Aus meinem Raytracer (tMin und tMax geben das gewünschte Segment auf dem Strahl an, begrenzen ihn also; invCopy() eines Vektors liefert (1/x, 1/y, 1/z); v enthält die Koordinaten eines Vektors als Array mit 3 Elementen):

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool Box::intersectsShadowRay(const Ray& ray,
                              double tMin,
                              double tMax) const
{
    const Vector3 invRayDirection(ray.direction.invCopy());
    double tEnter = tMin;
    double tLeave = tMax;

    for(int i = 0; i < 3; ++i)
    {
        if(ray.direction.v[i] > 0.0) 
        {
            tEnter = max(tEnter, (aabbMin.v[i] - ray.origin.v[i]) * invRayDirection.v[i]);
            tLeave = min(tLeave, (aabbMax.v[i] - ray.origin.v[i]) * invRayDirection.v[i]);
        }
        else if(ray.direction.v[i] < 0.0)
        {
            tEnter = max(tEnter, (aabbMax.v[i] - ray.origin.v[i]) * invRayDirection.v[i]);
            tLeave = min(tLeave, (aabbMin.v[i] - ray.origin.v[i]) * invRayDirection.v[i]);
        }
    }

    return tEnter <= tLeave;
}


Theoretisch könnte man noch nach jedem Durchlauf der Schleife ein

C-/C++-Quelltext

 
1

if(tEnter > tLeave) return false;

einbauen und anstelle des letzten Tests einfach "true" liefern. Aber das hatte sich nicht gelohnt.
David Scherfgens Website | Konzentrationstest Polizei

BlazeX

Alter Hase

  • »BlazeX« ist der Autor dieses Themas

Beiträge: 478

Wohnort: DD

Beruf: Maschinenbau-Student

  • Private Nachricht senden

8

09.01.2011, 21:57

Danke!
Kurze Frage: Muss ray.direction normiert sein?

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »BlazeX« (09.01.2011, 22:06)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

9

10.01.2011, 16:02

Nein.
Aber die Werte tMin und tMax müssen dann entsprechend angepasst sein.
Wenn der Richtungsvektor vom Start- bis zum Endpunkt zeigt, sollte tMin=0 und tMax=1 sein.
David Scherfgens Website | Konzentrationstest Polizei

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

10

10.01.2011, 16:15

Zitat von »David Scherfgen«

Du kannst den Test sofort abbrechen, wenn Du siehst, dass die Linie auf einer Achse (x, y, z) die Box nicht schneidet.
Das ist dann uebrigens eine "separating axis".
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Werbeanzeige

Ähnliche Themen