A new Subdivision Algorithm for the Intersection of Parametric Surfaces
(Bühler, June 2001) Bühler, Katja
Unterteilungsalgorithmen gehören zu den zuverlässigsten Algorithmen für den Schnitt zweier parametrischer Flächenpatches. Sie erfüllen vier der fünf Anforderungen an einen guten Schnittalgorithmus: Sie sind genau, zuverlässig, selbständig und auf alle Arten von parametrischen Flächen anwendbar - eine Kombination von Eigenschaften, die kaum ein anderer Schnittalgorithmus besitzt. Die hohe Laufzeit und ein großer Speicherverbrauch bei steigenden Anforderungen an die Genauigkeit der Ergebnisse, verhinderten allerdings weitgehend den praktischen Einsatz reiner Unterteilungsalgorithmen.\\ In dieser Arbeit werden mehrere Verbesserungen für Unterteilungsalgorithmen vorgeschlagen, deren zentrales Element eine neue Form von Hüllkörpern bildet: die Linearen Intervallabschätzungen (LIEs). Für sie werden, neben einer formalen Definition und Charakterisierung, zwei unterschiedliche sichere Berechnungsmethoden vorgestellt, die auf speziellen Taylor Modellen und Intervallarithmetik, bzw. auf der Ausnutzung der inneren Struktur von Affinformen und der damit verbundenen affinen Arithmetik basieren.\\ LIEs unterscheiden sich durch ihre parametrische Form essentiell von herkömmlichen kompakten Hüllkörpern. Sie erlauben eine völlig neue Behandlung der bei Unterteilungsalgorithmen auftretenden Teilprobleme, wie Schnittest, Parametergebietsreduzierung, Unterteilungsstrategie und der Verfeinerung der Ergebnisse. Für diese Teilprobleme werden neue Algorithmen entwickelt, die an die speziellen Eigenschaften der LIEs angepaßt sind und deren Gesamtheit einen neuen effizienten Unterteilungsalgorithmus bildet. - Subdivision algorithms are amongst the most reliable algorithms for the intersection of two parametric surface patches. They fit four of the five requirements on a good intersection algorithm: They are exact, reliable, independent and applicable to all kinds of parametric surfaces - a combination of properties that is hardly provided by any other type of algorithms to solve this problem. Though, the increasing consumption of memory and time in connection with higher requirements on the precision of the results inhibits the application of subdivision algorithms in practice up to now.\\ Several improvements for subdivision algorithms are proposed in this work. The center of these improvements is build by a new kind of bounding volumes: Linear Interval Estimations (LIEs). Besides of a formal definition and characterization of LIEs, two reliable methods for the computation of LIEs are introduced based on a new understanding of the use of affine arithmetic and a special application of Taylor Models and interval arithmetic. \\ LIEs differ in an essential way from conventional compact bounding volumes due to their parametric form. They allow a complete reconsideration of all occuring subproblems of subdivision algorithms, like the intersection test, the reduction of the parameter domains, subdivision strategies and the refinement of results. For all subproblems new algorithms adapted to the special characteristics of LIEs are proposed and combined to a new and efficient subdivision algorithm.
Priority Scheduling for Networked Virtual Environments
(Faissnauer, June 2001) Faisstnauer, Christian
Ein Mangel an Resourcen ist ein Problem, das bei nahezu allen Virtual-Reality Applikationen ( Virtual Environments ) und Videospielen beobachtet werden kann. Die Netzwerk-Bandbreite, der Durchsatz der Graphik-Pipeline, oder die verf¨ugbaren Prozessorzyklen reichen oft nicht aus, um die Anforderungen des Systems zu erf¨ullen. Der daraus folgende Wettstreit um die Resourcen f¨uhrt zu einer massiven Beeintr¨achtigung des gesamten Systems, und beschr¨ankt dessen Skalierbarkeit. In einer Client-Server Anwendung, zum Beispiel, wird die virtuelle Welt von einem zentralen Server verwaltet, und von mit dem Server in Verbindung stehenden Clients repliziert, welche außerdem eine graphische Darstellung f¨ur den Benutzer erzeugen. Dies erfordert, daß alle Clients vom Server ¨uber s¨amtliche ¨ Anderungen in der gemeinsamen Datenbank informiert werden. Die zum Erzeugen dieser Mitteilungen ben¨otigten Prozessorzyklen, oder die zum ¨ Ubermitteln ben¨otigte Netzwerk-Bandbreite, ¨ubersteigt oft die zur Verf¨ugung stehenden Resourcen des Systems, sodaß nur eine Teilmenge der erforderlichen Daten bearbeitet werden kann. Dies f¨uhrt zu einer Aufsummierung von Fehlern, z.B. Sichtbarkeitsfehler, welche auf Positions¨anderungen der sich bewegenden Objekte beruhen. Diese Dissertation pr¨asentiert einen Scheduling-Algorithmus, genannt Priority Round-Robin (PRR) Scheduling, welcher zur Verwaltung von um Systemresourcen konkurrierende Objekte entwickelt wurde. PRR weist s¨amtlichen Objekten eine Priorit¨at zu, welche anhand einer frei definierbaren Fehlermetrik bestimmt wird, und versucht den Gesamtfehler des Systems zu minimieren. Trotzdem ist der Aufwand des Algorithmus nur von der Anzahl der auszuw ¨ahlenden Objekte abh¨angig, und nicht von der Gesamtanzahl der Objekte ( output sensitive ). Außerdem garantiert der Algorithmus, daß alle Elemente mindestens einmal innerhalb einer gewissen Zeitspanne ausgew¨ahlt werden, was die Gefahr einer Starvation minimiert. Durch die frei definierbare Fehlermetrik kann PRR in nahezu allen Situationen eingesetzt werden, in denen es zu Engp¨assen bei der Zuteilung von Resourcen kommt, und durch die output sensitivity des Algorithmus wird die Konstruktion von skalierbaren Systemen wesentlich erleichtert. PRR ist in der Lage, den durch Resource-Engp¨asse erzeugten Fehler stufenlos zu minimieren, und passt sich laufend an dynamische Situationen an. - The problem of resource bottlenecks is encountered in almost any distributed virtual environment or networked game. Whenever the demand for resources such as network bandwidth, the graphics pipeline, or processing power exceeds their availability, the resulting competition for the resources leads to a degradation of the system s performance. In a typical client-server setup, for example, where the virtual world is managed by a server and replicated by connected clients which visualize the scene, the server must repeatedly transmit update messages to the clients. The computational power needed to select the messages to transmit to each client, or the network bandwidth limitations often allow only a subset of the update messages to be transmitted to the clients this leads to a performance degradation and an accumulation of errors, e.g. a visual error based on the positional displacement of the moving objects. This thesis presents a scheduling algorithm, developed to manage the objects competing for system resources, that is able to achieve a graceful degradation of the system s performance, while retaining an output sensitive behavior and being immune to starvation. This algorithm, called Priority Round-Robin (PRR) scheduling, enforces priorities based on a freely definable error metric, trying to minimize the overall error. The output sensitivity is a crucial requirement for the construction of scalable systems, and the freely definable error metric makes it suitable to be employed whenever objects compete for system resources, in client-server and peer-to-peer architectures as well. Therefore Priority Round-Robin scheduling is a substantial contribution to the development of distributed virtual environments and networked online-games.
Interactive Volume-Rendering Techniques for Medical Data Visualization
(Csébfalvi, June 2001) Csébfalvi, Balázs
Direktes Volumenrendering ist eine flexible, aber Rechenzeit-intensive Methode f¨ur die Visualisierung von 3D Volumsdaten. Wegen der enorm großen Anzahl an Voxeln ( volume elements ), die verarbeitet werden m¨ussen, ist es so gut wie nicht m¨oglich einen hochaufl¨osenden Datenblock mit Hilfe von brute force Algorithmen wie klassischem Ray Casting oder Splatting auf einer Singleprozessormaschine interaktiv zu rendern. Eine Alternative ist, Hardwarebeschleunigung zu verwenden. Bildwiederholfrequenzen in Echtzeit k¨onnen erreicht werden, wenn man parallele Versionen der Standardalgorithmen auf großen Multiprozessorsystemen ausf¨uhrt. Diese L¨osung ist nicht billig und wird daher auch nicht oft verwendet. Eine weitere Alternative ist, die Beschleunigung allein mit speziellen Softwaretechniken zu erreichen, um auch auf low-end PCs eine schnelle Volumsdarstellung erreichen zu k¨onnen. Die Methoden, die diesem Ansatz folgen, verwenden normalerweise einen Vorverarbeitungsschritt um die Volumsdarstellung schneller zu machen. Zum Beispiel k¨onnen Koh¨arenzen in einen Datensatz durch Vorverarbeitung ausgenutzt werden. Software- und Hardware-Beschleunigungsmethoden repr¨asentieren parallele Richtungen in der Volumenrendering-Forschung, die stark miteinander interagieren. In Hardware implementierte Algorithmen werden oft auch als reine Software-Optimierungen verwendet und ¨ublicherweise werden die schnellsten Softwarebeschleunigungstechniken in Hardware realisiert. Wenn man die oberen Aspekte bedenkt, folgt diese Arbiet der reinen Software-Richtung. Die neuesten schnellen Volumenrendering Techniken wie der klassische Shear-Warp-Algorithmus oder auf distance transformation basierende Methoden beschleunigen die Darstellung, k¨onnen aber nicht in interaktiven Anwendungen verwendet werden. Das prim¨are Ziel dieser Arbeit ist die Anwendungs-orientierte Optimierung existierender Volumenrenderingmethoden, um interaktive Bildwiederholfrequenzen auch auf low-end Rechnern zu erm¨oglichen. Neue Techniken f¨ur traditionelles alpha-blending rendering , Ober- fl¨achenschattierte Darstellung, maximum intensity projection (MIP) und schnelle Voransicht mit der M¨oglichkeit, Parameter interaktiv zu ver¨andern, werden vorgestellt. Es wird gezeigt, wie man die ALU einer Singleprozessorarchitektur anstatt einer Parallelprozessoranordnung verwenden kann, um Voxel parallel zu verarbeiten. Die vorgeschlagene Methode f¨uhrt zu einem allgemeinen Werkzeug, das sowohl alpha-blending rendering als auch maximum intensity projection unterst¨utzt. Weiters wird untersucht, wie man die zu verarbeitenden Daten, abh¨angig von der verwendeten Renderingmethode, reduzieren kann. Zum Beispiel, verschiedene Vorverarbeitungsstartegien f¨ur interactive Iso-Fl¨achendarstellung und schnelle Voransicht, basierend auf einem vereinfachten Visualisierungsmodell, werden vorgeschlagen. Da die in dieser Arbeit pr¨asentierten Methoden kein Supersampling unterst¨utzen, k¨onnen Treppenstufenartefakte in den generierten Bildern entstehen. Um diesen Nachteil zu kompensieren, wird ein neues Gradientensch¨atzungsverfahren, welches eine glatte Gradientenfunktion liefert, vorgestellt. - Direct volume rendering is a flexible but computationally expensive method for visualizing 3D sampled data. Because of the enormous number of voxels (volume elements) to be processed, it is hardly possible to interactively render a high-resolution volume using brute force algorithms like the classical ray casting or splatting on a recent single-processor machine. One alternative is to apply hardware acceleration. Real-time frame rates can be achieved by running the parallel versions of the standard algorithms on large multi-processor systems. This solution is not cheap, therefore it is not widely used. Another alternative is to develop pure software-only acceleration techniques to support fast volume rendering even on a low-end PC. The methods following this approach usually preprocess the volume in order to make the rendering procedure faster. For example, the coherence inside a data set can be exploited in such a preprocessing. The software and hardware acceleration methods represent parallel directions in volumerendering research strongly interacting with each other. Ideas used in hardware devices are often adapted to pure software optimization and usually the fastest software-acceleration techniques are implemented in hardware, like in the case of VolumePro board. Taking the upper aspects into account, this thesis follows the software-only direction. The recent fast volume-rendering techniques like the classical shear-warp algorithm or methods based on distance transformation speed up the rendering process but they cannot be used in interactive applications. The primary goal of this thesis is the application-oriented optimization of existing volumerendering methods providing interactive frame-rates even on low-end machines. New techniques are presented for traditional alpha-blending rendering, surface-shaded display, maximum intensity projection (MIP), and fast previewing with fully interactive parameter control. It is shown how to exploit the ALU of a single-processor architecture for parallel processing of voxels instead of using a parallel-processor array. The presented idea leads to a general tool supporting alpha-blending rendering as well as maximum intensity projection. It is also discussed how to reduce the data to be processed depending on the applied rendering method. For example, different preprocessing strategies are proposed for interactive iso-surface rendering and fast previewing based on a simplified visualization model. Since the presented methods do not support supersampling, staircase artifacts can appear in the generated images. In order to compensate this drawback a new gradient estimation scheme is also presented which provides a smooth gradient function.
Distributed Collaborative Augmented Reality
(Hesina, June 2001) Hesina, Gerd
Augmented Reality ist die Überlagerung von Computergraphik und Text mit der wirklichen Umgebung und/oder Videobildern. Diese Dissertation behandelt Verbesserungen für kollaborative Augemented Reality (AR) Umgebungen. Wir stellen ein Werkzeug vor, dass einen verteilten, mehrfach benutzten Szenegraphen, als Ansatz verwendet, um eine transparente Verteilung auf der untersten Ebene zu ermöglichen. Application migration wird verwendet um Berechnungen innerhalb des Systems aufzuteilen, eine dynamische Anwenderverwaltung zu erreichen, Kollaboration zwischen weit entfernten Anwendern zu ermöglichen und um ubiquitous computing zu unterstützen. Das resultierende System ist eine komplexe kollaborative AR Arbeitsumgebung, welche dazu verwendet wird, um die Frage, wie man dreidimensionale Interaktion in einer üblichen Arbeitsumgebung, in der verschiedenste Aufgabenstellungen gleichzeitig durch mehrere Benutzer bearbeitet werden, zu behandeln. Die Implementierung wurde im Studierstube System ausgeführt, welches eine kollaborative Augemented Reality Umbgebung ist. Als Kern verwendet das System kollaborative AR um echte 3D Interaktion in die Arbeitsumgebung einzubinden. Dieses Konzept wird um jeweils multiple Benutzer, Computer Plattformen, Anzeigegeräte, parallele Applikationen und Kontextschnittstellen (d.h. 3D Dokumente), zu einer heterogenen verteilten Umgebung erweitert. All dies geschieht beinahe völlig transparent für den Applikationsprogrammierer. - Augmented Reality is the mixture of computer graphics and text with real world and/or video images. This thesis presents improvements for collaborative augmented reality environments. We present a toolkit, which uses a distributed shared scene graph approach to enable transparent distribution at the lowest level. Application migration is used to distribute computational load within the system. We demonstrate how migration can be applied and used for load balancing, dynamic workgroup management, remote collaboration, and even ubiquitous computing . The resulting system is a complex distributed collaborative augmented reality work environment, which is used to address the question of how to use three-dimensional interaction and new media in a general work environment, where a variety of tasks are carried out simultaneously by several users. The implementation was done in the Studierstube system, a collaborative augmented reality environment. At its core, the system uses collaborative augmented reality to incorporate true 3D interaction into a productivity environment. This concept is extended to include multiple users, multiple host platforms, multiple display types, multiple concurrent applications, and a multi-context (i. e., 3D document) interface into a heterogeneous distributed environment. All this happens almost totally transparent to the application programmer.
Usability Issues in Medical Volume Visualization
(König, June 2001) König, Andreas H.
Eine der wichtigsten technologischen Entwicklungen im zwanzigsten Jahrhundert ist die Verwendung von Computern in vielen Bereichen des t¨aglichen Lebens, der Arbeit und der Forschung. Aufgrund der neuen M¨oglichkeiten zur Datenverarbeitung ist die Menge an Information, die behandelt wird, viel gr¨oßer als in fr¨uheren Zeiten. Als eine Folge davon hat sich die graphische Repr¨asentation, also die Visualisierung von Daten, als ein n¨utzlicher Ansatz zur Untersuchung von großen Datens¨atzen etabliert. Die Visualisierung von medizinischen Daten macht einen sehr wichtigen Anwendungsbereich aus. Volumendatens¨atze, wie sie mit Hilfe von Computertomographie- o der Magnetresonanzscannern erzeugt werden k¨onnen, dienen als die Grundlage f¨ur die Visualisierung von anatomischen oder pathologischen Strukturen des menschlichen K¨orpers. Viele verschiedene Techniken wurden zur Visualisierung von Volumendaten in den vergangenen Jahren entwickelt. In dieser Dissertation werden spezielle Probleme der Anwendbarkeit diskutiert, welche auftreten, wenn die aus dem akademischen Bereich der Visualisierung stammenden Methoden f¨ur ein Softwaresystem verwendet werden, welches im t¨aglich klinischen Betrieb zum Einsatz kommen soll. Nach einer kurzen Einf¨uhrung in den Bereich der Medizinischen Visualisierung und einem kurzen ¨Uberblick ¨uber den Stand der Wissenschaft, widmet sich der Hauptteil dieser Dissertation den Problemen, welche bei der Entwicklung eines Softwaresystems f¨ur den Einsatz im medizinischen Bereich auftreten. Danach werden drei spezielle Themen der medizinischen Visualisierung diskutiert, welche sich als im Hinblick auf ihre Anwendbarkeit als besonders herausfordernd gezeigt haben: Die Spezifikation von Transferfunktionen, die multimodale Visualisierung von MR und fMRI Daten und der Umgang mit besonders großen Datens¨atzen, wie sie von modernsten Mehrschicht-CT Ger¨aten erzeugt werden. - One of the most important technological developments in the 20th century is the use of computers in many areas of daily life, work, and research. Due to the new abilities in processing data, the amount of information that is handled, is much larger compared to previous times. As a consequence, the graphical representation, i.e., the visualization of data, established itself as a useful approach to investigate large data-sets. Among other application areas, the visualization of medical volume-data sets is a very important field of research. Anatomical or pathological structures acquired by medical imaging modalities like computed-tomography or magneticresonance scanners are visualized for further investigation. Many useful techniques have been developed in this area during the past decades. In this thesis the necessary adaptions and modifications to turn these scientific concepts into a software system for radiologists and other medical professionals are presented. After a brief introduction to the visualization of medical volume data and a short overview over the state of the art, the main part of this thesis focusses on usability issues that arise when techniques developed by the scientific community of visualization experts are to be utilized in a commercial workstation. Additionally, three special topics of medical visualization are discussed, which were most sensible to usability issues: The specification of transfer functions, multimodal visualization of MR and fMRI data, and the handling of large-scale data sets as acquired by advanced multi-slice CT scanners.
Real-Time Volume Visualization on Low-End Hardware
(Mroz, 2001-05) Mroz, Lukas
Die Visualisierung von Volumsdaten ist ein wichtiges Werkzeug zur Untersuchung und Präsentation von Daten innerhalb zahlreicher Anwendungsgebiete. Bildgebende Verfahren innerhalb der Medizin sowie numerische Simulationen, liefern beispielsweise Datenmengen, die ohne Visualisierung im 3D kaum zu bewältigen wären. Die Möglichkeit interaktiver Manipulation von Volumsdaten auf desktop-PCs ist insbesondere in Hinblick auf Anwendungen in der Telemedizin, kollaborativer Visualisierung sowie der Visualisierung über das Internet von großer Bedeutung. Eine Vorbedingung für interaktive, softwarebasierte Volumsdarstellung ist ef- fizientes Ausschließen von nicht relevanten Volumsbereichen von der Projektion (nicht relevant sind Daten, die keinen sichtbaren Einfluß auf das Ergebnis der Visualisierung haben). In dieser Arbeit wird ein diesbezügliches Verfahren vorgestellt, das ein ¨ Uberspringen nicht relevanter Voxel während der Darstellung faktisch ohne zusätzlichen Aufwand ermöglicht. Dazu werden während eines Vorverarbeitungsschritts potentiell relevante Voxel identifiziert und in einer abgeleiteten Datenstruktur gespeichert. Durch entsprechende Anordnung der Voxel innerhalb dieser Datenstruktur, können durch interaktive Veränderung von Visualisierungsparametern irrelevant gewordene Voxel ebenfalls effizient übergangen werden. Zusammen mit einer schnellen, shear/warp-basierten Projektion und einer auf flexibler Kombination von Look-up-Tabellen basierenden Schattierung, können die derart vorbereiteten Volumendaten interaktiv auf PC Hardware dargestellt werden. Da innerhalb der extrahierten Voxeldaten einzelne segmentierte Objekte unterschieden werden können, bietet das Verfahren weitreichende Flexibilität bei der Visualisierung: Wegschneiden einzelner Objekte, individuelle optische Parameter, Transferfunktionen und Beleuchtungsmodelle, sowie die objektweise Wahl des Compositing-verfahrens. Eine effiziente Kompression der Voxeldaten ermöglicht den Einsatz des Verfahrens zur Visualisierung über Netzwerke mit geringer Bandbreite, wie z.B. das Internet. - Volume visualization is an important tool for investigating and presenting data within numerous fields of application. Medical imaging modalities and numerical simulation applications, for example, produce huge amounts of data, which can be effectively viewed and investigated in 3D. The ability to interactively work with volumetric data on standard desktop hardware is of utmost importance for telemedicine, collaborative visualization, and especially for Internet-based visualization applications. The key to interactive but software-based volume rendering is an efficient approach to skip parts of the volume which do not contribute to the visualization results due to the visualization mapping in use and current parameter settings. In this work, an efficient way of skipping non-contributing parts of the data is presented. Skipping is done at a negligible effort by extracting just potentially contributing voxels from the volume during a preprocessing step, and by storing them in a derived enumeration-like data structure. Within this structure, voxels are ordered in a way which is optimized for the chosen compositing technique, and which allows to efficiently skip further voxels as they become irrelevant for the result due to changes to the visualization parameters. Together with a fast shear/warp-based rendering and flexible shading based on look-up tables, this approach can be used to provide interactive rendering of segmented volumes, featuring object-aware clipping, transfer functions, shading models, and compositing modes defined on a per-object basis, even on standard desktop hardware. In combination with a space-efficient encoding of the enumerated voxel data, the approach is well-suited for visualization over low-bandwidth networks, like the Internet.
Semantic Depth of Field - Using Blur for Focus+Context Visualization
(Kosara, 2004) Kosara, Robert
Ein zentrales Thema in der Informationsvisualisierung, wie auch in anderen Bereichen (etwa Volumens- und Strömungsvisualisierung), ist die Darstellung von Information in einem Kontext, der die Daten leichter erfassbar macht. Unschärfe ist eine visuelle Eigenschaft, die in der Fotografie seit über 150 Jahren eine wichtige Rolle spielt, dies in der Computergrafik aber so gut wie gar nicht tut. Scharfe Objekte oder Bereiche in einem Foto erregen aber sofort die Aufmerksamkeit des Betrachters/ der Betrachterin der Unterschied zwischen scharfen und unscharfen Objekten eignet sich daher ausgezeichnet, die Aufmerksamkeit auf bestimmte Dinge zu lenken. In dieser Arbeit wird eine Methode namens Semantic Depth of Field (SDOF) vorgeschlagen, die durch Unschärfe weniger wichtige Objekte weniger sichtbar macht, und damit die Aufmerksamkeit des Benutzers lenkt. Diese Methode benötigt nur eine zusätzliche Information pro Datenpunkt: dessen Relevanz. Diese wird in eine Unschärfe übersetzt, die dann zum Zeichnen von Objekten benutzt wird. Der/die BenutzerIn hat volle Kontrolle über die Funktionen, die in dieser Übersetzung verwendet werden. Eine Reihe von Applikationen, die SDOF einsetzen, wird besprochen um dessen Nutzen zu demonstrieren. Weil Unschärfe in der Computergrafik als langsam bekannt ist, wird eine Technik vorgestellt, die es möglich macht, SDOF in interaktiven Applikationen einzusetzen. Außerdem wird von den Ergebnissen einer Studie berichtet, in der gezeigt werden konnte, dass SDOF ein präattentives Merkmal ist, also innerhalb von 200 ms und ohne serielle Suche wahrgenommen wird. SDOF ist auch nicht signifikant langsamer als Farbe in Suchaufgaben, und es verlängert die Suchzeit nicht signifikant, wenn nach der Kombination von SDOF und einem anderen Merkmal gesucht wird wie das sonst der Fall ist. - One central task in information visualization and related fields (like volume and flow visualization) is displaying information in a context that makes it easier for users to understand. Blur is a visual cue that has been playing an important role in photography for over 150 years, but has been widely ignored in computer graphics. Sharp objects in photographs immediately attract the viewer s gaze distinguishing between sharp and blurred objects therefore is very well suited for directing the viewer s attention to certain objects or parts of the image. In this thesis, a method called Semantic Depth of Field (SDOF) is proposed, which blurs currently irrelevant objects and thus guides the viewer s attention. This method only requires one additional value for each data point: its relevance. This relevance is then translated into a blur level, which is used for drawing objects. The user has full control over the functions involved in this process. A number of applications is shown to demonstrate the usefulness of SDOF. Because blur is known to be slow, a method for fast blurring of objects is also presented, which makes it possible to use SDOF in interactive applications. The results of a user study are also presented, which showed that SDOF is a preattentive feature, i.e., can be perceived within 200 ms, and does not require serial search. SDOF is also not significantly slower than color when used in search tasks; and it does not decrease performance when combined with another feature, as is usually the case.
Constructions of Bidirectional Reflection Distribution Functions
(Neumann, June 2001) Neumann, Attila
Ursprünglich beinhaltete die Untersuchung von Material-Modellen lediglich die Suche nach Formeln die das reale Material beschreiben (Lambert, Minneart). Im Bereich der Computergrafik erwies sich aber die Anwendung von virtuellen Formeln als nützlich (Phong, Blinn, ...). Diese Vorgehensweise ist jedoch nur dann akzeptabel wenn das Konzept der physikalischen lausibilitt korrekt definiert ist. Abgesehen davon ob Realitäts-Anforderungen erfüllt werden, müssen einige Faktoren berücksichtigt werden die speziell im Bereich der Computergrafik signifikant sind, z.B. die Kosten der Anwendung einer Formel. Die Berechnung der unmittelbaren Relation von Paaren von Einfalls- und Ausfallsrichtungen ist solch ein Faktor, oder die Effekte der Lichtverteilung in verschiedene Ausfallsrichtungen, oder das Sampling von Radiance-Richtungen des einfallenden Lichtstrahls anhand von Monte Carlo-Methoden. Das Albedo-Konzept das für diffuse Material-Modelle definiert ist kann in die Definition der physikalis- chen PlausibilitaÄt inkludiert werden. Das neue Albedo-Konzept kann für mehrere Anwendungen ver- wendet werden. Die erweiterte Definition von Albedo kann für die detaillierte Charakterisierung des Verhaltens eines Material-Modells verwendet werden. Es kann direkt als Effekt von gleichmig verteil- tem Tageslicht angesehen werden. Die Tauglichkeit des Albedos kann ein signifikanter Faktor für die Tauglichkeit der BRDFs sein. Ebenso spielt es eine wichtige Rolle in der Technik des Importance Sam- plings. Für die korrekte Behandlung des Konzepts der Distanz für Material-Modelle kann das Konzept der Zusammensetzung als Analogon zur Korrelation definiert werden, welches ein interessantes neues Werkzeug für die Untersuchung der BRDF ist. Eine Anzahl an Formeln wurden für die Beschreibung von Metallen hergeleitet. Die metallische Erscheinung von Materialien wird vor allem durch die Albedo-Funktion, Spitzen in und neben der Spiegelungsrichtung und dem Verhalten bei flachen Winkeln charakterisiert. In dieser Studie wird die physikalische Plausibilitt mehrerer bekannter Material-Modelle kritisch begutachtet indem ihr Albedo- Verhalten untersucht wird. Wir beschreiben zwei einfache, allgemein anwendbare und effektive Methoden zur Eliminierung der Mngel bekannter Metall-Modelle oder, allgemein, damit Rendering-Material-Modelle realistischer erscheinen. Eine Methode eliminiert einige im allgemeinen auftretende Defekte der Albedo- Funktion praktisch ohne Berechnungskosten: sie beseitigt den Schaden an der Energie-Bilanz und gle- ichzeitig korrigiert sie die künstliche Verdunkelung der reflektierten Radiance. Die zweite, sogar noch einfachere Methode beinhaltet eine inverse Cosinus-Funktion, wodurch das Phong- und Blinn-Modell mittels einer einzelnen Multiplikation wesentlich verbessert wird. Die grundlegende Aufgabe der prsentierten Arbeit war eine BRDF-Formel zu entwickeln, die die An- forderung an die physikalische Plausibilitt erfüllt und für Importance Sampling verwendet werden kann, indem neue Konstruktionen verwendet werden oder indem existierende Formeln modifiziert werden. Die Patch-basierte BRDF-Konstruktion ist eine solche Formel, die Material-Modell-Funktionen produziert in- dem einfache BRDF-Formeln mit Parametern die den Zustand der physikalischen Plausibilitt erfüllen kon- tinuierlich und/oder diskret gemischt werden. Die uersten Paramterwerte der einfachen BRDF-Formeln liefern ideal diffuse Reflexion und ideale Spiegelung, daher sollte diese Konstruktion als eine gemeinsame Verallgemeinerung der beiden betrachtet werden. Hierbei ist die Dichtefunktion ein freier Parameter der resultierenden BRDF Klasse. Die grundlegende Idee der prsentierten Methode ist das zulssige Mis- chen von zulssigen Basisfunktionen. Dies ist die erste Konstruktion die speziell auf die Verbesserung der Geschwindigkeit des Importance Samplings zielt um die Effektivitt von Monte Carlo-Methoden zu erhoÄhen. Von einer Reihe von Verallgemeinerungen und Verfeinerungen ist das anisotropische und das retro-reflektierende Modell am interessantesten. - Historically the examination of material models involved searching merely for formulae that described real materials (Lambert, Minneart), but computer graphics rendered the application of virtual formulae useful (Phong, Blinn, etc). However, the latter approach is acceptable only if the concept of physical plausibility is correctly defined. Fulfillment of reality requirements apart, especially for computer graphics some significant factors may have to be taken into account, such as the cost of applying a formula. The computation of the immediate relationship between incoming and outgoing direction pairs is such a factor, or the effects of uniformly distributed lighting in various outgoing directions, or the sampling of radiance directions of the incoming light ray according to Monte Carlo method. An extension of the albedo concept defined for diffuse material models is included in the definition of physical plausibility. The new albedo concept may have multiple applications. The extended definition of albedo may be used for detailed characterization of the behavior of the material model. It can be directly seen as effect of uniformly distributed daylight. Fitting of albedo can be a significant factor of a BRDFs' fitting. Similarly it plays an important role in the technique of importance sampling. For the proper treatment of the concept of distance for material models, the concept of composition may be defined as the analogue of correlation, which is an interesting new tool for the examination of BRDF. A number of formulae were derived for the description of metals. The metallic appearance of materials is characterized first of all by the albedo function, specular and off-specular peaks and behavior at grazing angles. In this paper the physical plausibility of several known material models will be critically examined by investigating their albedo behavior. We shall describe two simple, generally applicable and effective methods for the elimination of the deficiencies of known metal models or, in general, rendering material models to appear more realistic. One method eliminates some generally recurring defects of the albedo function practically without computational costs: it cancels the damage to the energy balance and at the same time it corrects the artificial darkening of reflected radiance. The second, even simpler method involves an inverse-cosine function, which by a single multiplication significantly improves the Phong and Blinn model, while it conserves their assets. The basic task of this thesis the development of BRDF formulae, which fulfill the physical plausibility requirement and can be used for importance sampling, by applying new constructions or modifying existing formulae. The patch-based BRDF construction is one such formula, which produces material model functions by continuous and/or discrete mixing of basic BRDF formulae with parameters to fulfil the condition of physical plausibility. The extreme parameters of these basic BRDF formulae yield the ideal diffuse and ideal mirror options, and therefore this construction should be regarded as a mutual generalization of the two. Here a free parameter of the resultant BRDF class is a probability density function. The basic idea of the present method is to allow mixing of allowable base functions. This is the first construction aimed especially at enhancing the speed of importance sampling to improve the effectiveness of (Quasi) Monte Carlo methods. Of a number of generalizations and refinements, the anisotropic and retro-reflective models are of greatest interest.
Perceptually Driven Radiosity
(Prikryl, June 2001) Prikryl, Jan
Despite its popularity among researchers the radiosity method still suffers some disadvantage over other global illumination methods. Usual implementations of the radiosity method use criteria based on radiometric values to drive the computation to decide about sufficient mesh quality or to estimate the error of the simulation process and to decide when the simulation can be safely terminated. This is absolutely correct for the case of radiometric simulation, when the user is interested in actual values of radiometric quantities. On the other hand, the radiosity method is very often used just to generate pictures for the human observer and those pictures are not required to be the results of correct physical simulations, they just have to look the same. The results of research on human visual performance and visual signal processing can be built into the image synthesis algorithm itself under some circumstances and guarantee that no effort will be spent on computing changes that are only marginally important for the human observer. In the area of image processing, perceptual error metrics are used for image comparison and image coding that enable to better predict the differences between two images as opposed to the perceptually inappropriate and widely used meansquared error metrics. Tone reproduction operators known from image synthesis make it possible to map a bright scale of image luminances onto a narrow scale of CRT luminances in such a way that the perceived CRT image produces the same mental image as the original image. Perceptually-driven radiosity algorithms exist, which use various methods to control the optimum density of the finite-element mesh defining the scene that is being rendered, to include only visible discontinuity lines into this mesh, and to predict the convergence of the method. We will describe an hierarchical extension to the Monte Carlo radiosity that keeps the accuracy of the solution high only in the area immediately visible from the point of observation. We will also present a comparison of different perceptual and radiometric termination criteria for a view-independent version of Monte Carlo radiosity.
Optical Tracking - From User Motion To 3D Interaction
(Dorfmüller - Ulhaas, Dec 2002) Dorfmüller- Ulhaas, Klaus
Das Verfolgen von Benutzerbewegungen ist eine der grundlegenden Aufgaben, die von jedem System für Virtual Reality (VR) bereitgestellt werden muß. Es sind unterschiedliche Methoden bekannt, wie diese Verfolgung durchgeführt werden kann. Gebrächliche Trackingsysteme verwenden magnetische oder Ultraschall-Sensoren in verschiedensten Varianten sowie mechanische Hilfsmittel. Allerdings weist jedes dieser Syteme Nachteile auf, die in ihrem Funktionsprinzip begründet sind. Fast alle Techniken erfordern eine Verbindung des Benutzers mit einer Meßstation, entweder durch Kabel oder, was den Benutzer noch mehr in seiner Bewegung einschränkt, durch eine mechanische Verbindung. Während mechanische Systeme außerordentlich präzise arbeiten, werden magnetische und akkustische Trackingsysteme von unterschiedlichen Störquellen beeinflusst. Aus diesem Grund wurde ein optisches Trackingsystem entwickelt, das nicht die bekannten Nachteile konventioneller Syteme aufweist. Diese Arbeit konzentriert sich auf die Verwendung stereoskopischer Trackingverfahren, die unter anderem sehr effektiv die Genauigkeit optisch basierter Systeme verbessern. Auf Computer-Vision basierte Tracker ermöglichen im allgemeinen eine kabellose 3D-Interaktion. Zudem ist das vorgestellte System aufgrund der Verwendung von Standard-Sensor-Technologie sehr wirtschaftlich. Das beschriebene Trackingsystem bietet eine Genauigkeit im Submillimeterbereich und erfüllt somit die Anforderung der meisten VR-Anwendungen. Der beschriebene optische Tracker arbeitet mit langwelligem Licht und basiert auf der Verfolgung reflektierender Kugeln, die mit infrarotem Licht beleuchtet werden. Der verwendete Wellenlängenbereich ermöglicht, dass die Wahrnehmung des Benutzers von einer virtuellen Szene bei Verwendung von projektionsbasierten Ausgabegeräten und gedämpftem Licht nicht gestört wird. Im Gegensatz zu kommerziellen Systemen arbeitet das Ergebnis dieser Forschungsarbeit in Echtzeit. Desweiteren können mit dem vorgestellten System sehr kleine Kameras verwendet werden, so dass es für inside-out Trackingaufgaben anwendbar ist. Diese Arbeit zeigt neue Ansätze für die Kalibrierung einer stereoskopischen Kameraanordnung auf. Verwendet werden gebrächliche Kalibrationsgeräte kommerzieller optischer Systeme aus der Computeranimation, aber im Gegensatz zu den heutzutage zur Verfügung stehenden Kalibrierungsverfahren werden hier interne und externe Kameraparameter gleichzeitig kalibriert, was auch die Linsenverzeichnung mit einschließt. Diese Kalibrierung ist einfach anzuwenden und arbeitet schnell und präzise. Um eine hohe Zuverlässigkeit zu bieten, die von den meisten VR-Anwendungen vorausgesetzt wird, muss die menschliche Bewegung über die Zeit hinweg beobachtet werden. Das geschieht häfig mithilfe eines Kalmanfilters, wodurch eine Vorhersage der Bewegung ermöglicht wird. Dies erhöht nicht nur die Frequenz des Trackingsystems, sondern gleicht auch Verzögerungen bei der Darstellung komplexer virtueller Szenen oder Verzögerungen bei der Datenkommunikation aus. Eine neue Formulierung der Filtergleichungen wird vorgestellt, die auch für nicht-optisch arbeitende Tracker einsetztbar ist und die Lage eines Objektes mit sechs Freiheitsgraden bestimmt. Schließlich folgen einige Ausführungen zur Verfolgung einer Bewegung auf der Grundlage von natürlichen Merkmalen, wobei das vorgestellte Verfahren die Konturen eines Objektes verfolgt. Erste experimentelle Ergebnisse einer Implementierung zum Erkennen einer menschlichen Zeigegeste in Umgebungen mit unterschiedlichen Lichtverhältnissen und Hintergründen werden vorgestellt. Perspektiven werden aufgezeigt, wie diese Methode auf dreidimensionales modellbasiertes Hand- Tracking mithilfe stereoskopischen Sehens ausgeweitet werden kann. - Tracking user movements is one of the major low-level tasks which every Virtual Reality (VR) system needs to fulfill. There are different methods how this tracking may be performed. Common tracking systems use magnetic or ultrasonic trackers in different variations as well as mechanical devices. All of these systems have drawbacks which are caused by their principles of work. Typically, the user has to be linked to a measurement instrument, either by cable or, even more restraining for the user, by a mechanical linkage. Furthermore, while mechanical tracking systems are extremely precise, magnetic and acoustic tracking systems suffer from different sources of distortions. For this reason, an optical tracking system has been developed which overcomes many of the drawbacks of conventional tracking systems. This work is focused on stereoscopic tracking that provides an effective way to enhance the accuracy of optical based trackers. Vision based trackers in general facilitate wireless interaction with 3D worlds for the users of a virtual reality system. Additionally, the proposed tracker is very economic through the use of standard sensor technology that will furthermore reduce cost. The proposed tracker provides an accuracy in the range of sub-millimeters, thus it meets the requirements of most virtual reality applications. The presented optical tracker works with low frequency light and is based on retro-reflective sphere shaped markers illuminated with infrared light to not interfere with the user s perception of a virtual scene on projection based display technology systems in environments with dim light. In contrast to commercial optical tracking systems, the outcome of this work is operating in real-time. Furthermore, the presented sytem can make use of very small cameras to be applicable for inside-out tracking. This work presents novel approaches to calibrate a stereoscopic camera setup. It utilizes the standard equipment used for commercial optical trackers in computer animation, but contrarily to calibration methods available today, it calibrates internal and external camera parameters simultaneously, including lens distortion parameters. The calibration is very easy to use, fast and precise. To provide the robustness required by most virtual reality applications, human motion needs to be tracked over time. This has been often done with a Kalman filter facilitating a prediction of motion which may not only enhance the frequency of the tracking system, but may also cope with display lags of complex virtual scenes or with acquisition or communication delays. A new filter formulation is presented that may also be used with non-optical based trackers providing the pose of an object with six degrees of freedom. Finally, some extensions to natural landmark tracking are presented using a contour tracking approach. First experimental results of an early implementation are shown, detecting a human pointing gesture in environments with different lighting conditions and backgrounds. Perspectives are given how this method could be extended to 3D model based hand tracking using stereoscopic vision.
Photon Tracing for Complex Environments
(Wilkie, April 2001) Wilkie, Alexander
Qualitativ hochwertige Bildsyntheseverfahren haben im Allgemeinen das Problem, daß sie bei Anwendung auf komplexe Szenen entweder zu lange Rechenzeiten ben¨otigen, oder daß ihr Speicherplatzbedarf zu groß wird bei manchen ansonsten durchaus brauchbaren Methoden treten auch beide Probleme zugleich auf. Die Komplexit¨at einer Szene definiert sich in diesem Zusammenhang normalerweise ¨uber die Anzahl der zu ihrer Modellierung ben¨otigten Grundobjekte. Die Ressourcenanforderungen der im Rahmen dieser Arbeit betrachteten photorealistischen Bildsyntheseverfahren steigen mindestens linear mit der Anzahl der beteiligten Objekte, woraus sich ein direkter Zusammenhang zwischen der Szenenkomplexit¨at und dem Laufzeitverhalten der Bilderzeugungsprogramme ergibt. Daraus leitet sich als erster Ansatz die Forderung ab, m¨oglichst nur solche Modellierungsmethoden zu verwenden, die mit verh¨altnism¨aßig wenigen Grundobjekten bereits imstande sind, Szenen ausreichend zu beschreiben. Konkret geht es darum, die in der Computergraphik Industrie derzeit ¨ubliche Darstellungsweise durch große Mengen an Polygonen zu vermeiden, und effizientere Verfahren wie Constructive Solid Geometry (kurz CSG) oder regelbasierte Modellierung durch Automaten (wie etwa L Systeme) zu verwenden. Diese speichersparenden Methoden zur Szenenbeschreibung haben allerdings den Nachteil, daß sie aus verschiedenen Gr¨unden bislang nicht zusammen mit einer bestimmten Klasse von hochwertigen Bildsyntheseverfahren, den sogenannten photon tracing methods, verwendet werden konnten. Diese Verfahren berechnen eine L¨osung der Lichtverteilung in einer Szene durch Nachvollziehung der Lichtausbreitung mittels stochastischer Methoden. Das Ergebnis dieser Simulation wird dann in einem zweiten Arbeitsschritt von einem beliebigen Blickpunkt aus dargestellt. Besonders wenn die Erzeugung ganzer Bildsequenzen beispielsweise f¨ur Animationen erforderlich ist, erspart man sich durch diese Teilung des Ablaufes in 2 Phasen, von denen die erste pro Szene nur einmal durchgef¨uhrt werden muß, einen wesentlichen Aufwand. Allerdings kann der an sich n¨utzliche Umstand, daß die Verteilung der Lichtenergie in der Szene in irgendeiner Form zwischen den beiden Arbeitsschritten zwischengespeichert werden muß, auch ein Problem darstellen. Das ist dann der Fall, wenn derartige Verfahren auf komplexe Szenen angewandt werden. Bei diesen wird der Speicherplatzbedarf extrem groß, und kann unter Umst¨anden die Verwendung solcher Methoden ¨uberhaupt unm¨oglich machen. Im Rahmen dieser Arbeit werden nun drei Ans¨atze aufgezeigt, solche photon tracers doch auch f¨ur komplexere Umgebungen nutzen zu k¨onnen. Der erste pr¨asentiert eine M¨oglichkeit, durch die direkte Verwendung von CSG Modellen die Szenenkomplexit¨at an sich im Vorfeld der Berechnungen zu reduzieren. Der zweite setzt am Problem des Speicheraufwandes f¨ur die Lichtverteilung an, und stellt ein Verfahren vor, das f¨ur einzelne komplexe Objekte lediglich eine lokale N¨aherung f¨ur die Beleuchtung speichert. Dadurch werden zwar Abweichungen von der Ideall¨osung erzeugt, aber der dadurch drastisch reduzierte Platzbedarf kann in manchen F¨allen die Einbindung komplexer Objekte erst erm¨oglichen. Der dritte erweitert das im zweiten Punkt vorgeschlagene Verfahren insoferne, als er die Anwendung dieser N¨aherungsverfahren auch auf durch Automaten lediglich implizit gegebene Objekte erm¨oglicht, was eine weitere entscheidende Reduktion des zur Durchf¨uhrung von Beleuchtungsberechnungen erforderlichen Speicherplatzes m¨oglich macht. Im Anhang der Arbeit werden einige Aspekte der physikalisch korrekten photorealistischen Bildsynthese abgehandelt. Sie stehen zwar nicht in direktem Zusammenhang mit den im Hauptteil der Arbeit pr¨asentierten Verbesserungen, sind aber insoferne f¨ur den Themenbereich relevant, als es einer der Vorteile von photon tracing algorithms ist, derartige Effekte in die Bildberechnungen einbeziehen zu k¨onnen. Die entsprechenden Untersuchungen wurden ebenfalls im Zuge der Arbeit an dieser Dissertation vorgenommen. - When used on complex scenes, many high quality image synthesis methods encounter problems. These can either be that their calculation times become unacceptable, or that they would require inordinate amounts of memory. Some otherwise perfectly useful methods even suffer from both problems at once. In this context, scene complexity is directly related to the number of geometric primitives used to model the scene. The resource requirements of the image synthesis methods we consider in this work are linked to the number of involved primitives through an at least linear relationship, which leads to the obvious conclusion that a reduction in the number of primitives needed to model a scene is highly desirable. An efficient way of meeting this goal is to use scene description methods with higher descriptive power than the current industry standard of polygonal models. Good choices in this area are the approach of constructive solid geometry and rule based techiques such as L systems. However, these memory saving modeling methods have the disadvantage that so far it has not been possible to use them in conjunction with a particular, highly efficient class of global illumination methods, namely photon tracing algorithms. These techniques calculate the distribution of light in a scene through a stochastic simulation of light propagation. The result of these calculations is stored, and used as a basis for actually displaying the scene in a second step. This two step approach is highly useful and time saving if sequences of images e.g. for animations are to be rendered, since the first photon tracing step is viewpoint independent and only has to be performed once for each scene. However, the useful property of retaining illumination information for later use can turn into a serious problem when complex scenes are considered in that case the memory requirements can grow to such dimensions that use of photon tracing methods becomes totally unfeasible. In this thesis we present three approaches which aim at making the use of photon tracers possible even for complex environments. The first technique aims at reducing the overall scene complexity by making the direct use of CSG models for lightmap based photon tracers possible. The second addresses the problem of large memory requirements for the storage of illumination information on complex objects by introducing a special type of approximative lightmap which is capable of averaging the indirect illumination on entire objects. While this introduces artifacts, the drastic reduction of needed memory can make the otherwise impossible inclusion of complex objects in a photon tracing simulation feasible for the first time. The third extends the second proposal by making it possible to use these approximative data structures even on implicitly defined objects, such as those specified by L systems. In the appendix we cover several aspects of physically correct predictive rendering. While they are not directly related to the improvements presented in this thesis, they are of interest in this context because the capability of performing global illumination calculations where these effects are taken into consideration is one of the advantages of photon tracing methods. Also, the results which are presented in the appendix were obtained during the work on the main topic of the thesis.
Representing and Rendering Distant Objects for Real-Time Visualization
(Wimmer, June 2001) Wimmer, Michael
Computergraphik ist die Wissenschaft, die sich mit der Generierung glaubw¨urdiger Bilder besch¨aftigt. Eine der gr¨oßten Herausforderungen dabei ist, diese Bilder in ausreichender Geschwindigkeit zu erzeugen. Speziell bei der Simulation von Fahrzeugen in Stadtgebieten, bei der virtuellen Erforschung von Geb¨auden (ob noch nicht gebaute, existierende oder schon lange zerst¨orte), bei Computerspielen und vielen anderen Anwendungen ist es wichtig, daß die Bilder in fl¨ussiger Abfolge erscheinen. ¨ Ublicherweise versteht man darunter eine Bildrate von mindestens 60 Bildern pro Sekunde. Das ist das Thema der Echtzeitvisualisierung. In dieser Dissertation werden zwei Algorithmen zur beschleunigten Darstellung von großen virtuellen Szenen vorgestellt. Dabei wird bei beiden Algorithmen eine interessante Eigenschaft von vielen solchen Szenen ausgen¨utzt: Objekte, die sich weiter weg vom Betrachter befinden, machen nur einen kleinen Teil des endg¨ultigen Bildes aus, ben¨otigen aber relativ viel Rechenzeit. In dieser Dissertation wird gezeigt, wie man entfernte Objekte mit einer Komplexit¨at, die der ¨uberdeckten Bildfl¨ache und nicht ihrer eigentlichen geometrischen Komplexit¨at entspricht, repr¨asentieren und darstellen kann. Die beiden Algorithmen sind f¨ur unterschiedliche Szenarien gedacht. Die erste Methode funktioniert zur Laufzeit, braucht also keine Vorberechnung. Die zweite Methode hingegen hat einen wichtigen Vorberechnungsschritt, der bei der Darstellung sowohl die Geschwindigkeit als auch die Qualit¨at signifikant erh¨oht. Der erste Teil der Dissertation besch¨aftigt sich mit einem Algorithmus zur Darstellung von Szenen mit starker gegenseitiger Verdeckung von Objekten. Dabei kommen in mehreren Schritten bildbasierte Renderingmethoden zum Einsatz. Objekte bis zu einer bestimmten Entfernung vom Betrachter werden mit gew¨ohnlichen polygonbasierten Methoden gezeichnet. In einem weiteren pixelbasierten Schritt werden dann alle noch nicht bedeckten Pixel des Bildes identifiziert und in einem zylindrischen Zwischenspeicher f¨ur Farbwerte nachgesehen. Sollte dort kein sinnvollerWert vorhanden sein, wird die Farbe des Pixels mittels eines Blickstrahls ermittelt, sofern sich das Pixel nicht ¨uber dem Horizont befindet. Die Methode funktioniert praktisch unabh¨angig von der Anzahl der verwendeten Objekte in der Szene und erreicht eine bis zu zehnfache Beschleunigung im Vergleich zu ¨ublichen Darstellungsmethoden. Im zweiten Teil der Dissertation wird eine Datenstruktur zur getrennten Speicherung von Geometrie- und Farbinformationen f¨ur ein Objekt pr¨asentiert, geeignet f¨ur die Betrachtung aus einem bestimmten r¨aumlich abgegrenzten Bereich. Damit sollen komplexe Objekte in virtuellen Szenen insbesonders weit entfernte Objekte ersetzt werden, um eine schnellere und qualitativ bessere Darstellung dieser Objekte zu erreichen. Dabei wird das Objekt quasi mit einer Punktwolke dargestellt, deren Dichte sich nach den m¨oglichen Betrachterpositionen richtet. Das Aussehen der Punktwolke wird mittels eines Monte Carlo Verfahrens bestimmt, das eine artefaktfreie Darstellung von allen erlaubten Blickpunkten aus gestattet. Außerdem gibt diese Dissertation einen ausf¨uhrlichen ¨ Uberblick ¨uber schon publizierte Methoden im Bereich der Echtzeitvisualisierung, und enth¨alt eine Analyse ¨uber Vor- und Nachteile von bild- und punktbasierten Renderingmethoden f¨ur die Darstellung von entfernten Objekten. - Computer graphics is the art of creating believable images. The difficulty in many applications lies in doing so quickly. Architectural walkthroughs, urban simulation, computer games and many others require high-quality representation of very large models at interactive update rates. This usually means creating a new image at least 60 times a second. This is what real-time visualization is about. This thesis presents two methods to accelerate the rendering of very large virtual environments. Both algorithms exploit a common property of many such environments: distant objects usually take up a significant amount of computation time during rendering, but contribute only little to the final image. This thesis shows how to represent and render distant objects with a complexity proportional to the image area they cover, and not to their actual complexity. The algorithms are destined for different scenarios: the first is an online algorithm that carries out all computation during runtime and does not require precomputation. The second algorithm makes use of preprocessing to speed up online rendering and to improve rendering quality. The first part of the thesis shows an output-sensitive rendering algorithm for accelerating walkthroughs of large, densely occluded virtual environments using a multi-stage image-based rendering pipeline. In the first stage of the pipeline, objects within a certain distance (the near field) are rendered using the traditional graphics pipeline. In the following stages, the remainder of the scene (the far field), which consists of all pixels not yet covered by near-field geometry, is rendered by a pixel-based approach using a panoramic image cache, horizon estimation to avoid calculating sky pixels, and finally, ray casting. The time complexity of the approach does not depend on the total number of primitives in the scene. We have measured speedups of up to one order of magnitude compared to standard rendering with view-frustum culling. In the second part of the thesis, a new data structure for encoding the appearance of a geometric model as seen from a viewing region (view cell) is presented. This representation can be used in interactive or real-time visualization applications to replace complex models especially distant geometry by an impostor, maintaining high-quality rendering while cutting down on rendering time. The approach relies on an object-space sampled representation similar to a point cloud or a layered depth image, but introduces two fundamental additions to previous techniques. First, the sampling rate is controlled to provide sufficient density across all possible viewing conditions from the specified view cell. Second, a correct, antialiased representation of the plenoptic function is computed using Monte Carlo integration. The system therefore achieves high-quality rendering using a simple representation with bounded complexity. This thesis also contains a comprehensive overview of related work in the field of real-time visualization, and an in-depth discussion of the advantages and disadvantages of image-based and point-based representations for distant objects.
Occlusion Culling for Real-Time Rendering of Urban Environments
(Wonka, June 2001) Wonka, Peter
Diese Dissertation besch¨aftigt sich mit der Visualisierung von dreidimensionalen Stadtmodellen f¨ur Anwendungen wie Stadtplanung und Fahrsimulation. F¨ur eine Simulation ist es wichtig, daß ein Benutzer interaktiv in der Stadt navigieren kann. Dabei versucht man, wie bei einem Film, den Eindruck einer fl¨ussigen Bewegung zu erzeugen. Um dieses Ziel zu erreichen, ist es notwendig, mehrere Bilder pro Sekunde auf einem graphischen Ausgabeger¨at, wie einem Monitor, darzustellen. Die großen Datenmengen, die f¨ur die Visualisierung eines Stadtmodells verarbeitet werden m¨ussen, machen Beschleunigungsverfahren notwendig, um gen¨ugend Bilder pro Sekunde anzeigen zu k¨onnen. Der Beitrag dieser Dissertation sind neue Verfahren der Sichtbarkeitsberechnung, um schnell diejenigen Teile des Stadtmodells zu finden, die von weiter vorne liegenden Teilen verdeckt werden. Die verdeckten Teile liefern keinen Beitrag zu dem erstellten Bild und m¨ussen deshalb nicht von der Graphikhardware weiterverarbeitet werden. Die erzielten Geschwindigkeitsverbesserungen der Darstellung sind in der Gr¨oßenordnung von zehn bis hundertfacher Beschleunigung f¨ur die verwendeten Testszenen. Es werden drei neue Algorithmen vorgestellt: Der erste Algorithmus berechnet die Sichtbarkeit f¨ur jedes neue Bild in einer Simulation. Der Algorithmus berechnet eine konservative Absch¨atzung der Objekte, die vom aktuellen Blickpunkt sichtbar sind, ohne dabei sichtbare Objekte als unsichtbar zu klassifizieren. Einige wenige unsichtbare Objekte k¨onnen allerdings als sichtbar klassifiziert werden. F¨ur die Sichtbarkeitsberechnung wird mit Unterst¨utzung von Graphikhardware ein Bild gezeichnet, das die Sichtbarkeitsinformation codiert. Mit Hilfe dieses Bildes kann man f¨ur Szenenteile schnell feststellen, ob sie unsichtbar sind. Der zweite Algorithmus verwendet Vorberechnungen f¨ur die Sichtbarkeit. Die Szene wird in viele Regionen unterteilt, f¨ur die jeweils eine Liste von sichtbaren Objekten bestimmt wird. Im Gegensatz zum ersten Algorithmus wird aber die Sichtbarkeit von einer Region und nicht von einem Punkt ausgerechnet. Bekannte analytische Verfahren f¨ur dieses Problem sind instabil und zu zeitaufwendig f¨ur gr¨oßere Szenen. Das vorgeschlagene Verfahren zeigt, wie man diese komplexen Berechnungen mit Hilfe von Graphikhardware effizient approximieren kann. Der dritte Algorithmus ist die Grundlage f¨ur ein System, bei dem die Sichtbarkeitsberechnungen paralell zur Darstellung durchgef¨uhrt werden k¨onnen. Diese k¨onnen somit auf einem anderen Rechner, einem Server, ausgef¨uhrt werden, der das Ergebnis der Sichtbarkeitsberechnung dann ¨uber das Netzwerk kommuniziert. Dieses paralelle Verfahren erlaubt es, ohne Vorberechnungen schnelle Simulationen zu erstellen. - This thesis makes a contribution to the field of three-dimensional visualization of urban environments, for applications like urban planning and driving simulation. In a simulation system a user interactively navigates through virtual cities in real-time. To give the impression of fluid motion, high frame rates are necessary, and new images have to be rendered several times each second. To cope with the large amounts of data, acceleration algorithms have to be used to sustain high frame rates. The contributions of this thesis are new algorithms for occlusion culling, that is to quickly identify parts of the scene that are occluded by other objects. These parts are invisible and therefore do not need to be sent to the graphics hardware. This thesis contains three new algorithms: The first algorithm calculates occlusion culling online for each frame of a walkthrough. The algorithm computes a tight superset of objects that are visible from the current viewpoint. Graphics hardware is exploited to be able to combine a large number of occluders. In contrast to other approaches, an occlusion map is calculated using an orthographic projection to obtain smaller algorithm calculation times. The second algorithm precalculates visibility. The scene is discretized into view cells for which cellto- object visibility is precomputed, making online overhead negligible. This requires the calculation of occlusion from a region in space. The occlusion boundaries from a region are complex, and analytical computation methods are not very robust and do not scale to the large scenes we envision. We demonstrate how to approximate those complex occlusion boundaries using simple point sampling and occluder shrinking. This approximation is conservative and accurate in finding all significant occlusion and occluder interactions. The third algorithm calculates occlusion in parallel to the rendering pipeline. We show how to use point visibility algorithms to quickly calculate a tight potentially visible set which is valid for several frames, by shrinking the occluders by an adequate amount. These visibility calculations can be performed on a visibility server, possibly a distinct computer communicating with the display host over a local network. The resulting system essentially combines the advantages of online visibility processing and region-based visibility calculations, in that it is based on a simple online visibility algorithm, while calculating a visibility solution that remains valid for a sufficiently large region of space.

Browse

Recent Submissions

Results Per Page

Sort Options