Inhaltsverzeichnis
1 Display-Arten
2 Grenzen von Displays
3 Koordinatensysteme
4 Punktdarstellung
5 Liniendarstellung
6 Die Algorithmen
6.1 Symmetrie-DDA
6.2 Einfach-DDA
6.3 Bresenham-Algorithmus
7 Kreisdarstellung
1 Display-Arten
Um Graphiken, Bilder, geometrische Figuren, die von einem Computer berechnet werden, und auch Texte auf einem Bildschirm sichtbar zu machen, gibt es mehrere Möglichkeiten. Die wichtigsten zwei sind:
Punktgraphische Displays:
Als kleinste Einheit gilt hier ein Bildpunkt, häufig auch Pixel genannt.
Kurven und Linien bestehen dabei aus vielen einzelnen Punkten, die möglichst eng nebeneinander liegen müssen, damit daraus eine verbundene Linie erkannt werden kann. Aussehen und Dicke der Linie werden durch die Dichte der Pixel zueinander bestimmt. Für Buchstaben existiert eine Matrix, durch die Zeichen auf das Display abgebildet werden, d.h., es werden die Punktinformationen der jeweiligen Buchstabenmatrix auf dem Display angezeigt. Für Bilder braucht man viele hundert Pixel, also eine recht große Rechenkapazität, da jeder Punkt vom Computer erzeugt werden muß.
Punktgraphische Displays unterteilen sich in zwei Arten:
- Ohne Rahmenpuffer
- Mit Rahmenpuffer
Bei Displays ohne einen Rahmenpuffer generiert der Computer ein Bild durch einen jeweils neu berechneten Strom von Punktkoordinaten, d.h., für jeden gesetzten Bildpunkt muß ein Koordinaten-Paar an das Display gesendet werden. Ein starker Nachteil dieser Darstellungsart ist, daß nur eine recht geringe Punkteanzahl ohne einen Flackereffekt dargestellt werden kann. Dieses Flackern und auch der hohe Betriebsmittelverbrauch war wohl auch der Grund, weshalb diese Display-Art sich nicht durchsetzte.
Bei Displays mit einem Rahmenpuffer (anfangs Magnet-Trommeln und -Platten, heute Halbleiterspeicher) werden nur noch Informationen (Farbe, Helligkeit) über den Bildpunkt übertragen, nicht jedoch seine Position. Der Aufbau eines Bildes geschieht dann über die Synchronisationssignale, die parallel zur Bildinformation gesendet werden.
Eine wesentliche Verbesserung gegenüber den punktgraphischen Displays z.B. im CAD-Bereich (hauptsächlich Linien und Kreise) waren Mitte der 60er Jahre
Linienschreibende Displays:
Diese Display-Art beherrscht lediglich die Darstellung von geraden Linien. Einzelne Punkte werden als sehr kurze Linien behandelt.
Für Kreise, Kurven, Buchstaben etc. gibt es daher nur die Möglichkeit, diese in Geradensegmente zu unterteilen und auszugeben.
Vorteilhaft bei diesen Displays ist, daß die Datenmenge, die der Rechner zum Display schicken muß, stark reduziert ist, denn hierbei werden nur noch die Anfangs- und Endkoordinaten übermittelt. Somit ist der Rechner weniger mit dem Bildaufbau beschäftigt und es bleibt mehr Zeit für andere Aufgaben.
Häufig wird diese Display-Art auch Vektorbildschirm genannt.
Die Techniken, die bei der Liniendarstellung auf punktgraphischen Displays entwickelt wurden, gelten auch heute noch, wurden jedoch z.T. erheblich verbessert.
2 Grenzen von Displays
Es ist klar, daß jedes Display irgendwelche physikalischen Grenzen hat. Diese liegen bei normalen Displays in ihrer Bandbreite und der Auflösung der Bildschirmmaske: Je geringer die Bandbreite, desto weniger Informationen können in einer Zeiteinheit übertragen werden. Die Auflösung der Bildschirmmaske ist ein weiterer wichtiger Faktor, denn ein Display kann nur soviele Punkte pro Einheit (meist 100 dpi (dots per inch) darstellen, wie von der Maske vorgegeben sind. I.a. liegt der Punktabstand der Maske bei 0.28 mm (was gerade noch einigermaßen kostengünstig herstellbar ist), für z.B. 1024×786 sind dann also ca. 36 cm Bildschirmdiagonale notwendig.
Im Vergleich dazu: Bei der PAL-Norm braucht man etwa 800×600 Punkte für ein Bild, d.h. bei einer Bildschrimdiagonalen von 62 cm sind die Punkte 0.62 mm auseinander.
Eine weitere Grenze sind auch die vorhandenen Betriebsmittel, denn hohe Auflösungen benötigen sehr viel Speicher und z.B. bei Manipulationen auch sehr viel Rechenzeit.
Es ist also notwendig, Aufwand und Nutzen der hohen Auflösungen zu vergleichen: Eine oft gewählte Auflösung ist 1024×768, weil sich diese Werte gut als Dualzahlen darstellen lassen und der Speicherverbrauch noch relativ gering ist.
3 Koordinatensysteme
Um eine Computergraphik zu verwalten, ist es zweckmäßig, ein zweidimensionales Koordinatensystem zu verwenden.
Da Displays i.a. eine zweidimensionale Fläche darstellen, bietet sich für Computergraphik das kartesische Koordinatensystem an.
Abbildung in dieser Leseprobe nicht enthalten
Das Kartesische Koordinatensystem
Eine häufige Anwendung findet dabei der I. Quadrant des kartesischen Koordinatensystems, meist eingeschränkt auf die natürlichen Zahlen, obwohl es heute üblich ist, daß die y-Achse nach unten zeigt.
Abbildung in dieser Leseprobe nicht enthalten
Computer-Koordinatensysteme
In einigen seltenen Fällen findet man auch eine direkte Umsetzung des kart. Koordinatensystems in der normalen Form, jedoch der Einfachheit halber nur über Integer-Zahlen ansprechbar. Ein Vorteil dieser Umsetzung ist die einfachere mathematische Anwendbarkeit in bestimmten Fällen, jedoch kann auch jedes andere vorhandene Koordinatensystem durch einfache Translationen in diese Form gebracht werden.
4 Punktdarstellung
Die Hauptarbeit beim Punktesetzen wird vom Rechner durch das Setzen bzw. Löschen von einzelnen Bits erledigt. Dabei werden die vom Programm angegebenen Koordinaten in Speicherpositionen umgesetzt und beim nächsten Bildschirmaufbau mit angezeigt. Liegen die Punktkoordinaten außerhalb des Bildschirmbereichs, so werden diese ignoriert.
5 Liniendarstellung
Um eine Linie von A nach B zu ziehen, gibt es mehrere Möglichkeiten, d.h. Algorithmen, die natürlich wieder auf die eigentliche Punktdarstellung zurückgreifen.
Wie wichtig Linien bei der Computergraphik sind, wird daraus deutlich, daß z.B. alle geometrischen Figuren (also Geraden, Kreise etc.) aus Liniensegmenten zusammengesetzt sind.
Alle hier behandelten Algorithmen basieren auf der Inkrementierungsmethode, also dem einfachen Hochzählen von x nach y. Die dabei notwendigen Berechnungsschritte werden in viele kleine Schritte unterteilt, die jeweils nur aufgrund von 3 Informationen (aktuelle Position, Zielposition und der Richtungsangabe) das gewünschte Ergebnis liefern.
Bei der Linienberechnung finden die einzelnen Zwischenergebnisse eine entscheidene Verwen- dung.
Die grobe Vorgehensweise beim Linienzeichnen ist, daß zuerst aus den Koordinaten des Anfangs- und Endpunktes die Steigung berechnet wird. Alle Zwischenergebnisse der Inkrementierungs- methode führen auf die Koordinaten der auf der Linie liegenden Punkte bis einschließlich den Endkoordinaten.
Kriterien für die Brauchbarkeit einer gezogenen Linie:
- Linien sollen als Linien erscheinen
Ein Linie mit Unterbrechungen durch Rechenungenauigkeiten wirkt nicht sehr elegant und sollte vermieden werden. Normalerweise eignen sich die Algorithmen für die Berechnung von Linien, die parallel oder im 45 Grad-Winkel zu den Achsen verlaufen, bei bestimmten Steigungen können jedoch Probleme derart auftreten, daß eine Linie keine anderen adres- sierbaren Punkte kreuzt außer den gegebenen Anfangs- und Endkoordinaten. In einem solchen Fall muß ein Punkt gefunden werden, der der eigentlichen Linie sehr nahe liegt.
- Genaue Anfangs- und Endpunkt-Berechnung
Durch das andauernde Addieren bei der Inkrementierungsmethode und dem Versuch der möglichst guten Annäherung an die richtige Linie können sich Fehler ergeben, welche dann u.U. am Ende der Linienberechnung falsche Endkoordinaten liefern.
- Konstante Dichte
Liegt an einer oder mehreren Stellen der berechneten Linie eine Punkthäufung vor, so erscheint der zugehörige Linienteil dunkler und die gesamte Linie wirkt ungleichmäßig.
- Geschwindigkeit
Sowenige Berechnungen wie irgend möglich und Vermeidung von Fließkommazahlen.
Abbildung in dieser Leseprobe nicht enthalten
Einfache und brauchbare Rechenergebnisse
Abbildung in dieser Leseprobe nicht enthalten
Unbrauchbare Ergebnisse
Wie gut das Rechenergebnis ist, hängt stark vom verwendeten Algorithmus ab. Hier werden drei verschiedene Methoden vorgestellt, die jeweils ganz unterschiedliche Ergebnisse für die selbe Linie liefern.
6 Die Algorithmen
Grundlegend für alle hier beschriebenen Linien-Algorithmen sind sowohl normale Integerzahlen als auch Fließkommazahlen. Bei Fließkommazahlen ist jedoch immer eine gewisse Ungenauigkeit beim Rechnen vorhanden. Deshalb versucht man möglichst, diese Zahlen zu vermeiden bzw. die Anzahl solcher Rechnungen auf ein absolutes Minimum zu beschränken.
6.1 Symmetrie-DDA
Dieser Linienalgorithmus erzeugt gerade Linien aufgrund ihrer Differentialgleichung. Daher stammt auch der Name DDA: digital differential analyzer = Digitale Differenzstufe. Die Differentialgleichung für eine Gerade lautet:
Abbildung in dieser Leseprobe nicht enthalten
Bei Symmetrie-DDA werden x0 und y0 proprotional zur ersten Ableitung erweitert. Da die ersten Ableitungen gleich bleiben, sind sie proprotional zu Δx und Δy.
Einfach ausgedrückt, bedeutet dieses, auf die Basiswerte x0 und y0 werden die Werte εΔx und εΔy addiert, das Ergebnis gerundet und ausgegeben:
xn+1 = xn + εΔx
yn+1 = yn + εΔy
Wie ist nun ε zu wählen? Der Wert von ε ist abhängig von der Länge der zu zeichenden Linie und wird berechnet durch ε = 2−n mit
2n−1≤ max(|Δy|,|Δx|) < 2n
Die obere Grenze 2n ist dabei die Linienlängenschätzung, mit der dann die Zerlegung der Rechnung in kleine Einheiten vorgenommen wird. Die Anzahl der auszuführenden Schleifendurchläufe hängt auch von n ab und beträgt 2n + 1.
Die Wahl von ε ist für das endgültige Aussehen der Linie von großer Bedeutung, denn ist
- ε zu groß, sind unterbrochene Linie möglich oder
- ε zu klein, wird der Algorithmus unnötig langsam und es können Punktanhäufungen ent- stehen.
Die oben schon angesprochene Rundung ist bei diesem Verfahren wichtig, da hier sehr viel mit Fließkommazahlen gerechnet wird.
Beim einfachen Runden, d.h., die bei der Rechnung entstehende Zahl wird auf ihren ganzzahligen Anteil begrenzt und dann der Punkt gesetzt, entstehen schon recht gut aussehende Linien. Da dieses Verfahren nicht ganz korrekt ist (der Nachkommaanteil wird nicht beachtet) kann man auch mathematisch korrekter durch die Nutzung des arithmetischen Überlaufs runden. Dazu wird einfach der Wert 0.5 einmalig zu den Koordinaten addiert. Die Ausgabe des Punktes beschränkt sich dann wieder auf den ganzzahligen Anteil des Rechenergebnisses.
Programmaufbau des Symmetrie-DDA:
Abbildung in dieser Leseprobe nicht enthalten
ergibt z.B. für die Aufrufe (ohne verbesserte Rundung):
Abbildung in dieser Leseprobe nicht enthalten
und für die Aufrufe mit besserer Rundung:
Abbildung in dieser Leseprobe nicht enthalten
Ergebnis:
Das Resultat dieser Berechnungen ist schon als recht brauchbar zu bezeichnen, da die Abweichungen von der richtigen Linie gering sind. Unschön an diesen Linien sind die Punktanhäufungen an einigen Stellen, die die Linie ungleichmäßig aussehen lassen.
Der Aufwand dieses Algorithmus hält sich bei richtiger (optimierter) Programmierung in Grenzen, denn ε ist durch shiften leicht berechenbar, der Rest besteht aus zwei Additionen (bezogen auf die kritischen Teile des Algorithmus).
Nachteil des Algorithmus ist natürlich die Verwendung von Fließkommazahlen.
6.2 Einfach-DDA
Eine leichte Abwandlung des Symmetrie-DDA ist der Einfach-DDA, bei dem lediglich eine andere Linienlängenschätzung verwendet wird. Als Schätzung wird hier nicht 2n sondern einfach max (|Δx|, |Δy|) angenommen, somit berechnet sich ε durch
Abbildung in dieser Leseprobe nicht enthalten
Daraus ergibt sich, daß entweder εΔx oder εΔy = 1 ist und somit eine einfache Schleife aufgebaut werden kann.
Ansonsten ist der Aufbau des Algorithmus analog zum Symmetrie-DDA mit verbesserter Rundung durch Addition von 0.5.
Programmaufbau des Einfach-DDA:
Abbildung in dieser Leseprobe nicht enthalten
Dieses Ergebnis kann durchaus als sehr gut bezeichnet werden. Das liegt daran, daß hier keine Punkthäufungen auftreten können und auch die Werte sehr nahe an der richtigen Linie liegen. Im Gegensatz zum Symmetrie-DDA kann hier das shiften zur Ermittlung nicht angewandt wer- den sondern nur Divisionen. Für die restlichen Berechnungen reichen Fließkommaadditionen.
6.3 Bresenham-Algorithmus
ÄhnlichdemEinfach-DDAverwendetdieserAlgorithmuseineInkrementierungsschleifemit Erhöhungswert 1. Allerdings wird mit einer Fehlergröße δ gearbeitet, die die Entfernung zwischen der korrekten Linie und dem zuletzt erzeugten Punkt enthält.
Abbildung in dieser Leseprobe nicht enthalten
Lage der Fehlergröße δ
Ist δ ≤ 0, so müssen für den nächsten Punkt die x-Koordinate um 1 und δ um die Liniensteigung Δy/Δx erhöht werden. Das ist dann der Fall, wenn der Punkt unter oder auf der richtigen Linie liegt.
Für δ > 0 müssen für den nächsten Punkt die x- und y-Koordinate erhöht werden. Auf δ wird dafür −1 + Δy/Δx addiert, damit beim nächsten Punkt keine Verfälschung auftritt. Analog liegt hier der berechnete Punkt über des genauen Linienverlaufs.
Das direkt umgesetzte Programm kann folgende Form haben: Procedure Bresenham1(x1,y1,x2,y2 : Integer); Var i, x, y, d_x, d_y : Integer;
delta : Real;
Begin
d_x:=x2-x1; d_y:=y2-y1; x:=x1; y:=y1; delta:=(d_y/d_x)-0.5;
For i:=0 To d_x Do Begin Plot x,y;
If delta>0 Then Begin
y:=y+1; delta:=delta-1+(d_y/d_x) End
Else delta:=delta+(d_y/d_x); x:=x+1;
End;
End;
liefert für die bekannten Aufrufe:
Abbildung in dieser Leseprobe nicht enthalten
Das Ergebnis dieses Algorithmus ist sehr gut, da es keine Punkthäufung geben kann, auch liegen die Punkte so nah wie möglich an der richtigen Linie.
Nachteilig sind die häufige Anwendung der Division und die Fließkommazahlen, die jedoch durch einfaches Multiplizieren des δ im Algorithmus mit 2Δx umgangen werden können. Das Programm vereinfacht sich dann so:
Procedure Bresenham2(x1,y1,x2,y2 : Integer); Var i, x, y, delta, d_x, d_y : Integer; Begin
d_x:=x2-x1; d_y:=y2-y1; x:=x1; y:=y1; delta:=2*d_y-d_x;
For i:=0 To d_x Do Begin Plot x,y;
If delta>0 Then Begin
y:=y+1; delta:=delta+(2*d_y-2*d_x) End
Else delta:=delta+2*d_y; x:=x+1;
End;
End;
Das Ergebnis ändert sich dabei natürlich nicht (außer vielleicht durch so umgangene Rechenun- genauigkeiten und bezüglich der Geschwindigkeit), aber es gibt keine Divisionen mehr, sondern nur noch Multiplikationen von Integerzahlen mit 2, die ja durch shiften leicht realisiert werden können.
Beim genauen Hinsehen fällt jedoch auf, daß der Algorithmus in dieser Form nicht für alle Liniensteigungen geeignet ist. Für alle Linien, bei denen Δy > Δx ist, muß eine eigene Routine vorhanden sein, in der alle x- und y-Koordinaten vertauscht auftreten.
7 Kreisdarstellung
Häufig kommt es vor, daß neben Linien auch Kreise benötigt werden. Um einen Kreis zu erzeugen, gibt es die Möglichkeit, ihn durch ein n-Eck anzunähern, bei dem die berechneten Punkte durch gerade Linien verbunden werden. Dieses hat natürlich für sehr große Radien den Nachteil, daß der Kreis wieder als n-Eck erscheint. Es ist also notwendig, daß die Linienendpunkte möglichst nah beieinander liegen und zwar in Abhängigkeit vom Radius. Bei dem hier verwendeten Algorithmus liegen die Punkte sogar so dicht zusammen, daß keine Linien benötigt werden.
Ein einfaches Verfahren für die Berechnung basiert wieder auf einer Differentialgleichnung. Für einen Kreis mit dem Nullpunkt als Zentrum lautet sie:
Abbildung in dieser Leseprobe nicht enthalten
Diese Gleichung ähnelt sehr der Geraden-Differentialgleichung, deshalb liegt es nahe, einen analogen Algorithmus zum Symmetrie-DDA zu entwickeln. Die Grundgleichungen zur Punktberechnung aus dem Symmetrie-DDA werden entsprechend der Gleichung abgeändert:
xn+1 = xn + εyn
yn+1 = yn − εxn
Auch hier tritt wieder das ε auf, welches die Punktabstände bezüglich des Radius bestimmt. Für ε gilt:
Abbildung in dieser Leseprobe nicht enthalten
Weiterhin stellt sich die Frage nach der Maximalanzahl der Schleifendurchläufe. Diese berechnet sich aus der Länge des Kreisumfangs+1, also sind (2π2n) + 1 Durchläufe notwendig. Grob aufgerundet sind es dann 2n+3, was leichter berechenbar ist als (2π2n) + 1. Im Prinzip reicht es natürlich auch, die Koordinaten für einen Viertelkreis zu berechnen und die Punkte an den Achsen zu spiegeln, was den Rechenaufwand erheblich reduziert.
Wie oben bereits erwähnt, ist diese Formel für den Nullpunkt als Zentrum geeignet. Es darf also nicht vergessen werden, die Punktkoordinaten entsprechend zum gegebenen Mittelpunkt zu verschieben.
Procedure kreis(x0,y0,r : Integer) Var x1, y1, x2, y2, eps : Real;
i, n : Integer;
Begin
n:=Round(Ln(r)/Ln(2)+0.5); eps:=Exp(-1*n*Ln(2)); x1:=r; y1:=0;
For i:=0 To Exp((n+3)*Ln(2) Do Begin Plot x0+Trunc(x1),y0+Trunc(y1) x2:=x1+eps*y1; y2:=y1-eps*x1; x1:=x2; y1:=y2;
End;
End;
Das Ergebnis ist jedoch als Kreis nicht brauchbar, denn hier entsteht eine Spirale. Woran das liegt, läßt sich gut an der Matrixform der Koordinatengleichung erkennen:
( )
(xn+1,yn+1)=(xn,yn) 1 −ε
ε 1
Die Determinante der Matrix ist ungleich 1, also ist das Ergebnis kein Kreis, sondern eine Spirale. Für den nächsten Versuch muß die Matrix so abgeändert werden, daß die Determinante
= 1 wird: ( )
(xn+1,yn+1)=(xn,yn) 1 −ε
ε 1−ε2
Daraus ergeben sich folgende Koordinatengleichungen:
xn+1 = xn + εyn
yn+1 = yn − εxn+1
Wenn diese Gleichungen in den Algorithmus eingesetzt werden, wird ein Kreis und keine Spirale mehr berechnet. Obwohl, so richtig schöne runde Kreise sind das noch nicht!
Abbildung in dieser Leseprobe nicht enthalten
Daß hier keine gleichmäßigen Kreis berechnet werden, liegt u.a. daran, daß die obige Formel mit det = 1 eigentlich keine Kreis- sondern eine Ellipsenformel darstellt. Für kleine ε fällt dieses jedoch nicht auf.
Aber wie bekomme ich jetzt endlich einen ordentlichen Kreis? Die Lösung liegt in einer dritten Gleichung für die Punktkoordinaten:
xn+1 = xn cosθ + yn sinθ
yn+1 = yn cosθ − xn sinθ
Um hiermit einen Kreis zu berechnen, müssen jedoch θ festgelegt und die Werte für sin θ und cos θ ausgewertet werden. θ sollte dabei sehr klein gewählt werden, d.h. dann, daß sin θ →
0 und cos θ → 1 für θ → 0 gilt, also eine Annäherung an die Kreisgleichung erfolgt, aber mit det = 1. Die Güte des Kreises hängt dann stark von der Rechengenauigkeit ab.
Einige Proberechnungen zeigen, daß der Wert θ auch von dem Radius des zu zeichnenden Kreises abhängt, d.h., für kleine Kreise sind weniger Berechnungsschritte erforderlich als für Größere. Einige Beispiele:
Abbildung in dieser Leseprobe nicht enthalten
Resultat:
Den geringsten Rechenaufwand, aber ein durchaus brauchbares Ergebnis erzielt man bei der Verwendung von θ = 1/r, angegeben in Rad.
Wie oben jedoch schon erwähnt, ist es auch möglich, diese Formel mit einem relativ großen θ an- zuwenden und die entstandenen Punkte durch gerade Linien zu verbinden. Dieses ist vorteilhaft, wenn es nur auf die Geschwindigkeit, nicht aber auf das genaue Aussehen des Kreises ankommt.
-
-
-
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X.