Rasterkonvertierung

• Rasterisierung = Umwandlung von Vektor- in Rastergrafiken
• zur Darstellung müssen Vektorgrafiken rasterisiert werden

mathematische Grundlagen

Skalarprodukt

• berechnet Winkel zwischen zwei Vektoren

  

Kreuzprodukt

• berechnet zu zwei Vektoren senkrechten Vektor

Rasterkonvertierung von Linien

naiver Ansatz

• Schleife über alle $x$$x$-Pixel $x_0$$x_0$ bis $x_1$$x_1$

• in jedem Durchlauf wird abhängig von der Steigung der impliziten Geradengleichung ein Pixel gesetzt

• Problem: keine Linie, wenn $x_0>x_1$$x_0 > x_1$

  • Lösung: Fallunterscheidung: umgekehrt, falls $x_0>x_1$$x_0 > x_1$

• Problem: pro $x$$x$-Schritt kann nur ein Pixel gesetzt werden

  • Lösung: Fallunterscheidung: Iteration über $y$$y$-Pixel, falls $\mathrm{\Delta }y>\mathrm{\Delta }x$$\Delta y > \Delta x$

  

Beschleunigung

• Motivation: vorher brauchte jeder Schleifendurchlauf viele Rechenoperationen
• Idee: inkrementelle Lösung - in nächstem Durchlauf nur Steigungswert betrachten

Mittelpunktalgorithmus (von Bresenham)

• Idee: in jedem Schleifendurchlauf nur 2 Optionen

  • keine Erhöhung: nächster Pixel (x + 1, y)
  • Erhöhung um 1: nächster Pixel (x + 1, y + 1)

• Realisierung: Betrachtung des Mittelpunkts (x + 1, y + 0.5)

  • Gerade unter Mittelpunkt: keine Erhöhung
  • Gerade über Mittelpunkt: Erhöhung um 1

• nutzt implizite Geradengleichung $g(x,y)=a\ast x+b\ast y+c$$g(x, y) = a*x + b*y + c$

Rasterkonvertierung von Kreisen

• ähnlich Linienkonvertierung mit impliziter Kreisgleichung $g(x,y)=x²+y²-r^2$$g(x, y)=x² + y² -r^2$

• Symmetrie: nur ein Achtel des Kreisumfangs muss berechnet werden

  • Annahme: Kreis befindet sich im Ursprung $\to$$\rightarrow$ Transposition
  • keine Fallunterscheidung notwendig

Rasterkonvertierung von Polygonen

Scanline-Algorithmus

• Pixelraster wird zeilenweise durchlaufen

  • Schnittpunkte mit Polygonkante werden berechnet
  • Schnittpunkte werden nach $x$$x$ aufsteigend sortiert
  • Zeichne Pixel bei ungerader Parität der Schnittpunkte

Pineda-Algorithmus

• Idee: Verwendung der Hesseschen Normalform der Geraden

  • Abstand zur Geraden wird betrachtet

• nur bei konvexen Polygonen

  • kein Innenwinkel $>180\mathrm{°}$$>180 \degree$

• Polygon muss im Uhrzeigersinn durchlaufen werden

  

  • Pixel liegt rechts von allen Geraden: innerhalb des Polygons
  • Pixel liegt links min. einer Geraden: außerhalb des Polygons

Optimierungen

• Parallelisierung

  

• Abbruch, nach zweitem Überschreiten einer Geraden

  • nur möglich durch Annahme eines konvexen Polygons