Inexor’s first alpha release

Inexor is the new name of our open source game project. The recently launched website is available here: https://inexor.org/

The project makes good progress and we are about to release the very first alpha. Starting from the rock solid Sauerbraten source code which is sadly stalling right now, we are forking the project and bring it on a higher level. From the developer perspective we created a GitHub repository, introduced a feature branch development model and two-weekly meetings. Also, we’re using CMake as new cross platform build system and Travis for lightweight continuous integration. At a later point we want to replace Travis with Jenkins. We started to document the source code (yes, the old source code too) and created a wiki on GitHub for describing the architecture and features. Lastly, we introduced a unit test framework and want to write tests for all new features.

Building a stable base for development is important, but creating high quality content for the game is even more important. Sauerbraten’s source code is free, but the content is not. We started to drop all non-free content and include new high quality content such as HD textures. Because the maps of Sauerbraten are not free, we try to contact the creators and ask them for re-licensing on a free license like creative commons attribution.

New big features to be expect in the next alpha releases are: JavaScript Scripting Engine, Interprocess Communication, User Interface based on HTML5 and JavaScript technologies.

Changelog

For all progress on the first alpha release follow this link: https://github.com/inexor-game/code/blob/master/changelog.md#inexor—coffein-edition-

Developer Resources

https://github.com/inexor-game

Soundtrack

https://soundcloud.com/schaeffer-andreas/sets/inexor-coffein-soundtrack

Screenshots

cartel_1

cartel_2

dust6

pandora_1

Sauerbraten Fork

SauerFork is a new project to fork Sauerbraten. 15 developers and artists attend to the team. The goal is to stay as sauer-like as possible while adding new features and renewing everything which blocks future progress and creativity.

The official Blog and the activity log:

http://sauerfork.tk/
http://sauerfork.tk/activity

Interview of the SauerWorld team with the SauerFork team:

http://www.sauerworld.org/sauerfork-interview/

Source code and the wiki:

https://github.com/sauerbraten-fork/sauerbraten-fork

Videos by me (Particle System):

In this stage the videos shows mostly the technical implementation… The art comes later :-)











Videos by others of the team:



Message-Broker entkoppeln, routen und verbinden

Immer mehr Software kommuniziert mit anderer Software. Doch diese Kommunikation muss organisiert werden. HTTP(S) ist eine Möglichkeit und nutzt ein klassisches Client-Server-Modell. Mit REST ist es in den letzten Jahren sogar salonfähig geworden und bietet sich an, um Daten zwischen den vielen im Web verfügbaren Diensten auszutauschen. Ob Facebook, Twitter oder zahlreiche Content-Management-Systeme: sie bieten alle REST-Schnittstellen an und befördern das Web katapultartig voran. Jedoch sind HTTP- und REST auf Client-Server-Anwendungen beschränkt, sofern man keine weiteren Abstraktionsschichten einführt.

Die Motivation um sogenannte Message-Broker einzusetzen ist die Universalität dieser Broker. Am leichtesten zu verstehen ist ein Message-Broker, indem man sich einen in Software geschriebenen Router vorstellt, der Nachrichten empfängt und weiterverteilt. Doch dieser Router, bzw. Broker, vermittelt keine rohen Netzwerkpakete, sondern Nachrichten mit Inhalt.

Vermittlung von Nachrichten bedeutet: Auf der einen Seite sendet eine Anwendung, der sogenannte Producer, eine Nachricht an den Broker und dieser empfängt die Nachricht auf einem Eingangsport, in der Messenging-Terminologie heißt dieser Exchange. Ein Exchange hat einen bestimmten Typ, der die Weiterleitung der Nachrichten in eine oder mehrere Warteschlangen, sogenannte Queues, bestimmt. Auf der anderen Seite lauscht eine (andere) Anwendung, der sogenannte Consumer, ob Nachrichten in der Queue vorhanden sind.

Eine Queue kann mehrere Eigenschaften haben. Sie kann beispielsweise einem Consumer exklusiv zugewiesen werden, so dass nur dieser eine Consumer die Nachrichten, die in die Warteschlange einsortiert werden, zugestellt bekommt. Eine weitere Eigenschaft ist, dass eine Queue nach Beendigung der Verbindung automatisch gelöscht wird (autoDelete). Auch ist es möglich, eine Queue so zu konfigurieren, dass in der Warteschlange befindliche Nachrichten einen Neustart des Message-Brokers überleben. Eine Queue kann einen Namen haben oder anonym sein. Anonyme Queues werden beispielsweise für den Rückweg verwendet.

Das Routing findet zwischen Exchanges und Queues statt und nennt sich Binding und ist abhängig vom Typ des Exchange.

Ein Fanout-Exchange leitet eine Nachricht an alle an den Exchange gebundenen Queues weiter, ohne ein aktives Einsortieren. Das bedeutet ein Consumer legt eine (anonyme) Queue an und ebenfalls ein Binding zwischen dem Fanout-Exchange und der angelegten Queue. Wenn ein weiterer Consumer dasgleiche macht, leitet der Fanout-Exchange eine eingehende Nachricht an beide Queues weiter und somit empfangen beide Consumer die Nachricht (Publish-Subscribe-Pattern).

Direct-Exchanges sind ebenfalls mit einer oder mehreren Queues verbunden. Jedoch enthält ein Binding einen sogenannten Routing-Key. Kommt nun eine Nachricht an einem Direct-Exchange an, wird der Routing-Key in der Nachricht untersucht und die Nachricht nur an diejenigen Queues weitergeleitet, bei denen ein Binding mit dem entsprechenden Routing-Key besteht (Routing-Pattern). Beispielsweise gibt es eine Queue, die mit dem Routing-Key “wichtig” gebindet wurde, und eine Queue namens “Spam”, die mit dem Routing-Key “unwichtig” gebindet wurde. Kommt eine wichtige Nachricht an, wird sie in die wichtige Queue einsortigt und unwichtige Nachrichten landen in der Spam-Queue. Es ist möglich, dass mehrere Queues mit dem gleichen Routing-Key mit einem Direct-Exchange verbunden sind. Beispielsweise werden zwei Bindings mit dem Routing-Key “möglicherweise wichtig” vom Direct-Exchange erstellt, die zu beiden Queues führen. Eine möglicherweise wichtige Nachricht landet dann in beiden Queues.

Der dritte Typ heißt Topic-Exchange und setzt das Topic-Pattern um. Der Topic-Exchange wird wiederum mittels Bindings mit Queues verbunden. Doch der Routing-Key der Bindings enthält nun eine Liste von Wörtern, die mit einem Punkt getrennt werden. Diese Liste von Wörtern ist hierarchisch aufgebaut. Beispiel: Queue 1 ist per Binding mit dem Routing-Key “schaeffernet.andreas.raspberry” und Queue 2 mit dem Routing-Key “schaeffernet.*.laptop” verbunden. Die Verarbeitung der Topics ähnelt etwas einer sehr einfachen Regular Expression. So müssen die Topics im Routing-Key der eingehenden Nachricht mit den Topics im Routing-Key des Bindings übereinstimmen. Wie zu sehen ist, sind Platzhalter erlaubt. Während das Binding zu Queue 1 exakt stimmen muss, erlaubt das Binding zu Queue 2 alle Vornamen im zweiten Topic. Interpretieren könnte man den ersten Routing-Key mit “ich möchte die Nachricht an den Raspberry Pi von Andreas Schaeffer zustellen”. Der zweite Routing-Key würde “ich möchte die Nachricht an alle Laptops der Familie Schaeffer zustellen” bedeuten.

Mit diesem relativ einfachen, aber flexiblen System lassen sich nun verschiedenste Anwendungsfälle umsetzen:

1. Ein Producer sendet an eine benamte, exklusive Queue. Die Nachrichten werden von exakt einem Consumer empfangen.

2. Ein Producer sendet an eine benamte, nicht-exklusive Queue. Die Nachrichten werden von einem oder mehreren Consumer empfangen (Worker-Pattern).

3. Ein Producer sendet an einen Fanout-Exchange. Mehrere Consumer legen anonyme Queues an, die sie mit dem Exchange verbinden (Publish-Subscribe-Pattern).

4. Ein Producer sendet an einen Direct-Exchange. Die Nachricht enthält einen Routing-Key. Mehrere Consumer legen anonyme Queues an, die sie mit dem Exchange unter Nutzung eines Routing-Keys verbinden (Routing-Pattern). Eine Queue kann mit mehreren Bindings und unterschiedlichen Routing-Keys verbunden werden (Multiple-Bindings).

5. Ein Producer sendet an einen Topic-Exchange. Die Nachricht enthält einen Routing-Key, der die Topics-Expression beinhaltet. Mehrere Consumer legen anonyme Queues an, die sie mit dem Exchange unter Nutzung eines Routing-Keys, die die Topics-Expression beinhalten, verbinden (Topic-Pattern). Eine Queue kann mit mehreren Bindings und unterschiedlichen Topic-Expressions verbunden werden (Multiple-Bindings).

6. Ein Producer sendet an eine benamte, exklusive Queue. Die Nachricht enthält eine Reply-To-Adresse sowie eine Id, von wem die Nachricht stammt. Exakt ein Consumer empfängt die Nachricht, führt eine Remote-Procedure aus und sendet eine Nachricht mit dem Ergebnis der Ausführung an eine zweite, anonyme, exklusive Queue (RPC-Pattern).

Diese Anwendungsfälle zeigen bereits, wie flexibel ein Message-Broker eingesetzt werden kann. Da wir nun wissen wie ein Message-Broker funktioniert, wird an dieser Stelle noch ausgeführt, welche weiteren Vorteile der Einsatz eines Message-Brokers zu erwarten sind.

Zum Ersten erfolgt die Kommunikation über ein standardisiertes Protokoll namens AMQP. Dieses Protokoll wird von einer ganzen Reihe von Message-Broker-Implementierungen wie beispielsweise RabbitMQ oder ZeroMQ unterstützt. Damit ist man nicht abhängig von einem bestimmten Message-Broker. Die meisten Message-Broker sind darüber hinaus Open-Source und plattformunabhängig.

Weiterhin gibt es für zahlreiche Programmiersprachen Client-Bibliotheken. Das bedeutet, dass die Anwendungen, die miteinander kommunizieren, nicht zwingend in der gleichen Programmiersprache geschrieben sein müssen. Dies ist ein Vorteil gegenüber RMI oder JMS. Der Transportweg kann zudem mit OpenSSL verschlüsselt werden.

Message-Broker sind für einen hohen Durchsatz ausgelegt. Es gibt Anwendungsfälle, in den mehrere Millionen Nachrichten pro Tag verarbeitet werden. Zudem erlauben manche Message-Broker wie beispielsweise RabbitMQ das Clustering von Message-Brokern.

Der größte Vorteil ist jedoch die Entkoppelung. Software kann in kleinere Einheiten aufgespalten werden, die möglicherweise auf unterschiedlichen Rechnern ausgeführt werden und nur an den notwendigen Stellen miteinander kommunizieren. Dabei ist eine heterogene Landschaft kein Problem: in C# programmierte Desktop-Clients auf Windows können mit in Java programmierten Management-Anwendungen auf leistungsstarken Linux-Servern kommunizieren. Oder eine Farm von tausenden von Rechenknechten organisieren dezentral untereinander, welche Aufgaben welche Instanz als nächstes berechnen soll (P2PoB). Oder die Zentralisierung von Logging. Oder die Automatisierung von Rechenzentren…

Implementation einer Software zur Simulation und Visualisierung von Partikeln

Minimal Rendering_2013-01-15_07-28-19

Diese Arbeit beschreibt die Implementierung einer Software zur Simulation von Partikeln. Dabei wurde auf eine hohe Flexibilität Wert gelegt, die es erlaubt, zahlreiche Szenarien zu kreieren. Sowohl das Partikelsystem als auch die Darstellung sind, wie ein Baukastensystem, kombinierbar, konfigurierbar und erweiterbar. Die Software gibt dem Benutzer nichts vor, sondern fordert seine Kreativität heraus. Sie leistet einen Beitrag zu Forschungsprojekten.

1. Einleitung

In vielen Filmen, Computerspielen und Simulationen stellt sich die Frage, wie man natürliche Systeme wie beispielsweise Feuer oder Rauch darstellen kann. Aufgrund ihrer Komplexität oder ihres chaotischen Verhaltens ist die Umsetzung nicht trivial.

Partikelsysteme sind Verfahren, um möglichst realistisch aussehende Darstellungen zu erzielen. Zum ersten Mal wurden Partikelsysteme von William T. Reeves im Jahr 1982 für den Kinofilm “Star Trek II – The Wrath Of Khan” eingesetzt und 1983 in [Ree1983] beschrieben und 1985 in [Ree1985] ergänzt [Paet2005].

Im Kern basieren Partikelsysteme auf dem Grundsatz, etwas Großes aus einer Menge von kleinen Elementen zu erschaffen. Der Funkenregen beim Schweißen bildet sich aus einer Vielzahl von einzelnen und kurzlebigen Funken. Dabei geht es bei Partikelsystemen nicht um eine physikalisch korrekte Simulation von beispielsweise Explosionen, sondern um den Gesamteindruck [Hel2009].

Anwendungsfälle für Partikelsysteme gibt es viele: beispielsweise Feuer, Rauch, Regen oder Schnee. Doch die meisten konkreten Implementierungen von Partikelsystemen sind für einen spezifischen Einsatz gedacht. Daher haben sie ein eingeschränktes Einsatzfeld. Der Grund dafür ist auf geringe oder fehlende Kombinierbarkeit, Konfigurierbarkeit und Erweiterbarkeit zurückzuführen.

Mit dieser Arbeit soll die Implementierung einer OpenSource Software vorgestellt werden, die zum Experimentieren einlädt und die Kreativität des Benutzers fordert. Sie dient nicht der Erfüllung eines konkreten Anwendungsfalls, sondern erlaubt eine Vielzahl von Möglichkeiten. Es soll gezeigt werden, dass dieses Ziel durch Kombinierbarkeit, Konfigurierbarkeit und Erweiterbarkeit erreicht wurde.

2. Grundlagen

Der Architektur von Partikelsystemen ist maßgeblich für die effiziente Verarbeitung. Philipp Pätzold beschreibt in Entwicklung eines Partikelsystems auf Basis moderner 3D-Grafikhardware [Paet2005] eine grundlegende Architektur eines Partikelsystems. Diese umfasst ein Partikelsystem, die eine Menge von Emittern enthält, welche eine Menge von Partikel emittieren. Er beschreibt weiterhin, dass die Implementierung auf der CPU oder auf der Grafikkarte erfolgen kann. Bei der Implementierung auf der Grafikkarte sei mit erheblichen Leistungssteigerungen zu rechnen.

Nach [Paet2005] besitzt jedes Partikel einen Lebenszyklus, der mit der durch das Emittieren beginnt und nach Ablauf der Lebensspanne endet. Ein zwingendes Attribut eines Partikels ist also seine Lebensdauer. Weitere zwingende Attribute von Partikeln sind Position und Richtungsvektor. In der Regel enthält Partikel eine Berechnungsfunktion, um die neue Position in Abhängigkeit von äußeren Einflüssen wie Wind und Gravitation zu berechnen. Der Nachteil dieser Methode wird in dieser Arbeit herausgearbeitet.

Nina Damasky beschreibt in [Dam2008] die Implementierung der Visualisierung von verschiedenen Effekten wie Schnee, Feuer und Feuerwerk. Jeder einzelne dieser Effekte erfolgte in einer eigenen Implementierung. Vorteil der Methode ist, dass die Software um weitere Effekte erweitert werden kann, ohne dass die anderen Implementierungen beeinträchtigt werden. Jedoch sind die Effekte nicht kombinierbar. Auch dies soll in dieser Arbeit näher betrachtet werden.

Die Darstellung von Partikeln ist ebenfalls von besonderer Bedeutung. Moderne Grafikkarten ermöglichen mit Billboarding eine Technik, die bei der Darstellung von Partikeln üblich ist. Dabei werden texturierte Flächen immer so gedreht, das die Kamera stets senkrecht darauf schaut. Auch bei einer Änderung der Kameraposition oder des Blickwinkels sieht man die Textur von vorn. Damit entsteht der Eindruck von dreidimensionalen Objekten wie z.B. Kugeln. Alpha Blending ist eine weitere Technik, die für die Darstellung von Partikeln nützlich ist. Beim additiven Alpha-Blending werden die Farbwerte eines Partikels auf den Hintergrund zu einem gewissen Teil, dem Alphawert, aufaddiert. Dieser Effekt lässt sich beispielsweise dazu nutzen, dass eine Menge von sich überlagernden Rauch-Partikeln eine Rauchwolke ergibt.

3. Konzept und Architektur

Kombinierbarkeit, Konfigurierbarkeit und Erweiterbarkeit sind wesentliche Anforderungen an diese Software. In diesem Abschnitt wird beschrieben, wie diese Anforderungen erfüllt werden.

Abbildung 1 zeigt die Architektur der Software. Sie besteht aus zwei Komponenten: einerseits der Partikelsimulation und andererseits der Visualisierungs- und Editierkomponente. Zweck der Komponente Partikelsimulation ist es, Partikel zu erschaffen, zu verändern und zu terminieren. Diese Komponente ist unabhängig von der Visualisierungs- und Editierkomponente. Das bedeutet, die Partikelsimulation ist auch ohne eine Visualisierung nutzbar. Zweck der Visualisierungs- und Editierkomponente ist es, eine 3D Szene darzustellen und Funktionalitäten zum Editieren der Partikelsimulation anzubieten.

3.1 Partikelsimulation

Die Partikelsimulation enthält eine Menge von Partikeln, Faces, Emittern, Features und Modifieren. Partikel sind einzelne Objekte, die in einer Liste effizient verwaltet werden. Sie enthalten einige notwendige Attribute, wie z.B. Position, Richtungsvektor, Anzahl der vergangenen und restlichen Iterationen des Lebenszyklus sowie welcher PartikelRenderer zum Einsatz kommen soll. Faces sind Flächen, die durch mindestens drei Partikel definiert sind. Zusätzlich enthalten Faces die Information, welcher FaceRenderer bei der Visualisierung Anwendung finden soll.

Emitter erzeugen neue Partikel sowie Faces und fügen sie der Partikelsimulation hinzu. Ein einzelnes Partikel enthält aus Gründen der Performance und des Speicherverbrauchs möglichst wenige Attribute. Bei komplexeren Einsatzszenarien ist es jedoch notwendig, dass Partikel zusätzliche Attribute besitzen. Die Flexibilität eines Partikels wird erreicht, indem dem Partikelsystem sogenannte Features hinzugefügt werden können. Ein Feature erweitert das Basispartikel durch ein oder mehrere zusätzliche Attribute. Die Initialisierung der zusätzlichen Attribute wird vom Emitter an alle in der Partikelsimulation instanzierten Features delegiert.

Die Aufgabe von Modifiern ist es, die Attribute jedes Partikel pro Simulationsiterationsschritt zu verändern. Beispielsweise können Modifier den Bewegungsrichtungsvektor eines Partikels ändern. Auf konkrete Implementierungen von Modifiern wird im Abschnitt Realisierung eingegangen.

3.2 Visualisierung

Die Visualisierungs- und Editierkomponente besteht aus einer Menge von Renderern, Editoren, Partikel-Renderern und Face-Renderern. Die Aufgabe eines Renderers ist es, ein bestimmtes Element der Partikelsimulation zu visualisieren. So kann eine konkrete Implementierung eines Renderers eine konkrete Implementierung eines Emitters oder Modifiers in der 3D-Szene sichtbar machen. Beispielsweise rendert ein GravityPointRenderer einen GravityPoint-Modifier in der 3D-Szene. Konkrete Implementierungen von Renderern werden im Abschnitt Realisierung vorgestellt.

Editoren dienen dem Bearbeiten von Attributen von Elementen der Partikelsimulation. Eine konkrete Implementierung eines Editors ermöglicht es dem Anwender die Attribute einer konkreten Implementierung eines Emitters oder Modifiers zu ändern. Zum Beispiel stellt der Gravity-PointEditor einen Editor für jede Instanz eines GravityPointModifier zur Verfügung.

Nur dadurch, dass Renderer für Modifier und Emitter in der 3D-Szene dargestellt werden, ist es möglich diese per 3D-Picking auszuwählen und somit den Editor für den ausgewählten Modifier oder Emitter zu aktivieren.

Die Aufgabe von Partikel- und FaceRenderer ist es, ein Partikel bzw. ein Face in der 3D-Szene darzustellen. Jedem Partikel wird bei seiner Erzeugung durch einen Emitter die Information zugewiesen, welcher PartikelRenderer zum Einsatz kommen soll. Gleiches gilt analog für Faces und FaceRenderer.

Die konkreten Implementierungen eines PartikelRenderers stellen die einzelnen Partikel unterschiedlich dar. Beispielsweise als einfache Punktprimitive, als Dreieck oder als Tetraeder. Aber auch komplexere Darstellungsverfahren sind möglich: z.B. Ringe oder Röhren.

FaceRenderer visualisieren – ähnlich wie PartikelRenderer – Faces. Jede Face enthält eine Menge von mindestens drei Partikeln, die die Eckpunkte der Fläche definieren. Konkrete Implementierungen von FaceRenderern können die Flächen unterschiedlich darstellen. Beispielsweise als eingefärbtes Polygon oder als texturiertes Polygon.

3.3 Zwischenfazit

Wie eingangs erwähnt, soll die Software erweiterbar sein und dem Anwender umfangreiche Kombinations- und Konfigurationsmöglichkeiten bieten. Kann diese Software diese Anforderungen erfüllen? Erstens ist die Software erweiterbar, indem neue Emitter, Modifier, Features, Renderer, Editoren, PartikelRenderer oder FaceRenderer implementiert werden. Zweitens kann der Anwender beliebig viele Emitter, Modifier und Features einer konkreten Partikelsimulation hinzufügen und durch Editoren konfigurieren – damit ist die Kombinierbarkeit und Konfigurierbarkeit gewährleistet. Schließlich ist die Visualisierung einer konkreten Szenerie durch Renderer, PartikelRenderer und FaceRenderer sehr flexibel.

4. Realisierung

In Abschnitt 3 wurde bereits die Architektur der Software beschrieben. Dieser Abschnitt soll die konkrete Implementierung und den Funktionsumfang der Software erläutern.

4.1 Eingesetzte Technologien

Die in Java geschriebene Software nutzt OpenGL zur Visualisierung. Für Java existiert eine performante und leichtgewichtige Open-Source-Bibliothek, die das OpenGL Application Programming Interface für Java zur Verfügung stellt. Des Weiteren bietet Slick2D Funktionalitäten zum Darstellen von Text per OpenGL zur Verfügung. Als Werkzeug zum Bauen und zur Abhängigkeitsverwaltung von eingesetzten Bibliotheken wurde das in der Java-Welt verbreitete Maven genutzt.

4.2 Partikel und Features

Partikel sind inhaltlich das wichtigste Element einer Partikelsimulation. Jedoch sind bei der Implementierung einige wichtige Voraussetzungen zu erfüllen. Zunächst muss davon ausgegangen werden, dass eine hohe Anzahl von Partikeln erzeugt werden soll. Je mehr Partikel es gibt, desto mehr Speicherplatz wird benötigt. Daher ist bei der Datenstruktur von Partikeln darauf zu achten, dass keine unnötigen Informationen gespeichert werden. Des Weiteren sollen die Partikel als reine Datencontainer implementiert werden, die keinerlei Fachlogik enthalten. Dies ist aus mehreren Gründen sinnvoll. Einerseits führt die Trennung von Daten und Fachlogik zu einer höheren Wartbarkeit der Software. Andererseits benötigen Objektinstanzen von reinen Datenklassen weniger Arbeitsspeicher als Instanzen von Klassen mit Methoden. Eine weitere Anforderung ist die gewünschte Flexibilität der Software, die insbesondere bei der Implementierung von Partikeln zu berücksichtigen ist. Die Erweiterbarkeit und Austauschbarkeit von einer konkreten Implementierung einer Partikelklasse wurde ermöglicht, indem ein Interface Particle definiert wurde. In der gesamten Anwendung wird auf das Interface referenziert. Somit ist es ein leichtes, eine alternative Implementierung einer Partikelklasse zu nutzen. Die Standardimplementierung erbt von HashMap erlaubt daher, neben festen Attributen wie Position und Richtungsvektor, dynamische Attribute hinzufügen. Diese Flexibilität erlaubt es, Partikel durch Features zu erweitern, wie es bereits in Abschnitt 3.1 beschrieben wurde. Nachfolgend werden einige implementierte Features vorgestellt.

Mit dem Feature ParticleColor können die Partikel um die Informationen für Farben erweitert werden. Dazu werden in einem Partikel die Farbwerte für Rot, Grün und Blau für Start- und Endposition hinterlegt. Ein weiteres Feature ist ParticleSize, das die Partikel um die Start- und Endgröße erweitert. Durch das Hinzufügen des Features InitialVelocityScatter bewirkt man, dass die Richtungsvektoren der emittierten Partikel eine Streuung erfahren. Wie sich die Streuung auswirkt, kann jeweils für die x-, y- und z-Richtung konfiguriert werden. Ein weiteres Feature ist Mass-Spring, welches die Partikelsimulation um Federn zwischen Partikeln erweitert. Die Federn werden in einer Liste in jedem Partikel verwaltet. Schließlich kann durch das Feature PositionPath die Simulation dahingehend erweitert werden, dass in jedem Partikel die letzten Positionen eines Partikels gespeichert werden können. Dies eignet sich beispielsweise, um für ein Partikel einen Schweif oder eine Röhre entlang seiner vergangenen Positionen zu zeichnen. Features erlauben eine Erweiterung der Datenstruktur der Partikel und sie können genutzt werden um beim Emittieren Attribute des Partikels zu setzen oder zu beeinflussen. Jedoch haben sie keine modifizierende Wirkung während der Lebenszeit des Partikels. Daher ist es für die meisten Anwendungsfälle notwendig, Modifier zu implementieren, die Partikelattribute während der Lebenszeit zu verändern. Mehr dazu in Kapitel 4.4.

4.3 Emitter

In der Anwendung wurden mehrere Emitter implementiert. Der PointEmitter erzeugt an einer bestimmten Position neue Partikel. Bei diesem Vorgang wird ein neues Partikelobjekt erzeugt und ihm die Position des Emitters zugewiesen. Zusätzlich werden anhand der Konfiguration des Emitters der Richtungsvektor und die Anzahl der verbleibenden Lebenszyklusiterationen gesetzt.

Eine weitere Implementierung ist der PlaneEmitter, der die initiale Position des erzeugten Partikels auf eine zufällige Position einer konfigurierten Fläche setzt. Ein SphereEmitter unterscheidet sich zu einem PointEmitter dadurch, dass der Richtungsvektor zufällig ist. Das bedeutet das Partikel in alle Richtungen ausgestoßen werden.

Während die bereits erwähnten Emitter relativ einfach sind, lässt sich die Komplexität von Emittern weiter steigern. Der Tetrahedron-Emitter erzeugt Tetraeder, die aus vier Partikeln bestehen, die jeweils durch Federn miteinander verbunden sind. Zusätzlich werden vier Faces erzeugt, die die Außenhaut des Tetraeders bilden. Der ClothEmitter erzeugt ein Netz von Partikeln, die jeweils mit Federn verbunden sind. Dadurch lässt sich Stoff simulieren. Ein weiterer Emitter ist der SoftBodyEmitter. Dieser lädt ein 3D-Modell aus einer Datei und erzeugt pro Vertices des 3D-Modells ein Partikel. Zusätzlich werden die Faces des 3D-Modells ausgelesen und die erzeugten Partikel zu Faces der Partikelsimulation verbunden. Die Partikel eines Faces werden weiterhin mit Federn verbunden, um dem 3D-Modell eine Stabiltät zu verleihen. Außerdem werden Ankerpunkte an der initialen Position eines Partikels erzeugt und mit einer starken Feder mit dem Partikel verbunden um ihn an seiner ursprünglichen Position zu halten. Es ist zu sehen, dass Emittern einfach oder komplex sein können. Für Stoff oder wacklige Objekte wurden komplexere Emitter implementiert. Doch Emitter alleine, selbst wenn sie komplex sind, bewirken noch kein dynamisches System. Die Dynamik der Partikelsimulation wird erst durch die Modifikation der Partikel während ihrer Laufzeit erreicht.

4.4 Modifier

Diese Aufgabe obliegt Modifiern. Die Attribute von Partikeln werden ausschließlich durch Modifier verändert. Das bedeutet, dass in einer Partikelsimulation ohne Modifier sich der Zustand von Partikeln nicht ändert. Für diese Software wurde daher eine Reihe von Modifiern implementiert. Der wichtigste Modifier ist die Klasse VelocityTransformation. Er ändert die Position des Partikels, indem auf die bisherige Position der Richtungsvektor aufaddiert wird:

Formel 1: Velocity Transformation

Der Modifier VelocityTransformation ist der einzige Modifier, der die Position des Partikels ändert. Die weiteren verändern in der Regel den Richtungsvektor des Partikels. Dies ist auch beim Modifier VelocityDamper der Fall. Dabei wird der Richtungsvektor um einen Dämpfungsfaktor verringert:

Formel 2: Velocity Damper

Drei weitere Modifier lassen eine Gravitationskraft auf die Partikel wirken. Erstens ist der GravityPoint eine punktförmige Gravitationsquelle, deren Gravitationskraft in alle Richtungen wirkt. Zweitens wirkt beim Modifier GravityPlane die Gravitationskraft in Lotrichtung einer Fläche. Drittens der Modifier ParticleGravity, der alle Gravitationskräfte zwischen allen Partikeln berechnet. Die Gravitationskraft beeinflusst jeweils wiederum den Richtungsvektor. Da die Berechnung der Gravitationskräfte für alle drei Modifier ähnlich ist, wird nachfolgend die Berechnung der Gravitationskraft exemplarisch für den Modifier GravityPoint erläutert.

Formel 3: Berechnung der Gravitationskraft und Änderung des Richtungsvektors

Zunächst wird die Distanz des Partikels zum Gravitationspunkt berechnet. Anschließend wird die Gravitationskraft berechnet, die von der Distanz und der Masse des Partikels sowie des Gravitationspunkts abhängig ist. Das Partikel wird in Richtung des Gravitationspunkts um die eben berechnete Gravitationskraft in Abhängigkeit zur Distanz und Masse des Partikels beschleunigt. Abschließend wird der Beschleunigungsvektor mit dem bisherigen Richtungsvektor addiert, um den neuen Richtungsvektor zu erhalten.

Eine Eigenschaft der Partikelsimulation ist, dass Partikel voneinander unabhängig sind. Durch das Feature MassSpring und den Modifier MassSpringTransformation wird die Simulation um das physikalische Konzept Masse-Feder-Systeme erweitert. Partikel besitzen jeweils eine Masse und sind mit Federn untereinander verbunden. Jede Feder hat eine festgelegte Länge, bei welcher sie sich im Ruhezustand befindet. Sie kann jedoch auch gestaucht sein, d.h. die Distanz zweier mit Federn verbundener Partikel ist geringer als die eigentliche Länge der Feder. Andersherum ist die Feder gestreckt wenn die Distanz größer ist. Der Modifier berechnet in jeder Iteration für jedes Partikel und jede ihrer Federn die Federkraft und ändert den Richtungsvektor beider mit der Feder verbundenen Partikel. Um zu vermeiden, dass die Federkräfte doppelt berechnet werden, und damit Geschwindigkeitseinbußen zu verzeichnen wären, ist eine Feder eindeutig einem Partikel zugeordnet. Damit Partikel überhaupt über Federn verfügen, müssen sie dem Partikel von einem spezialisierten Emitter hinzugefügt werden. Beispiele sind der ClothEmitter und der SoftBodyEmitter.

Formel 4: Berechnung der Federkräfte und Änderung des Richtungsvektors

In Abschnitt 4.2 wurden bereits die Features ParticleColor und ParticleSize erwähnt. Doch beim Einsatz dieser Features ohne einen zugehörigen Modifier würde zwar die Datenstruktur des Partikels erweitert werden, aber der Farbwert bzw. die Größe des Partikels nicht geändert werden. Daher wurden zur Änderung der Farben und der Partikelgröße über die Zeit mehrere Modifier implementiert. Die LinearColorTransformation ändert die aktuelle Farbe des Partikels zwischen Startfarbe und Endfarbe durch lineare Interpolation. Somit ist es beispielsweise möglich, dass ein anfänglich rotes Partikel sich zu einem gelben Partikel entwickelt. Der Modifier RandomStartColor vergibt jedem Partikel bei der ersten Iteration eine zufällige Farbe. Ein weiterer Modifier LinearSizeTransformation arbeitet ähnlich wie der Modifier LinearColorTransformation und ändert die Partikelgröße von einer Startgröße bis hin zur Endgröße. Hingegen lässt der Modifier PulseSizeTransformation die Größe des Partikels mit Hilfe einer Sinusschwingung pulsieren.

Ebenfalls in Abschnitt 4.2 wurde das Feature PositionPath vorgestellt. Ziel ist es, dass ein Partikel die letzten Positionen speichert. Der Modifier PositionPathBuffering entfernt bei jeder Iteration die älteste Position und fügt die aktuelle Position hinzu.

Wie zu sehen ist, nehmen die Modifier eine zentrale Rolle im Partikelsystem ein. Sie verringern die Komplexität des gesamten Systems, indem einzelne Operationen jeweils in einem eigenen Modifier gekapselt werden. Modifier sind kombinierbar und es können alternative Implementierungen, wie z.B. bei der Art wie die Farben über die Zeit geändert werden, angeboten werden.

4.5 Renderer

Die bisherigen Abschnitte behandelten die Erzeugung und Modifizierung innerhalb des Partikelsystems. Dieser Abschnitt zeigt die Visualisierung des Partikelsystems. Dabei umfasst die Visualisierung nicht nur die Partikel und Faces selbst, sondern es gilt weitere Elemente wie beispielsweise Emitter und Modifier darzustellen. Für jedes darzustellende Element muss das Interface Renderer implementiert werden. Da es einige Methoden gibt, die allen Renderern gemeinsam sind, implementieren die konkreten Renderer von der abstrakten Klasse AbstractRenderer.

Renderer können der Visualisierungs- und Editierkomponente dynamisch hinzugefügt werden. Zudem können Renderer auch temporär aktiviert und deaktiviert werden. Die Klasse RendererManager verwaltet alle Renderer und ruft in jedem Frame jeden hinzugefügten und aktivierten Renderer auf.

Zur Visualisierung von Emittern wurde die Klasse EmitterRenderer implementiert. Der EmitterRenderer zeichnet an der Position aller in der Partikelsimulation vorhandenen Emitter eine Kugel. Diese kann per Mausklick durch den Raum gezogen werden, und ändert die Position des Emitters. Beim Anklicken einer Kugel wird ein Editor für den ausgewählten Emitter geöffnet. Zudem ist es möglich, einen ausgewählten Emitter per Tastendruck zu entfernen. Jedoch sind nicht alle Emitter punktförmig und müssen daher auf eine andere Weise dargestellt werden. Beispielsweise ist der PlaneEmitter mit zwei Punkten und einer Normale definiert und muss dementsprechend als Fläche im Raum dargestellt werden.

Bei den Modifiern wird in darstellbare und nicht darstellbare Modifier unterschieden. Nichtdarstellbare Modifier sind beispielsweise die Klasse ParticleLimiter, die die Höchstzahl von Partikeln im System reguliert und die Klasse VelocityTranstransformation, die den aktuellen Richtungsvektor zur aktuellen Position addiert. Jedoch existieren einige Modifier, die darstellbar sind. Dies sind zum Beispiel punktförmige Gravitationspunkte, die durch den Renderer GravityPointRenderer dargestellt werden. Wie Emitter besitzen sie eine Position und werden ebenfalls als Kugel, jedoch in einer anderen Farbe, gezeichnet.

Ein weiterer Renderer ist von Nutzen, wenn das Feature MassSpring genutzt wird. Der SpringRenderer zeichnet die in der Partikelsimulation existierenden Federn zwischen Partikeln ein. Um darzustellen, ob eine Feder im entspannten Zustand ist, werden drei Farben zum Zeichnen der Linie verwendet. Eine rote Linie bedeutet, dass die Feder gedehnt ist und sich zusammenziehen will. Hingegen bedeutet eine grüne Linie, dass die Feder gestaucht ist und sich ausdehnen möchte. Eine Feder im Ruhezustand wird grau gezeichnet. Ob sich die Feder im gedehnten, gestauchten oder Ruhezustand befindet, berechnet sich dadurch, ob die Distanz beider Partikel größer, kleiner oder gleich der Federlänge ist.

Es gibt weitere Renderer, die kurz vorgestellt werden sollen: der CameraRenderer stellt an den Positionen der Kameras einen Trichter in Blickrichtung der Kamera dar. Der AxisRenderer zeichnet ein Achsenkreuz durch den Ursprung des World Space.

4.6 Rendering von Partikeln und Faces

Nun stellt sich die Frage, wie Partikel und Faces gezeichnet werden. Auch dies soll der Anforderung der Software entsprechen, flexibel und erweiterbar zu sein. Um unterschiedliche Partikeltypen darzustellen, existiert ein Interface ParticleRenderer. Das konkrete Zeichnen von Partikeln findet in einer Klasse statt, die dieses Interface implementiert.

Die Klasse ParticleRendererManager verwaltet die einzelnen Renderer für Partikel. Auch sie können dynamisch zur Laufzeit hinzugefügt, entfernt oder ausgetauscht werden. Zur Effizienzsteigerung ist eine weitere Aufgabe des ParticleRendererManager das Cachen von Partikeln in separaten Listen für jeden genutzten ParticleRenderer. Diese Listen ermöglichen es, Partikel, die einen bestimmten ParticleRenderer nutzen, direkt nacheinander zu zeichnen. Das bedeutet, dass die Initialisierung und Deinitialisierung des Zeichnens, wie beispielsweise das Laden einer Textur oder das Setzen einer Zeichenprimitive in OpenGL, nicht einmal pro Partikel geschieht, sondern nur einmal pro ParticleRenderer. Auf diese Weise konnte, je nach konkreter Implementierung, eine enorme Steigerung der Performance erreicht werden. Der zu zahlende Preis ist eine gesteigerte Komplexität durch die Verwaltung der Listen und die Invalidierung von Cacheobjekten, d.h. Partikel deren Lebenszyklus beendet ist. Gerade das Entfernen von Partikelobjekten aus dem Cache ist Performancekritisch. Daher wurde es nötig, die Java-Klasse LinkedList zu verwenden, die im Gegensatz zu ArrayList sowohl beim hinzufügen als auch beim entfernen von Listenobjekten in linearer Zeit arbeitet.

Die Darstellung von Partikeln selbst kann unterschiedlich komplex sein. Die einfachsten Fälle sind das Zeichnen von Primitiven wie Punkten, Linien, Linienzüge, Dreiecken und Vierecken. Diese konnten so erweitert werden, dass sie farbig gezeichnet werden, wenn das Feature ParticleColor vorhanden ist. Auch die Verwendung des Features ParticleSize ist beispielsweise durch die Punktgröße oder die Liniendicke auf einfache Weise möglich. Zudem wurde Alphablending eingesetzt, so dass Punktwolken deutlich realistischer wirken, da die Dichte der Wolke sichtbar wird.

Sollen optisch ansprechende Partikelrenderer implementiert werden, so steigt der Aufwand bei der Implementierung. OpenGL unterstützt mit sogenannte Point Sprites, mit welchen sich das Verfahren Billboarding anwenden lässt (siehe Abschnitt 2). Die Initialisierungsphase eines Partikelrenderers ist bei der Nutzung von Billboarding deutlich umfangreicher. Doch dieses Verfahren ist lohnenswert: in Verbindung mit geeigneten Texturen werden optisch ansprechende Effekte möglich. So greifen einige Partikelrenderer für diese Technik zurück, um Feuer- und Energiebälle, Lagerfeuer, grüne Giftwolken, Nebelschwaden und Schnee-flocken darzustellen. Dank der Unterstützung der Grafikhardware und OpenGL ist das Zeichnen nur wenig langsamer als das Zeichnen einer Punktprimitive.

Die Möglichkeiten der Visualisierung von Partikeln sind damit jedoch noch nicht ausgeschöpft. So wurde ein Partikelrenderer für Ringe implementiert, der einen Kreis mit dem Durchmesser der Partikelgröße zeichnet. Dabei liegt der Richtungsvektor des Partikels im Lot der Fläche des Kreises, so dass bei hintereinander emittierten Partikeln der Effekt einer gekrümmten Röhre entsteht. Der TubeParticleRenderer nutzt das Feature PositionPath und stellt anhand der letzten Positionen eine Röhre dar. Dazu muss neben der Normale und der Tangente auch die Bitangente des Partikels für die Berechnung der einzelnen Röhrensegmente genutzt werden. Eine Variante des TubeParticleRenderers ist die Klasse SpiralParticleRenderer, die die Röhrensegmente beim Zeichnen verdreht, so dass statt einer Röhre eine Spirale entsteht.

Im Laufe der Entwicklung wurden Partikelrenderer auch dazu verwendet, um physikalische Vorgänge zu visualisieren. In einer Partikelsimulation mit mehreren Gravitationspunkten ist es beispielsweise von Interesse, wie sich der Richtungsvektor eines Partikels pro Iteration ändert. Sehr anschaulich wird dies durch die Klasse VelocityIndicatorParticleRenderer. Diese zeichnet ausgehend von der Position des Partikels den Richtungsvektor als Linie. Eine weitere Darstellungsform ist die Klasse VeloCube, die einen Quader zeichnet. Die Ausmaße ergeben sich dabei durch die drei Komponenten des Richtungsvektors.

Analog zur Darstellung von Partikeln erfolgte die Umsetzung der Darstellung von Faces. Jedoch muss das Interface FaceRenderer implementiert werden. Die Verwaltung erfolgt durch die Klasse FaceRendererManager. Das beschriebene Verfahren zum Cachen von Partikeln wurde ebenfalls beim FaceRendererManager angewendet. Der bedeutenste Unterschied liegt darin, dass FaceRenderer die Positionen von einer variablen Anzahl von in den Faces enthaltenen Partikeln nutzen müssen. Eine einfache Implementierung ist die Klasse PolygonFaceRenderer, die ein Polygon unter Verwendung der Partikelpositionen als Eckpunkte zeichnet. Jedoch sind weitere Anwendungsfälle möglich, wie beispielsweise gekrümmte Oberflächen oder das Zeichnen von mehreren Flächen.

4.7 Performance

Ein wichtiger Aspekt bei der Implementierung der Partikelsimulation ist die Performance. Um die Performance zu steigern, wurden mehrere Maßnahmen durchgeführt.

Pro Iterationsschritt wird jeweils jeder Emitter aufgerufen. Anschließend werden in jedem Iterationsschritt für jedes Partikel jeder Modifier aufgerufen. Im Gegensatz zu Emittern ist also die Anzahl von Modifiern entscheidend für die Performance. Da Modifier für jeden Partikel aufgerufen werden, sinkt die Performance je mehr Partikel existiert sind. Zusätzlich unterscheiden sich der Aufwand der Implementierungen von Emittern und Modifiern.

Wie in Abschnitt 3 gezeigt, ist die Komponente Partikelsimulation unabhängig von der Visualisierungs- und Editierkomponente. Durch diese Trennung wird es möglich beide Komponenten in eigenen Threads zu betreiben. Dies ist in doppeltem Sinne erstrebenswert: die Verarbeitungsgeschwindigkeit wird einerseits erhöht und andererseits blockieren sich beide Komponenten nicht.

Weiterhin werden Partikel, Faces, Emitter, Modifier und Features in einer ArrayList verwaltet, da dies in Java den schnellstmöglichen Zugriff per Iterator ermöglicht.

Ein weiterer Aspekt betrifft das fortlaufende Erzeugen von neuen Partikelobjekten durch Emitter. Schon das Erzeugen von Java-Objekten belastet die Performance. Noch drastischer wirkt sich jedoch das Aufräumen von nicht mehr genutzten Objekten in Java aus. Wird ein Objekt referenzlos, so wird dieses bei der nächsten GarbageCollection von der Java Virtual Maschine entfernt. Während der GarbageCollection wird jedoch die Anwendung, die auf der virtuellen Maschine läuft, in diesem Fall die Partikelsimulation, vollständig blockiert bis die Garbage-Collection beendet ist. Dies führt bei wenigen Partikeln, zu gelegentlichen und kaum merkbaren Rucklern. Je mehr Partikel jedoch emittiert wurden und nach ihrem Lebenszyklus schließlich aufgeräumt werden müssen, desto häufiger und störender wirkt sich dieser Effekt aus.

Als Maßnahme um diese störenden Effekte zu minimieren, werden Partikel wiederverwendet. Statt ein Partikelobjekt nach dem Lebenszyklus aus der Liste von lebenden Partikeln zu entfernen, und damit der Garbage-Collection zu überlassen, werden sie in einem als Stack implementierten Pool gespeichert. Emitter erzeugen nur noch dann neue Partikel- objekte, wenn in dem Pool keine Partikelobjekte mehr vorhanden sind. Anderenfalls wird ein Partikelobjekt aus vom Stack geholt und initialisiert. Somit konnte verhindert werden, dass die Anwendung durch häufige und länger dauernde GarbageCollection-Vorgänge unterbrochen wird. Zudem konnte durch das Reduzieren des Erzeugens von neuen Java-Objekten Performancesteigerungen erreicht werden.

5. Ergebnisse

Die Software leistet einen Beitrag zur Entwicklung von Partikelsimulationen mittels Java, OpenGL und der Leightweight Java Game Library. Sie ist als Open-Source Experimentiersoftware für Partikelsysteme bisher konkurrenzlos. Durch die Architektur der Software wird nicht nur die Erweiterbarkeit gewährleistet, sondern zudem eine hohe Performance erreicht.

Die vorgestellte Anwendung könnte zum Ausprobieren von neuartigen visuellen Effekten, beispielsweise für Computerspiele oder Filme, genutzt werden oder sogar Künstlern als neue Ausdrucksform dienen. Des Weiteren bietet sich die Software zur Visualisierung von Simulationen an.

Um die Erkenntnisse öffentlich verfügbar zu machen, steht die entwickelte Software unter dem General Public License. Dies erlaubt es Dritten, die Software zu nutzen, erweitern und unter gleichen Bedingungen weiterzugeben.

6. Zusammenfassung und Ausblick

Diese Arbeit zeigt die Implementierung einer Experimentiersoftware zur Simulation und Darstellung von Partikeln. Sie erlaubt es dem Anwender, visuell eindrucksvolle, aus Partikel bestehende Szenarien zu entwickeln. Dieses Ziel wurde durch die Erweiterbarkeit der Software einerseits und die Kombinierbarkeit und Konfigurierbarkeit innerhalb der Anwendung andererseits erreicht.

Zukünftige Weiterentwicklungen könnten weitere Emitter, Modifier und Features umfassen. Beispielsweise könnten Emitter für die Generierung von fraktalen Landschaften oder für die Generierung von Vegetation mittels Lindenmayer Systemen implementiert werden. Eine weitere Erweiterungsmöglichkeit bestünde darin, einen Modifier zu implementieren, der die Reproduktion und Vervielfältigung von Partikeln anhand von Regeln simuliert. Darüber hinaus könnte die Software um Beleuchtungs- und Reflexionsmodelle erweitert.

Literatur:

[BFA2002] Bridson, Robert; Felkiw, Ronald und Anderson, John. Robust Treatment of Collisions, Contact and Friction for Cloth Animation. 2002, Standford, USA

[BW1998] Baraff, David und Witkin, Andrew. Large Steps in Cloth Simulation. 1998, Orlando, USA

[Dam2008] Damasky, Nina Partikelsimulation (Studienarbeit). 2008, Koblenz

[FR1986] Fournier, Alain und Reeves, William T. A simple model of ocean waves. 1986, Toronto, USA

[Hel2009] Helminger, Mathias. Physics – Particle Systems. 2009, München

[Lan2004] Lange, Marc. Simulation Stoffähnlicher Objekte. 2004, Koblenz

[LMT1991] Lafleur, Benoit; Magnenat Thalmann, Nadia und Thalmann, Daniel. Cloth Animation with Self-Collision Detection- 1991, Switzerland.

[OS2003] O’Connor, Corey und Stevens, Keith. Modeling Cloth Using Mass Spring Systems. 2003, Claremont, USA

[Paet2005] Pätzold, Philipp. Entwicklung eines Partikelsystems auf Basis moderner 3D-Grafikhardware(Studienarbeit). 2005, Koblenz

[Ree1981] Reeves, William T. Inbetweening for Computer Animation Utilizing Moving Point Constraints. 1981

[Ree1983] Reeves, William T. Particles Systems – A Technique for Modeling a Class of Fuzzy Objects. 1983

[Ree1985] Reeves, William T. Approximate and Probabilistic Algorithms for Shading and Rendering Structured Particle Systems. 1985.

Terrain Generation in der Cube2 Engine

Die Cube2-Engine verfügt über einen exzellenten in-game Map-Editor. Basierend auf einem Octree, können Cubes auf allen sechs Seiten deformiert werden. Das Format spart nicht nur Platz auf der Festplatte, sondern auch im Arbeitsspeicher. Damit ist es möglich große 3D-Welten auch auf resourcenschwacher Hardware darzustellen. Da die Welt jedoch nicht einfach aus einer Menge von Vertices besteht, ist die Implementierung eines Terrain Generators deutlich aufwändiger.

Der grundlegende Algorithmus ist Simplex-Noise, eine Weiterentwicklung von Perlin-Noise. Vorteil des Algorithmus gegenüber seinem Vorgänger ist es, dass er in höheren Dimensionen deutlich performanter ist. Das Ergebnis des Algorithmus ist eine Höhenmap für entweder 2D oder 3D. Wird Simplex-Noise für 2D generiert, bekommt man pro x,y-Koordinate einen Höhenwert, also den z-Wert. Somit erhält man eine hügelige Landschaft. Wird Simplex-Noise jedoch für 3D generiert, bekommt man einen Dichtewert pro x,y,z-Koordinate. Dieser Dichtewert bewegt sich zwischen einem Minimum und einem Maximum, üblicherweise zwischen 0 und 1. Setzt man einen Grenzwert, beispielsweise 0.5, kann man zwischen solidem Gestein und Luft unterscheiden. Ein Dichtewert an einer Position x,y,z ist Gestein, wenn er den Grenzwert unterschreitet, ansonsten Luft. Außerdem ist es möglich das Spektrum zwischen 0 und 1 in mehrere Segmente aufzuteilen, um beispielsweise mehrere Schichten unterschiedlichen Gesteins zu erzeugen. Tiefere Schichten bestehen beispielsweise aus Granit, höhere Schichten aus Erde.

Um Höhen- und Dichtewerte in der Cube-Engine zu nutzen, muss die Map in gleich große Blöcke eingeteilt werden. Der Wert entscheidet darüber, ob ein Block erstellt wird oder ob der Platz frei bleibt. Diese Welt ist jedoch eine Klötzchenwelt und damit ist der Realitätsgehalt sehr niedrig. Die Blöcke mussen nun noch interpoliert werden, um nahtlos aneinander anzuschließen. Dazu ist ein weiterer Algorithmus zuständig: Marching Cubes. Dabei werden die Blöcke weiter in kleinere Blöcke zerlegt und für jeden kleineren Block bestimmt, wie die Oberfläche des größeren Blocks diesen kleineren Block durchschneidet. Abhängig davon wird eine von 15 möglichen Deformationen durchgeführt. Damit ist die Geometrie erzeugt.

Um Lichter zu setzen, wird wiederum der Dichtewert bemüht. Es wird derjendige Punkt ausgewählt, der in der Mitte einer Höhle, d.h. garantiert in der Luft und in einiger Entfernung zu einer Wand, ist. Dies erreicht man indem man wiederum einen Grenzwert bestimmt, der deutlich größer ist, als der Grenzwert zwischen Gestein und Luft, aber etwas niedriger als das Maximum. Außerdem wird ein Minimalabstand zwischen den erzeugten Lichter eingehalten um eine gleichmäßigere Ausleuchtung zu erzielen.

NoobLauncher: Software Architecture vs. Limited Language

NoobLauncher is served two ways. It’s an development framework in cubescript, the built in macro language of the open souce cube 2 game engine. And it’s a whole set of addons provided by plugins.

Why does NoobLauncher exists? At first, I tried to make things possible with a limited language. Secondly, there are many simple scripts and only a few bigger applications written in cubescript. Because of the global namespace the scripts can interfer with each other. The same counts for the bigger collections. Both have no software architecture at all.

What’s needed to make a good piece of software using a limited language? The same as in every language – ideas and software architecture. You just have to apply technologies that exists elsewhere. At first I implemented a plugin loading mechanism, to make the software modular. To avoid problems in the plugins, I provided a mechanism for handling the global namespace and for persisting information. Also there is an abstraction layer for making guis easier and more consistent. Because keys are also limited resources an input handling system is nessesary, too. Finally an register/subscribe event system makes core components and plugins play well together.

Dependency Injection in C++ isn’t possible?

Starting up a new project called Cube a Libre I was confronted with no cool dependency injection framework in C++ like the famous Spring Framework in Java. I tested some of them: pococapsule, autumnframework and qtioccontainer. No one was acceptable (dependency to java(!), 6 years old, too complicated.

So I started a new experiment: Is Dependency Injection in C++ possible?

Yes and no. No, because there is no introspection. Yes, if you had a little help from the Qt framework which provides the metaobject system and a preprocessor called moc. So your project has the dependency to Qt. Also your classes can’t be implemented as plain old POJOs POCOs. They has to inherit from QObject. In addition, they has to implement some methods and has to register themselfs.

Lets take a look into the xml file:

 XML |  copy code |? 
01
<objects>
02
  <object name="scriptingManager" class="ScriptingManager" />
03
  <object name="pythonInterpreter" class="PythonInterpreter" />
04
  <object class="NetworkManager" init-method="init">
05
    <property name="pythonInterpreter" ref="pythonInterpreter" />
06
    <property name="startupScriptFilename" value="../engine/alive.py" />
07
  </object>
08
  <object name="jabberClient" class="JabberClient" destroy-method="destroy">
09
    <property name="name" value="**********" />
10
    <property name="password" value="**********" />
11
    <property name="server" value="**********" />
12
    <property name="resource" value="cube-a-libre" />
13
  </object>
14
</objects>

This looks much like a xml file you would use in Java/Spring. You can define objects from a classname (a string!), give them names, sets properties and inject other objects using the ref attribute.

Now lets take a look on a class definition:

 C++ (Qt) |  copy code |? 
01
class JabberClient : public QObject
02
{
03
    // For Qt Meta system
04
    Q_OBJECT
05
 
06
    Q_PROPERTY(QString name WRITE setName)
07
    Q_PROPERTY(QString password WRITE setPassword)
08
    Q_PROPERTY(QString server WRITE setServer)
09
    Q_PROPERTY(QString resource WRITE setResource)
10
 
11
    public:
12
        JabberClient();
13
        JabberClient(const JabberClient& jabberClient) {};
14
        virtual ~JabberClient();
15
 
16
        void connect();
17
        void disconnect();
18
        void sendMessage(QString jid, QString text);
19
 
20
        void onConnect(void);
21
 
22
        void setName(QString name);
23
        void setPassword(QString name);
24
        void setServer(QString server);
25
        void setResource(QString resource);
26
 
27
    public slots:
28
        void init();
29
        void destroy();
30
 
31
    private:
32
        QString name;
33
        QString password;
34
        QString server;
35
        QString resource;
36
};
37
 
38
REGISTER_CLASS(namespace::JabberClient, JabberClient);
39
 
40
Q_DECLARE_METATYPE(namespace::JabberClient*)
41

You can see, we need a constructor, a destructor and a copy constructor. The copy constructor doesn’t have to be implemented, but must exist. The class itself inherits from QObject, so we can use the Qt meta object system. Also we define the some properties and their setters. Using Qt’s PROPERTY macro we make the meta object system know them. At the bottom we can see, that we register the metatype using Q_DECLARE_METATYPE. Also, we register the class using the macro REGISTER_CLASS provided by cube-a-libre.

Finally we have to initialize the application context:

 C++ (Qt) |  copy code |? 
1
engine::XmlApplicationContext context;
2
context.createContextFromXmlFile("context.xml");
3
engine::JabberClient* jabberClient = (engine::JabberClient*) context.getObject("jabberClient");
4
jabberClient->init();
5
 
6
[...] more code [...]
7
 
8
context.destroyContext();

First, we create a XmlApplicationContext object. Then we let it create an application context from a xml file. The application context will be automagically created. Then we can make use of the getObject Method to get the singleton object instance. Finally, we destroy the context.