Bounding Box

Eine Galeone mit Bounding Box

Eine Bounding Box ist ein spezielles Bounding Volume. Der Begriff wird allgemein für Axis-Aligned Bounding Box (AABB) benutzt. Dabei handelt es sich um einen Quader, dessen Seiten parallel zu den Achsen des (Objekt-lokalen) Koordinatensystems stehen.

Anwendung

Bounding Boxes werden häufig für Occlusion Culling benutzt, da sie eine sehr einfache Geometrie aufweisen. Dort sind sie vor allem gut für quaderförmige Objekte wie z.B. Autos oder Häuser geeignet, da sie eine ähnliche Füllrate besitzen. Weniger gut geeignet sind Bounding Boxes für runde oder stark konkave Objekte wie z.B. Flugzeuge.

Berechnung

Um die Koordinaten einer Bounding Box zu berechnen, reicht es aus, die minimalen und maximalen x, y und z-Koordinaten des zu umschliessenden Objektes zu bestimmen. Daraus lassen sich dann bereits alle acht Eckpunkte der Bounding Box herleiten.

Beispielcode

Point3D = RECORD
    x, y, z: GLFloat;
END;

BoundingBox = RECORD
    vs : Array[0..1,0..1,0..1] Of Point3D;
END;

FUNCTION BoundingBox(vertices : Array Of Point3D) : BoundingBox;
VAR
    //minimale und maximale Grenzwerte für Bounding Box
    min, max : Point3D; Box
    i, j : Integer;
    
BEGIN
    //minimale Werte möglichst hoch setzen
    //maximale Werte möglichst niedrig setzen
    min.x := 10000000; max.x := -10000000;
    min.y := 10000000; max.y := -10000000;
    min.z := 10000000; max.z := -10000000;

    //minimale und maximale Werte berechnen
    FOR i := 0 TO Length(vertices)-1 DO
        WITH vertices[i] DO BEGIN
            IF x < min.x THEN min.x := x;
            IF x > max.x THEN max.x := x;
            IF y < min.y THEN min.y := y;
            IF y > max.y THEN max.y := y;
            IF z < min.z THEN min.z := z;
            IF z > max.z THEN max.z := z;
        END;
        
    //Bounding Box erstellen
    FOR i:=0 TO 1 DO
        FOR j:=0 TO 1 DO BEGIN
            BoundingBox.vs[0,i,j].x := min.x;
            BoundingBox.vs[1,i,j].x := max.x;
            BoundingBox.vs[i,0,j].y := min.y;
            BoundingBox.vs[i,1,j].y := max.y;
            BoundingBox.vs[i,j,0].z := min.z;
            BoundingBox.vs[i,j,1].z := max.z;
        END;    
END;

Weblinks

http://www.geo.informatik.uni-bonn.de/publications/1999/dipl-hecht/node39.html