Sampled and prefiltered anti-aliasing on parallel hardware

Abstract

Die Erzeugung zweidimensionaler Bilder zählt zu den grundlegenden Aufgaben der Computergrafik. Bedeutende Beispiele sind die Umwandlung von Text oder dreidimensionalen Szenen in ein Format, das sich zur Ausgabe auf einem Rasterdisplay eignet. Eine solche Konvertierung - oft Rasterisierung oder Sampling genannt - unterliegt inhärenten Limitierungen, die sich in der Natur des Ausgabeformates begründen. Dies bewirkt nicht nur einen Informationsverlust im Rasterisierungsresultat, der sich einer Reduktion der Bildschärfe äußert, sondern verursacht auch eine Verfälschung der verbleibendend Information in Form von Aliasingartefakten. Gängige Beispiele sind Treppenmuster an Objektsilhouetten oder Moiré-artige Muster. Das Hauptaugenmerk der hier vorliegenden Dissertation ist die effiziente Behebung ebendieser Artefakte - ein Vorgang, der üblicherweise als Anti-Aliasing bezeichnet wird. Dies wird durch ein Entfernen der unzulässigen Eingangsinformation während der Rasterisierung mithilfe einer Filterung erreicht. Wir präsentieren in dieser Dissertation verschiedene Ansätze, die ihr Hauptaugenmerk entweder auf eine Minimierung des Rechenaufwandes oder auf maximale Ausgabequalität legen. Wir folgen der ersten Zielsetzung in einer Anwendung aus der medizinischen Visualisierung, in der wir die Inspektion von Blutsgefäßinnenräumen von komplexe Gefäßanordnungen unterstützen, indem wir eine beliebige Betrachtungsrichtung ermöglichen. Verdeckungen von überlappenden Gefäßen werden durch das automatisierte Einfügen von Ausschnitten minimiert, wofür eine Verdeckungskostenfunktion eingesetzt wird. Darüber hinaus wird eine Erweiterung der Blutgefäßschnitte in das umliegende Gewebe ermöglicht. Mittels einem detailgradbasierendem Verfahren werden die Schnitte mit steigender Distanz von ihrem zugehörigen Gefäß graduell geglättet. Eine interaktive Reaktionszeit unserer Implementation wird durch eine Kombination von Sichtbarkeitssampling, Schattierungssupersampling und nachträglicher Filterung ermöglicht. Im Weiteren nehmen wir einen anderen Ansatz und entwickeln die theoretischen Grundlagen für Anti-Aliasing Methoden, die der zweiten Zielsetzung eines Höchstgrades an Ausgabequalität folgen. Als Hauptbeitrag in diesem Zusammenhang präsentieren wir exaktes Anti-Aliasing in der Form von Präfilterung. Durch das Berechnen geschlossener Lösungen der auftretenden Filterungsfaltungen im Kontinuierlichen, umgehen wir sämtliche Problematiken, die sich durch numerische Integrationsansätze ergeben, und bieten mathematisch korrekte Resultate. Zusammen mit einer parallelen Elimination versteckter Oberflächen, die alle verdeckten Objektteile bei der Rasterisierung dreidimensionaler Szenen entfernt, präsentieren wir eine Referenzlösung für dieses Szenario mittels exaktem Anti-Aliasing. Weiters ermöglichen wir die Verwendung von komplexen Beleuchtungsmodellen und perspektivisch korrekter Schattierung indem Sichtbarkeitspräfilterung mit Schattierungsampling kombiniert wird; woraus eine Referenzlösung für Multisampling-Anti-Aliasing abgeleitet werden kann. Sämtliche obengenannten Methoden weisen hochparallele Berechnungslasten auf. Daraus folgend, präsentieren wir im Zuge der gesamten Dissertation deren Abbildung auf massiv-parallele Hardwarearchitekturen in der Form von Grafikprozessoren. Da unsere Ansätze nicht auf herkömmlichen Grafikpipelines umzusetzen sind, implementierten wir sie mithilfe von generellen Berechnungskonzepten. Dies schlägt sich in reduzierten Laufzeiten nieder und ermöglicht die Interaktivität all unserer Methoden.

A fundamental task in computer graphics is the generation of two-dimensional images. Prominent examples are the conversion of text or three-dimensional scenes to formats that can be presented on a raster display. Such a conversion process - often referred to as rasterization or sampling - underlies inherent limitations due to the nature of the output format. This causes not only a loss of information in the rasterization result, which manifests as reduced image sharpness, but also causes corruption of the retained information in form of aliasing artifacts. Commonly observed examples in the final image are staircase artifacts along object silhouettes or Moiré-like patterns. The main focus of this thesis is on the effective removal of such artifacts - a process that is generally referred to as anti-aliasing. This is achieved by removing the offending input information in a filtering step during rasterization. In this thesis, we present different approaches that either minimize computational effort or emphasize output quality. We follow the former objective in the context of an applied scenario from medical visualization. There, we support the investigation of the interiors of blood vessels in complex arrangements by allowing for unrestricted view orientation. Occlusions of overlapping blood vessels are minimized by automatically generating cut-aways with the help of an occlusion cost function. Furthermore, we allow for suitable extensions of the vessel cuts into the surrounding tissue. Utilizing a level of detail approach, these cuts are gradually smoothed with increasing distance from their respective vessels. Since interactive response is a strong requirement for a medical application, we employ fast sample-based anti-aliasing methods in the form of visibility sampling, shading supersampling, and post-process filtering. We then take a step back and develop the theoretical foundations for anti-aliasing methods that follow the second objective of providing the highest degree of output quality. As the main contribution in this context, we present exact anti-aliasing in the form of prefiltering. By computing closed-form solutions of the filter convolution integrals in the continuous domain, we circumvent any issues that are caused by numerical integration and provide mathematically correct results. Together with a parallel hidden-surface elimination, which removes all occluded object parts when rasterizing three-dimensional scenes, we present a ground-truth solution for this setting with exact anti-aliasing. We allow for complex illumination models and perspective-correct shading by combining visibility prefiltering with shading sampling and generate a ground-truth solution for multisampling anti-aliasing. All our aforementioned methods exhibit highly parallel workloads. Throughout the thesis, we present their mapping to massively parallel hardware architectures in the form of graphics processing units. Since our approaches do not map to conventional graphics pipelines, we implement our approach using general-purpose computing concepts. This results in decreased runtime of our methods and makes all of them interactive.