Bounding Sphere: Unterschied zwischen den Versionen
(neu erstellt) |
DGLBot (Diskussion | Beiträge) K (Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.) |
||
| (3 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 19: | Zeile 19: | ||
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. | 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. | ||
| − | <pascal> | + | <source lang="pascal"> |
Point3D = RECORD | Point3D = RECORD | ||
x, y, z: GLfloat; | x, y, z: GLfloat; | ||
| Zeile 59: | Zeile 59: | ||
BoundingSphere1 := sphere; | BoundingSphere1 := sphere; | ||
END; | END; | ||
| − | </ | + | </source> |
=== Schwerpunkt als Mittelpunkt === | === Schwerpunkt als Mittelpunkt === | ||
| − | Die Idee dieses Algorithmus ist es, den Mittelpunkt aller [[ | + | Die Idee dieses Algorithmus ist es, den Mittelpunkt aller [[Vertex|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. |
| − | <pascal> | + | <source lang="pascal"> |
Point3D = RECORD | Point3D = RECORD | ||
x, y, z: GLfloat; | x, y, z: GLfloat; | ||
| Zeile 118: | Zeile 118: | ||
BoundingSphere2 := sphere; | BoundingSphere2 := sphere; | ||
END; | END; | ||
| − | </ | + | </source> |
| + | |||
| + | [[Kategorie:Technik_oder_Algorithmus]] | ||
Aktuelle Version vom 10. März 2009, 19:03 Uhr
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.
Inhaltsverzeichnis
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;
