Culling out non-visible portions of 3D scenes is important for rendering large complex worlds at an interactive frame rate. Past 3D engines used static prebaked visibility data which was generated using complex algorithms. Hardware Occlusion Queries are a modern feature that allows engines to determine if objects are invisible on the fly. This allows for fully dynamic destructible and editable environments as opposed to static prebaked environments of the past. This paper presents an algorithm that uses Hardware Occlusion Queries to cull fully dynamic scenes in real-time. This algorithm is relatively simple in comparison to other real-time occlusion culling techniques, making it possible for the average developer to render large detailed scenes. It also requires very little work from the artists who design the scenes since no portals, occluders, or other special objects need to be used.

Real-time rendering of massive 3D models has been recognized as a challenging task due to the limited computational power and memory available in a workstation. Most existing acceleration techniques, such as mesh simplification algorithms with hierarchical data structures, suffer from the nature of sequential executions. As data complexity increases due to the fundamental advances in modeling and simulation technologies, 3D models become complex and require gigabytes in storage. Consequently, visualizing such large datasets becomes a computationally intensive process where sequential solutions are unable to satisfy the demands of real-time rendering. Recently, the Graphics Processing Unit (GPU) has been praised as a massively parallel architecture not only for its significant improvements in performance but also because of its programmability for general-purpose computation. Today's GPUs allow researchers to solve problems by delivering fine-grained parallel implementations. In this dissertation, I concentrate on the design of parallel algorithms for real-time rendering of massive 3D polygonal models towards modern GPU architectures. As a result, the delivered rendering system supports high-performance visualization of 3D models composed of hundreds of millions of polygons on a single commodity workstation. / Ph. D.

In this report, an object-space solution to occluder fusion of OBB occluders is explored. Two different approaches are considered were the object-space fusion is reduced to a 2D problem. The first approach finds axis-aligned silhouettes within the projection of occluder OBBs which are then fused together creating large axis-aligned silhouettes. The other approach creates concave hulls of the projected OBB silhouettes from which convex inscribed silhouettes are then found. These silhouettes are then converted back to object-space where shadow frusta created around the silhouettes are used for the culling operation. The effectiveness of the two approaches is evaluated considering the amount of culled geometry. It is shown that fused convex silhouettes are needed to produce competitive results.

La synthèse d'images, qui consiste à développer des algorithmes pour générer des images à l'aide d'un ordinateur, est devenue incontournable dans de nombreuses disciplines. Les méthodes d'affichage interactives permettent à l'utilisateur d'explorer des environnements virtuels en réalisant l'affichage des images à une cadence suffisamment élevée pour donner une impression de continuité et d'immersion. Malgré les progrès réalisés par le matériel, de nouveaux besoins supplantent toujours les capacités de traitement, et des techniques d'accélération sont nécessaires pour parvenir à maintenir une cadence d'affichage suffisante. Ce travail s'inscrit précisemment dans ce cadre. Il est consacré à la problématique de l'élimination efficace des objets masqués, en vue d'accélérer l'affichage de scènes complexes. Nous nous sommes plus particulièrement intéressé aux méthodes de précalcul, qui effectuent les calculs coûteux de visibilité durant une phase de prétraitement et les réutilisent lors de la phase de navigation interactive. Les méthodes permettant un précalcul complet et exact sont encore hors de portée à l'heure actuelle, c'est pourquoi des techniques approchées leur sont préférée en pratique. Nous proposons trois méthodes de ce type. La première, présentée dans le chapitre 4, est un algorithme permettant de déterminer de manière exacte si deux polygones convexes sont mutuellement visibles, lorsque des écrans sont placés entre eux. Nos contributions principales ont été de simplifier cette requête, tant du point de vue théorique que du point de vue de l'implémentation, ainsi que d'accélérer son temps moyen d'exécution à l'aide d'un ensemble de techniques d'optimisation. Il en résulte un algorithme considérablement plus simple à mettre en oeuvre que les algorithmes exacts existant dans la littérature. Nous montrons qu'il est également beaucoup plus efficace que ces derniers en termes de temps de calcul. La seconde méthode, présentée dans le chapitre 5, est une approche originale pour encoder l'information de visibilité, qui consiste à stocker l'ombre que générerait chaque objet de la scène s'il était remplacé par une source lumineuse. Nous présentons une analyse des avantages et des inconvénients de cette nouvelle représentation. Finalement, nous proposons dans le chapitre 6 une méthode de calcul de visibilité adaptée aux scènes d'intérieur. Dans ce type d'environnements, les graphes cellules-portails sont très répandus pour l'élimination des objets masqués, en raison de leur faible coût mémoire et de leur grande efficacité. Nous reformulons le problème de la génération de ces graphes en termes de segmentation d'images, et adaptons un algorithme classique, appelé «watershed», pour les obtenir de manière automatique. Nous montrons que la décomposition calculée de la sorte est proche de la décomposition classique, et qu'elle peut être utilisée pour l'élimination des objets masqués.

Virtual crowd rendering have been used in film industry with offine rendering methods for a long time. But its existence in interactive real-time applications such as video games is not so common due to the limited rendering power of current graphics hardware. This thesis describes a novel method to improve shadow mapping performance of a crowded scene by taking into account the screen space visibility of the casted shadow of a crowd instance when rendering the shadow maps. A grid-based visibility mask creation method is proposed which is irrelevant to scene complexity. This improves the rendering performance especially when there are many occluded instances of the crowd which is a common scenario in urban environments and accelerates the usage of crowds in real time applications, such as games. We compute visibility of all agents in a crowd in parallel on the graphics processing unit(GPU) without having a requirement of a stencil buer or light direction dependent shadow mask. Technique also improves the view space rendering time by reducing the visibility check cost of the agents that are located on the invisible areas of the scene. The methodology introduced in this thesis gets more effective in each shadow map rendering pass by re-using the same visibility mask for shadow caster culling and enables many local lights with shadows. We also give a brief information about the state of the art of crowd rendering and shadowing, explaining how suitable the method with the implementations of different shadow mapping approaches. The technique is very well compatible with the modern crowd rendering techniques such as skinned instancing, dynamic level of detail(LOD) determination and GPU-based simulation.

Diese Arbeit beschreibt den Entwurf und die Funktionsweise einer parallelen OpenGL-Renderingschnittstelle, die den effizienten Betrieb unmodifizierter graphischer Anwendungen auf segmentierten Anzeigen ermöglicht. Diese Schnittstelle integriert sich vollständig in eine verteilte graphische Benutzeroberfläche. Die herausragende Eigenschaft der entwickelten parallelen OpenGL-Schnittstelle ist ihre gleich bleibende Bildrate bei wachsender Anzahl von Segmenten. Als Erweiterung des frei verfügbaren Chromium-Systems stellt die Implementation eine virtuelle Graphikpipeline mit der Gesamtauflösung der segmentierten Anzeige bereit, die den eingehenden Datenstrom über ein Kommunikationsnetzwerk an die Knoten eines Visualisierungsclusters überträgt. Jeder Knoten des Clusters rendert einen Ausschnitt des Gesamtbildes und bringt diesen auf dem zugehörigen Segment synchronisiert zur Anzeige. Die interne Verarbeitung der von der Applikation generierten OpenGL-Datenströme unterscheidet sich jedoch grundlegend von der existierenden Lösung. Während die Tilesort-SPU von Chromium die Daten entsprechend der Segmentierung der Anzeige sortiert und sequenziell an die relevanten Knoten versendet, überträgt die in der Arbeit vorgestellte Schnittstelle die Graphikbefehle simultan. Die dadurch erreichte Vermeidung redundanter Übertragungen bewirkt bereits einen besseren Durchsatz der Kommunikationskanäle und zusätzlich eine signifikante Verringerung der Prozessorbelastung des Applikationsrechners. Die freie gewordene Kapazität schafft wiederum die Voraussetzung für die Anwendung verschiedener Optimierungsverfahren zur weiteren Steigerung der graphischen Gesamtleistung der parallelen Schnittstelle. Dazu zählt neben der Zwischenspeicherung von Datensequenzen in einem Stream Cache die Filterung der OpenGL-Kommandoströme mit graphischen Culling-Verfahren. Speziell zum aktiv-stereoskopischen Rendern auf dem an der Professur vorhandenen zylindrischen Projektionssystem enthält die Schnittstelle Anpassungen für die Synchronisationshardware und die bildbasierte Korrektur der Parallaxe.

Für die schnelle Visualisierung großer Modelle werden sogenannte Echtzeit-Visualisierungsverfahren (real time rendering techniques) eingesetzt. Durch parallele Verarbeitung der Objektdaten auf Multicore-CPUs ist es möglich, die Geschwindigkeit der Darstellung gegenüber GPU-basierten Verfahren weiter zu erhöhen. Insbesondere wurde die Möglichkeit untersucht, das Occlusion-Culling mit Hilfe der CPU durchzuführen. Dabei konnte speziell das Worst-Case-Verhalten verbessert werden. Mit der Anzahl der Systemkomponenten (z.B. Trackingsystem, Beamer, Rechner) steigt die Trägheit (Latenz) des Gesamtsystems, was eine Echtzeitverarbeitung der Daten deutlich erschwert. Durch Bewegungsvorhersagen, die speziell an das Nutzerverhalten im Rahmen der Anwendung angepasst sind, können auftretende Latenzen kompensiert werden. Die Entwicklungen erfolgten im Kontext einer immersiven Tischtennissimulation. Tischtennis gehört zu den schnellsten Sportarten und repräsentiert somit eine anspruchsvolle Umgebung. Ein weiterer wichtiger Aspekt bei der Interaktion mit virtuellen Umgebungen ist die Natürlichkeit (Intuitivität) der Benutzeroberfläche. Durch eine möglichst direkte (aus der Realität bekannte) Umsetzung der Benutzerbewegungen in Systembefehle wird eine höchstmögliche Effektivität im Umgang mit dem System erzielt. Im Rahmen einer Designanwendung wurden Interaktionstechniken realisiert, die den alltäglichen Bewegungsabläufen nachempfunden sind.

[pt] Um dos problemas mais antigos da computação gráfica tem sido a determinação de visibilidade. Vários algoritmos têm sido desenvolvidos para viabilizar modelos cada vez maiores e detalhados. Dentre estes algoritmos, destaca-se o frustum culling, cujo papel é remover objetos que não sejam visíveis ao observador. Esse algoritmo, muito comum em várias aplicações, vem sofrendo melhorias ao longo dos anos, a fim de acelerar ainda mais a sua execução. Apesar de ser tratado como um problema bem resolvido na computação gráfica, alguns pontos ainda podem ser aperfeiçoados, e novas formas de descarte desenvolvidas. No que se refere aos modelos massivos, necessita-se de algoritmos de alta performance, pois a quantidade de cálculos aumenta significativamente. Este trabalho objetiva avaliar o algoritmo de frustum culling e suas otimizações, com o propósito de obter o melhor algoritmo possível implementado em CPU, além de analisar a influência de cada uma de suas partes em modelos massivos. Com base nessa análise, novas técnicas de frustum culling serão desenvolvidas, utilizando o poder computacional da GPU (Graphics Processing Unit), e comparadas com o resultado obtido apenas pela CPU. Como resultado, será proposta uma forma de frustum culling híbrido, que tentará aproveitar o melhor da CPU e da GPU. / [en] The definition of visibility is a classical problem in Computer Graphics. Several algorithms have been developed to enable the visualization of huge and complex models. Among these algorithms, the frustum culling, which plays an important role in this area, is used to remove invisible objects by the observer. Besides being very usual in applications, this algorithm has been improved in order to accelerate its execution. Although being treated as a well-solved problem in Computer Graphics, some points can be enhanced yet, and new forms of culling may be disclosed as well. In massive models, for example, algorithms of high performance are required, since the calculus arises considerably. This work analyses the frustum culling algorithm and its optimizations, aiming to obtain the state-of-the-art algorithm implemented in CPU, as well as explains the influence of each of its steps in massive models. Based on this analysis, new GPU (Graphics Processing Unit) based frustum culling techniques will be developed and compared with the ones using only CPU. As a result, a hybrid frustum culling will be proposed, in order to achieve the best of CPU and GPU processing.

The purpose of this thesis is to present methods for visibility determination and to design and implement an application to demonstrate visibility determination in a 3D maze.

This work is focusing on optimization of large scale terrain rendering. It explains basic methods and data structures for optimization. It describes fundamentals of methods such as ROAM, Geometrical clipmaps, GPU Based Geometrical Clipmaps, GeoMipMapping and Chunked LOD. It explains implementation details of system for terrain optimization based on GeoMipMapping method.