About aschaeffer


Website: http://www.schaeffernet.de/
aschaeffer has written 12 articles so far, you can find them below.


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:



10 Java-Bibliotheken die man kennen sollte

  1. Spring
  2. Vaadin
  3. MetaWidget
  4. Lucene
  5. Neo4j
  6. Jackson
  7. Freemarker
  8. slf4j
  9. Apache Commons
  10. Reflections

Alle Bibliotheken sind Open-Source und Freie Software.

Das Spring Framework ist ein kleines Universum und bietet neben dem Hauptkonzept der Dependency-Injection viele weitere Bibliotheken f√ľr g√§ngige Use-Cases. So gibt es Bibliotheken f√ľr den Sicherheits-Layer, ein deklaratives Model-View-Controller Framework f√ľrs Web, eine Persistenz-Abstraktionsschicht, um nur die wichtigsten zu nennen.

JavaScript-Bibliotheken sprie√üen wie Pilze aus dem Boden. Es gibt sicherlich hunderte davon, alle mit einem √§hnlichen Ziel. Wer aber Java-Webanwendungen implementieren und kein Sprachmix mehr haben m√∂chte, der kann mit Vaadin nun Server-seitig grafische Oberfl√§chen programmieren. √Ąhnlich wie Swing bietet Vaadin eine umfangreiches, komponentenbasiertes GUI-Toolkit an. In Java geschriebene Oberfl√§chen werden von Vaadin in JavaScript √ľbersetzt und an den Client √ľbertragen. Auch die Synchronisation der Daten zwischen Client und Server und umgekehrt √ľbernimmt Vaadin.

MetaWidget ist ebenfalls im Bereich der grafischen Oberfl√§chen angesiedelt und l√∂st das Problem, dass viele Masken √§hnlich sind. Mittels Introspection und/oder deklarativen Annotationen kann man automatisiert Formulare und Listenansichten f√ľr Daten anzeigen lassen. Ein sogenanntes MetaWidget untersucht beispielsweise alle Felder, Getter, Setter (mit oder ohne Annotationen) eines POJOs und generiert ein Formular zur Verwendung im Webbrowser. √Ąnderungen im Formular kann man in das zur√ľckschreiben und anschlie√üend speichern. Woher die Daten kommen, ist abstrahiert, ebenso mit welcher Frontend-Technologie diese Daten angezeigt werden. Das bedeutet einerseits, dass man Daten aus POJOs, einer Datenbank, von REST Webservices, usw. verwenden kann. Andererseits kann man daraus Formulare und Listenansichten f√ľr Frontends wie Swing, Android, HTML & JavaScript, Vaadin, JSF, usw. generieren lassen.

Ein oft auftretender Use-Case ist die Suche. Statt selbst Indexe zu erstellen und zu updaten, sollte man dies eine Bibliothek machen lassen, die darauf spezialisiert ist. Lucene ist eine solche Bibliothek und bringt alle notwendigen Werkzeuge mit: Analyser, Index-Writer und Querys. Lucene ist zudem die Basis f√ľr Solr, einer Bibliothek, die die Anwendung abermals abstrahiert und vereinfacht. Beispielsweise k√ľmmert sich Solr um Cache, Replikation und die Bereitstellung eines REST-Webservices, den man in Webanwendungen prima gebrauchen kann.

Relationale Datenbanken sind prima, sind aber nicht immer die ideale Weise um Daten zu persistieren. Konkurrenz kommt dank dem Hype-Wort “NoSQL” von allen Seiten – und das zu Recht! Eine dieser Alternativen stellen Graphendatenbanken dar, dessen prominentester Vertreter Neo4j ist. Graphendatenbanken sind der Schl√ľssel f√ľr eine hochgradig vernetzte (hoch-dimensionale) Datenlandschaft. Durch die Vernetzung der Daten untereinander ist es m√∂glich, dass semantische Informationen nicht verloren gehen. Damit lassen sich komplexere Abfragen formulieren, die bereits nahe am menschlichen Denken sind, wie beispielsweise: “gib mir alle Personen einer Organisation, deren Freunde Freunde haben, die bei Google arbeiten”. Eine solche Suchanfrage l√§sst sich √ľber ein Navigieren von Knoten zu Knoten √ľber eine oder mehrere benamte Relation(en) bewerkstelligen.

Jackson dient zum Serialisieren und Deserialisieren von Daten im JSON- und XML-Format. Diese Bibliothek ist sehr einfach zu verwenden und erfreut sich einer Integration in viele Web-Frameworks.

Man kennt Templates bereits von Serienbriefen, doch auch im Web sind Templates gefragt. Ob als Template f√ľr eine Webseitenansicht oder als Vorlage f√ľr eine E-Mail-Kampagne, Freemarker liefert daf√ľr eine soliden Funktionsumfang.

Wer Debugging so liebt wie ich, der freut sich √ľber slf4j. Denn slf4j abstrahiert das Logging-Framework und l√∂st damit das Problem, dass in einer Anwendung mehrere Logging-Frameworks gleichzeitig zum Einsatz kommen, da die Bibliotheken unterschiedliche Logging-Frameworks einsetzen.

Wer mit Java programmiert, sollte die Apache Commons Projekte kennen. Darunter befinden sich einige Perlen, die dem Java-Programmierer das Leben deutlich erleichtern. Beispielsweise wird der Umgang mit Collections durch Apache Commons Collections vereinfacht. Aber auch das Apache Commons VFS ist sehr interessant, wenn es um den Zugriff auf Dateien geht. Denn √ľber ein virtuelles Dateisystem kann beispielsweise auf den Inhalt von ZIP-Dateien oder FTP-Ordnern zugegriffen werden, als ob es lokale Dateien w√§ren. Ein Blick auf die Commons-Projekte ist daher jedem dringend angeraten.

Schließlich sollte man einen Blick auf Reflections werden. Diese Bibliothek abstrahiert die von Java mitgelieferte Reflection-Funktionalitäten und vereinfacht damit deutlich die Suche nach Klassen, Methoden oder Feldern nach Typ, Interface, Annotationen etc.

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…

Graphendatenbanken: Neo4j, Spring und Spring Data Neo4j

Im ersten Artikel √ľber Graphendatenbanken ging es um die Motivation und einige grundlegende Konzepte. Dieser Artikel soll etwas konkreter werden: Es wird die Graphendatenbank Neo4j vorgestellt und Spring Data Neo4j genutzt, um ein auf Graphen basiertes Schema zu entwickeln.

Sowohl Neo4j als auch Spring Data Neo4j sind √ľber Maven Central verf√ľgbar. Daher ist die Einbindung in einem Maven-Projekt ein leichtes:



org.springframework.data
spring-data-neo4j
${version.spring.data.neo4j}


org.springframework.data
spring-data-neo4j-tx
${version.spring.data.neo4j}


org.neo4j
neo4j
${version.neo4j}


org.neo4j
neo4j-kernel
${version.neo4j}


org.neo4j
neo4j-cypher
${version.neo4j}

Nun folgt die Modellierung von Dom√§nenklassen. Wir greifen das Beispiel aus dem ersten Artikel auf und erzeugen Dom√§nenklassen f√ľr Personen, Autoren und Artikel. Dabei nutzen wir konsequent die Vererbungshierarchie und erzeugen zun√§chst eine generische Basis f√ľr Knotentypen. Diese abstrakte Domainenklasse beinhaltet als wichtigstes Attribut die Node-ID, welche von Spring-Data-Neo4j ben√∂tigt und mit der Annotation @GraphId versehen wird. Zus√§tzlich f√ľhren wir mit einer UUID einen zweiten, redundanten Identifier ein, der eine gewisse Unabh√§ngigkeit der Daten von der konkret eingesetzten Datenbank gew√§hrleistet. Beispielsweise k√∂nnen so Datenbest√§nde gemischt werden oder schlicht auf eine andere Persistenz umgezogen werden. Mit der Annotation @Indexed sorgen wir daf√ľr, dass Spring-Data-Neo4j einen Lucene-Index erstellt. Mit dem unique forcieren wir, dass das der Identifier einzigartig ist. Schlie√ülich hat sich bew√§hrt, dass jeder Knoten √ľber Timestamps verf√ľgen, wann der Knoten erzeugt und zuletzt ver√§ndert wurde.

@NodeEntity
public abstract class Node {

@GraphId
private Long nodeId;

@Indexed(unique = true)
@NotNull
private String uuid;

@NotNull
private Long created;

@NotNull
private Long lastModified;

// Getter and setters ommitted
}

Nun erstellen wir eine Dom√§nenklasse f√ľr Personen. Au√üerdem annotieren wir die Klasse mit @NodeEntity, um Spring-Data-Neo4j mitzuteilen, dass es sich um einen Knotentyp handelt. Die beiden Attribute Vorname und Nachname werden mit @Indexed annotiert, damit wir nach diesen Attributen suchen k√∂nnen. In diesem Beispiel beschr√§nken wir uns auf die Attribute Vor- und Nachname, obwohl man in der Praxis noch einige Informationen mehr hinzuf√ľgen w√ľrde. Allerdings ist beim Hinzuf√ľgen von neuen Attributen immer zu beachten, ob es sich nicht eigentlich um einen weiteren Knotentyp handelt, der mit einer Relation verbunden wird. Beispielsweise w√ľrde man abh√§ngig vom konkreten Anwendungsfall eine Adresse nicht als Attribute, sondern als eigenen Knotentyp definieren, da so N:M-Relationen abgebildet und eine feinere Semantik erreicht werden kann. Eine Person kann beispielsweise bei mehreren Adressen wohnen und eine Adresse kann von mehreren Personen bewohnt werden. Um eine feinere Semantik zu erreichen w√ľrden man beide Knotentypen mit mehreren Kantentypen verbinden, beispielsweise: Person “wohnt bei” Adresse oder Person “ist Hausmeister von” Adresse.

@NodeEntity
public class Person extends Node {

@Size(min = 2, max = 80)
@Indexed
private String firstName;

@Size(min = 2, max = 80)
@Indexed
private String lastName;

// Getter and setters ommitted
}

Die Spezialisierung einer Person ist ein Autor. Es reicht aus eine leere Klasse erzeugen, um einen Autor von einer Person zu unterscheiden.

@NodeEntity
public class Author extends Person {
}

Und schlie√ülich ben√∂tigen wir die Dom√§nenklasse f√ľr Artikel.

@NodeEntity
public class Article extends Node {

@Size(min = 10, max = 80)
private String title;

@Size(min = 40, max = 240)
private String summary;

@Size(min = 500)
private String text;

// Getter and setters ommitted
}

Nun sind wir soweit, dass wir die Knotentypen miteinander in Beziehung stellen können. Auch bei den Relationen ist eine Vererbungshierarchie möglich. Wie schon bei der Definition von Knotentypen erspart uns dies etwas Tipparbeit und erlaubt später das Arbeiten mit den Super-Klassen, ohne den genauen Typ der Relation zu kennen.

public abstract class AbstractRelationship {

@GraphId
private Long relationshipId;

// Getter and setters ommitted
}

Nun erstellen wir eine Klasse, die die Beziehung “hat gelesen” zwischen einer Person und einem Artikel beschreibt. Dabei definieren wir in einem statischen String den Namen der Relation. Um Komplikationen zu vermeiden, sollte der Name eindeutig sein. Mit der Annotation @RelationshipEntity teilen wir Spring-Data-Neo4j mit, dass es sich um eine Kantentyp, d.h. eine Relation handelt. Eine Relation hat immer einen Elternknoten (oder Startknoten), der mit @StartNode annotiert wird, und ein Kindknoten (oder Endknoten), der mit @EndNode annotiert wird. In der Welt der Graphen spricht man von einem gerichteten Graphen. Visualisieren k√∂nnte man dies, indem man zwischen zwei Knoten eine Pfeil in Richtung des Kindes zieht. Zus√§tzlich k√∂nnen wir auch in den Relationen Attribute speichern. In diesem Beispiel wollen wir den Zeitpunkt speichern, wann eine Person einen Artikel gelesen hat. Es zeigt sich, dass dies zu einer nat√ľrlicheren Form der Datenmodellierung f√ľhrt, denn die Information wird genau dort gespeichert, wo sie hingeh√∂rt – in der Relation selbst. Einfach, verst√§ndlich und effektiv.

@RelationshipEntity(type = HasRead.NAME)
public class HasRead extends AbstractRelationship {

public static final String NAME = "HAS_READ";

@StartNode
private Person person;

@EndNode
private Article article;

private Long when;

// Getter and setters ommitted
}

Nun beschreiben wir eine weitere Beziehung, und zwar dass ein Autor einen Artikel geschrieben hat. Neben dem Klassennamen unterscheidet sich auch der Name der Relation und der Typ des Startknotens.

@RelationshipEntity(type = HasWritten.NAME)
public class HasWritten extends AbstractRelationship {

public static final String NAME = "HAS_WRITTEN";

@StartNode
private Author author;

@EndNode
private Article article;

private Long when;

// Getter and setters ommitted
}

Da wir nun √ľber Dom√§nen- und Relationenklassen verf√ľgen stellt sich die Frage, wie wir auf die Daten zugreifen k√∂nnen. Dazu bedient sich Spring Data Neo4j dem Data-Access-Object-Pattern (DAO-Pattern) und abstrahiert es soweit, dass wir kaum noch etwas zu programmieren haben. In der Tat sieht es etwas nach “Magic” aus, denn wir implementieren nichts, sondern definieren nur noch einige Interfaces. Im n√§chsten Code-Beispiel ist eine solches DAO-Interface zu sehen. Zun√§chst wird das Interface mit der Annotation @Repository annotiert. Dies sorgt daf√ľr, dass Spring Data Neo4j dieses Interface automatisch als DAO-Interface im Spring-Context erkennen kann. Mehr dazu sp√§ter, wenn wir unsere Anwendung in Spring integrieren. Zus√§tzlich nutzen wir einen Transaktionskontext indem wir das Interface mit @Neo4jTransactional annotieren. Das Interface erbt Methoden von den √ľbergeordneten Interaces GraphRepository, RelationshipOperationsRepository, CRUDRepository und NamedIndexRepository. Dies sind Methoden um Knoten zu suchen, zu erzeugen und Verkn√ľpfungen zu erstellen. Zus√§tzlich definieren wir Methoden wie findByUuid, um Knoten vom Typ Person mit der angegebenen UUID zu suchen. Spring Data Neo4j k√ľmmert sich darum, zur Laufzeit eine Implementierung f√ľr diese Methodendefinition bereitzustellen. Somit entf√§llt f√ľr uns die Implementierung fast vollst√§ndig und DAOs werden haupts√§chlich deklarativ beschrieben.

@Repository
@Neo4jTransactional
public interface PersonRepository extends GraphRepository, RelationshipOperationsRepository, CRUDRepository, NamedIndexRepository {

Person findByUuid(String uuid);

Person findByFirstName(String firstName);

Person findByLastName(String lastName);

}

Spring Data Neo4j abstrahiert f√ľr uns eine Menge Arbeit, die wir sonst von Hand erledigen m√ľssten. Dabei l√§sst es aber uns die Freiheit, es selbst tun zu k√∂nnen, wenn es notwendig sein sollte. Aber Spring Data Neo4j unterst√ľtzt uns auch bei komplexeren Aufgaben. So ist es beispielsweise m√∂glich, eine Anfrage √§hnlich wie SQL zu schreiben. Dies erfolgt beispielsweise mit der Abfragesprache Cypher, die wie SQL relativ einfach zu verstehen ist. Im ersten Artikel interessierte uns die Frage, von wievielen Autoren ein Artikel geschrieben wurde. Dies l√§sst sich mit Cypher so ausdr√ľcken:

START article=node(123) MATCH (author)-[rel:HAS_WRITTEN]->(article) RETURN COUNT(rel)

Zur Erkl√§rung: Im START-Teil der Abfrage wird definiert, wo wir beginnen sollen zu suchen. Wir wissen die ID eines Artikels (123) und starten an diesem Knoten im Graphen. Auf diesen Knoten k√∂nnen wir mit “article” referenzieren. Im MATCH-Teil beschreiben wir nun, dass es Autoren gibt, die den Artikel geschrieben haben. Dabei ist “article” ein einzelner Knoten (wie zuvor definiert), aber “author” representiert alle Autoren, die mit einer Relation vom Typ “HAS_WRITTEN” verbunden sind. Auf die Autoren k√∂nnen wir mit “author” referenzieren und auch die Relation k√∂nnen wir referenzieren. Der RETURN-Teil gibt nun ein oder mehrere Ausgaben zur√ľck. Das kann ein einzelner Knoten sein, eine Menge von Knoten, eine Relation, eine Menge von Relationen oder in unserem Fall ein Integer. Im RETURN-Teil z√§hlen wir lediglich die Relationen.

Spring Data Neo4j unterst√ľtzt uns nun, indem wir nicht direkt auf die Java-API von Neo4j zugreifen m√ľssen, sondern einfach das DAO-Interface erweitern. Dazu nutzen wir die Annotation @Query, in der wir den Cypher-Query-String definieren. Statt der festen ID wird nun ein Platzhalter {article} definiert. Die Methodensignatur muss f√ľr jeden Platzhalter einen Parameter liefern. Dies tun wir mit der Annotation @Param und dem Namen des Platzhalters “article”.

@Repository
@Neo4jTransactional
public interface AuthorRepository extends GraphRepository, RelationshipOperationsRepository, CRUDRepository, NamedIndexRepository {

// other methods ommited

@Query("START article=node({article}) MATCH (author)-[rel:HAS_WRITTEN]->(article) RETURN COUNT(rel)")
Integer getNumberOfAuthors(@Param("article") Article article);

}

Nun geht’s ans Eingemachte. Wir m√∂chten alles nutzen, was wir zuvor definiert haben. Daher m√ľssen wir Neo4j zun√§chst integrieren. Dazu

Wie nutzt man nun ein solches Repository? Zun√§chst m√ľssen wir daf√ľr sorgen, dass Spring Data Neo4j die Repositories findet und Instanzen bildet. Wir konfigurieren Spring mittels Java-Config, indem wir eine Klasse erstellen und sie mit @Configuration annotieren. In dieser Klasse definieren wir eine Methode, die eine Instanz einer Embedded Neo4j Graph Database erzeugt und als Bean zur verf√ľgung stellt. Weiterhin binden wir Spring Data Neo4j ein, indem wir die Klasse mit der Annotation @EnableNeo4jRepositories versehen und den Package-Path angeben, indem die DAOs zu finden sind. Schlie√ülich lassen wir Spring nach Services suchen (@ComponentScan).

@Configuration
@EnableNeo4jRepositories(basePackages = { "de.schaeffernet.repository" })
@ComponentScan(basePackages = { "de.schaeffernet.services" })
public class Neo4JConfig extends Neo4jConfiguration {

@Bean(name = "graphDatabaseService", destroyMethod = "shutdown")
public GraphDatabaseService getEmbeddedGraphDatabase() {
return new GraphDatabaseFactory().newEmbeddedDatabaseBuilder("/tmp/neo4j").setConfig(ShellSettings.remote_shell_enabled, Settings.TRUE).newGraphDatabase();
}

}

Einen solchen Service m√∂chte ich noch vorstellen, um zu zeigen, wie man mit den DAOs umgeht. Zun√§chst injizieren wir die DAOs mittels @Autowired. In der Methode printArticleOverview lassen wir uns vom Artikel DAO alle Artikel zur√ľck liefern und iterieren √ľber diese. F√ľr jeden Artikel fragen wir die Anzahl der Autoren ab und geben eine Zeile im Log aus. Normalerweise sollte man Aufrufe wie findAll() vermeiden, wenn es geht, da man, je nach Datenbestand, sehr viele Daten in den Arbeitsspeicher l√§dt. Dies soll jedoch nur ein einfaches Beispiel sein. Weiterhin ist zu beachten, dass wir in den Service-Klassen die Komplexit√§t deutlich verringert haben, da die Cypher-Abfrage im DAO steckt. Dies ist sicherlich kein zu untersch√§tzender Vorteil. Oftmals kann so ein deutlich einfacherer Quellcode geschaffen werden.

@Service
public class AuthorService {

@Autowired
private AuthorRepository authorRepository;

@Autowired
private ArticleRepository articleRepository;

Logger logger; // Ommited

public final void printArticleOverview() {
EndResult

result = articleRepository.findAll();
for (Article article : result) {
logger.debug(String.format("Article %s was written by %d authors.", article.getTitle(), authorRepository.getNumberOfAuthors(article)));
}
}

}

Fazit

Im ersten Artikel wurden die theoretischen Grundlagen geschaffen, die in diesem zweiten Artikel durch praxistaugliche Beispiele unterf√ľttert wurden. Es wurde gezeigt, wie ein Graphen-Schema mit Knoten- und Kantentypen deklarativ modelliert wird und wie mit “Data-Access-Interfaces” eine Persistenzschicht deklariert wird. Zudem wurde die Abfragesprache Cypher angerissen, die die Formulierung von einfachen und komplexeren Fragestellungen im Graphen erm√∂glicht. Schlie√ülich wurde Neo4j und Spring Data Neo4j in Spring integriert und ein einfaches Beispiel anhand einer Service-Klasse vorgef√ľhrt.

Graphendatenbanken: Der neue Geheimtipp

Seit Jahrzehnten haben sich relationale Datenbanken in allen gesch√§ftsrelevanten Unternehmensanwendungen bew√§hrt. Sowohl kommerzielle als auch Open-Source Datenbanken wie beispielsweise PostgreSQL erf√ľllen in 999 von 1000 F√§llen alle Anforderungen. Doch sp√§testens seit dem NoSQL-Hype gibt es keinen Automatismus bei der Persistenzwahl mehr. Es wird nachgedacht, welche Persistenztechnologie am Besten passt.

Dieser Artikel ist kein Vergleich mit relationalen Datenbanken oder anderen Persistenztechnologien, die man unter NoSQL zusammenfasst, soll aber Appetit auf Graphendatenbanken machen. Ich werde in diesem Artikel anders vorgehen als andere Einleitungen zum Thema und beginne nicht mit den mathematischen Grundlagen von Graphen und werde weitere Aspekte von Graphendatenbanken erst im Laufe des Artikels einf√ľhren, sobald es didaktisch sinnvoll ist. Wer also schon Kenntnisse hat, wird beim Lesen eventuell unruhig auf dem Stuhl wackeln.

Doch warum sollte man alles erlernte √ľber den Haufen werfen und sich dem Wagnis aussetzen (und diesen Artikel lesen)?

Wissen ist Macht

Relationale Datenbanken bestehen stark vereinfacht aus zweidimensionalen Tabellen und Relationen. Diese Form der Speicherung eignet sich bestens f√ľr tabellarische Informationen. Jedoch sind die Relationen stumpfe Verkn√ľpfungen ohne jede Aussagekraft. Die Informationen sind zwar in der Datenbanken vorhanden, aber nur durch die in der Anwendung implementierten Gesch√§ftsprozesse bekommen sie eine Bedeutung. Bei Graphendatenbanken ist dies anders. In einer Graphendatenbank ist es m√∂glich Informationen semantisch abzulegen, d.h. sowohl die Informationen als auch ihre Bedeutung werden in der Graphendatenbank gespeichert.

Im Wesentlichen besitzt man ein Schema, das allen Knoten und Kanten typisiert. Beispielsweise ist ein m√∂glicher Knotentyp “Person” vorhanden. Durch Vererbung kann man den Knotentyp “Person” spezialisieren, z.B. “Autor”. Ein Autor hat dieselben Eigenschaften wie eine Person und hat dar√ľber hinaus zus√§tzliche Eigenschaften. Zu einem Graphen wird es, indem zwischen den konkreten Knoten Verkn√ľpfungen gebildet werden. Auch dies wird im Schema modelliert. Beispielsweise besteht zwischen dem Knotentyp “Person” und dem Knotentyp “Artikel” die Beziehung, d.h. den Kantentyp “hat gelesen”. Auch Attribute f√ľr Beziehungen sind in einem Property-Graphen m√∂glich. So hat die Beziehung “hat gelesen” das Attribut “gelesen am”. Somit w√ľrde man in einem Content-Management-System auf einfachste Weise abbilden k√∂nnen, ob und wann ein Benutzer einen Artikel gelesen hat indem einfach zwischen beiden Knoten eine Verkn√ľpfung erstellt wird. Ein weiteres Beispiel w√§re ein Kantentyp “hat geschrieben” zwischen den Knotentypen “Autor” und “Artikel”. Da es sich um einen gerichteten Graphen handelt, k√∂nnen wir auch die Richtung der Beziehung bestimmen, d.h. vom Autor zum Artikel und nicht umgekehrt. Zus√§tzlich stellen wir fest, dass die Vererbungshierarchie greift: Da ein Autor gleichzeitig eine Person ist, bestehen zwischen einem Knoten vom Typ “Autor” und vom Typ “Artikel” zwei m√∂gliche Beziehungen. Als Autor hat er m√∂glicherweise den Artikel geschrieben, als Person hat er m√∂glicherweise den Artikel gelesen. Das besondere daran ist, dass wir nicht erst den Quellcode einer Anwendung lesen m√ľssen, um den Sinn der Daten zu begreifen, wie es mit einem Heer von Tabellen, M:N-Tabellen, Prim√§r- und Fremdschl√ľsseln der Fall w√§re.

Doch das ist nicht nur sch√∂n sondern auch n√ľtzlich: Dadurch, dass wir wissen, was unsere Daten bedeuten, k√∂nnen wir in unseren Anwendungen entsprechende Abfragen stellen. Uns interessiert beispielsweise die Frage, von wievielen Autoren ein Artikel geschrieben wurde. Nichts einfacher als das: man z√§hlt alle Verkn√ľpfungen vom Kantentyp “hat geschrieben” die zum Knoten des besagten Artikel f√ľhren. Noch interessanter erscheint jedoch die Frage, welche Autoren f√ľr einen bestimmte Person interessant sind. Sp√§testens an dieser Stelle geraten relationale Datenbanken ins Hintertreffen. Mit einer Graphendatenbank m√ľssen wir jedoch nur den Graphen betrachten: Die betreffende Person hat mehrere Artikel gelesen und diese Artikel wurden von Autoren geschrieben. Wir “navigieren” nun durch den Graphen und “z√§hlen”. Derjenige Autor ist am meisten interessant, der die meisten Artikel geschrieben hat, die die betreffende Person bereits gelesen hat. Andere Autoren haben vielleicht mehr Artikel geschrieben, aber diese wurden von der betreffenden Person nicht gelesen, und daher sind diese Autoren nicht so interessant. Nun fehlt noch die Frage, welche Artikel man empfehlen k√∂nnte. Wir wissen, welche Artikel eine Person gelesen hat. Diese scheiden also aus. Des weiteren wissen wir, welche Autoren interessant sind. Diese beiden Erkenntnisse verkn√ľpfen wir nun, und erhalten ein Ergebnis: Alle von der betroffenen Person noch nicht gelesenen Artikel des interessantesten Autors. Durch Erweiterung des Schemas k√∂nnte man das Ergebnis weiter verfeinern. Beispielsweise k√∂nnen Personen Artikel “liken” oder bewerten, ein Artikel kann ein Thema “behandeln” und eine Person kann an einem Thema “interessiert” sein.

Trotz dessen, dass wir ein Schema haben, das nur aus drei Knotentypen und zwei Kantentypen besteht, k√∂nnen wir bereits einige Schl√ľsse ziehen. Und genau dies ist der Grund, warum Graphendatenbanken anderen Persistenztechnologien √ľberlegen sind. Das Schema wird niemals so kompliziert werden, wie ein Schema in einer relationalen Datenbank, in der beispielsweise Tabellen nur existieren, um M:N-Relationen abzubilden. Das Schema und m√∂gliche Fragestellungen lassen sich wunderbar auf Papier skizzieren. Auch auch der Graph selbst l√§sst sich visualisieren.

Visualisierung

Ein weiterer Vorteil eines Graphen ist es, in visualisieren zu k√∂nnen. √úblicherweise zeichnet man Knoten als Kreise oder K√§stchen, die durch Linien oder Kurven verbunden sind, die die Kanten darstellen. Durch das Betrachten des Graphen kann man intuitiv erkennen, welche Knoten, bezogen auf einen bestimmten Aspekt, wichtiger sind als andere. W√ľrden wir unser Beispiel von oben visualisieren, w√ľrden wir sofort erkennen, welche Autoren viele Artikel geschrieben haben, welche Personen viele Artikel gelesen haben. Durch entsprechende Zeichenalgorithmen ist es sogar m√∂glich, dass mit Kanten verbundene Knoten wie Gewichte aneinander ziehen. Das Ergebnis ist, dass zwei Knoten, die viel miteinander zu tun haben, n√§her beieinander sind, als Knoten, die weniger miteinander zu tun haben. Da mit wachsendem Datenbestand die Anzahl von Knoten und Kanten un√ľberschaubar werden kann, wird man sicherlich eine Auswahl treffen, welche Knotentypen und Kantentypen f√ľr eine bestimmte Fragestellung √ľberhaupt relevant sind.

Die Navigation im Graphen

Der Unterschied zu Big-Table, Key-Value-Stores und relationale Datenbanken ist, dass man innerhalb eines Graphen navigieren kann. Dadurch lassen sich einfache und sogar komplexere Fragestellungen beantworten, wie oben gezeigt. Noch nicht angesprochen ist die Tatsache, dass das Navigieren im Graphen weniger Zeit beansprucht als die Abfrage von Tabellendaten, wie es beispielsweise mittels SQL gemacht wird. Doch dazu muss man sein “Denken” vom Modus “ich denke in Tabellen” auf “ich denke in Graphen” umstellen. Das bedeutet, dass man auch das Schema anders erstellt, als man es bei relationalen Datenbanken tun w√ľrde. Wie bei relationalen Datenbanken k√∂nnte man einem Artikel ein Attribut f√ľr das Erstellungsdatum zuweisen. Will man nun alle Artikel eines Jahres haben, m√ľsste man in allen Knoten, die vom Knotentyp “Artikel” sind, das Datum √ľberpr√ľfen. Da man dabei jedoch alle Knoten betrachten muss, wird viel Zeit ben√∂tigt. Zwar ist es m√∂glich, die Abfragezeiten mittels eines Index deutlich zu senken, trotzdem ist es nicht die effektivste Methode, um die gew√ľnschten Artikel zu erhalten. Stattdessen liegt die L√∂sung im Schema: Die Knotentypen “Jahr”, “Monat” und “Tag” erlauben es einen Knoten “Jahr 2013” f√ľr das Jahr 2013 oder einen Knoten “05. Dezember 2013” f√ľr den heutigen Tag zu erstellen. Diese Knoten werden durch die Kantentypen “hat Monat” und “hat Tag” verkn√ľpft. Zus√§tzlich wird der Kantentyp “wurde erstellt am” genutzt um auszusagen, dass ein Artikel an einem bestimmten Tag erstellt wurde. Um nun alle Artikel aus dem Jahr 2013 zu finden, muss man beim Jahresknoten 2013 beginnen, alle Monate und deren Tage um schlie√ülich alle Artikel einzusammeln. Das Verfahren l√§sst sich ohne √Ąnderung auch auf Monate oder Tage anwenden. Vorteil dieses Verfahrens ist, dass es schnell ist. Die Navigation von einem Knoten zu einem anderen Knoten liegt im Nanosekundenbereich. Zus√§tzlich erspart man sich Vergleichsoperatoren und Indexlookups. Stattdessen werden nur Knoten “eingesammelt”. Voraussetzung ist lediglich, dass man von einem Knoten aus starten kann, in unserem Beispiel war das der Knoten “Jahr 2013”.

Fazit

Graphen sind n√ľtzlich, wenn die Informationen miteinander vernetzt sind. Graphendatenbanken liefern die Umgebung, die n√∂tig ist, um Graphen performant zu nutzen. In diesem Artikel sollte vermittelt werden, wann sich der Einsatz von Graphendatenbanken lohnt. Im n√§chsten Teil werde ich euch mit der Praxis konfrontieren: Das in diesem Artikel genutzte Beispiel wird mit Neo4j, Spring und Spring Data Neo4j umgesetzt.

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.

Neue PPC Amiga Hardware

Neue Hardware f√ľr den Amiga: Acube k√ľndigt f√ľr Ende September einen neuen Amiga Rechner mit einer PPC460ex (1,15 GHz) auf einem SAM460ex Motherboard an. Als Betriebssystem ist AmigaOS 4.1 Update 3 vorinstalliert. Kosten des Systems: etwa 1000 Euro.

Page 1 of 212»