Bounding Sphere

Ein Raumschiff-Modell mit Bounding Sphere

Die Bounding Sphere ist ein spezielles Bounding Volume. Es handelt sich dabei um eine Kugel, deren Mittelpunkt möglichst mit dem Mittelpunkt des zu umschliessenden Objektes übereinstimmen sollte, um dieses optimal zu überdecken. Eine Bounding Sphere ist eindeutig durch ihren Mittelpunkt und ihrem Radius festgelegt.

Anwendung

Bounding Spheres findet man häufig bei Collision Detection im Einsatz. Sie sind besonders gut für kugelförmige Objekte wie z.B. Felsen, Asteroiden oder auch Raumschiffe geeignet. Ziemlich schlecht geeignet sind Bounding Spheres für längliche Objekte, wie z.B. Menschen oder Türme, da sie diese nur mit viel Freiraum überdecken können. D.h., dass das innere 3D-Objekt von der Bounding Sphere nicht nach allen Seiten hin abgegrenzt wird. In diesem Falle sollte man besser Bounding Cylinders verwenden.

Berechnung

Eine optimale Bounding Sphere für ein 3D-Modell zu bestimmen ist im Allgemeinen sehr rechenaufwendig (besonders für die Bestimmung des optimalen Mittelpunktes).

In den meisten Fällen kann man aber mit den folgenden beiden Algorithmen eine gute Näherungslösung finden.

Mittelpunkt der Bounding Box als Zentrum

Bei dem ersten Algorithmus bestimmt man zuerst den Mittelpunkt der Bounding Box. Der Radius der Bounding Sphere ist dann die Hälfte der Länge der Diagonale der Bounding Box. Dieser Algorithmus ist vor allem für punktsymmetrische Objekte gut geeignet.

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

BoundingSphere = RECORD
    center : Point3D;
    radius : Float;
END;

FUNCTION BoundingSphere1(vertices : Array Of Point3D) : BoundingSphere;
VAR
    i : Integer;
    dx, dy, dz, le : Float;
    box : BoundingBox;
    sphere : BoundingSphere;
    
BEGIN

    //Bestimmung des Mittelpunktes
    box := BoundingBox(vertices);
    WITH sphere DO BEGIN
        center.x := (box.vs[0][0][0].x+box.vs[1][1][1].x)/2;
        center.y := (box.vs[0][0][0].y+box.vs[1][1][1].y)/2;
        center.z := (box.vs[0][0][0].z+box.vs[1][1][1].z)/2;
    END;
        
    //längstmöglichsten Abstand vom Schwerpunkt aus ermitteln
    sphere.radius := 0;
    FOR i := 0 TO Length(vertices)-1 DO
        WITH sphere DO BEGIN
            dx := vertices[i].x - center.x;
            dy := vertices[i].y - center.y;
            dz := vertices[i].z - center.z;
            le := sqrt(dx*dx+dy*dy+dz*dz);
            IF radius < le THEN radius := le;
        END;
        
    BoundingSphere1 := sphere;  
END;

Schwerpunkt als Mittelpunkt

Die Idee dieses Algorithmus ist es, den Mittelpunkt aller Vertices als Zentrum der Bounding Sphere zu benutzen. Sind die Vertices gleichmässig über das 3D-Modell verteilt, so bekommt man in den meisten Fällen einen optimaleren Mittelpunkt als beim ersten Algorithmus.

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

BoundingSphere = RECORD
    center : Point3D;
    radius : Float;
END;

FUNCTION BoundingSphere2(vertices : Array Of Point3D) : BoundingSphere;
VAR
    i : Integer;
    n : Integer;
    dx, dy, dz, le : Float;
    sphere : BoundingSphere;
    
BEGIN
    n := Length(vertices);

    //Bestimmung des Schwerpunktes
    
    sphere.center.x := 0;
    sphere.center.y := 0;
    sphere.center.z := 0;
    
    FOR i := 0 TO n-1 DO
        WITH sphere DO BEGIN
            center.x := center.x + vertices[i].x;
            center.y := center.y + vertices[i].y;
            center.z := center.z + vertices[i].z;
        END;
    
    WITH sphere DO BEGIN    
        center.x := center.x / n;
        center.y := center.y / n;
        center.z := center.z / n;
    END;    
        
    //längstmöglichsten Abstand vom Schwerpunkt aus ermitteln
    
    sphere.radius := 0;
    
    FOR i := 0 TO Length(vertices)-1 DO
        WITH sphere DO BEGIN
            dx := vertices[i].x - center.x;
            dy := vertices[i].y - center.y;
            dz := vertices[i].z - center.z;
            le := sqrt(dx*dx+dy*dy+dz*dz);
            IF radius < le THEN radius := le;
        END;
        
    BoundingSphere2 := sphere;  
END;