HEINZ NIXDORF INSTITUT Theoretische Informatik: Algorithmen, Komplexitätstheorie, Parallelität...

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Reisen in virtuellen Welten:Architektur und Algorithmen für

volldynamischen Walkthrough in 3D-Szenen

Friedhelm Meyer auf der HeideHeinz Nixdorf Institut &

Fachbereich Mathematik/InformatikUniversität Paderborn

Arbeiten im Projekt „Hierarchische Realzeitalgorithmen“ im DFG-SPP„Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen“

gemeinsam mit Matthias Fischer, Tamas Lukovszki, Martin Ziegler

Die Vision

• Sie planen einen Kultur & Technik-Trip?

• Bereiten Sie sich virtuell vor: Navigieren Sie an Ihrem PC per Bahn von Berlin nach Paderborn, geniessen Sie die Aussicht!

Statten Sie der Karolinger-Ausstellung und dem Heinz Nixdorf MuseumsForum einen virtuellen Besuch ab!

Computermuseen im Vergleich? Fliegen Sie „virtuell“ nach Boston und vergleichen Sie!

Wie wär‘s mit Hongkong? ...

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

„Multimediale Entdeckungsreisen mit dem Internet“

Matthias FischerTamas Lukovszki

Martin Ziegler

Ideenbeschreibung + Geschäftsplan wurdebeim Gründerwettbewerb Multimedia 1998vom Bundesministerium für Wirtschaft und

Technologie (BMWi) ausgezeichnet.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Die Aufgabe

• Verwaltung riesiger virtueller Szenen, verteilt auf einem Netzwerk von Servern.

• Navigation durch die Szene ist von beliebigen an das Netzwerk angeschlossenen PCs aus möglich (hilfreich: gute 3D-Graphikkarte oder besser Graphik-Pipe).

• Es entsteht der Eindruck fließender Bewegung (möglichst kein „ruckeln“), trotz der Komplexität der Szene und der Übertragung über das Netzwerk.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Inhalt des Vortrags

• Einige Grundbegriffe.

• Beschreibung einer Architektur zur volldynamischen, verteilten Verwaltung riesiger virtueller Szenen.

• Spezifikation grundlegender algorithmischer Probleme.

• Einige algorithmische Ideen.

• Unser volldynamisches Walkthrough-System PaRSIWal (Paderborn Realtime System for Interactive Walkthrough).

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Grundbegriffe

Modellierung von 3D-Szenen.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

• Polygondarstellung

• Farbgebung

• Festlegung von Lichtquellen

Grundbegriffe

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

• Entfernen verdeckter Kanten

• Einfärbung, Beleuchtung

Rendering wird massiv durch Hardware unterstützt!

RenderingModell + Besucherposition- und Blickrichtung -> 2D-Bild.

• Projektion 3D -> 2D

Grundbegriffe

-> Realzeitanforderung: Bildaufbau darf höchstens 1/10 sec. dauern!-> Komplexitätsreduktion!!

WalkthroughNavigation in der Szene.

Volldynamischer Walkthrough Veränderung der Szene zur Laufzeit .

Anforderung Mindestens 10 Bilder pro Sekunde.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Statische Komplexitätsreduktion:• Approximationen• Level of Detail• Texturen• ........•Datenstrukturen für die ...

3D-Modell

Rendering-hardware

Besucherpositionund -blickrichtung

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der HeideState-of-the-Art Architektur

ReduziertesModell Komplexitätsreduktion zur Laufzeit:

• Auswahl wichtiger Objekte• Culling• Approximationen• .........

Manager 1 Manager 2 Manager 3

Kommunikationsnetzwerk

Manager halten je einen Teil der Gesamtszene auf Platte.B/M bekommen jeweils den Ausschnitt der Szene von den Managern, die in der nächsten Zeiteinheit (z.B. 1 Sekunde) für ihn relevant sind.

Unser ArchitekturvorschlagHEINZ NIXDORF INSTITUT

Theoretische Informatik:Algorithmen, Komplexitätstheorie, Parallelität

Friedhelm Meyer auf der Heide

Besucher/Modellierer

Besucher/Modellierer

Besucher/Modellierer

Unser Architekturvorschlag

(1 Manager, 1 B/M)

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Anforderungen an Algorithmen undDatenstrukturen

• Szene: n Objekte in „2 D“ -Raum

• Suchanfrage: Zu Position x berechne alle Objekte im Abstand höchstens t zu x.

• Aktualisierung: Einfügen/Löschen: Füge an Position x Objekt ein/lösche dort ein Objekt.

21

--> Dynamisches Circular Range Searching.

--> Zeit (log (n) [+ Output-Größe] ) pro Operation. --> nicht „realzeitfähig“, da Laufzeit mit Szenengröße wächst.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Nützliche Eigenschaften von Walkthrough

• Objekte haben „Ausdehnung“, z.B. umschreibende Kugel. Vereinfachung: Kugeln haben Durchmesser 1, überschneiden sich nicht.

• Besucher bewegt sich „langsam“, Höchstgeschwindigkeit b.

--> Hintereinander folgende Anfragepunkte liegen nahe beieinander.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der HeideDas dynamische Suchproblem

• Szene: n Objekte (Verallgemeinerung auf verschiedene Durchmesser möglich).

• Suche (x, t): Berechne alle Objekte im Abstand x von t.

• Update (y, x, t): Berechne alle Objekte in.

• Füge-ein (x, obj): Nachdem Update (y, x, t) ausgeführt wurde: Füge obj an Position x ein.

• Lösche (x, obj): ....

„Realzeitfähigkeit“: Update, Einfügen, Löschen darf nur Zeit „Output-Größe“ benötigen, darf nicht von n abhängen!

X Y

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der HeideSuchstrukturen: Ergebnisse

Fischer, MadH, Strothmann (ESA‘97)Randomisierte Datenstruktur mit geforderten Eigenschaften,Speicherplatz O (n); Grundstruktur: weak spanner + Steiner-Punkte.

Fischer, Lukovszki, Ziegler (ESA‘98)Deterministische Datenstruktur mit geforderten Eigenschaften,Reduktion des Speicherbedarfs.

Fischer, Lukovszki, Ziegler (CCCS‘99)Systematische Untersuchung von speichereffizienten Spannern undweak Spannern.

Lukovszki (WADS‘99)Fehlertolerante Datenstrukturen

Dissertation LukovszkiGesamtdarstellung dieser und weiterer Resultate

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der HeideEinige algorithmische Ideen: Weak Spanner

• Organisiere Szene als vollständigen Graphen auf n Objekten,• Nachbarliste ist für jeden Punkt x gemäß ihrer Abstände zu x sortiert.

• Suche (x, t) benötigt Zeit = Ausgabe-Größe, falls x Objekt ist.• Größe der Datenstruktur =n2 .

e3:4

e2:3

e4:5

e1:2

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

)29.253

Weak Spanner

Idee: Approximiere Graph durch dünnen Graphen

--> Konstanter Outgrad, Ergebnis von Suche (x, t) in f . t -Umgebung von x, (f: Stretch Faktor).

--> weak Spanner existieren bereits mit 4n Kanten (f =

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Der Sektorengraph

Ein weak Spanner mit Outgrad 6 und Stretch-Faktor 2.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der HeideDynamischer weak Spanner

Probleme:- Suche (x, t) wird nur für Objekte x unterstützt.- Einfügen / Löschen / Update sehr teuer.

Lösung:Füge Steiner- Punkte ein, d.h. zusätzliche Dummy-Objekte.--> kurze Kanten, kleiner Ingrad

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Randomisierte volldynamische Datenstruktur

Steiner-Punkte bilden Gitter,

Speicherreduktion durchperfektes Hashing(randomisiert)

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

Deterministische inkrementelle Datenstruktur

Steiner-Punkte mit Hilfe balanzierter Quad-Trees definieren.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

PaRSIWal: Status

Unser experimentelles Walkthrough-System

PaRSIWal Paderborn Realtime System for Interactive Walkthrough

Fischer, Lukovszki, Ziegler (WAE ‘98)Machbarkeitsstudie (Kommunikation und Belastung der B/M)

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

PaRSIWal: Status

• 1 Manager, viele Besucher/Modellierer, Verbindung TCP/IP (Ethernet <10 Mbit)

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

PaRSIWal: Status

•Benchmark: Szenegenerator Objekte:

– 100 ~ 300 Polygone,– etwa gleiche Ausdehnung, – keine Überlappung.

--> ca. 150 Objekte können bei 100% Last in 1/10 Sekunden gerendert werden, bei 80 % - 90% Last also etwa 130 Objekte (SGI O2).

•Machbarkeitsstudie:

Falls B/M 10 % der Leistung für Datenstruktur-Management •reserviert und sich wie „schneller Fußgänger“ bewegt, ist Kommunikationsvolumen ausreichend.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

PaRSIWal: Status

•Monitorfunktion (Manager):

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

PaRSIWal: Ausblick

in 99:

• Vergleich verschiedener Suchstrukturen: (Sektorengraphen, Quad-Trees, Hash Tables, Fair-Splits-Trees, 2D-Bäume, Range Trees, Epsilon-Netze).

• Manager: Kommunikation mit Platten.

• Approximationsverfahren für Hintergrund.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

PaRSIWal: Ausblick

nach 99:

• Approximationen (vorwiegend Hintergrundapproximation).

• Culling-Techniken (Algorithmenentwurf, Integration in PaRSIWal, Evaluation).

• Evaluieren als Internet-Anwendung.

• Szenenpartitionierung für I/O effizienten Zugriff und Verteilung auf verschiedene Manager.

HEINZ NIXDORF INSTITUTTheoretische Informatik:

Algorithmen, Komplexitätstheorie, ParallelitätFriedhelm Meyer auf der Heide

PaRSIWal