Projekt PaRSIWal

PaRSIWal

Paderborn Realtime System for Interactive Walkthrough

Virtuelle Szenen finden sich heute in Anwendungsgebieten der industriellen Entwicklung, Städteplanung und im Bildungsbereich. Besucher können mit einem so genanntem Walkthrough-System virtuelle Szenen durchwandern und manipulieren. Ein zentrales Problem solcher Systeme sind die zunehmenden Anforderungen an die Größe einer virtuellen Szene. Eine zufrieden stellende Visualisierung so großer Szenen ist nur durch den Einsatz entsprechend geschickter Methoden möglich. Diese werden im PaRSIWal-Projekt entwickelt und in einem prototypischen System implementiert und erprobt.

Virtuelle Szenen und Walkthrough-Systeme

Virtuelle Szenen finden heute vielfältige Anwendungen in der industriellen Entwicklung und Produktion, Architektur, Ausbildung und bei der Visualisierung komplexer Daten. Ziel dieser Systeme ist die Visualisierung von 3D-Szenen (z.B. Häuser, Städte, Autos, Landschaften). Zur Darstellung bedient man sich so genannter Walkthrough-Systeme, die einem Betrachter erlauben Objekte wie Häuser, Autos und Fabriken, anzuschauen. Da die Standorte des Besuchers beliebig sein können, spricht man auch von einem "virtuellen Flug" durch die Szene. Man kann z.B. auch aus Positionen auf die Szene schauen, die man in der realen Welt nicht einnehmen kann.

Abb. 1: Systemarchitektur

Problembeschreibung

Virtuelle Szenen bestehen aus Objekten, die im Computer durch polygonale Flächen beschrieben werden. Um in eine virtuelle Welt zu schauen, berechnet der Computer aus diesen Flächen ein Bild, das auf dem Bildschirm zu sehen ist. In einem Walkthrough-System hat der Besucher mit Hilfe eines Eingabegerätes, wie z.B. Maus, die Möglichkeit, seinen Standpunkt zu verändern. Für einen neuen Standpunkt berechnet der Computer ein neues Bild. Für einen flüssigen Ablauf von Bildern und eine gute Navigation muss bei einem Positionswechsel des Besuchers das neue Bild möglichst schnell berechnet werden. Für große Szenen reicht trotz spezieller Grafik-Hardware die Rechenleistung nicht aus, um genügend schnell Bilder hintereinander zu berechnen. Man ist darum auf intelligente Verfahren angewiesen, die eine sehr große Szene mit entsprechenden Methoden so aufbereiten, dass sie vom Computer schnell genug berechnet werden kann.

Projektbeschreibung

Inhalt des Projektes ist die Entwicklung, Implementierung und Evaluierung eines Walkthrough-Systems zur Visualisierung sehr großer Szenen. Die Szenen haben eine Größe, die ohne Anwendung spezieller Methoden in Realzeit nicht mehr visualisiert werden könnten. Die Szenen werden auf einem speziellen Szenenserver, dem Manager, gespeichert (s. Abb. 1). Die Visualisierung bzw. der Besuch der Szene durch einen Besucher erfolgt auf einer speziellen Grafikmaschine, der Rendering-Maschine. Je nach Standort des Besuchers in der Szene schickt der Manager den für den Besucher notwendigen Teil der Szene zu dem Besucher. Neben einem Besucher kann auch ein Modellierer in der Szene arbeiten, der neue Objekte einfügt oder entfernt und damit die Szenen nach seinen Vorstellungen gestalten kann. Wichtiger Bestandteil eines Walkthrough-Systems und des Projektes sind dabei die Verwendung von Methoden, die eine beliebige Skalierbarkeit des Systems zulassen, d.h. für vergrößerte Szenen können die Aufgaben auf mehreren Rechnern (Managern) verteilt werden. Dies ist beispielsweise notwendig, wenn die Szenengröße oder die Anzahl der Besucher (Rendering-Maschinen) steigt. Zur Lösung der Aufgaben werden unter anderem Ergebnisse aus der algorithmischen Geometrie verwendet.


Abb. 4: Virtuelle Szene

Abb. 2: Spannerkonstruktion	Abb. 3: Spanner-Graph

Objekte der Szene sind bei uns beispielsweise Häuser, Bäume, Straßenstücke, Autos etc. (s. Abb. 4). Diese Objekte werden mit Hilfe eines geometrischen Graphen abstrahiert und modelliert. Jedem Knoten in diesem Graphen entspricht ein Knoten im Graphen. Als Graph wird eine so genannte Weak-Spanner Konstruktion verwendet (s. Abb. 2). Der Weak-Spanner übernimmt damit die Funktion eines Netzwerkes, das zur Navigation durch die Szene verwendet wird (s. Abb.: 3).

Neben den Fragestellungen zur Verteilung einer Szene in Netzwerken, sind Probleme im Bereich der Approximation und Reduzierung nicht sichtbarer Objekte (Culling) zu lösen. Hier werden verschiedene Ansätze verfolgt und untersucht.

Weitergehende Informationen sind bei der Arbeitsgruppe bzw. auf der Projektseite http://www.uni-paderborn.de/parsiwal zu erhalten.

Wir kooperieren in unserem Projekt mit der Fachgruppe Rechnerintegrierte Produktion des Heinz Nixdorf Instituts. Dort werden mehrere Projekte im Bereich Virtual Reality durchgeführt.

Im Projekt Cyberbikes beispielsweise soll eine modellhaft im Rechner nachgebildete Fahrradfabrik dazu beitragen, ein besseres Verständnis für die Abläufe in einem industriellen Produktionsunternehmen zu ermöglichen. Einsatzmöglichkeiten und Nutzenpotential der Informationstechnologie können damit aufgezeigt werden.

Zur Evaluierung unserer Algorithmen und Datenstrukturen haben wir ein prototypisches Walkthrough-System entwickelt. Die Schlüsseleigenschaft ist die unabhängige Bewegung innerhalb einem lokalen Teil der Szene. Unabhängig heißt hier, daß alle Daten und Szenenteile, die der Besucher benötigt, nur von den sich in der unmittelbaren Umgebung des Besuchers befindlichen Objekten und Datenstrukturen abhängen. Eine solche Umgebung haben wir `Bubble' genannt. Zur Pufferung des langsamen Zugriffs auf Festplatte und Netzwerk werden diese Bubbles auf den Managern, die die Szene verwalten, größer. Damit ist es auch möglich, daß ein großes Bubble mehrere kleine enthält. Dieses könnten zum Beispiel mehrere Besucher sein, die sich zwar nicht mehr sehen, aber gleichzeitig in ihrer näheren Umgebung aufhalten.

Die Objekte und Datenstrukturen werden damit auf verschiedenen Speichermedien gespeichert (Festplatte, Hauptspeicher) und transportiert (Netzwerk). Damit ist durch die gestellten Anforderungen die Entwicklung einer Schnittstelle sinnvoll, die zwischen den Algorithmen und Datenstrukturen abstrahiert. Ein solche Schnittstelle haben wir entwickelt und die erforderlichen Funktionalitäten in Form einer Library implementiert. Auf diese Art und Weise erfolgte gleichzeitig eine Trennung zwischen dem verwendeten Grafikstandard zum Rendern der Objekte, den Formaten zur Speicherung der Objekte und den Datenstrukturen, die die Objekte verwalten und eine Navigation erlauben.

Publikationen

Jan Klein, Jens Krokowski, Matthias Fischer, Michael Wand, Rolf Wanka, Friedhelm Meyer auf der Heide
The Randomized Sample Tree: A Data Structure for Interactive Walkthroughs in Externally Stored Virtual Environments
In Symposium on Virtual Reality Software and Technology (VRST '2002), pages 137 - 146, 2002.

Abstract und Paper

Bengt Mueck, Wilhelm Dangelmaier, Matthias Fischer, Wolfram Klemisch
Bi-directional Coupling of Simulation Tools with a Walkthrough-System
In Thomas Schulz, Stefan Schlechtweg, and Volkmar Hinz, editors, Simulation und Visualisierung, pages 71-84. SCS - Europe, February 2002.
Abstract und Paper

Jan Klein, Matthias Fischer
Occlusion Culling for Virtual Environments based on the 3D-Sectorgraph
In Informatiktage 2001, pages 275 - 278, Bad Schussenried, 2001.
Abstract und Paper
Michael Wand, Matthias Fischer, Ingmar Peter, Friedhelm Meyer auf der Heide, Wolfgang Straßer
The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes
In Computer Graphics (SIGGRAPH 01 Conference Proceedings), pages 361 - 370, 2001.
Abstract und Paper

Zur vorhergehenden Arbeit ist ein Technical Report erhältlich:

Michael Wand, Matthias Fischer, Friedhelm Meyer auf der Heide
Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes
Technical Report tr-ri-00-217, Universität Paderborn, 2000. also appeared as: Technical Report Tübingen University, WSI-2000-20, ISSN 0946-3852, 2000.
Abstract und Paper

Matthias Fischer, Tamás Lukovszki, Martin Ziegler
Partitioned Neighborhood Spanners of Minimal Outdegree
In Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), pages 47-50, 1999.
Abstract und Paper
Tamás Lukovszki
New Results on Fault Tolerant Geometric Spanners
In Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS'99), LNCS, pages 193-204. Springer Verlag, 1999.
Abstract und Paper
Christian Sohler
Fast Reconstruction of Delaunay Triangulations

In Proceedings of the 11th Canadian Conference on Computational Geometry ( CCCG'99), pages 136-141, 1999.
Abstract und Paper
Christian Sohler
Generating Random Star-Shaped Polygons
In Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG'99), pages 174-177, 1999.
Abstract und Paper
A. Czumaj and A. Lingas
On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem
In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 281-290, 17 - 19 January 1999.
Abstract und Paper
Matthias Fischer, Tamás Lukovszki, Martin Ziegler
A Network Based Approach for Realtime Walkthrough of Massive Models
In Proceedings of the 2nd Workshop on Algorithms Engineering (WAE'98), pages 133-142, 1998.
Abstract und Paper
Matthias Fischer, Tamás Lukovszki, Martin Ziegler
Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
In Proceedings of the 6th Annual European Symposium on Algorithms (ESA'98), LNCS, pages 163-174. Springer Verlag, 1998. (preliminary version as technical report tr-ri-98-199)
Abstract und Paper

A. Czumaj and A. Lingas
A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity
In Proceedings of the 25th International Colloquium on Automata, Languages, and Programming, volume 1113 of LNCS, pages 682-694. Springer-Verlag, 1998.
Abstract und Paper

Matthias Fischer, Friedhelm Meyer auf der Heide, Willy-B. Strothmann
Dynamic Data Structures for Realtime Management of Large Geometric Scenes
In 5th Annual European Symposium on Algorithms (ESA '97), volume 1284 of LNCS, pages 157 - 170. Springer Verlag, 1997.
Abstract und Paper
Artur Czumaj, Willy-B. Strothmann
Bounded Degree Spanning Trees
In Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97), volume 1284 of LNCS, pages 104-117. Springer Verlag, 1997.
Abstract und Paper

Matthias Fischer, Jochen Rethmann, Alf Wachsmann
A Realistic Cost Model for the Communication Time in Parallel Programs
In 3rd Workshop on Abstract Machine Models for Parallel and Distributed Computing (AMW '96), pages 13-27, 1996.
Abstract und Paper

Zur vorhergehenden Arbeit ist ein Technical Report erhältlich:

Matthias Fischer, Jochen Rethmann, Alf Wachsmann
A Realistic Cost Model for the Communication Time in Parallel Programs on Parallel Computers Using a Service Hardware
Technical Report tr-rsfb-96-007, Universität Paderborn, 1996.
Abstract und Paper
Tamás Lukovszki, Willy-B. Strothmann
Decremental Biconnectivity on Planar Graphs
Technical Report tr-ri-97-186, Paderborn University, Paderborn, 1997.
Abstract und Paper

Dissertationen

Tamás Lukovszki
New Results on Geometric Spanners and Their Applications
Universität Paderborn, Dissertation, 1999.
Referenz und Paper
Willy-B. Strothmann
Bounded Degree Spanning Trees
Universität Paderborn, Dissertation, 1997
Referenz und Paper

Preise

Matthias Fischer, Tamás Lukovszki, Martin Ziegler
Multimediale Entdeckungsreisen unserer Welt mit dem Internet
Gründerwettbewerb Multimedia des Bundesministerium für Wirtschaft und Technologie(BMWi), 1998. http://www.gruenderwettbewerb.de
Referenz

Universität Paderborn	http://www.uni-paderborn.de
Heinz Nixdorf Institut	http://hni.uni-paderborn.de
Arbeitsgruppe Prof. Dr. Meyer auf der Heide	http://www.uni-paderborn.de/cs/ag-madh

Deutsche Forschungsgemeinschaft	http://www.dfg.de
DFG-Schwerpunktprogramm	http://www.gmd.de/SCAI/dfg
Geförderte Projekte	http://www.gmd.de/SCAI/dfg/e-version/projects.html
Abschlusspräsentation des Schwerpunktprogramms	http://wwwipr.ira.uka.de/~spp2000/sppcd/index.htm

Postanschrift	Universität Paderborn D-33095 Paderborn
Hausanschrift	Universität Paderborn Fürstenallee 11 D-33102 Paderborn

Name	E-Mail	Telefon	Fax	Web-Page
Friedhelm Meyer auf der Heide	fmadh@upb.de	05251 606480	05251 606482	http://www.upb.de/cs/fmadh.html
Matthias Fischer	mafi@upb.de	05251 606490	05251 606482	http://www.upb.de/cs/mafi
Tamás Lukovszki	talu@upb.de	05251 606517	05251 606502	http://wwwhni.upb.de/~tamas
Christian Sohler	csohler@upb.de	05251 606427	05251 606482	http://www.upb.de/cs/csohler.html
Willy-B. Strothmann	willy@upb.de			http://www.uni-paderborn.de/cs/willy.html
Martin Ziegler	ziegler@upb.de	05251 606427	05251 606482	http://www.upb.de/cs/ziegler.html