Strichzeichnungsalgorithmus: Beherrschen von Techniken zur präzisen Bildwiedergabe

Von Fouad Sabry

Was ist ein Linienzeichnungsalgorithmus

In der Computergrafik ist ein Linienzeichnungsalgorithmus ein Algorithmus zur Annäherung an ein Liniensegment auf diskreten grafischen Medien, wie z. B. pixelbasierten Displays und Drucker. Auf solchen Medien erfordert das Zeichnen von Strichen eine Annäherung. Grundlegende Algorithmen rastern Linien in einer Farbe. Eine bessere Darstellung mit mehreren Farbabstufungen erfordert einen fortschrittlichen Prozess, räumliches Anti-Aliasing.

Wie Sie profitieren

(I) Einblicke und Validierungen darüber die folgenden Themen:

Kapitel 1: Linienzeichnungsalgorithmus

Kapitel 2: Bresenhams Linienalgorithmus

Kapitel 3: Xiaolin Wus Linienalgorithmus

Kapitel 4: Digitaler Differentialanalysator (Grafikalgorithmus)

Kapitel 5: Mittelpunktkreisalgorithmus

Kapitel 6: 2D-Computergrafik

Kapitel 7: Digitale Geometrie

Kapitel 8: Hough-Transformation

Kapitel 9: Ray Casting

Kapitel 10: Gaußsche Funktion

(II) Beantwortung der öffentlichen Top-Fragen über Strichzeichnungsalgorithmen.

(III) Beispiele aus der Praxis für die Verwendung von Strichzeichnungsalgorithmen in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über das Grundwissen oder die Informationen für jede Art von Strichzeichnungsalgorithmus hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 5. Mai 2024

Buchvorschau

Kapitel 1: Algorithmus zum Zeichnen von Linien

Ein Linienzeichnungsalgorithmus in der Computergrafik ist ein Algorithmus, der ein Liniensegment auf diskreten grafischen Medien, wie z. B. pixelbasierten Bildschirmen und Druckern, approximiert. Auf solchen Flächen erfordert das Zeichnen von Linien eine Annäherung (in nicht trivialen Fällen). Einfache Algorithmen rastern Linien in einem einzigen Farbton. Räumliches Anti-Aliasing ist ein fortschrittliches Verfahren, das für eine genauere Darstellung zahlreicher Farbabstufungen notwendig ist.

Auf einem kontinuierlichen Medium ist für das Zeichnen einer Linie kein Algorithmus erforderlich. Zum Beispiel erzeugen Kathodenstrahloszilloskope Linien und Kurven mit analogen Phänomenen.

Im Folgenden finden Sie eine unvollständige Liste von Algorithmen für das Zeichnen von Linien:

Naiver Algorithmus

Digital Differential Analyzer (Grafikalgorithmus) – Vergleichbar mit dem naiven Linienzeichnungsalgorithmus, mit ein paar kleinen Unterschieden.

Der Linienalgorithmus von Bresenham ist so abgestimmt, dass er nur Additionen verwendet (d. h. keine Division oder Multiplikation) und Gleitkommaberechnungen vermeidet.

Der Linienalgorithmus von Xiaolin Wu – der räumliches Anti-Aliasing durchführen kann – scheint aufgrund der schwankenden Helligkeit entlang der Länge der Linie seilig zu sein. Dieser Effekt kann jedoch deutlich minimiert werden, indem die Pixelwerte für die Gammakurve des Zieldisplays vorkompensiert werden, z. B. out = in (1/2,4).

Gupta-Spruill-Formel

Das direkte Skizzieren der Gleichung, die die Linie bestimmt, ist die einfachste Methode des Screenings.

dx = x2 − x1

dy = y2 − y1

für x von x1 bis x2 do

y = y1 + dy × (x − x1) / dx

Grundstück(x, y)

Hier wurden die Punkte bereits geordnet, so dass x_{2}>x_{1} .

Dieser Algorithmus funktioniert einwandfrei, wenn {\displaystyle dx\geq dy} (d. h. der Farbverlauf kleiner oder gleich 1 ist), aber wenn dx

Der primitive Algorithmus zum Zeichnen von Linien ist auf einem digitalen Computer ineffizient und daher langsam. Die Anzahl der Operationen und die Verwendung von Gleitkommaberechnungen tragen zu seiner Ineffizienz bei. Stattdessen werden Algorithmen wie der Linienalgorithmus von Bresenham oder der Linienalgorithmus von Xiaolin Wu bevorzugt.

Basierend auf dem Linienalgorithmus von Bresenham fügt der Gupta-Sproll-Algorithmus Antialiasing hinzu.

Der Pseudocode für eine optimierte Form des Gupta-Sproull-Algorithmus lautet wie folgt:

DrawLine(x1, x2, y1, y2) {

x = x1;  y = y1;  dx = x2 − x1;  dy = y2 − y1;  d = 2 * dy − dx; Impulsunterscheider

Euklidischer Abstand des Punktes (x,y) von der Linie (mit Vorzeichen)

D = 0;  Euklidischer Abstand zwischen Punkten (x1, y1) und (x2, y2)

length = sqrt(dx * dx + dy * dy);  sin = dx / Länge;  cos = dy / Länge;  while (x <= x2) {

IntensifyPixels(x, y − 1, D + cos);  IntensifyPixels(x, y, D);  IntensifyPixels(x, y + 1, D − cos);  x = x + 1

if (d <= 0) {

D = D + Sünde;  d = d + 2 * dy;  } else {

D = D + sin − cos;  d = d + 2 * (dy − dx);  y = y + 1; } }}

Die Funktion IntensifyPixel(x,y,r) verwendet eine radiale Linientransformation und legt die Intensität des Pixels (x,y) mit einem kubischen Polynom fest, dessen Wert vom Abstand des Pixels r von der Linie abhängt.

{Ende Kapitel 1}

Kapitel 2: Bresenhams Linienalgorithmus

Der Linienalgorithmus von Bresenham ist ein Linienzeichnungsverfahren, das die n-dimensionalen Rasterpunkte identifiziert, die ausgewählt werden sollen, um eine gerade Linie zwischen zwei Punkten anzunähern. Es wird häufig verwendet, um Linienprimitive in einem Bitmap-Bild (z. B. auf einem Computerbildschirm) zu zeichnen, da es nur ganzzahlige Addition, Subtraktion und Bitverschiebung erfordert, was alles relativ kostengünstige Operationen in historisch vorherrschenden Computerarchitekturen sind. Es ist einer der frühen Algorithmen, die im Bereich der Computergrafik entwickelt wurden, und ist ein inkrementeller Fehleralgorithmus. Eine Modifikation des ursprünglichen Algorithmus kann verwendet werden, um Kreise zu erstellen.

Während Antialiasing-fähige Techniken wie der Wu-Algorithmus auch in der modernen Computergrafik weit verbreitet sind, bleibt Bresenhams Linienalgorithmus aufgrund seiner Geschwindigkeit und Einfachheit von Bedeutung. Der Algorithmus wird in Plottern und den Grafikchips moderner Grafikkarten verwendet. Auch in zahlreichen Software-Grafikbibliotheken vorhanden. Aufgrund der Einfachheit des Algorithmus wird er häufig in die Grafikhardware oder Firmware aktueller Grafikkarten implementiert.

Heute bezieht sich der Begriff Bresenham auf eine Familie von Algorithmen, die Bresenhams ursprünglichen Ansatz erweitern oder verändern.

Der Linienalgorithmus von Bresenham ist nach Jack Elton Bresenham benannt, dem IBM-Mitarbeiter, der ihn 1962 entwickelte. Im Jahr 2001 veröffentlichte Bresenham:

Ich arbeitete im Rechenlabor des IBM San Jose Development Lab. Über das Schreibmaschinenterminal 1407 wurde ein Calcomp-Plotter mit einem IBM 1401 verbunden. Der Algorithmus wurde im Sommer 1962 oder möglicherweise einen Monat früher in der Produktion eingesetzt. Calcomp (Jim Newland und Calvin Heft) besaß Kopien der Programme, weil Unternehmen sie damals offen teilten. Als ich im Herbst 1962 nach Stanford zurückkehrte, spendete ich ein Exemplar an die Bibliothek des Stanford-Rechenzentrums. Auf der nationalen ACM-Tagung 1963 in Denver, Colorado, wurde eine Beschreibung der Strichzeichnungsroutine zur Präsentation angenommen. In jenem Jahr wurden nur die Tagesordnung der Referenten und Themen in einer Ausgabe der Mitteilungen der ACM veröffentlicht. Nach meinem Vortrag fragte jemand vom IBM Systems Journal, ob sie die Arbeit veröffentlichen dürften. Ich willigte gerne ein, und es wurde 1965 veröffentlicht.

Bresenhams Ansatz wurde erweitert, um Kreise, Ellipsen, kubische und quadratische Bézier-Kurven sowie native Anti-Aliasing-Versionen dieser Kurven zu erzeugen.

Die folgenden Konventionen werden verwendet:

Die obere linke Koordinate ist (0,0), so dass die Pixelkoordinaten nach rechts und unten wachsen (z. B. befindet sich das Pixel bei (7,4) direkt über dem Pixel bei (7,5)), während die untere rechte Koordinate (1,1) ist).

Die Mittelpunkte der Pixel haben ganzzahlige Koordinaten.

Die Endpunkte der Linie sind die Pixel bei (x_{0},y_{0}) und (x_{1},y_{1}) , wobei die erste Koordinate die Spalte und die zweite Koordinate die Zeile darstellt.

Der Algorithmus wird zunächst nur für das Oktant angezeigt, in dem das Segment nach unten und nach rechts ( x_{0}\leq x_{1} und y_{0}\leq y_{1} ) verläuft und