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!

Kürzester Abstand eines Punktes von einer AABB

  • 1
  • 2

Werbeanzeige

BlazeX

Alter Hase

  • »BlazeX« ist der Autor dieses Themas

Beiträge: 478

Wohnort: DD

Beruf: Maschinenbau-Student

  • Private Nachricht senden

1

02.01.2011, 13:42

Kürzester Abstand eines Punktes von einer AABB

Hi Leute!
Wie berechne ich den kürzesten Abstand eines Punktes von einer AABB?
Die AABB ist durch ihren Mittelpunkt und der Hälte ihrer Größe gegeben.
Ich habe da jetzt überhaupt keinen Ansatz.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

2

02.01.2011, 13:44

Zitat von »BlazeX«

Die AABB ist durch ihren Mittelpunkt und der Hälte ihrer Größe gegeben..

:thumbsup:
Das würde ich mir am liebsten gleich in die Signatur packen...
Kannst Du das eventuell vielleicht nochmal verständlich erklären? Was ist eine AABB?
Im Falle, dass es sich um eine Achsis-Aligned-Bounding-Box handelt, was ist die "Hälte ihrer Größe"? Handelt es sich um einen Kubus? Dann ist deine Frage reduzierbar auf:
1) Berechnung der kürzesten Abstände des Punktes zu den Achsen-Ebenen und dieser Lotpunkte
2) Berechnung der kürzesten Abstände des Punktes zu den Kubus-Kanten über Abstand zwischen Punkt und Strecke und diesem konkret nächstliegendem Punkt
3) Der gesuchte Punkt ist der mit dem minimalen Abstand aus 1 und 2
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]

NachoMan

Community-Fossil

Beiträge: 3 885

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

3

02.01.2011, 13:46

Zitat von »BlueCobold«

Kannst Du das eventuell vielleicht nochmal verständlich erklären? Was ist eine AABB?

von einem programmierer erwarte ich dass er wikipedia benutzen kann.
hier stehts

sry, das musste jetzt sein xD

edit: sry. vor dem edit klang die frage "Was ist eine AABB?" beim ersten mal lesen etwas abfällig. so spielt erwartung und müdigkeit(+ zu schnelles posten) zusammen^^ ich nehm alles zurück >.<
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »NachoMan« (02.01.2011, 14:21)

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

4

02.01.2011, 13:48

Von einem Programmierer erwarte ich, dass er sich vernünftig ausdrücken kann.

Immerhin kann es sich auch um ein Problem damit handeln:
http://www.andre-borrmann.de/docs/paper_…_ForumBI_07.pdf

Außerdem: Wo ist denn dein Lösungsvorschlag, NachoMan? Kannst auch nur rumpflaumen, oder? Ich habe ja immerhin etwas beigetragen.
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]

BlazeX

Alter Hase

  • »BlazeX« ist der Autor dieses Themas

Beiträge: 478

Wohnort: DD

Beruf: Maschinenbau-Student

  • Private Nachricht senden

5

02.01.2011, 14:28

Natürlich ist eine AABB eine Achsis-Aligned-Bounding-Box. Das muss kein Würfel (=Kubus) sein.
Kann der Kobold etwas mit Minimumpunkt und Maximumpunkt einer AABB anfangen?
Wenn ja, dann wird die Hälte der Größe und der Mittelpunkt so berechnet:

C-/C++-Quelltext

 
1
2

vHalfSize= (vMax - vMin) * 0.5;
vCenter= vMin + vHalfSize;


Dann müsste ich aber ziemlich Bruteforce-like den Abstand von Punkt zu allen Seitenflächen-Ebenen berechnen und den Abstand von Punkt zu allen Eckpunkten. Unter all diesen Abständen wird der kleinste benutzt. Außerdem muss noch überprüft werden, ob der Punkt innerhalb der AABB liegt. Das ist zu viel Rechnerei.
Gibt es etwas simpleres?

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

6

02.01.2011, 14:35

Zitat von »BlazeX«

C-/C++-Quelltext

 
1
2

vHalfSize= (vMax - vMin) * 0.5;
vCenter= vMin + vHalfSize;

Das kann man auch kürzer schreiben:

C-/C++-Quelltext

 
1

vCenter = (vMin + vMax) * 0.5;


Zitat von »BlazeX«

Gibt es etwas simpleres?

Eher nicht.
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]

NachoMan

Community-Fossil

Beiträge: 3 885

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

7

02.01.2011, 14:47

interessenfrage: könnte man das nicht mit hilfe der richtung(zwischen dem punkt und dem mittelpunkt) relativ einfach auf 4 eckpunkte und eine seitenfläche reduzieren?
ob der code dann einfacher und schneller ist, ist eine andere frage.
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

8

02.01.2011, 14:55

Hmm, das nicht. Aber man kann die Normalen der Oberflächen nehmen, den Winkel zum Ziel-Punkt berechnen und damit einige Flächen gleich komplett eliminieren. Ob das aber am Ende viel schneller ist...
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]

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

9

02.01.2011, 15:42

Du Berechnest den Abstand zwischen Mittelpunkt und dem anderen Punkt. Dann musst du mit jeder Fläche auf einen Schnittpunkt prüfen. Du könntest die Richtung des Vektors zwischen den beiden Punkten dazu benutzen, um schon einige Flächen auszuschließen.
Ist der x-Wert Beispielsweise positiv, kannst würde die eine Fläche wegfallen, bei negativem x-Wert die gegenüberliegende.
Es müssen also nur 3 Flächen auf einen Schnittpunkt berechnet werden.
Danach hast du den Punkt und kannst den Abstand berechnen.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

BlazeX

Alter Hase

  • »BlazeX« ist der Autor dieses Themas

Beiträge: 478

Wohnort: DD

Beruf: Maschinenbau-Student

  • Private Nachricht senden

10

02.01.2011, 19:04

Mir ist noch etwas eingefallen: Man könnte doch einen Punkt auf/in der AABB suchen, in dem man jede Achse einzeln betrachtet.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13

//Gegeben: Punkt "A", Mittelpunkt der AABB "Center" und die halbe Größe der AABB "HalfSize"

//AABB in den Mittelpunkt rücken.
A-= Center;

//Den Punkt auf bzw. in der AABB mit dem kürzesten Abstand zum Punkt A bestimmen.
//Dazu wird jede Achse einzeln untersucht.
Vector3 vNearPoint;
vNearPoint.x= A.x < -HalfSize.x ? -HalfSize.x : A.x > HalfSize.x ? HalfSize.x : A.x;
vNearPoint.y= A.y < -HalfSize.y ? -HalfSize.y : A.y > HalfSize.y ? HalfSize.y : A.y;
vNearPoint.z= A.z < -HalfSize.z ? -HalfSize.z : A.z > HalfSize.z ? HalfSize.z : A.z;

//Abstand ist dann |A-vNearPoint|


Müsste doch funktionieren, oder?

Werbeanzeige

  • 1
  • 2

Ähnliche Themen