(3) Rasterisierung

VorlesungC t fikComputergrafik

T. Grosch

WiederholungWiederholung

Letzte Woche: GrundlagenLetzte Woche: GrundlagenTrigonometrieVektorrechnungVektorrechnungEinfache PutPixel Funktion

HeuteRasterisierungZeichnen von LinienClipping

T. Grosch - 2 -

RastergraphikRastergraphikAuf der Graphikkarte habenAuf der Graphikkarte haben wir einen eigenen BildspeicherHi h ib “ i

AD/Wandler

Hier „schreiben“ wir unsere Bilder reinEin Digital/Analog-Wandler g gliest diesen periodisch aus und wandelt den Inhalt in das Bildsignal für den Monitor um.Bildsignal für den Monitor um.Typisches Format: 3 Byte pro Pixel (r,g,b)

Bildspeicher

T. Grosch - 3 -

BeispieleBeispiele

Wir haben einen Bildschirm von 1024x768 Pixeln undWir haben einen Bildschirm von 1024x768 Pixeln und je 1 Byte für r, g und b Wieviele Farben können wir darstellen?Wieviele Farben können wir darstellen?

Wie groß muss der Bildspeicher sein?216.777.16256256256 =⋅⋅

Wie groß muss der Bildspeicher sein?

Bei einer Bildwiederholrate von 60 Hz wie lange istByteByte 296.359.237681024 =⋅⋅

Bei einer Bildwiederholrate von 60 Hz, wie lange ist jedes Bild sichtbar?

1 msekseksek 16016,0601

≈=

T. Grosch - 4 -

CRT (Kathodenstrahlröhre)CRT (Kathodenstrahlröhre)

T. Grosch - 5 -

FlachbildschirmeFlachbildschirme

T. Grosch - 6 -

TFT (Thin Film Transistor)/LCDTFT (Thin Film Transistor)/LCD

Hintergrundbeleuchtung + PolarisationsfilterLiegt Spannung an, also unter Einwirkung eines l k i h F ld i d di Flü i k i ll delektrischen Feldes, sind die Flüssigkristalle gerade

ausgerichtet. Das polarisierte Licht wird am zweiten Polarisationsfilter absorbiert Damit kann das Licht anPolarisationsfilter absorbiert. Damit kann das Licht an dieser Stelle des TFT Bildschirms nicht austreten.Für jedes Pixel 3mal (rgb)Für jedes Pixel 3mal (rgb)

T. Grosch - 7 -

PixelPixelWir haben Ausgabegeräte mitWir haben Ausgabegeräte mit endlicher, fester Auflösung und damit ein festes RasterBild kt d Pi l“ tBildpunkte werden „Pixel“ genannt für „picture element“In Wirklichkeit ist ein Pixel kein fester Punkt, sondern eine FlächeRasterisierung:

Wir nähern z B eine Linie durchWir nähern z.B. eine Linie durch „Flächen“ anProblem der Unterabtastung ( li h li i “) füh t(englisch: „aliasing“) führt zu gezackten Strukturen (speziell bei schrägen Linien)

T. Grosch - 8 -

Linien ILinien Ivoid draw_line(GLint ax, GLint ay, )( ABtAX −⋅+=

GLint bx, GLint by){

GLint x, y;float t;

)( ABtAX +

)( xxx abtax −⋅+= float t;

for (t = 0.0; t <= 1.0; t += 0.01){

)( xxx abtax

)( yyy abtay −⋅+=

x = ax + t*(bx - ax);y = ay + t*(by - ay);put_pixel(x, y);

}}

Problem: wie ist Schrittweite entlang t ähl ? 01von t zu wählen?

Besser: x als Parameter pixelweise ),max(

0.1yx

tΔΔ

=Δ

erhöhen

T. Grosch - 9 -

Linien II Byv

Linien II)( ABtAX −⋅+=

Byb

aby −=Δ

Aya)( xxx abtax −⋅+=

)(bxx abx −=Δ

yy abyΔ

αα

b

)( yyy abtay −⋅+=

ax

αc

xvxa xbxx

x

abaxt

−−

=

b )( axmay −⋅+=)( x

xx

yyy ax

abab

ay −⋅−−

+=)( xy axmay +=

xmamay xy ⋅+⋅−=

αtan=ΔΔ

=−−

=xy

abab

mxx

yy xmcy ⋅+=xx

T. Grosch - 10 -

Linie zeichnenLinie zeichnenvoid draw line(GLint ax, GLint ay, GLint bx, GLint by)_ ( , y, , y){

GLint x;fl t (fl t)(b )/(b )float m = (float)(by - ay)/(bx - ax);float c = ay - m*ax;

for (x = ax; x <= bx; x++)put_pixel(x, m*x+c);

}}

Bemerkung: in C liefert 1 / 2 den Wert 0, da es sich um eine Division von Integerwerten handelt Dagegen liefern 1 0 / 2 denDivision von Integerwerten handelt. Dagegen liefern 1.0 / 2 den Wert 0.5; ebenso liefert (float) 1 / 2 den Wert 0.5.

T. Grosch - 11 -

y-Werte inkrementell änderny-Werte inkrementell ändernDas Zeichnen einer Linie ist Trick: inkrementell arbeitenDas Zeichnen einer Linie ist ein sehr essentieller Befehl in Graphiksystemen. Er muss also äußerst effizient

Trick: inkrementell arbeiten

:x cxmy +⋅=0also äußerst effizient implementiert werdenWie kann man den letzten

y0

cxmy ++⋅= )1(1:1+xAlgorithmus beschleunigen?

Teuer ist z.B. die Float-Multiplikation m*x+c

y )(1

mcxmy ++⋅=1

myy += 01

T. Grosch - 12 -

ImplementierungImplementierungvoid draw line(GLint ax, GLint ay, GLint bx, GLint by)_ ( , y, , y){

GLint x;fl tfloat y = ay;float m = (float)(by - ay)/(bx - ax);

for (x = ax; x <= bx; x++){

put pixel(x y);put_pixel(x, y);y = y + m;

}}

Keine Multiplikation mehr

T. Grosch - 13 -

Beliebige SteigungBeliebige Steigung

Wie zeichnet man steile“ Linien (>45°) ?Wie zeichnet man „steile Linien (>45 ) ?Lücken zwischen den Punktenx und y vertauschen: Gehe entlang y und berechne xy g y

• x=x+1/mFallunterscheidung für 8 Oktanden

T. Grosch - 14 -

Schnellster AlgorithmusSchnellster Algorithmus

Noch schnellere LinienNoch schnellere LinienBresenham Algorithmus (Midpoint Algorithmus) 1965

• Linien nur mit Integer Werten berechneng• Früher um Größenordnungen schneller als float• Heute fast gleich schnell• Siehe z.B. Shirley „Fundamentals of Computer Graphics“

Idee: Verwende implizite GeradengleichgungIdee: Verwende implizite Geradengleichgung• Setze Mittelpunkt zwischen zwei Pixeln ein• Vorzeichen entscheidet über nächstes Pixel• Kann mit Integer Operationen berechnet werden

T. Grosch - 15 -

(Anti-)Aliasing(Anti-)Aliasing

4%

1% 43% 87% 4%

14% 75% 75% 14%

4%

4% 87% 43% 1%

Ergebnis von BresenhamAliasing (Unterabtastung)

AntialiasingIdee: bestimme die g ( g)

Eindruck von „Treppenstufen“Problem: „Alles-oder-Nichts“

Farbe/Deckkraft eines Pixels in Abhängigkeit vom Prozentsatz wie stark einProzentsatz wie stark ein Pixel bedeckt wird.

T. Grosch - 16 -

AntialiasingAntialiasing

line_antialias.exe

T. Grosch - 17 -

RandbehandlungRandbehandlungWas passiert wenn eineWas passiert, wenn eine Linie über den Bildschirmrand hinausgeht?J h I l ti dJe nach Implementierung der putpixel-Funktion könnte es zu einer Speicherverletzung führen, oder zu einem warping-Effekt: rechts aus dem Bild heißt links wieder reinDer Bildschirmspeicher wird zeilenweise abgelegtzeilenweise abgelegt

Nicht gut…

T. Grosch - 18 -

Mögliche LösungenMögliche Lösungen

Aufwendige putpixel-RoutineAufwendige putpixel-RoutineTest, ob x,y im Bildbereich liegt und Setzen des Pixels nur, wenn diese Bedingung erfüllt istNachteil: putpixel wird eine „zu teure“ Operation (im Sinne der Effizienz)

Andere Möglichkeit: Clipping ( Wegschneiden“)Andere Möglichkeit: Clipping („Wegschneiden )Die Zeichenroutinen der Primitive stellen sicher, dass putpixel nur im gültigen Bereich aufgerufen wird.g g gBeispiel Linie: Zerlegen der Linien in „sichtbare“ Segmente und Aufruf von draw_line nur für diese Segmente

T. Grosch - 19 -

ClippingClipping

Clipping wird im Bereich der Computergraphik rechtClipping wird im Bereich der Computergraphik recht häufig benötigt, z.B.:

Schneiden von Linien an den Bildschirmgrenzen, um gsichtbare Liniensegmente zu ermittelnSchneiden von Objekten an einer Ebene, um für die Lichtausbreitung den vorderen“ Halbraum zu ermittelnLichtausbreitung den „vorderen Halbraum zu ermittelnSchneiden der „Blickpyramide“ mit der Szene, um den Teil der Szene zu bestimmen, der aktuell von einer Kamera gesehen werden kann

Im Prinzip geht es dabei um einfache Schnitttests oder berechnungen z B von einer Linie mit einem–berechnungen z.B. von einer Linie mit einem

Rechteck (Bildschirmkanten)

T. Grosch - 20 -

Beispiele: ClippingBeispiele: Clipping

Bildschirm Bildschirm

Vorher Nachher

T. Grosch - 21 -

Cohen-SutherlandCohen-Sutherland

Clipping ist eine wichtige Basisoperation und mussClipping ist eine wichtige Basisoperation und muss sehr effizient implementiert werdenGenereller Trick:Genereller Trick:

Erst einfachen Test durchführen, ob Clipping nötig ist.Dann erst im „nötigen“ Fall die (teuren) mathematischen Operationen durchführen

Ein solches, effizientes Verfahren wurde von Dan Cohen und Ivan Sutherland (1967) vorgeschlagenCohen und Ivan Sutherland (1967) vorgeschlagen.

T. Grosch - 22 -

1 Schritt: Bereichscode1. Schritt: BereichscodeDie 8 Bereiche um das

1001 10101000Die 8 Bereiche um das Rechteck, an dem geclippt werden soll, werden mit Hilfe eines 4 Bit Codes 00000001 0010eines 4-Bit-Codes beschrieben

00000001 0010

0100 01100101

Oben Unten Rechts Links

Rechteck, an dem geclippt werden soll (z.B. Bild hi f t )

Punkt liegt oberhalb des Rechtecks

Punkt liegt unterhalb des Rechtecks

Punkt liegt rechts vom Rechteck

Punkt liegt links vom Rechtecks

Bildschirmfenster)

T. Grosch - 23 -

BereichscodeBereichscode Für den Anfangs- und EndpunktFür den Anfangs und Endpunkt einer Linie wird der Bereichscode ermittelt:

1001 10101000

maxy

00000001 0010

maxy

unsigned char outcode( int x, int y){

0100 01100101

minyunsigned char c = 0;

if (y > ymax) c = c | 8; // 1000if (y < ymin) c = c | 4; // 0100

minx maxxif (y < ymin) c c | 4; // 0100if (x > xmax) c = c | 2; // 0010if (x < xmin) c = c | 1; // 0001

return c;}

T. Grosch - 24 -

BeispielBeispielLinksRechtsUntenObenyx B

Bildschirm1001545-100A

yx

A 499

000010075C

000165025BE

H

0000375175E

0010-15085D

CF

0

0010100350G

0000150300F

0000

G0

0499

0010-100350G

0100250550H

D

T. Grosch - 25 -

BereichscodeBereichscodeDurch einfache Bit-Operationen

1001 10101000

AB

p(und, oder) lässt sich schnell erkennen, ob eine Linie vollständig innerhalb bzw. außerhalb des Bereichs liegt

00000001 0010

A

EH

Bereichs liegt.

1. 0& 21 ≠cc

C

D

F

G

2.

3.

21

0| 21 ==cc0100 01100101

Linie vollständig außerhalb, fertig.

ignore1000cA&cB4.

5.

Linie vollständig innerhalb, alles zeichnen.

Sonst: neue Punkte

cut0100cC | cD0000cC&cD

gcA&cB

5. Sonst: neue Punkte bestimmen bis 1) oder 3) erreicht ist cut0110cG | cH0000cG&cH

draw0000cE | cF0000cE&cF

T. Grosch - 26 -

SchnittpunktberechnungSchnittpunktberechnung0)()( =⋅−⋅+−⋅+−⋅ xyyxxxyy babaabybaxImplizite

Geradengleichung yyyy

maxy 0=+⋅+⋅ dybxa

Geradengleichung

xx

yy

abb

baa

−=

−=B

A

minx maxxminy

xyyx

xx

babad ⋅−⋅=

minxx = maxxx = maxmin . ybzwyy =

adybx +⋅

−=bdxay +⋅

−=b

dxay +⋅−=

a

T. Grosch - 27 -

ImplementierungDivision durch b? b ist Null, wenn ax=bx ist (also eine senkrechte Linie) Im Falle Links“ würde aberImplementierung

void clip_and_draw(GLint ax, GLint ay, i i

Linie). Im Falle „Links würde aber bereits durch c1&c2=0 abgebrochen.

GLint bx, GLint by){

unsigned char c1 = outcode( ax, ay);unsigned char c2 = outcode( bx, by);

if ((c & C_LEFT) != 0){ x = xmin; y = -(a*x+d)/b;}

else if ((c & C_RIGHT) != 0){ x = xmax; y = -(a*x+d)/b;}

unsigned char c;float a, b, d, x, y;

while((c1 | c2) != 0)

else if ((c & C_TOP) != 0){ y = ymax; x = -(b*y+d)/a;}

else if ((c & C_BOTTOM) != 0){ y = ymin; x = -(b*y+d)/a;}

{if ((c1 & c2) != 0) return ;

a = ay-by;

if (c == c1){ ax = x; ay = y;

c1 = outcode(ax, ay);}Kann vor die while Schleife b = bx-ax;

d = ax*by-ay*bx;

if (c1 == 0) c = c2;

yelse

{ bx = x; by = y; c2 = outcode(bx, by);}

}

while Schleife, da sich die Geradenglei-chung nicht ändert

else c = c1;}draw_line(ax, ay, bx, by);

}

ändert.

line_clip.vcproj

T. Grosch - 28 -

BeispieleBeispiele{

c1 = outcode( ax, ay);c2 = outcode( bx by);A (Oben, Links) A (Oben Rechts) c2 = outcode( bx, by);while((c1 | c2) != 0){

if ((c1 & c2) != 0) return ;b b b d *b *b

( , )

A‘ (Oben)

A (Oben, Rechts)

a = ay-by; b = bx-ax; d = ax*by-ay*bx;if (c1 == 0) c = c2;else c = c1;if ((c & C_LEFT) != 0)

{ i ( * d)/b }A‘ (0000)

A‘‘ (0000)

{ x = xmin; y = -(a*x+d)/b;}else if ((c & C_RIGHT) != 0)

{ x = xmax; y = -(a*x+d)/b;}else if ((c & C_TOP) != 0)

B (0000) B (0000)

A (0000)

B (Rechts){ y = ymax; x = -(b*y+d)/a;}

else if ((c & C_BOTTOM) != 0){ y = ymin; x = -(b*y+d)/a;}

if (c == c1)

A‘ (Rechts)

{ ax = x; ay = y; c1 = outcode(ax, ay);}else

{ bx = x; by = y; c2 = outcode(bx, by);}}

A (Unten)

draw_line(ax, ay, bx, by);

}

T. Grosch - 29 -

BeispielBeispielyx

65025B

545-100A

y

10075C

65025B

375175E

-15085D

100350G

150300F

-100350G

250550H

T. Grosch - 30 -

Fazit: Cohen-SutherlandFazit: Cohen-Sutherland

Dieser Clipping-Algorithmus bietet eine effizienteDieser Clipping-Algorithmus bietet eine effiziente Implementierung für die Schnittberechnung von Linien mit rechteckigen AusschnittsfensterngDer Algorithmus arbeitet 2-stufig:

Für Start- und Endpunkt der Linie wird ein Bereichscode ermittelt.Durch einfache Bit-Operationen (und, oder) lässt sich schnell erkennen ob eine Linie vollständig innerhalb bzw außerhalberkennen, ob eine Linie vollständig innerhalb bzw. außerhalb des Bereichs liegt.Ansonsten wird die Linie iterativ mit den Rechteckkanten

h itt d St t b E d kt fü di Li igeschnitten und neue Start- bzw. Endpunkte für die Linie ermittelt, so dass die resultierenden Liniensegmente garantiert innerhalb des Rechteckfensters liegen.

T. Grosch - 31 -

Fazit: Cohen-SutherlandFazit: Cohen-Sutherland

Dieser Algorithmus arbeitet sehr effizientDieser Algorithmus arbeitet sehr effizientEr findet vor allem für Clipping an Bildschirmkanten VerwendungVerwendungNachteil: er funktioniert nur für rechteckige Ausschnitte

für beliebige Ausschnittsfenster ist der Bereichscode so nicht gmehr einsetzbar; das gleiche gilt für die einfache Berechnung der Schnittpunkte zwischen den Kanten der Ausschnittsfenster und den Linienzwischen den Kanten der Ausschnittsfenster und den Linien

Erweiterung für beliebige Ausschnittsfenster: Cyrus-BeckBeck

T. Grosch - 32 -

Mausabfrage undMausabfrage und Polygon-Datenstruktur

PolygonPolygon

Ein Polygon ist ein n-Eck“ und setzt sich aus einerEin Polygon ist ein „n-Eck und setzt sich aus einer Reihe von zusammenhängenden Linien zusammen.Für eine korrekte Normalenberechnung wirdFür eine korrekte Normalenberechnung wird vorausgesetzt, dass die Eckpunkte gegen den Uhrzeigersinn definiert sind.Datenstruktur für ein Polygon (2-dimensional), z.B.:

Liste von Eckpunkten,Für jeden Eckpunkt x,y-Koordinate

T. Grosch - 34 -

Polygon2D Klasse (Polygon2D h)Polygon2D Klasse (Polygon2D.h)#ifndef _POLYGON2D_H#define POLYGON2D H_ _#include "Vector2D.h"#include <vector>using namespace std;

class Polygon2D {public:

Polygon2D();Polygon2D();~Polygon2D();void addPoint(Vector2D point); // neuen Punkt anfuegenVector2D getPoint(int i) const; // Punkt i zurueckliefernvoid deletePoints(); // alle Punkte loeschenint numPoints() const; // Anzahl Punktevoid draw() const; // Polygon zeichnen

private:vector<Vector2D> mPoints; // dyn. Array der Punkte

};#endif#endif

T. Grosch - 35 -

Polygon2D Klasse (Polygon2D cpp)Polygon2D Klasse (Polygon2D.cpp)#include "Polygon2D.h" void Polygon2D::deletePoints()#include <GL/glut.h>

Polygon2D::Polygon2D(){

{mPoints.clear();

}

}

Polygon2D::~Polygon2D(){

int Polygon2D::numPoints() const{

return mPoints.size();}

}

void Polygon2D::addPoint(Vector2D point){

void Polygon2D::draw() const{glBegin(GL LINE LOOP);

mPoints.push_back(point);}

Vector2D Polygon2D::getPoint(int i) const

g g _ _for (int i = 0 ; i < mPoints.size() ; i++) glVertex2f(mPoints[i].x(), mPoints[i].y());

glEnd();

}yg g ( ){

return mPoints[i];}

}

T. Grosch - 36 -

GLUT Funktion zur MausabfrageGLUT Funktion zur Mausabfrage

GLUT stellt uns eine Callback-Funktion für die MausGLUT stellt uns eine Callback-Funktion für die Maus zur Verfügung.Diese wird aufgerufen, wenn eine Maustaste gedrücktDiese wird aufgerufen, wenn eine Maustaste gedrückt wird.void mouse (int button, int state, int x, int y)

Die Parameter:button: GLUT_LEFT_BUTTON, GLUT_MIDDLE_BUTTON, GLUT RIGHT BUTTON (zeigt an welche Knöpfe gedrücktGLUT_RIGHT_BUTTON (zeigt an, welche Knöpfe gedrückt wurden)state: GLUT_UP, GLUT_DOWN (zeigt an, ob die Taste gedrückt oder losgelassen wurde).x, y: Die Position des Mauszeigers beim Drücken der Taste (gemessen von der linken oberen Ecke des Fenster !!!)(gemessen von der linken oberen Ecke des Fenster !!!)

T. Grosch - 37 -

Beispielprogramm mit MauseingabeBeispielprogramm mit Mauseingabevoid mouse(int button, int state, int x, int y){

Bildschirm

y

Maus

x

{Vector2D vertex( x, HOEHE - y);

if (button == GLUT LEFT BUTTON && state == GLUT DOWN)

xy

( _ _ _ )

poly.addPoint ( vertex) ;

else if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)

poly.deletePoints();

glutPostRedisplay();}

Wurde die linke Maustaste gedrückt, dann wird ein neuer Punkt zum Polygon hinzugefügt.

Wurde die rechte Maustaste gedrückt, so wird das Polygon gelöscht (genauer: Liste auf Null Elemente zurückgesetzt).

T. Grosch - 38 -

Beispielprogramm mit MauseingabeBeispielprogramm mit Mauseingabe#include "Vector2D.h"#include "Polygon2D h"

void mouse( int button, int state, int x, int y)#include Polygon2D.h

#include <GL/glut.h>

#define BREITE 520#define HOEHE 520

, y){

s. letzte Folie}

#define HOEHE 520

Polygon2D poly;

id di l ( id)

int main(int argc, char** argv){

glutInit(&argc, argv);glutInitDisplayMode (GLUT SINGLE |void display( void)

{glClear (GL_COLOR_BUFFER_BIT);glColor3f( 0.0, 0.0, 1.0);

l d ()

glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);glutInitWindowSize( BREITE, HOEHE);glutInitWindowPosition (100, 100);glutCreateWindow („Polygoneingabe");poly.draw();

glFlush ();}

glutCreateWindow („Polygoneingabe );init ();glutMouseFunc(mouse);glutDisplayFunc(display); glutMainLoop();void init( void)

{glClearColor (1.0, 1.0, 1.0, 0.0);glOrtho(0, BREITE, 0, HOEHE, -1, 1);

glutMainLoop();return 0;

}

P l i t j} Poly_input.vcproj

T. Grosch - 39 -

ZusammenfassungZusammenfassung

LinienLinienClipping

Cohen-Sutherland Algorithmus

Nächstes MalClipping an nicht-rechteckigem PolygonClipping „Polygon-gegen-Polygon“

T. Grosch - 40 -