Der Bildschirm ist in eine Reihe von Punkten zerlegt, die alle mit verschiedenen Intensität 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ällen speichersparend sein. In den Letzen Jahren wurden eine ganze Reihe von Algorithmen entwickelt, die mittlerweile in Hardware Einzug gehalten hat. Die modernen Grafikkarten unterstützen neben grafischen Operationen wie Pixel und Farbe mischen auch Funktionen zum Zeichen von Linien, Kreisen, Polygonen, gefüllten Flächen und weiteres. Daneben sind dreidimensionale Koordinatentransformationen in Hardware gegossen wie das Abbilden einer Bitmap auf eine Fläche, das Erzeugen von Nebel (engl. Fogging) oder auch perspektivische Korrektionen (engl. Perspective Correction). Natürlich überlassen wir das Zeichen der Linien der Grafikkarte und die dreidimensionalen Transformationen der 2D-Bibliothek. Java ist allerdings eine einfache Sprache und die Arbeitsweise kann somit schnell erklärt werden. Notfalls können wir Funktionen, die nicht in der Grafikbibliothek vorliegen, nachbilden.
Linien zeichnen
Linien sind ein einfachen Beispiel dafür, 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).
Um nun die Punkte auf dem physikalischen Bildschirm zu setzen, müssen die Punkte so verteilt werden, dass sie möglichst nah an der wirklichen Linien liegen. Gehen wir die X-Achse von xl nach x2 ab, so müssen wir die Y-Punkte wählen. Bei der Wahl können wir folgende Entscheidung fällen: An jedem Punkt müssen wir einen Pixel wählen, nämlich 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.
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ählen,
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öffentlicht. Bresenham
betrachtet Linien im ersten kartesischen Oktanten, die Steigung der Linie ist also kleiner Eins, formal: 0 < Δy / Δx < 1. Die Rasterung ist von links nach rechts. Betrachten wir nun ein Programmsegment in
Pseudocode das, welches eine Linie mit Steigung kleiner Eins zeichnet:
Δx = x2 - x1
Δy = y2 - y1
error = - Δx / 2;
setPixel( x1, y1 );
while( x < x2 ) {
error = error + Δy;
if ( error >= 0 ) {
y = y + 1;
error = error - Δx;
}
x = x + 1;
setPixel( x, y );
}
Liegen die Linien in anderen Oktanten, so müssen wir den Algorithmus nur leicht abändern. 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.
Bresenhams Linienalgorithmus arbeitet schnell und optimal (was bedeutet, die Fehler sind am kleinsten), weil alle Berechnungen auf Ganzzahlen ausgeführt werden. Dies war in den sechziger Jahren
noch wichtiger als heute, wo eine Fließkommaoperation schon genauso viel kostet wie eine lnteger-Operation. Da der Beweis langwierig — aber für die mathematisch geschulten nicht schwierig — 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ür aufgewendet, den Algorithmus für die verschiedenen Lagen im kartesischen Koordinatensystem anzupassen. Da wir später noch andere grafische Objekte zeichnen, dient dieses Programm gleichzeitig als Rahmen.
import java.awt.*;
import java.awt.event.*;
public class GDV extends Frame
{
private Graphics g;
static final int CLASSIC = 0;
static final int BRESENHAM = 1;
public int lineType = CLASSIC;
public GDV() {
setSize( 400, 400 );
addWindowListener( new WindowAdapter() {
public void windowClosing ( WindowEvent e ) { System.exit(0); }
});
}
/**
* Draws a line with algorithm of Bresenham
*/
private void drawBresenhamLine( int x1, int y1, int x2, int y2 )
{
int xIncrement = 1,
yIncrement = 1,
dy = 2*(y2-y1),
dx = 2*(x1-x2),
tmp;
if ( x1 > x2 ) { // Spiegeln an Y-Achse
xIncrement = -1;
dx = -dx;
}
if ( y1 > y2 ) { // Spiegeln an X-Achse
yIncrement= -1;
dy= -dy;
}
int e = 2*dy + dx;
int x = x1; // Startpunkte setzen
int y = y1;
if ( dy < -dx ) // Steigung < 1
{
while( x != (x2+1) )
{
e += dy;
if ( e > 0)
{
e += dx;
y += yIncrement;
}
g.drawLine( x, y, x, y );
x += xIncrement;
}
}
else // ( dy >= -dx ) Steigung >=1
{
// an der Winkelhalbierenden spiegeln
tmp = -dx;
dx = -dy;
dy = tmp;
e = 2*dy + dx;
while( y != (y2+1) )
{
e += dy;
if( e > 0 ) {
e += dx;
x += xIncrement;
}
g.drawLine( x, y, x, y );
y += yIncrement;
}
}
}
private void line( int x1, int y1, int x2, int y2 ) {
if ( lineType == BRESENHAM )
drawBresenhamLine( x1, y1, x2, y2 );
else
g.drawLine( x1, y1, x2, y2 );
}
public void paint( Graphics g ) {
this.g = g;
for ( int i=30; i < 300; i+=20 )
line( 10+i, 40, 300-i, 100 );
}
public static void main( String[] args ) {
GDV line = new GDV();
// line.lineType = CLASSIC;
line.lineType = BRESENHAM;
line.show();
}
}
Bresenhams Algorithmus arbeitet ohne Frage schnell. Wir können aber noch einige Erweiterungen programmieren: Wie wird eine antialiased Linie, also eine weiche Linie gezeichnet? Es gibt mehrere
Mögichkeiten, wobei aber nicht alle schnell sind. Eine Lösung besteht darin, auf jeden Punkt einen Filter loszulassen. Dies läuft aber auf viele Multiplikationen hinaus. Bekannt geworden ist ein anderer
Ansatz, ein Algoritmus von Gupta—Sproull (1981). Dieser ist in allen bekannten Grafik-Büchern nachzulesen.
Da der Algorithmus von Bresenham sehr schnell ist, wundert es einen, wenn wir noch von einer Geschwindigkeitsoptimierung sprechen. Das ist tatsächlich möglich und wurde von Angel, Edward
und Don Morrison in einem Aufsatz in den “IEEE Computer Graphics and Applications” 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öhen des X-Zählers auch ein Erhöhen des Y-Zählers 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önnen wir den Rhythmus erkennen, dann haben wir es einfach, denn dann müssen uns nur die Zeichentechnik merken und dann immer wieder kopieren. Für parallele Prozesse gibt es nichts schöneres. Wir berechnen dazu den Größten Gemeinsamen Teiler von Δy und -Δx. Ist dieser echt größer 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(Δy, -Δx, y1 + b/ggT(Δy/-yΔx) aus.