Bounding Sphere - Versionsgeschichte

DGLBot: Der Ausdruck ''(.*?)'' wurde ersetzt mit ''$1''.

2009-03-10T18:03:23Z

Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.

Thoronador: Link korrigiert (Vertex statt "Vertice")

2008-04-24T20:16:58Z

Link korrigiert (Vertex statt "Vertice")

Dj3hut1: Buchstaben vertauscht

2006-01-13T16:16:23Z

Buchstaben vertauscht

Dj3hut1: Kategorie hinzugefügt

2006-01-01T14:37:03Z

Kategorie hinzugefügt

Dj3hut1: neu erstellt

2006-01-01T12:25:45Z

neu erstellt

Neue Seite

[[Bild:boundingsphere.png|framed|right|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 Cylinder]]s 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.

<pascal>
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;
</pascal>

=== Schwerpunkt als Mittelpunkt ===
Die Idee dieses Algorithmus ist es, den Mittelpunkt aller [[Vertice]]s 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 Algorithums.

<pascal>
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;
</pascal>

@@ Zeile 62: / Zeile 62: @@
 === Schwerpunkt als Mittelpunkt ===
-Die Idee dieses Algorithmus ist es, den Mittelpunkt aller [[Vertice]]s 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.
+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>

← Nächstältere Version		Version vom 1. Januar 2006, 14:37 Uhr
Zeile 119:		Zeile 119:
	END;		END;
	</pascal>		</pascal>
		+
		+	[[Kategorie:Technik_oder_Algorithmus]]

@@ 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.
-<pascal>
+<source lang="pascal">
 Point3D = RECORD
      x, y, z: GLfloat;
@@ Zeile 59: / Zeile 59: @@
      BoundingSphere1 := sphere;
 END;
-</pascal>
+</source>
 === Schwerpunkt als Mittelpunkt ===
 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
      x, y, z: GLfloat;
@@ Zeile 118: / Zeile 118: @@
      BoundingSphere2 := sphere;
 END;
-</pascal>
+</source>
 [[Kategorie:Technik_oder_Algorithmus]]