BoundingBox und -Rectangle Grundlagen

Vergangenen Dienstag hat mich die Bitte erreicht, daß ich doch mal etwas zu BoundingBoxes schreibe und ein wenig erkläre, was das überhaupt ist, wie diese funktionieren und wozu sie verwendet werden. Da ich dieses Thema sehr interessant finde und dieses Thema auch für andere Artikel als Grundlage extrem hilfreich sein kann, habe ich mich dazu entschlossen, ein paar Zeilen darüber zu schreiben.

Wie fängt man mit so einem Artikel an? Sicherlich ist es sinnvoll, erst einmal zu erklären, was eine BoundingBox und ein BoundingRectangle überhaupt ist. Das ist auch nicht weiter schwer zu erklären, da dies doch recht simple Konstrukte sind.

Was ist eine BoundingBox bzw. -Rectangle?

Ein Bounding-Rectangle ist schlicht und einfach ein Rechteck, das ein Objekt vollständig umschließt. Da ein Rechteck zweidimensional ist, ist natürlich auch ein BoundingRectangle zweidimensional und eignet sich damit z.B. für Sprites. Eine BoundingBox ist das dreidimensionale Pendant dieses Rechtecks, also eine Art Kasten im Raum, daß ein Objekt vollständig umschließt.

Dazu habe ich einfach mal zwei kleine Konzeptzeichnung erstellt.

Links ist ein einfacher Smilie, der von einem Bounding-Rectangle umschlossen wird. Dieses ist in Magenta dargestellt, damit es sich schön vom eigentlichen Sprite abhebt.

Das zweite Bild, welches ich auch als Artikelbild verwendet habe, zeigt eine BoundingBox im dreidimensionalen Raum. Dazu habe ich ein Drahtgittermodell von Blender’s Suzanna verwendet. Schön zu erkennen ist der orangene Kasten, der Suzanna vollständig einschließt.

Im Grunde genommen sind diese beiden Objekte, sie werden auch Primitive genannt, also Vereinfachungen für ein Objekt. Und zwar so starke Vereinfachungen, daß nur noch das absolute Minimum an Informationen übrig bleibt, das benötigt wird, um das Objekt zu umfassen. Diese Bounding-Primitives werden auch Bounding-Volume genannt, da sie immer ein bestimmtes Volumen haben. Übrigens gibt es nicht nur rechteckige Bounding-Volumes, sondern auch runde (BoundingCircle und -Sphere), oder aber auch komplexere Polygone, sogenannte Bounding-Meshes. Wichtig ist hierbei immer, daß ein Bounding-Volume eine Vereinfachung ist, also eine Art von Optimierung.

Ein deutscher Begriff ist übrigens Hüllkörper, der recht plastisch ist, wie ich finde. Ein Körper, der einen anderen komplett umhüllt.

Arten von Bounding-Volumes

Unabhängig davon, ob wir uns im 2D- oder 3D-Raum befinden, kann man Bounding-Boxen und -Rechtecke in zwei Kategorien einordnen:

  • Axis Aligned
  • Oriented

Die Erklärung dabei ist wieder recht einfach. Axis Aligned bedeutet schlicht und einfach, daß die Seiten der BoundingBox immer exakt parallel zu den Achsen des Koordinatensystems ausgerichtet sind. Warum dies gemacht wird, erkläre ich später. Wichtig ist erstmal nur, daß dies eine weitere Vereinfachung und damit Optimierung ist. Noch wichtiger ist jedoch, daß sich die Größe des Hüllkörpers verändert, wenn der umschlossene Körper gedreht wird. Im Bild rechts ist dies zu erkennen. Wenn das grüne Rechteck rotiert wird, dann muss das BoundingRectangle größer werden, damit die Ecken nicht überstehen. Die Seiten sind dabei immer exakt zu den Achsen des Koordinatensystems ausgerichtet.

Und das ist auch schon der Unterschied. Die Oriented-Bounding-Rectangles bzw. -Boxes sind nämlich eben nicht zu den Achsen ausgerichtet, sondern immer exakt zum zugrundeliegenden Objekt. Der Vorteil dabei ist natürlich, daß diese bei rotierten Objekten deutlich enger anliegen, der Nachteil ist jedoch, daß diese deutlich komplizierter zu behandeln sind. Die Ermittlung von Kollisionen ist z.B. teurer als mit Hüllkörpern, die an den Achsen ausgerichtet sind.

Wie sieht das jetzt in C# aus?

Das ist eine gute Frage und zum Glück ist auch diese Frage sehr einfach zu beantworten, zumindest für die ausgerichteten Varianten.

public struct AxisAlignedBoundingRectangle
{
  public Vector2 TopLeft;
  public Vector2 BottomRight;
}

public struct AxisAlignedBoundingBox
{
  public Vector3 Min;
  public Vector3 Max;
}

Wir benötigen jeweils nur zwei Koordinaten, da wir ja schlicht und einfach nur den Anfang und das Ende auf der X-Achse benötigen (TopLeft.X ist der Anfang, BottomRight.X das Ende) und entsprechend auch auf der Y-Achse (TopLeft.Y ist der Anfang und BottomRight.Y ist das Ende). Dazu noch eine kleine Zeichnung, damit es etwas klarer wird.

Gegeben ist in unserer Struktur AxisAlignedBoundingRectangle die linke, obere Ecke (TopLeft) und rechte, untere Ecke (BottomRight) unseres grünen Kastens. Ich habe jeweils Anfang und Ende des BoundingRectangles auf der jeweiligen Achse durch eine rote, gepunktete Linie dargestellt. Diese sind immer exakt zu den Achsen ausgerichtet. Bei einem dreidimensionalen Objekt würde natürlich noch die Tiefe hinzukommen. Dies kann sich aber vermutlich jeder vorstellen.

Anders ausgedrückt benötigen wir also schlicht und einfach die kleinste und größte Ausdehnung (=Koordinate) auf jeder Achse um einen Hüllkörper zu erzeugen.

Wozu der ganze Aufwand?

Durch die Verwendung von Bounding-Volumes verringern wir schlicht und einfach die Datenmenge die wir für bestimmte Operationen verwenden müssten. Das 3D-Modell aus einem der vorherigen Bilder ist ein gutes Beispiel. Um z.B. die Kollision zweier dieser Objekte zu ermitteln, müssten wir für jeden Vertex des Objektes prüfen, ob dieser innerhalb des anderen Objektes liegt. Das Objekt besteht dabei aus knapp 8000 Vertices, eine ganze Menge Prüfungen also.

Wenn wir jedoch eine BoundingBox verwenden, die auch noch an den Achsen ausgerichtet ist, so ist diese Kollisions-Prüfung ziemlich simpel. Wir prüfen schlicht und einfach, aufgeteilt nach jeder Achse, ob eine der Koordinaten zwischen denen des anderen Objektes liegt. Ein Beispiel anhand der obigen Zeichnung mit den Achsen. Ein Bounding-Rectangle überschneidet sich mit unserer grünen Box, wenn:

– die kleinere ODER größere X-Koordinate des anderen Objektes zwischen 2 und 4 liegt (X-Achse des grünen Rechtecks)

UND

– die kleinere ODER größere Y-Koordinate des anderen Objektes zwischen 2 und 4 liegt (Y-Achse des grünen Rechtecks)

In Code gefasst:

public bool Intersects(AxisAlignedBoundingRectangle me, AxisAlignedBoundingRectangle other)
{
  bool overlapOnX = (me.TopLeft.X >= other.TopLeft.X && me.TopLeft.X <= other.BottomRight.X) || (me.BottomRight.X >= other.TopLeft.X && me.BottomRight.X <= other.BottomRight.X) );
  bool overlapOnY = (me.TopLeft.Y >= other.TopLeft.Y && me.TopLeft.Y <= other.BottomRight.Y) || (me.BottomRight.Y >= other.TopLeft.Y && me.BottomRight.Y <= other.BottomRight.Y) );
  
  return overlapOnX && overlapOnY;
}

Wir habe also einfach acht Prüfungen, die mit vier logischen UND und zwei logischen ODER verknüpft werden. Davon können wir problemlos tausende Prüfungen pro Sekunde machen ohne Performance-Probleme zu bekommen.

Recht einfach also das Ganze.

Ausblick

Da mir leider ein wenig die Zeit weggelaufen ist und dieser Artikel bereits ein wenig angestaubt ist (fast eine Woche liegt er jetzt immerhin in den Entwürfen), möchte ich diesen nun veröffentlichen und daher erstmal abschliessen. Ursprünglich wollte ich noch folgende Themen besprechen:

  • Darstellung und Visualisierung
  • Kollisionserkennung
  • Sichtbarkeitsprüfungen bzw. Culling

Diese Themen werde ich bei Gelegenheit noch nachreichen. Ich kann leider noch nicht versprechen, wann ich die Zeit finden werde, ein paar Zeilen dazu zu schreiben.

Ich hoffe, daß dieser kurze Artikel ein wenig Licht ins Dunkel gebracht hat und dem ein oder anderen ein paar neue Erkenntnisse gebracht hat. Ich jedenfalls werde diesen Artikel sicherlich in Zukunft häufiger in meinen anderen Artikeln verlinken, da ich so nicht jedesmal aufs Neue erklären muss, was es mit BoundingBox und BoundingRectangle auf sich hat.

Advertisements

Veröffentlicht am 29.08.2011 in Grundlagen, XNA und mit , , , , , getaggt. Setze ein Lesezeichen auf den Permalink. 2 Kommentare.

  1. Hallo Lockenkopf ^^

    vielen Dank für diesen tollen Artikel.
    Durch ihn habe ich endlich Zugang zu den Bindungskisten gefunden und mein 3D-Spiel freut sich derzeit über Kollision.

    Allerdings stoße ich gerade wie vermutlich jeder Anfänger auf ein Problem.
    Bei 26 Blendermodellen deren BoundingBoxes ich zur laufzeit immer wieder neu berechne bei jedem durchgang zwecks aktualisierung der position und so geht mein Core i5 2,6GHz CPU langsam aber sicher in die Knie ^^
    (ich hab gelesen im Forum das es heißt „schreib n ContentProzessor“ aber soviel wissen hab ich noch nicht um das zu schaffen ^^)

    Wirst du im nächsten Artikel darauf eingehen oder kannst du mir evtl hier direkt einen Tipp geben?

    Grüße,
    MoArt

    P.S.: preiset den Haarlosen 🙂

    • Hier im Blog gibt es schon den ein oder anderen Artikel, der in diese Richtung geht. Ansonsten würde ich dir empfehlen dir mal starLiGHT.Collision anzusehen. 3D ist zwar noch nicht drin, aber es ist vorbereitet und vielleicht bekommst du da eine Idee.

      Im Grunde genommen musst du möglichst viele Tests ohne viel Aufwand ausschliessen. Dazu gibt es mehrere Strategien, die man in der Regel „Broadphase“ nennt.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: