HEINZ NIXDORF INSTITUT Theoretische Informatik: Algorithmen, Komplexitätstheorie, Parallelität Friedhelm Meyer auf der Heide Reisen in virtuellen Welten:

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? ...



„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.



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.



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).



Grundbegriffe

Modellierung von 3D-Szenen.



• Polygondarstellung

• Farbgebung

• Festlegung von Lichtquellen

Grundbegriffe



• 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.



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

3D-Modell

Rendering-hardware

Besucherpositionund -blickrichtung


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



Unser Architekturvorschlag

(1 Manager, 1 B/M)





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.



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.


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


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


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



)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 =



Der Sektorengraph

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


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



Randomisierte volldynamische Datenstruktur

Steiner-Punkte bilden Gitter,

Speicherreduktion durchperfektes Hashing(randomisiert)



Deterministische inkrementelle Datenstruktur

Steiner-Punkte mit Hilfe balanzierter Quad-Trees definieren.



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)



PaRSIWal: Status

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



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.



PaRSIWal: Status

•Monitorfunktion (Manager):



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.



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.



PaRSIWal

Documents

HEINZ NIXDORF INSTITUT Theoretische Informatik: Algorithmen, Komplexitätstheorie, Parallelität Friedhelm Meyer auf der Heide Reisen in virtuellen Welten: