Effiziente Verarbeitung komplexer Signale der Computergraphik mittels nichtperiodischer Parkettierung
Zusammenfassung der Projektergebnisse
Kachelbasierte Methoden in der Computergrafik basieren auf der Idee, große Mengen komplexer Inhalte – wie etwa Bildinformationen in Form von Texturen oder Punktmengen mit gewissen Eigenschaften – über eine kleine Menge sich nicht wiederholender Kacheln zusammenzusetzen, was sowohl Speicherplatzersparnisse als auch die effiziente Generierung komplexer Inhalte ermöglicht. Zu Beginn des Projekts war dies nur zur Generierung von homogenen, d.h. istotropen Ergebnissen ohne variierenden Inhalt möglich. Zum einen weil die Kacheln selbst nur isotrop gefüllt waren, zum anderen weil die resultierenden Parkettierungen lediglich stochastischen Charakter hatten. Das rein zufällige Anordnen der Kacheln verhindert aber eine globale Inhaltskontrolle und kann zudem zu lokalen Wiederholungsartefakten führen. Auf diese Probleme gingen die frühen Arbeitspakete des Projekts ein, die Fragen zu Qualität und Größe der Kachelmengen, nach der Generierung von variierendem Inhalt und zur Hierarchisierung des Parkettierungsprinzips stellten. Während des Projekts konnten wir in allen drei Bereichen Fortschritte erzielen. So konnten wir eine Optimierungsmethode für Punktmengen auf Basis von kapazitätsbeschränkten Voronoidiagrammen vorstellen und eine neuartige Parkettierungsmethode auf Basis einer quasi-Monte Carlo Sequenz. Erstere verbesserte den Stand der Technik in Bezug auf die Dichtefunktionsanpassung von Punktmengen, letztere führt zu einer deutlichen Verbesserung der Bildqualitäten von synthetisierten Texturen. Bei gleichzeitig kleineren Kachelmengen ist die Methode weniger anfällig für lokale Wiederholungsartefakte als bisherige rein stochastische Methoden. Wir stellten außerdem eine zweite Methode vor, die eine Synthese von Texturen mit variierendem Inhalt erlaubt, ohne dabei die Anzahl der Kacheln kombinatorisch explodieren zu lassen, und darüber hinaus ist es uns gelungen, Lösungen für das sogenannte Packungsproblem von Eckkacheln zu finden. Die späteren Arbeitspakete des Projekts konzentrierten sich daher auf die effiziente Generierung von irregulären Punktmengen, die für viele Kernprobleme der Computergrafik von Wichtigkeit sind. Die Herausforderung bestand darin, solche Punktanordnungen zu finden, die keiner Gitterstruktur ähneln, aber dennoch hohe Abstände aufweisen. Für Probleme wie das Abtasten der Bildebene oder die effiziente numerische Approximation von Integralen in der „globalen Beleuchtung“ verbessern unsere distanzoptimierten Punktmengen bisherige Methoden. Zu den schönsten Ergebnissen zählte die Widerlegung der Vermutung, dass Punktmengen mit hohen Mindestabständen schnell einer regulärer Anordnung folgen müssen. Als schwierig gestaltete sich die Verallgemeinerung unserer Ergebnisse auf den dreidimensionalen Fall. Unsere Arbeit nutzt eine spezielle Form von Kacheln mit farbkodierten Ecken, deren Prinzip sich mit den von uns gefundenen Parkettierungsmethoden leicht ins Dreidimensionale erweitern lässt. Allerdings ist das Füllen der nun farbkodierten Würfel deutlich schwieriger als das Füllen zweidimensionaler Kacheln. Volumentexturen oder Geometrie ließen sich nicht auf eine ähnlich effiziente und kontrollierte Weise generieren wie ihre zweidimensionalen Pendants. Insbesondere steigt die Anzahl der notwendigen Parkettierungselemente mit der Dimension, so dass kachelbasierte Methoden zunehmend unattraktiver werden.
Projektbezogene Publikationen (Auswahl)
- Capacity-Constrained Point Distributions: A Variant of Lloyd's Method. ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 28(3), p. 86:1–10, 2009
M. Balzer, T. Schlömer, O. Deussen
- Semi-Stochastic Tilings for Example-Based Texture Synthesis. Computer Graphics Forum (Eurographics Symposium on Rendering), Vol. 29, No. 4, 2010
T. Schlömer, O. Deussen
- Accurate Spectral Analysis of Two-Dimensional Point Sets. Journal of Graphics, GPU, and Game Tools, 15(3):152−160, 2011
T. Schlömer, O. Deussen
- Farthest-Point Optimized Point Sets with Maximized Minimum Distance. Proc. High Performance Graphics, 135−154, 2011
T. Schlömer, D. Heck, O. Deussen
- Loose Capacity-Constrained Representatives for the Qualitative Visual Analysis in Molecular Dynamics. PacificVis '11: Proc. IEEE Pacific Visualization Symposium, 51−58, 2011
S. Frey, T. Schlömer, S. Grottel, C. Dachsbacher, T. Ertl, O. Deussen
- Non-Periodic Corner Tilings in Computer Graphics. Dissertation, Universität Konstanz, Juli 2012
T. Schlömer
- Blue Noise Sampling with Controlled Aliasing ACM Transactions on Graphics, 32(3), Article 25, 2013
D. Heck, T. Schlömer, O. Deussen
