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 -
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 -
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 -
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 -
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 -