Tutorial Kollision3 - Versionsgeschichte

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

2009-03-10T18:47:44Z

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

Flash: /* Wo liegen die Grenzen des Verfahrens? */

2009-02-22T17:34:12Z

‎Wo liegen die Grenzen des Verfahrens?

Flash: /* Bounding Volumes */

2008-06-30T15:49:40Z

‎Bounding Volumes

Erin: /* Bounding Volumes */

2008-06-20T15:35:21Z

‎Bounding Volumes

Flash: Neues Tutorial

2008-06-18T09:30:07Z

Neues Tutorial

Änderungen zeigen

@@ Zeile 61: / Zeile 61: @@
 Am Anfang der Bearbeitungskette steht wahrscheinlich ein 3D-Programm wie Blender oder 3ds-Max, dessen Output wir in irgendeiner Form in unser Programm einlesen, entweder direkt mit Hilfe eines Model-Loaders oder über den Umweg einer '''Modelldatei''', die wir unseren persönlichen Bedürfnissen angepasst haben. Ich bevorzuge den zweiten Weg, weil er nach meiner Auffassung  flexibler und universeller ist. Für das in der Einleitung gezeigte Haus sieht meine gekürzte Modelldatei so aus:
-<cpp>
+<source lang="cpp">
 # file: house.lst
@@ Zeile 87: / Zeile 87: @@
 # Material:
 [S] m [amb] 0.5 0.1 0.1 1.0 [diff] 0.9 0.3 0.1 1.0 [spec] 0.0 0.0 0.0 1.0
-</cpp>
+</source>
 Das alles ist recht normal aufgebaut: eine Vertexliste sowie eine Dreiecksliste, die über Indices auf die Vertexliste zurückgreift. Die Texturkoordinaten [t1] und [t2] sind noch nicht eingetragen, da das Testobjekt ohne Textur auskommt. Dasselbe gilt für die Vertexnormalen [n1]...[n3], denn Smooth-Shading ist in der Testphase ebenfalls unerwünscht. Eigentlich könnte auch noch auf die Flächennormale [N] verzichtet werden, denn nach der Skalierung muss sie ohnehin neu berechnet werden. - Das Objekt wurde übrigens mit Milkshape modelliert und mit Hilfe eines kleinen Delphi-Programms in das gezeigte Skript-Format übersetzt. Dieses robuste und leicht auszuwertende Skript-Format verwende ich unter Linux und Windows und nicht nur für Objektbeschreibungen, sondern für Konfigurationsdaten aller Art. Das aber nur am Rande.
@@ Zeile 95: / Zeile 95: @@
 Die Modelldatei bechreibt vor allem die geometrische Struktur. In der Regel möchten wir noch andere Merkmale festlegen, so dass es sinnvoll ist, eine zusätzliche '''Objektdatei''' einzuführen, die wie folgt oder ähnlich aufgebaut sein kann:
-<cpp>
+<source lang="cpp">
 # file: objects.lst
@@ Zeile 104: / Zeile 104: @@
 [collision] 1 [collect] 0 [model] tree1.lst [sound] [billboard] [mat] 0
 ...
-</cpp>
+</source>
 [type] ist hier eine grundsätzliche Typisierung. So handelt es sich bei [type] 3 um ein dreidimensionales Objekt, dessen Geometrie in [model] zu finden ist, während [type] 2 ein Objekt beschreibt, das lediglich in Form gekreuzter Texturen gezeichnet wird. Im lezteren Fall enthält [model] einige Parameter wie Form, Höhe, Breite, Fusspunkt usw., eben jene Parameter, die für eine Kollision am Gesamtobjekt von Bedeutung sind.
@@ Zeile 115: / Zeile 115: @@
 Die Daten aller benötigten Objekttypen werden also eingelesen und in ein geeignetes Array übertragen. Damit stehen die allgemeinen Eigenschaften des Objekttyps zur Verfügung. Darüber hinaus benötigen wir eine Datei, in der die alle vorkommenden Objektinstanzen aufgelistet sind. Was dazu gehört, sehen wir sofort, wenn wir uns einen Auszug aus einer '''Instanzendatei''' betrachten:
-<cpp>
+<source lang="cpp">
 # file: items.lst
@@ Zeile 129: / Zeile 129: @@
 [name] tree3 [position] 1  0.0  -35.0 \
 [scale] 2.0 3.0 2.0 [rotation] 8 120 0 [translation] 0 0 0
-</cpp>
+</source>
 Jede einzelne Objektinstanz erhält eine Positions-, Rotations- und Skalierungsangabe, während [name] den Bezug zur Objektbeschreibung herstellt. Mit [translation] kann eine Feinjustierung der Position vorgenommen werden. Die Korrektur ist z.B. nützlich, wenn die Positionsdaten auf die ganzzahligen Pixelpositionen der Heightmap bezogen sind. Unumgänglich ist die Korrektur bei Objekten, die auf abschüssigem Gelände positioniert werden.
@@ Zeile 135: / Zeile 135: @@
 Wie gesagt, ohne Kollision könnten wir die Instanzdaten einlesen und mit dem Triple ''glTranslate, glRotate'' und ''glScale'' direkt die damit verbundenen Objekte zeichnen. Aber für die Kollisionsberechnung benötigen wir die Daten in ihrer endgültigen Form. Das heißt, die Vertexdaten müssen so vorliegen, wie sie sich '''nach''' der Verschiebung, Rotation und Skalierung ergeben. Was OpenGL intern durchführt, müssen wir extern ebenfalls erledigen. Nun, das Umrechnen ist kein Problem. Wir machen es genau so wie OpenGL und besorgen uns am besten gleich die passende Matrix von diesem "Matrizenprofi".
-<cpp>
+<source lang="cpp">
          TGLMatrix glmat; // Typ: GLfloat[16]
@@ Zeile 147: / Zeile 147: @@
          glGetFloatv (GL_MODELVIEW_MATRIX, glmat);
          glPopMatrix ();
-</cpp>
+</source>
 Mit dieser Matrix multiplizieren wir die Vertices aller Objektinstanzen und speichern sie in einem strukturierten Array. Bei den Umrechnungen achten wir darauf, dass OpenGL die Matrix nicht zeilenweise, sondern spaltenweise anordnet. Aber ich denke, das wird jeder, der mit GL-Matrizen rechnet, wohl im Hinterkopf haben.
@@ Zeile 153: / Zeile 153: @@
 Wir dürfen nicht vergessen, die für die Beleuchtung unerlässlichen Polygonnormalen neu zu berechnen. Die ursprünglichen, von dem 3D-Programm berechneten Normalen sind nach der Skalierung nicht mehr zu gebrauchen. - Wenn wir ohnehin schon die Daten aller vorkommenden Polygone in absoluten Koordinaten vorliegen haben, brauchen wir schließlich beim Rendern nicht mehr das Triple glTranslate, glRotate und glScale zu bemühen, sondern können die im voraus berechneten Daten direkt übergeben. Die Funktion für das Rendern eines einzelnen Objektes könnte etwa so aussehen:
-<cpp>
+<source lang="cpp">
 void DrawObjectInstance (TInstance *inst) {
      TVector normal, vert;
@@ Zeile 172: / Zeile 172: @@
      } else ...
+}
-</cpp>
+</source>
 Der Parameter ''inst'' ist ein Zeiger auf ein Element des Instanzenarrays. Das soll hier als Anregung reichen; wie wir das Array nun im einzelnen gestalten, hängt vom grundsätzlichen Programmaufbau und nicht zuletzt von den Programmiergewohnheiten ab.
@@ Zeile 194: / Zeile 194: @@
 Wie prüfen wir, ob ein Objekt für eine Kollision in Frage kommt? Nun, dazu bietet sich eine übliche Ray-Sphere-Intersection-Funktion an, die wir aber etwas kürzen können. Wir wollen ja lediglich feststellen, '''ob''' die Hüllkugel getroffen wird, nicht '''wo''' das geschieht. Auf die überflüssige Berechnung der Wurzel verzichten wir und prüfen nur, ob der Ausdruck unter der Wurzel positiv oder negativ ist. Entsprechend der boolsche Rückgabewert.
-<cpp>
+<source lang="cpp">
 bool SphereIntersect (TVector center, double rad,
          TVector p, TVector dir)
@@ Zeile 206: / Zeile 206: @@
          else return true;
+}
-</cpp>
+</source>
 Streng genommen müsste eine Funktion zur Sphere-Sphere-Intersection zum Einsatz kommen, aber da wir uns nicht für den genauen Intersektionspunkt interessieren, geht es mit der gezeigten Ray-Sphere-Intersektion. Wir müssen dann nur den Radius der bewegten Kugel zum Radius der Hüllkugel addieren. Im Falle eines Ellipsoids nehmen wir den größten der 3 Radien.

@@ Zeile 298: / Zeile 298: @@
 Nun, es ist offensichtlich, dass das Verfahren nur zu gebrauchen ist, wenn das bewegte Objekt - schön abgerundet zu einer Kugel oder einem Ellipsoid - als Ganzes kollidiert. Sobald das Objekt aber Ecken und Kanten hat, die in verschiedener Weise anstoßen können, müssen wir zu differenzierteren Verfahren greifen, auf die ich hier nicht eingehen kann.
-Darüber hinaus es gibt weitere Einschränkungen. So kann es z.B. zu Problemen kommen, wenn sich innerhalb eines Zeitintervalls bedeutsame Änderungen ergeben. Das kann der Fall bei mehreren bewegten Objekten sein, die miteinander kollidieren können und ihre Wege in der Zwischenzeit kreuzen. Das kann aber auch der Fall sein, wenn in einem Intervall viele Terrainpolygone überquert werden. Dann ist das "Zeitnetz" zu grobmaschig gegenüber dem räumlichen Netz der Szenerie. Große Geschwindigkeiten oder eine sehr hohe Auflösung des Mesh sind die Hauptursachen. Das heißt nicht, dass der Bewegungsablauf gleich aus den Fugen gerät, aber es läuft eher holprig und sprunghaft ab, nicht mehr so geschmeidig. Außerdem lässt sich das Objekt schlechter steuern. Was die Auflösung des Mesh betrifft, müssen wir einen Kompromiss akzeptieren. Einerseits sorgt eine hohe Auflösung für eine detaillierte und angenehme Landschaftsdarstellung; andererseits ist der Bewegungsablauf flüssiger bei großflächigen Terrain-Polygonen.
+Darüber hinaus es gibt weitere Einschränkungen. So kann es z.B. zu Problemen kommen, wenn sich innerhalb eines Zeitintervalls bedeutsame Änderungen ergeben. Das kann der Fall bei mehreren bewegten Objekten sein, die miteinander kollidieren können und ihre Wege in der Zwischenzeit kreuzen. Das kann aber auch der Fall sein, wenn in einem Intervall viele Terrainpolygone überquert werden. Dann ist das "Zeitnetz" zu grobmaschig gegenüber dem räumlichen Netz der Szenerie. Große Geschwindigkeiten oder eine sehr hohe Auflösung des [[Mesh]] sind die Hauptursachen. Das heißt nicht, dass der Bewegungsablauf gleich aus den Fugen gerät, aber es läuft eher holprig und sprunghaft ab, nicht mehr so geschmeidig. Außerdem lässt sich das Objekt schlechter steuern. Was die Auflösung des Mesh betrifft, müssen wir einen Kompromiss akzeptieren. Einerseits sorgt eine hohe Auflösung für eine detaillierte und angenehme Landschaftsdarstellung; andererseits ist der Bewegungsablauf flüssiger bei großflächigen Terrain-Polygonen.
 Für Abhilfe sorgt ggfs. eine Unterteilung des Zeitintervalls. In jedem Frame werden mehrere Weg-Zeit-Marken bearbeitet, wobei die Anzahl hauptsächlich von der Geschwindigkeit abhängt. Nach jedem Teilintervall erfolgt eine komplette Kollisionsberechnung mit interpolierten Parametern. Evtl. kann dabei der oben erwähnte ODE-Solver erforderlich werden. Der Rechenaufwand im ODE-Solver ist beachtlich, aber andererseits kann ein gut eingestellter Solver die Kollisionsberechnungen vereinfachen bzw. beschleunigen, weil an die Intersektions-Funktionen geringere Anforderungen gestellt werden.

@@ Zeile 180: / Zeile 180: @@
 ===Bounding Volumes===
-Damit komme ich zu den Hüllkörpern ''(bounding volumes)''. Wir haben solche Hüllkörper bereits kennengelernt, denn die Kugel und das Ellipsoid, womit wir unser bewegtes Objekt einpacken, gehören dazu. Es gibt verschiedene Arten von Hüllkörpern, über die man sich ruhig ein wenig schlau machen sollte (Stichwörter ''bounding volume, bounding sphere, bounding cylinder ...''). Meistens, so auch in der bisher beschriebenen Anwendung, werden Hüllkörper benutzt, um ein komplexeres Objekt auf eine einfache Form zurückzuführen. Dadurch halten wir die Rechenvorgänge in Grenzen - oder ermöglichen sie überhaupt erst. Hüllkörper werden ferner gebraucht, um '''statische Kollisionsobjekte''' zu vereinfachen. So könnte z.B. ein Baumstamm, der aus mehreren Polygonen besteht, als Zylinder betrachtet werden, und die Kollision würde so berechnet, als handle es sich um einen echten, wirklich runden Zylinder.
+Damit komme ich zu den Hüllkörpern ''(bounding volumes)''. Wir haben solche Hüllkörper bereits kennengelernt, denn die Kugel und das Ellipsoid, womit wir unser bewegtes Objekt einpacken, gehören dazu. Es gibt verschiedene Arten von Hüllkörpern, über die man sich ruhig ein wenig schlau machen sollte (Stichwörter ''bounding volume, bounding sphere, bounding cylinder ...'' Ihr findet auch Infos im Artikel [[Hüllkörper]].). Meistens, so auch in der bisher beschriebenen Anwendung, werden Hüllkörper benutzt, um ein komplexeres Objekt auf eine einfache Form zurückzuführen. Dadurch halten wir die Rechenvorgänge in Grenzen - oder ermöglichen sie überhaupt erst. Hüllkörper werden ferner gebraucht, um '''statische Kollisionsobjekte''' zu vereinfachen. So könnte z.B. ein Baumstamm, der aus mehreren Polygonen besteht, als Zylinder betrachtet werden, und die Kollision würde so berechnet, als handle es sich um einen echten, wirklich runden Zylinder.
 Im folgenden möchte ich aber auf eine andere Verwendung der ''bounding volumes'' eingehen. Sie sind hervorragend geeignet, die Kollisionsberechnung zu optimieren, indem die Zahl der zu untersuchenden Polygone reduziert wird. Ein einfaches Rechenbeispiel: Wir haben eine Szenerie mit rund 1000 Objekten, von denen jedes im Schnitt aus 50 Polygonen zusammengesetzt ist. Das ergibt 50000 Polygone, die wir in jedem Frame untersuchen müssten. Vielleicht schafft der Rechner das, aber viel Luft bleibt nicht mehr.

@@ Zeile 210: / Zeile 210: @@
 Streng genommen müsste eine Funktion zur Sphere-Sphere-Intersection zum Einsatz kommen, aber da wir uns nicht für den genauen Intersektionspunkt interessieren, geht es mit der gezeigten Ray-Sphere-Intersektion. Wir müssen dann nur den Radius der bewegten Kugel zum Radius der Hüllkugel addieren. Im Falle eines Ellipsoids nehmen wir den größten der 3 Radien.
-[[Bild:Tutorial_Kollision3_16.png|center|framed|Vergrößern des Hüllkörpers um eine Ray-Sphere-Intersektion zu berechnen anstatt der Sphere-Sphere-Intersektion.]]
+[[Bild:Tutorial_Kollision3_16.png|center|framed|Vergrößern des Hüllkörpers um eine Ray-Sphere-Intersektion anstatt der Sphere-Sphere-Intersektion verwenden zu können.]]
 Evtl. kommt ein verkürztes und schnelleres Verfahren in Frage. Dabei prüfen wir lediglich, ob sich nach Durchführung des Bewegungsschrittes das bewegte Objekt im Bereich der Hüllkugel befindet. Das ist nichts anderes als ein schlichter Abstandstest. Eine Kollision kommt dann in Frage, wenn der Abstand der beiden Mittelpunkte kleiner als die Summe der beiden Radien ist. Hierbei brauchen wir ebenfalls keine Wurzelberechnung; es genügt, wenn wir die Quadrate der Entfernungen miteinander vergleichen, da keine negativen Werte vorkommen.
@@ Zeile 216: / Zeile 216: @@
 [[Bild:Tutorial_Kollision3_15.png|center|framed|Problemfälle die zu beachten sind. Falls das Objekt zu schnell ist, kann ein Kollisionspunkt "verpasst" werden.]]
 Wir müssen jedoch bedenken, dass dieses Verfahren nicht ganz ohne Tücken ist. Es kann nämlich vorkommen, dass mit einem Bewegungsschritt der Bereich der Hüllkügel bereits überschritten wird (rechts im Bild). Die Gefahr ist umso größer, je schneller sich das Objekt bewegt und je kleiner die Hüllkugel ist. Evtl. können wir uns helfen, indem wir in Abhängigkeit von der Geschwindigkeit die Hüllkugel vergrößern.
 ===Weitere Optimierungen===