Der Bildschirm ist in eine Reihe von Punkten zerlegt, die alle mit verschiedenen Intensit\u00e4t oder Farbe gesetzt sind. Die Rastergrafik versucht, die geometrischen Beschreibungen von Objekten auf die Pixel des Bildschirmes abzubilden. Diese Umrechnung muss schnell und in einigen F\u00e4llen speichersparend sein. In den Letzen Jahren wurden eine ganze Reihe von Algorithmen entwickelt, die mittlerweile in Hardware Einzug gehalten hat. Die modernen Grafikkarten unterst\u00fctzen neben grafischen Operatio\u00adnen wie Pixel und Farbe mischen auch Funktionen zum Zeichen von Linien, Kreisen, Polygonen, gef\u00fcllten Fl\u00e4chen und weiteres. Daneben sind dreidimensionale Koordinatentransformationen in Hardware gegossen wie das Abbilden einer Bitmap auf eine Fl\u00e4che, das Erzeugen von Nebel (engl. Fog\u00adging) oder auch perspektivische Korrektionen (engl. Perspective Correction). Nat\u00fcrlich \u00fcberlassen wir das Zeichen der Linien der Grafikkarte und die dreidimensionalen Transformationen der 2D-Biblio\u00adthek. Java ist allerdings eine einfache Sprache und die Arbeitsweise kann somit schnell erkl\u00e4rt werden. Notfalls k\u00f6nnen wir Funktionen, die nicht in der Grafikbibliothek vorliegen, nachbilden.<\/p>\n
Linien sind ein einfachen Beispiel daf\u00fcr, wie Punkte auf dem Raster verteilt werden. Beachten wir dazu die Grafik. Wie zeichnen eine Linie von den Koordinaten (x1,y1) zum Punkt (x2,y2).<\/p>\n
Um nun die Punkte auf dem physikalischen Bildschirm zu setzen, m\u00fcssen die Punkte so verteilt wer\u00adden, dass sie m\u00f6glichst nah an der wirklichen Linien liegen. Gehen wir die X-Achse von xl nach x2 ab, so m\u00fcssen wir die Y-Punkte w\u00e4hlen. Bei der Wahl k\u00f6nnen wir folgende Entscheidung f\u00e4llen: An jedem Punkt m\u00fcssen wir einen Pixel w\u00e4hlen, n\u00e4mlich diesen, der den geringsten Abstand zum Pixelraster besitzt. Ist die Linie horizontal, so ist der Abstand zwischen wirklicher Linie und Rasterpunkt immer Null und die Wahl ist einfach.<\/p>\n
Ein Algorithmus kann nun wie folgt arbeiten: Es ist der Abstand zwischen der wirklichen Linie und einem Pixel auf der Y-Achse gleich einem Fehlerwert. Es ist der Punkt auf der Y-Achse auszuw\u00e4hlen,
der zur wirklichen Linie den kleinsten Fehlerwert aufweist. Einen schnellen Algorithmus, der genau mit diesem Fehlerwert arbeitet, wurde zuerst von j. E. Bresenham (1965) ver\u00f6ffentlicht. Bresenham
betrachtet Linien im ersten kartesischen Oktanten, die Steigung der Linie ist also kleiner Eins, formal: 0 < \u0394y \/ \u0394x < 1. Die Rasterung ist von links nach rechts. Betrachten wir nun ein Programmsegment in
Pseudocode das, welches eine Linie mit Steigung kleiner Eins zeichnet:<\/p>\n
\u0394x = x2 - x1\n\u0394y = y2 - y1\nerror = - \u0394x \/ 2;\nsetPixel( x1, y1 );\nwhile( x < x2 ) {\n error = error + \u0394y;\n if ( error >= 0 ) {\n y = y + 1;\n error = error - \u0394x;\n }\n x = x + 1;\n setPixel( x, y );\n}<\/pre>\nLiegen die Linien in anderen Oktanten, so m\u00fcssen wir den Algorithmus nur leicht ab\u00e4ndern. So sind durch einfache Spiegelungen an Winkelhalbierenden oder Ordinate bzw. Abszisse die Punkte zu verschieben. Liegt die Linie beispielsweise im siebten Oktanten, so rastern wir entlang der Y-Achse und vertauschen dx mit -dx und liegt die Linie im achten Oktanten, so rastern wir wir im ersten Oktanten, nur dass dy mit -dy vertauscht wird.<\/p>\n
Bresenhams Linienalgorithmus arbeitet schnell und optimal (was bedeutet, die Fehler sind am kleinsten), weil alle Berechnungen auf Ganzzahlen ausgef\u00fchrt werden. Dies war in den sechziger Jahren
\n
noch wichtiger als heute, wo eine Flie\u00dfkommaoperation schon genauso viel kostet wie eine lnteger-Operation. Da der Beweis langwierig \u2014 aber f\u00fcr die mathematisch geschulten nicht schwierig \u2014 ist, wollen wir an dieser Stelle auf den Formalismus verzichten. Anstelle dessen betrachten den Quellcode einer Klasse, die eine einfaches Linienmuster schreibt. Ein nicht unwesentlicher Teil wird daf\u00fcr aufgewendet, den Algorithmus f\u00fcr die verschiedenen Lagen im kartesischen Koordinatensystem anzupassen. Da wir sp\u00e4ter noch andere grafische Objekte zeichnen, dient dieses Programm gleichzeitig als Rahmen.<\/p>\n
import java.awt.*;\nimport java.awt.event.*;\n\npublic class GDV extends Frame\n{\n private Graphics g;\n static final int CLASSIC = 0;\n static final int BRESENHAM = 1;\n public int lineType = CLASSIC;\n \n public GDV() {\n setSize( 400, 400 );\n addWindowListener( new WindowAdapter() {\n public void windowClosing ( WindowEvent e ) { System.exit(0); }\n });\n }\n\n \/**\n * Draws a line with algorithm of Bresenham\n *\/\n private void drawBresenhamLine( int x1, int y1, int x2, int y2 )\n {\n int xIncrement = 1,\n yIncrement = 1,\n dy = 2*(y2-y1),\n dx = 2*(x1-x2),\n tmp;\n \n if ( x1 > x2 ) { \/\/ Spiegeln an Y-Achse\n xIncrement = -1;\n dx = -dx;\n }\n \n if ( y1 > y2 ) { \/\/ Spiegeln an X-Achse\n yIncrement= -1;\n dy= -dy;\n }\n \n int e = 2*dy + dx;\n int x = x1; \/\/ Startpunkte setzen\n int y = y1;\n\n if ( dy < -dx ) \/\/ Steigung < 1\n { \n while( x != (x2+1) )\n {\n e += dy;\n if ( e > 0) \n {\n e += dx;\n y += yIncrement;\n }\n g.drawLine( x, y, x, y );\n x += xIncrement;\n }\n }\n else \/\/ ( dy >= -dx ) Steigung >=1\n {\n \/\/ an der Winkelhalbierenden spiegeln\n tmp = -dx;\n dx = -dy;\n dy = tmp;\n\n e = 2*dy + dx;\n\n while( y != (y2+1) )\n {\n e += dy;\n if( e > 0 ) {\n e += dx;\n x += xIncrement;\n }\n g.drawLine( x, y, x, y );\n y += yIncrement;\n }\n }\n }\n \n private void line( int x1, int y1, int x2, int y2 ) {\n if ( lineType == BRESENHAM )\n drawBresenhamLine( x1, y1, x2, y2 );\n else\n g.drawLine( x1, y1, x2, y2 );\n }\n\n public void paint( Graphics g ) {\n this.g = g;\n\n for ( int i=30; i < 300; i+=20 )\n line( 10+i, 40, 300-i, 100 );\n }\n \n public static void main( String[] args ) {\n GDV line = new GDV();\n\n\/\/ line.lineType = CLASSIC;\n line.lineType = BRESENHAM;\n\n line.show();\n }\n}<\/pre>\nBresenhams Algorithmus arbeitet ohne Frage schnell. Wir k\u00f6nnen aber noch einige Erweiterungen programmieren: Wie wird eine antialiased Linie, also eine weiche Linie gezeichnet? Es gibt mehrere
\n
M\u00f6gichkeiten, wobei aber nicht alle schnell sind. Eine L\u00f6sung besteht darin, auf jeden Punkt einen Filter loszulassen. Dies l\u00e4uft aber auf viele Multiplikationen hinaus. Bekannt geworden ist ein anderer <\/p>\n
Ansatz, ein Algoritmus von Gupta\u2014Sproull (1981). Dieser ist in allen bekannten Grafik-B\u00fcchern nachzulesen.<\/p>\n
Da der Algorithmus von Bresenham sehr schnell ist, wundert es einen, wenn wir noch von einer Geschwindigkeitsoptimierung sprechen. Das ist tats\u00e4chlich m\u00f6glich und wurde von Angel, Edward
\n
und Don Morrison in einem Aufsatz in den \u201cIEEE Computer Graphics and Applications\u201d auf zwei Seiten Ende 1991 beschrieben. Der Hintergrund ist einfach und kann daher kurz mit einer Programmieraufgabe umgesetzt werden: Die Pixelbewegungen wiederholen sich zyklisch. In einer Linie der Steigung 1, ist mit jedem Erh\u00f6hen des X-Z\u00e4hlers auch ein Erh\u00f6hen des Y-Z\u00e4hlers Verbunden. Eine Gerade mit der Steigung 1\/8 setzt vier Punkte auf der Horizontalen, geht dann einen Pixel nach oben und setzt wieder vier Punkte. K\u00f6nnen wir den Rhythmus erkennen, dann haben wir es einfach, denn dann m\u00fcssen uns nur die Zeichentechnik merken und dann immer wieder kopieren. F\u00fcr parallele Prozesse gibt es nichts sch\u00f6neres. Wir berechnen dazu den Gr\u00f6\u00dften Gemeinsamen Teiler von \u0394y und -\u0394x. Ist dieser echt gr\u00f6\u00dfer als Eins, dann haben wir damit den ersten Punkt, an dem die Berechnungsfolge von vorne beginnt. Der Punkt zeichnet sich durch die Koordinaten (x1 + a\/ggT(\u0394y, -\u0394x, y1 + b\/ggT(\u0394y\/-y\u0394x) aus.<\/p>\n","protected":false},"excerpt":{"rendered":"
Der Bildschirm ist in eine Reihe von Punkten zerlegt, die alle mit verschiedenen Intensit\u00e4t oder Farbe gesetzt sind. Die Rastergrafik versucht, die geometrischen Beschreibungen von Objekten auf die Pixel des Bildschirmes abzubilden. Diese Umrechnung muss schnell und in einigen F\u00e4llen speichersparend sein. In den Letzen Jahren wurden eine ganze Reihe von Algorithmen entwickelt, die mittlerweile […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[1],"tags":[],"class_list":["post-2343","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2343","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/comments?post=2343"}],"version-history":[{"count":2,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2343\/revisions"}],"predecessor-version":[{"id":2345,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2343\/revisions\/2345"}],"wp:attachment":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/media?parent=2343"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/categories?post=2343"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/tags?post=2343"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}