Axis Aligned Bounding Box

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:

Korrektheit: 4 (großteils überprüft)

Umfang: 3 (einige wichtige Fakten fehlen)

Quellenangaben: 1 (fehlen großteils)

Quellenarten: 5 (ausgezeichnet)

Konformität: 5 (ausgezeichnet)

Definition (von Kowarschick)

zweidimensionale Bounding Box

Es sei $o$ ein kompaktes (d. h. ein abgeschlossenes und beschränktes) geometrisches 2D- bzw. 3D-Objekt. Eine Axis Aligned Bounding Box (AABB) oder kurz Bounding Box ist ein spezieller Hüllkörper für das Objekt $o$ in Form eines achsenparallelen Rechtecks (2D) bzw. Quaders (3D). Das Objekt $o$ berührt alle 4 bzw. 6 Seiten der Bounding Box.

Eigenschaften

• Es gibt für jedes kompakte Objekt jeweils genau eine AABB. Dieses ist das kleinstmögliche achsenparallele Rechteck bzw. der kleinstmögliche achsenparallele Quader das bzw. der $o$ einschließt. Es wird sogar die konvexe Hülle von $o$ eingeschlossen.

• Die Bounding Box kann bei polygonalen Objekten sehr einfach über eine Minimums- und Maximumssuche über die Koordinaten aller Eckpunkte des Objektes ermittelt werden. Aber auch für andere geometrische Objekte, wie Kreise oder achsenparallele Ellipsen, ist die Ermittlung der AABB sehr einfach.

Integritätsbedingungen einer zwei-dimensionalen Bounding Box

Attribute einer zweidimensionalen Bounding Box

Es sei eine Bounding Box mit folgenden Attributen gegeben:

• lft: $x$-Koordinate der beiden linken Ecken
• rgt: $y$-Koordinate der beiden rechten Ecken
• top: $x$-Koordinate der beiden oberen Ecken
• btm: $y$-Koordinate der beiden unteren Ecken
• width: Breite der Bounding Box
• height: Höhe der Bounding Box
• x: $x$-Koordinate der Drehpunkts (engl.: pivot)
• y: $y$-Koordinate der Drehpunkts
• xPivot: Abstand der $x$-Koordinate des Drehpunkts vom linken Rand
• yPivot: Abstand der $y$-Koordinate des Drehpunkts vom oberen Rand
• xAnchor: Relativer Abstand der $x$-Koordinate des Drehpunkts vom linken Rand
• yAnchor: Relativer Abstand der $y$-Koordinate des Drehpunkts vom oberen Rand

Für eine Bounding Box gelten folgende Integritätsbedingungen (wenn man ein in der Computergrafik übliches Koordinatensystem zugrundelegt, bei dem sich der Null punkt in der linken oberen Ecke der Bühne befindet und die $y$-Werte in Richtung unterem Bühnenrand größer werden):

• rgt >= lft
• btm >= top (Koordinatensystem!)
• width = rgt-lft >= 0
• height = btm-top >= 0 (Koordinatensystem!)
• lft = x-xPivot
• rgt = x-xPivot+width = lft+width
• top = y-yPivot
• btm = y-yPivot+height = top+height (Koordinatensystem!)
• xAnchor = xPivot/width
• yAnchor = yPivot/height

Kollisionserkennung

Zwei kollidierende Bounding Boxes

Zwei nicht kollidierende Bounding Boxes

Die Kollisionserkennung ist für Bounding Boxes relativ einfach. Daher geht man in der Computergrafik oft zweistufig vor. Im ersten Schritt überprüft man, ob sich zwei Bounding Boxes berühren oder überlappen. Falls dies nicht der Fall ist, berühren oder überlappen sich die zugehörigen Objekte ebenfalls nicht. Das heißt, in diesem Fall liegt mit Sicherheit keine Kollision vor. Dieser Fall tritt sehr häufig ein, wenn sich viele relativ kleine Objekte auf der Bühne befinden. Falls die Bounding Boxes kollidieren, ist damit allerdings noch nicht gesagt, das auch die darin enthaltenen Objekte kollidieren. Das heißt, in diesem Fall müssen i. Allg. weitere mathematische Tests unternommen, um festzustellen, ob die beiden in den Boxen eingeschlossenen Objekte kollidieren. Falls dies der Fall ist, schließt sich daran üblicherweise die Kollisionsbehandlung an.

Um eine Formel für die Kollisionserkennung zweier Bounding Boxes b1 und b2 herzuleiten, ist es von Vorteil sich zunächst den gegenteiligen Fall anzusehen: Die Boxes überlappen sich genau dann nicht, wenn der linke Rand einer Box größer ist als der rechte der anderen oder der obere Rand der einen größer ist als der untere der anderen. Damit hat man folgende Bedingung:

Siehe auch

• Einhüllende Kurve
• Hüllkörper