Computergraphik - WS 18/19

Diese Vorlesung soll eine Einführung in die theoretischen und methodischen Grundlagen der Computergraphik geben, als auch die Grundlagen für die praktische Implementierung von computergraphischen Systemen legen.

Der Schwerpunkt liegt auf Algorithmen und Konzepten zur Repräsentation und Visualisierung von polygonalen, 3-dimensionalen graphischen Szenen. Die Übungsaufgaben werden teils theoretisch, teils praktisch sein, wobei die praktischen Aufgaben gewisse Programmierfähigkeiten in C++ verlangen. Ich empfehle den Besuch des "Propädeutikums C/C++" vor der Computergraphik-Vorlesung. Die theoretischen Aufgaben setzen teilweise einfache Matrix-Vektor-Rechnung voraus.

Bemerkung: in der Vorlesung wird nicht die Benutzung von fertiger Software zur Modellierung, Animation, oder Bildbearbeitung (z.B. Photoshop, Blender, Maya, Cinema4D, etc.) behandelt! Wir beschäftigen uns mit den Algorithmen, die hinter diesen Programmen stecken.

Aus dem Inhalt:

1. Gerätetechnische Grundlagen
2. Mathematische Grundlagen
3. OpenGL 3 and C++
4. 2D Algorithmen der Computergraphik (Scan Conversion, Visibility Computations, etc.)
5. Theorie der Farben und Farbräume
6. 3D Algorithmen der Computergraphik (Rendering Pipeline, Transformationen, Beleuchtung, etc.)
7. Techniken zum Echtzeit-Rendering
8. Shader
9. Texturierung

Aktuelles

Folien

Die folgende Tabelle wird die behandelten Themen und die dazugehörigen Folien enthalten.

Woche	Thema	Folien	Übungsaufgaben	Frameworks
1.	Organisation, Einführung, Geschichte, Display-Technologien und -Technik 1: Raster- und Vektor-Graphik, Critical Flicker Frequency, Buffering-Varianten (double buffering, triple buffering), Synchronisation-Verfahren( VSYNC, GSYNC, et al.),	PDF1 PDF2	Blatt1 Tutorium-Folien QtCreator-Installation	OpenGL-"Hello World"
2.	Display-Technologien und -Technik 2: Display-Technologien (CRT, LCD, DLP), Gammakorrektur, Geometrie 1: geometrische Bedeutung des Skalar- und Kreuzproduktes, Koordinatensysteme, Flächeninhalt von Dreieck und Polygonen	PDF	Blatt2	Matrix
3.	Geometrie 2: geometrische Prädikate, Konvexität, Volumen von Spat und Tetraeder, parametrische Darstellung von Linie und Ebene, lineare Interpolation, implizite Ebenengleichung, Dreiecke.	PDF	C++ Crash Course	Aufgabe 1, 2, 3, 4 Lösung 1, 2, 3, 4
4.	Übersicht über die Graphik-Pipeline, verschiedene Sichtweisen der Pipeline. Einführung in OpenGL: programmable Pipeline, Shader, immediate mode versus retained mode, vertex array objects, vertex buffer objects.	PDF	Blatt3	Edges
5.	Rasterisierung von Linien: Midpoint-Algorithmus, Interpolation entlang der Linie, Span-basierte Scanline-Conversion, Anwendung auf Raycasting zum Terrain-Rendering, Anwendung auf Continuous Collision Detection mit Voxmap-Pointshell-Verfahren, scan conversion of circles.	PDF	Blatt4	Midpoint
6.	Visibility Computations: Painter's Algorithm, Z-Buffer, Z-Fighting, Depth-of-Field, Depth Complexity & Overdraw, Hierarchischer Z-Buffer, Implementierung in Hardware, Object-Space- & Image-Space-Algorithmen, BSP-Tree, depth sorting using BSP, camera collision detection using BSP, Warnock's Algorithmus & Quadtree, Stencil-Buffer, Rendering planar reflections using the stencil buffer, Schatten-Rendering mittels Shadow Volumes.	PDF	Blatt5	BSP Framework
7.	Baryzentrische Koordinaten: affine Kombinationen, affine Abbildungen, konvexe Hülle, baryzentrische Koordinaten im Dreieck, Berechnungsmethoden, baryzentrische Interpolation, Anwendungen (Kürzeste Distanz Punkt-Dreieck, Punkt-in-Dreieck-Test, Dreieck-Dreieck-Schnittest, Mesh Simplification)	Videos PDF	Blatt6
8.	Polygon Scan Conversion: Rasterisierung von Dreiecken, Algorithmus von Pineda, Parallelisierung (und die Pixel-Planes-Story). Füllen nicht-einfacher Polygone, Odd-Even-Rule, Winding-Number-Rule, Verallgemeinerung. Flood Fill. Triangulation: ein O(n log n) Algorithmus, Art Gallery Theorem, Font-Rendering: Grundbegriffe, Outlines mittels Bezier-Kurven, Flag-Fill-Algorithmus von Ackland, Hinting.	PDF	Blatt7	Pineda
9.	Farben: Licht, Lichtquellen, Chromatizität, Reflectance spectrum, das Auge, Human Spectral Sensitivity, wahrgenommener Stimulus, Metamere, Grassmann'sche Experimente und Gesetze, wahrgenommene Gleichheit von Spektren, die "Sensor-Abbildung", Definition des Begriffes "Farbe", CIEXYZ-Farbraum, matching curves, Chromatizitätsdiagramm, Gegenfarbenmodell, Farbmodelle RGB, CMY, HSV, Abstand zwischen Farben, uniforme Farbräume, CIE Lab-Farbraum, Gamut,	PDF	Blatt8
10.	Transformationen: Koordinatensysteme in der Pipeline, elementare Rotation, Skalierung, Scherung, Spiegelung, Concatenation, Euler-Winkel, Gimbal Lock, Rotation um beliebige Achse mittels Basiswechsel, Zerlegung einer Rotationsmatrix, Quaternionen, Darstellung und Durchführung von Rotationen mittels Quaternionen, Interpolation von Orientierungen mittels Quaternionen, virtueller Trackball, affine Abbildungen, homogene Koordinaten, Translation, Anatomie einer Matrix, starre Transformationen, Berechnung einer Rot.matrix für beliebige Achse+Winkel im Raum, Klassifikation aller Transformationen, Matrizen in OpenGL, relative/hierarchische Transformationen, Objekthierarchien und Matrix-Stack.	Videos PDF	Blatt9	Transformation
11.	Projektionen & Perspektive: Kamera-Transformation, orthographische Projektion, perspektivische Projektion, Eigenschaften der perspektivischen Projektion, allgemeine projektive Abbildungen, Projektion in OpenGL Lighting & Shading 1: Arten von Lichtquellen, diffuse Reflexion, spiegelnde Reflexion, Phong-Beleuchtungsmodell, Blinn-Phong-Modell, BRDF's, Lafortune-Modell, Flat-/Gouraud-/Phong-Shading, Mach-Bänder, Per-Pixel-Shading,	PDF1 PDF2	Blatt10	Billiard Framework
13.	Shader Programming: fixed-function pipeline, programmable pipeline, vertex processor, fragment processor, Einführung in GLSL, Uniform- und Attribut-Variablen, Geometrie-Modifikation, Toon- and Gooch-Shader, Per-Pixel-Lighting, Texturierung: Übersicht, diskrete & prozedurale Texturen, formale Definition, Texturkoordinaten (stückweise lineare Parametrisierung), Texturkoordinaten-Interpolation (nur linear), Modulation der Beleuchtung durch Texturen,	PDF1 PDF2

Literatur

Folgende Literatur eignet sich als begleitende Literatur:

• Peter Shirley: Fundamentals of Computer Graphics; 2nd Edition, AK Peters.
• Hearn, Baker, Carithers: Computer Graphics with OpenGL; 4th edition, Pearson
• Foley, van Dam, Feiner, Hughes: Computer Graphics -- Principles and Practice; Addison Wesley.
• Eric Lengyel: Mathematics for 3D Game Programming and Computer Graphics. Cengage Learning PTR.
  Enthält gute Kapitel zu Geometrie, Lighting and Shading, Visibility, Schatten, und Transformationen.
• Fletcher Dunn and Ian Parberry: 3D math primer for graphics and game development; A K Peters/CRC Press. Taylor & Francis Group.
  Eine sehr einfache, und gleichzeitig unterhaltsame Einführung in 3D-Vektor-Algebra. Als E-Book in der Uni-Bibliothek erhältlich, oder zum Reinschauen im Handapparat der Arbeitsgruppe CGVR. (Das Buch enthält einige wenige Errata.)
• David C. Lay: Linear Algebra and its Applications; Pearson.
• Banesh Hoffmann: About Vectors; Dover Publications.
  Sehr angenehm zu lesen, fängt ganz unten an und arbeitet sich langsam bis zu Quaternionen und Tensoren hoch.
• David F. Rogers: Procedural Elements for Computer Graphics; 2nd Edition, McGraw-Hill.
• Tomas Akenine-Möller, Eric Haines: Real-Time Rendering; AK Peters.
• J. L. Encarnação, W. Strasser, R. Klein: Graphische Datenverarbeitung 1 und 2. Oldenbourg, 1996
• Alan Watt: 3D Computer Graphics; Addison-Wesley.
• Bender & Brill: Computergrafik; Hanser.
• Dave Shreiner: OpenGL Programming Guide: The Official Guide to Learning OpenGL; Addison-Wesley Educational Publishers, Version 3.0, 3.1, oder 4.1. Achtung: die neueste Ausgabe passt nicht 100%-ig zur Vorlesung, sie ist daher nur für OpenGL-Fortgeschrittene brauchbar.
• Satyan L. Devadoss, Joseph O'Rourke: Discrete and Computational Geometry. Princeton University Press. (Kapitel 1 zum Thema Triangulation)

Falls Sie sich diese Bücher anschaffen möchten sollten Sie vielleicht überlegen, gebrauchte Exemplare zu erwerben -- oft gibt es diese zu einem Bruchteil des Neupreises. Zwei gute Internetadressen sind Abebooks und BookButler.

Übungsbetrieb

Die Übungsblätter werden jeweils am Montag auf der Homepage der VL (also hier) ins Netz gestellt.

Die Abgabe der Lösungen ist jeweils am Sonntag bzw. eine Woche später per Git. Bitte erstellt Euch Eures Repository beim gitlab.informatik.uni-bremen.de und uns (mkalusch und toni) als Developer einladen. Die Korrektur laden wir direkt in eures Repo hoch.

Hinweise zur Klausur

Die Klausur ist "closed book, open notes", d.h., während der Klausur sind erlaubt:

• 3 DIN-A4 Blätter eigenhändig beschriftet (Vorder- und Rückseite)
• Getränk

Außer diesen Dingen darf sich sonst nichts auf dem Tisch befinden, insbesondere nicht erlaubt sind:

• Kein weiteres eigenes Papier
• Keine sonstigen Unterlagen, Bücher, etc.
• Kein Handy, keine Smartwatch, kein Taschenrechner, kein Laptop, etc.

Hier findet Ihr einige Probeklausuren. (Etliche sind auf Englisch, die richtige Klausur wird natürlich auf Deutsch sein.) Der ZIP-File ist Passwort-geschützt -- Ihr bekommt das Passwort von Eurem Tutor oder Professor.
Bitte lasst euch nicht von einer eventuell leicht abweichenden Terminologie irritieren. Es gilt in der Klausur immer die Terminologie, die ich eingeführt habe. Lasst Euch bitte auch nicht von der Fülle der Probeklausuren einschüchtern. Ihr müsst sicherlich nicht alle durchrechnen, um fit zu werden.

Online Literatur und Links zum Programmieren in C/C++ und in OpenGL

• Ein Kompaktkurs zu C mit Beispielen in OpenGL.
• Tutorials/Bücher zu C++ :
  • C++ Tutorial (Quelle); fängt von ganz unten an.
  • Thinking in C++, Book 1: als PDF und als HTML
  • Thinking in C++, Book 2: als PDF und als HTML
  • A modest STL tutorial ist eine einfache Einführung in einige grundlegende Konzepte, Container und Algorithmen der Standard Library von C++ (der sogenannten STL). (Quelle)
  • cplusplus.com
  • online-tutorials.net
• OpenGL:
  • Das Buch OpenGL development cookbook
  • Das Buch GLSL essentials über die OpenGL Shader Language und die unterschiedlichen Shader
  • Eine Reihe von Tutorials für modernes OpenGL, in Form von Code-Beispielen und Erklärungen, die ganz leicht anfangen. (Quelle, Github)
  • Recording of the Siggraph course An Introduction to OpenGL Programming, 2013. (Quelle)
  • OpenGL Samples
  • NeHe Tutorials (viele sehr ausführliche Tutorials und Beispiele
  • The OpenGL Reference Manual - The Blue Book
  • Offizielle Spezifikationen (z.B. die OpenGL-Specification)
• Qt (ein Cross-Plattform-GUI Toolkit, als "Wrapper" für OpenGL-Fenster) (für open-source Anwendungen ist die Library kostenlos)
  • Downloads im Abschnitt "Qt Libraries"
  • Wer sich für Qt interessiert, findet Tutorials, hier einige schöne aber im Rahmen der Vorlesung ist das nicht nötig.
  • Einige hübsche Beispiele für OpenGL mit Qt
• Zu GLSL und Shader-Programming:
  • Shader Maker is our simple, cross-platform GLSL editor. It works on Windows, Linux, and Mac OS X.
  • BKcore's Shdr, a shader editor that runs in the browser. Pretty cool, except it lacks a few features of our ShaderMaker: it does not have a geometry shader, no time uniform, no textures, and I don't see a way to change the values of uniforms interactively. But very nice for simple GLSL programs. (Source code can be found here, in case you want to improve it.)
  • Here you can find the source code of the GLSL shader examples that were discussed in class.
    They comprise:
    • some very simple shaders, each with its own Qt application;
    • a number of shaders that create a procedural brick texture (inspired by the orange book), with increasing sophistication (noise);
    • a set of shaders implementing lighting, the last of which does per-pixel lighting;
    All demos should compile and run out-of-the-box under Linux and Mac OS X 10.6. (The executables contained in the zip were compiled under MAC OS X 10.5/10.6 Intel.)
  • Gute Tutorials zu OpenGL allgemein, die immer auch mit Shadern arbeiten. Geht von "Hello OpenGL" bis zu sehr fortgeschrittenen Techniken (z.B. physically-based rendering).
  • Die offizielle GLSL Spezifikation (falls man etwas nochmal ganz genau nachschlagen muß).
  • Die OpenGL 4.x Reference Pages (sehr praktisch zum schnellen Nachschlagen).

Online Literatur und Resources zu Computergraphik

• Literatur zu Vektor- und Matrizenrechnung:
  • Norman Wittels: Introductory Vector Calculus (Quelle)
  • Konstantin Tretyakov: A Brief Introduction to Matrix Algebra (geht auch speziell auf Translationen, Rotationen, etc., ein) (Quelle)
  • Stefan Lang: Einführung in die Matrizenrechnung (Quelle)
  • Linear Algebra - An Introduction to Linear Algebra for Pre-Calculus Students by Tamara Carter, Richard Tapia, Anne Papakonstantinou (Quelle)
  • Immersive linear algebra ist eine Web-Seite mit schönen interaktiven Beispielen zu Themen der linearen Algebra, die nebenbei auch leicht verständlich erklärt werden.
• Demo (Java Applet) zur Farbverschmelzung in Monitoren. (Unter macOS muss man http://cgvr.informatik.uni-bremen.de/teaching zur Exception Site List in System Preferences/Java hinzufügen.
• Ein sehr ausführliches Skript von Prof. Straßer.
• Ein sehr gutes Lehrbuch über alle Arten von Displays (konventionelle, holographische, Stereo, light-fields displays, HMDs, etc.) und deren Grundlagen (Photometrie, Physik des Lichts, Herstellungsprozesse, etc.): Displays: Fundamentals and Applications von Oliver Bimber und Rolf Hainich (Quelle)
• Literatur zur Gammakorrektur:
  • Das Bild zur manuellen Bestimmung des Gammas
  • Gamma FAQ - Frequently Asked Questions about Gamma ( Quelle)
  • Eine sehr ausführliche Darstellung und Motivation der Gammakorrektur: Rehabilitation of Gamma (Quelle)
  • Ein nettes Applet zur Gamma Correction (Quelle)
• Zu Visibility Computations:
  • Zum Hierarchischen Z-Buffer in ATIs Radeon-Karten (und so ähnlich in allen modernen Graphikkarten
  • Mark Kilgard: Improving Shadows and Reflections via the Stencil Buffer
  • David Blythe et al.: Lighting and Shading Techniques for Interactive Applications; Siggraph '99, Course 12, pp. 150 .
  • Morgan McGuire, John F. Hughes, and Kevin T. Egan, Mark J. Kilgard and Cass Everitt: Fast, Practical and Robust Shadows; 2003. (Quelle)
    Dieses Paper geht schon deutlich über das hinaus, was in der Vorlesung besprochen wird.
• Mehr zu Homogenen Koordinaten:
  • Two parallel lines can intersect
  • Projective Geometry and Homogeneous Coordinates ( Quelle)
  • Eine sehr pragmatische und teils witzige Einführung: Homogeneous Coordinates with Glorphs and Smynxes (Quelle)
  • Transformations and Homogeneous Coordinates (Quelle)
• Einige allgemeine Prinzipien bezüglich Animationen:
  • 12 basic principles of animation aus dem Buch The Illusion of Life von Ollie Johnston und Frank Thomas (1981). (Quelle des Films)
  • Und die selben Prinzipien noch einmal als (sehr bekannt gewordenes) Siggraph-Paper vom berühmten John Lasseter von Pixar (1987). Es enthält zahlreiche, hilfreiche Erläuterungen zu den Prinzipien. (Quelle)
• On Orthogonal Matrices
• Zu Quaternionen:
  • Joe McMahon: A (Mostly) Linear Algebraic Introduction to Quaternions. (Quelle)
  • Dam, Koch, Lillholm: Quaternions, Interpolation, Animation. (Quelle)
  • Eine sehr schöne Visualisierung der Einheits-Quaternionen und deren Wirkungsweise als Rotation. Arbeitet sich langsam von 1D bis 4D hoch, so dass man am Ende immer noch gut folgen kann. Wenn man diesen Video gesehen hat, dann hat man sicherlich zumindest eine Intuition von Quaternionen; und vielleicht kann sich der/die eine oder andere sogar den 4-dimensionalen Raum vorstellen. (Quelle)
• Ein leicht verständlicher Artikel zum Thema perspektivische Projektionen: Projektive Abbildungen, zeichnerischer Zugang (Quelle)
• Zu Licht und Farben:
  • Gary W. Meyer: Tutorial on color science; The Visual Computer, Volume 2, Number 5 / September, 1986. (Quelle)
  • Eine leicht verständliche Einführung zu Color Management and ICC profiles (Quelle)
  • Lichttechnische Grundlagen von der Firma ADB GmbH (Quelle) — falls Sie gerne ins Theater gehen, dann erfahren Sie hier außerdem eine ganze Menge über Theater-Beleuchtung.
  • Alex Ryer: Light Measurement Book (Quelle); die erste Hälfte des Buches erklärt viele Konzepte bzgl. Licht und Lichtausbreitung.
  • Eine unterhaltsame Reprtage über das Farbensehen einiger Tierarten -- mit einer verblüffenden Auralisierung (Quelle).
• Zum menschelichen Auge, Sehvermögen, und Sehapparat:
  • Eine Zusammenfassung der Erkenntnisse bzgl. der menschlichen Sehschärfe des menschlichen Auges von Gerald Westheimer: Visual Acuity and Hyperacuity (Quelle, aus dem Handbook of Optics).
  • Ein kleiner philosophischer Aufsatz zum Problem der Qualia und der Erklärungslücke: What Is It Like to Be A Bat? von Thomas Nagel (1974). (Quelle)
    Hier ist der vollständige Aufsatz in The Philosophical Review, Vol. 83, No. 4 (Oct. 1974), pp. 435-450.
  • Webvision: The Organization of the Retina and Visual System, edited by Dr. Helga Kolb, Dr. Ralph Nelson, Dr. Eduardo Fernandez, Dr. Bryan William Jones. Eine hervorragende Sammlung von Buch-Kapiteln zu den verschiedensten Themen des menschlichen Sehapparates, auf verschiedenen Niveau-Stufen.
• Zu Lighting & Shading:
  • Siggraph Course Notes Lighting and Shading Techniques for Interactive Applications , 1999 (Kapitel 11.1 behandelt Spiegelungen in OpenGL, 11.4 behandelt Schatten, 6.1 behandelt Texturen)
• Zwei Anwendungen der Shader-Programmierung:
  • Algorithms for Rendering Depth of Field Effects in Computer Graphics (Quelle)
  • Rendering Depth of Field Effects Survey (Quelle)
• Zur Texturierung:
  • Ein paar sehr nette Demos zur perspektivisch korrekten (bzw. inkorrekten) Texturierung. Dabei finden sich auch ein paar sehr schöne Erläuterungen zu diesem Thema. (Quelle)
  • Der berühmte Artikel " Texture Mapping as a Fundamental Drawing Primitive" von Paul Haeberli and Mark Segal, 1993. (Quelle)
• Ein einfacher Beweis für das Jordan Curve Theorem für die Klasse der Polygone (Quelle)

Tools and Demos

• Das in der Vorlesung gezeigte "Transformation Game" befindet sich in diesem ZIP-Archive. Es befindet sich im Verzeichnis freeSoftware/repository/edu/brown/cs/exploratories/applets/transformationGame; Start mit java -jar transformation_game.jar.
  Quelle: Brown University
• Ein Tool zur Konvertierung von verschiedenen Repräsentationen von 3D-Rotationen ineinander.

Videos

• Video-Tutorial zu LCD-Diplays von 3M.
• An Introduction to OpenGL Programming, Siggraph Course 2013. (Quelle)
• Video zum Phong-Modell von Matthias Parchettka (etwas albern, auch oberflächlicher als ein Buch, dafür vielleicht unterhaltsamer) (Quelle 1, Quelle 2).
• Video zu BRDFs auch von Matthias Parchettka (Quelle 1, Quelle 2).
• Über Gouraud-Shading von Andrew Silke (Quelle).
• Rediscovering Euler's formula with a mug

Literatur und Infos, die nichts mit Computergraphik zu tun haben

• Ein Artikel über moderne Tools zur Beeinflussung von Wählern über die sogenannten sozialen Medien: Wahlmanipulation mittels Psychometrik und Social Media (Quelle: Das Magazin). Die Gefahr geht noch weit darüber hinaus, da man diese Technologien natürlich genauso gut benuzten kann, um die Stimmung gegenüber Firmen zu beeinflussen (z.B. bzgl. Genmanipulation, oder umweltschädliche Praktiken, etc.).
• Eines der letzten Interviews mit Joseph Weizenbaum, einem berühmten Pionier der KI und späterer Kritiker allzu großer Technikgläubigkeit. (Hat nichts mit Computer-Graphik direkt zu tun, gehört aber trotzdem zur Allgemeinbildung.)

Gabriel Zachmann
Last modified: Tue Jun 18 20:53:57 CEST 2019