DE4013851C2 - Verfahren zur grafischen darstellung einer geraden auf einem bildschirm - Google Patents

Description

Die Erfindung betrifft ein Verfahren zur grafischen Darstellung einer zwischen einem Anfangspunkt und einem Endpunkt verlaufenden Geraden unter Verwendung eines die Pixel des Bildschirms ansteuernden Algorithmus, mit dem wenigstens im Bereich von durch die Pixelverteilung entstehenden Stufen der Geraden eine Mehrzahl von Pixelpunkten mit unterschiedlichen Intensitäten angesteuert wird, wobei verschiedene Winkelbereiche unterschieden werden.

Für die Darstellung von Geraden auf einem Bildschirm müssen natur­ gemäß die regelmäßig in Zeilen und Spalten angeordneten Pixel verwendet werden. Sind die Geraden gegenüber der Horizontalen bzw. der Vertikalen geneigt, müssen die Pixel Stufen bilden, um resul­ tierend die Gerade darzustellen. Insbesondere bei geringen Abwei­ chungen von den Winkeln 0°, 45° und 90° treten erhebliche, deutlich sichtbare Stufen auf, die in manchen Anwendungsfällen besonders störend sind.

Die Berechnung der anzusteuernden Pixel des Bildschirms erfolgt überlicherweise mit dem Bresenham-Algorithmus, der auf Multipli­ kationen und Divisionen verzichtet und daher relativ schnell ar­ beitet. Nachteilig an dem Bresenham-Algorithmus sind die deutlich sichtbaren Treppenstufen der gezogenen Linien sowie die Tatsache, daß eine 45°-Linie eine geringere Helligkeit als eine 0°-Linie hat, weil die Pixeldichte auf der 45°-Linie um den Faktor kleiner ist als auf der 0°-Linie.

Es ist bereits vorgeschlagen worden, den störenden Eindruck der Stufen in den gezogenen Linien dadurch zu vermindern, daß in den Stufen zusätzliche Punkte mit geringerer Intensität gesetzt werden. Hierfür sind zeitintensive Software-Lösungen vorgeschlagen worden, bei denen für jede Linie die Steigung berechnet und mit Hilfe der Nachkomma-Stellen die Punkte im Raster für die zusätzlichen Pixel mit geringerer Intensität ermittelt werden. Für das Ziehen einer Linie wird dabei eine zusätzlichen Fließkomma-Recheneinheit und etwa die doppelte Zeit gegenüber der Linie nach dem Bresenham-Algorithmus benötigt. Eine derartige Lösung ist daher nachteilig.

Ein Verfahren der eingangs erwähnten Art ist durch IBM Technical Disclosure Bulletin, Vol. 26, No. 7 B, Dec. 1983, Seiten 3758 bis 3761, bekannt. Bei diesem Verfahren wird zur Verbesserung der Darstellung von Vektoren (Geraden) auf einem Bildschirm die Gerade mehrfach gezogen, und zwar mit regelmäßig veränderten Endpunkten. Für das wiederholte Ziehen der Geraden wird dabei eine mehrfache Rechenzeit benötigt, um die gewünschte verbesserte Darstellung zu erreichen. Zusätzlich erfolgt eine meist unerwünschte Verbreiterung der Geraden.

Aus der DE 35 08 606 A1 ist ein Verfahren bekannt, bei dem ganze Geraden mit Grundlinien und Zusatzlinien abgespeichert werden, aus denen für den Einzelfall schnelle Interpolationen möglich sein sollen. Auch hierfür werden erhebliche Rechenzeiten benötigt.

Der Erfindung liegt die Aufgabe zugrunde, bei einem Verfahren der eingangs genannten Art die Qualität der grafischen Darstellung einer Geraden auf einem Bildschirm zu verbessern, ohne hierfür regelmäßig eine zusätzliche Rechenzeit zu benötigen.

Diese Aufgabe wird bei einem Verfahren der eingangs erwähnten Art dadurch gelöst, daß für die verschiedenen Winkelbereiche verschiedene Pixelkonfigurationen unter Verwendung von Pixelpunkten mit verringerter Intensität festgelegt werden, die im Bereich ermittelter Stufen automatisch anstelle einere Mehrzahl von errechneten Pixelpunkten angesteuert werden.

Das erfindungsgemäße Verfahren geht im Unterschied zum Bresenham-Algorithmus nicht davon aus, daß Einzelpixel linear (unter Bildung der Stufen) aneinandergereiht werden, um so eine der dargestellten Geraden angenäherte Gerade zu bilden. Im Gegensatz dazu sieht das erfindungsgemäße Verfahren vor, in vielen Fällen solche Einzelpixel durch Pixelpaare zu ersetzen, die mit verringerter Intensität angesteuert werden, und zwar auch für den Fall, daß die gewünschte Gerade genau durch ein Pixel hindurchläuft. So ist beispielsweise in einem bevorzugten Ausführungsbeispiel der Erfindung die Dar­ stellung einer 45°-Linie, die ausschließlich (ohne Bildung von Stufen) durch Pixel hindurchläuft, ausschließlich mit Pixelpaaren erfolgt, wobei der Anfangs- und der Endpunkt ausgenommen sind. Kennzeichnend für die vorliegende Erfindung sind daher Pixelkon­ figurationen mit Pixelpunkten verringerter Intensität, die normal angesteuerte Pixelpunkte - vorzugsweise im Bereich von sonst ent­ stehenden Stufen - ersetzen. Für die erwähnte 45°-Linie führt die Erfindung dazu, daß die Helligkeit dieser Linie genauso groß sein kann, wie die Helligkeit einer 0°-Linie. In einer bevorzugten Ausführungsform der Erfindung erfolgt die Ersetzung der normal angesteuerten Pixelpunkte mit Konfigurationen von Pixelpunkten mit verringerter Intensität unter dem Gesichtspunkt der gleichen Helligkeit für unter verschiedenen Winkeln dargestellte Geraden.

Zweckmäßig ist eine Ausgestaltung der Erfindung, bei der die ver­ ringerte Intensität 65%-80% der normalen Intensität beträgt. Bevorzugt ist allerdings die Verwendung von zwei unterschiedlich verringerten Intensitäten, von denen die erste verringerte Inten­ sität 65%-80% der normalen Intensität und die zweite verringerte Intensität 45%-60% der normalen Intensität beträgt. Bei Farbdar­ stellungen wird die jeweils verringerte Intensität farbabhängig aus einer üblichen Farbtafel ausgewählt.

Ein sehr funktionstüchtiger und schneller Algorithmus läßt sich erstellen, wenn eine Unterscheidung in wenigstens drei, vorzugsweise fünf Winkelbereiche zwischen 0° und 45° vorgenommen wird, wobei zweckmäßigerweise die Winkel 0° und 45° gesondert behandelt werden. Für die Schnelligkeit ist es von Bedeutung, daß der Algorithmus ohne Multiplikationen und Divisionen auskommt. Dies gilt auch für die Aufteilung in die verschiedenen Winkelbereiche, die vorzugsweise durch Additionen und Subtraktionen der Abstände von Anfangs- und Endpunkt in X- und Y-Richtung bzw. hieraus durch Addition und/oder Subtraktion gebildeter Hilfsgrößen erfolgt.

Für die durch den erfindungsgemäßen Algorithmus erreichbare Bear­ beitungsgeschwindigkeit ist es wesentlich, daß bei der Aufteilung in die unterschiedlichen Winkelbereiche Gesetzmäßigkeiten vorliegen, die es erlauben, bestimmte Pixelpunkte bzw. Konfigurationen beim Vorliegen gewisser Voraussetzungen ohne weitere Berechnung sofort festzulegen, so daß nicht für jeden Punkt der Linie eine Rechen­ schleife erforderlich ist. Die Zentrierung der einzusetzenden Konfigurationen erfolgt durch eine für den betreffenden Winkel­ bereich geeignete Vorbesetzung einer Entscheidungsschwelle für eine Stufe in der X- oder Y-Richtung. Die sich bei einer bevorzugten Aufteilung des Winkelbereichs zwischen 0° und 45° ergebenden Konfi­ gurationen sind in der nachstehenden Beschreibung eines anhand der Zeichnung verdeutlichten Ausführungsbeipiels näher erläutert.

In der Zeichnung zeigt

Fig. 1 eine Darstellung einer 45°-Linie mit dem erfindungs­ gemäßen Algorithmus und mit dem bekannten Bresenham- Algorithmus,

Fig. 2 bis 4 Darstellungen für den Winkelbereich zwischen 38° und 45°, wobei Fig. 2 die obere Grenze dieses Bereiches, Fig. 3 einen mittleren Fall dieses Be­ reiches und Fig. 4 die untere Grenze dieses Be­ reiches zeigt,

Fig. 5 bis 7 Darstellungen gemäß Fig. 1 für den Winkelbereich von 18,4° bis 38°, wobei Fig. 5 die obere Grenze, Fig. 6 einen mittleren Fall und Fig. 7 die untere Grenze dieses Winkelbereiches zeigen

Fig. 8 bis 9 Darstellungen gemäß Fig. 1 für den Winkelbereich von 14,0° bis 18,4°, wobei Fig. 8 die obere Grenze und Fig. 9 die untere Grenze dieses Winkelbereiches zeigen,

Fig. 10 und 11 Darstellungen gemäß Fig. 1 für den Winkelbereich von 9,5° bis 14,0°, wobei Fig. 10 die obere Grenze und Fig. 11 die untere Grenze dieses Winkelbereiches zeigen,

Fig. 12 bis 14 Darstellungen gemäß Fig. 1 für den Winkelbereich von 5,7° bis 9,5°, wobei Fig. 12 die obere Grenze, Fig. 13 einen mittleren Fall und Fig. 14 die untere Grenze dieses Winkelbereiches zeigen,

Fig. 15 bis 17 Darstellungen gemäß Fig. 1 für den Winkelbereich von < 0 bis 5,7°, wobei Fig. 15 die obere Grenze, Fig. 16 einen mittleren Fall und Fig. 17 die untere Grenze dieses Bereiches zeigen.

In den Figuren bedeuten x normale Pixelpunkte mit voller Intensität, O Pixelpunkte mit einer ersten, verminderten Intensität (ca. zwei Drittel der vollen Intensität) und - Pixelpunkte mit einer zweiten, verminderten Intensität (etwa halbe Intensität).

In den nachstehenden Figuren sind jeweils die Darstellungen der Linien verschiedener Winkel oben nach dem erfindungsgemäßen Ver­ fahren und unten im Vergleich dazu nach dem Bresenham-Algorithmus dargestellt.

Fig. 1 zeigt eine 45°-Linie, deren Darstellung nach dem Bresenham- Algorithmus an sich unproblematisch ist, weil die angesteuerten Pixelpunkte alle genau auf der darzustellenden Geraden liegen. Dennoch entsteht nach dem Bresenham-Algorithmus der Nachteil, daß die dargestellte Gerade eine geringere Helligkeit hat als eine horizontale Gerade, weil die Pixelpunkte einen um größeren Abstand zueinander aufweisen als bei einer horizontalen Geraden. Nach dem erfindungsgemäßen Verfahren wird die 45°-Linie daher mit einem Anfangs- und Endpunkt mit normaler Intensität, im übrigen aber mit untereinander angeordneten Pixelpaaren dargestellt, die jeweils mit der ersten verminderten Intensität angesteuert sind. Dadurch wird gewährleistet, daß die resultierende Helligkeit der dargestellten Geraden der Helligkeit einer horizontalen Geraden entspricht.

Fig. 2 zeigt den Fall einer Geraden, die geringfügig unter 45° geneigt ist. Hier führt der Bresenham-Algorithmus zu einer deutlich erkennbaren Stufe. Fig. 3 und 4 zeigen, daß bei etwas größeren Abweichungen von der 45°-Richtung mehrere deutlich er­ kennbare Stufen auftreten. Bei dem erfindungsgemäßen Verfahren wird für diesen Winkelbereich ein Punkt mit normaler Intensität erzeugt, wenn dieser auf der Geraden liegt. Im Anschluß an den Punkt mit einer normalen Intensität wird in derselben Zeile ein Punkt mit der verminderten zweiten Intensität und in Neigungs­ richtung darüber oder darunter ein Punkt mit der verminderten ersten Intensität gesetzt. Diese Konfiguration ist typisch für den Winkel­ bereich unter 45° bishin zu etwa 38°, wie dies in Fig. 4 ver­ deutlicht ist. Zwischen diesen Konfigurationen befinden sich die aus Fig. 1 bekannten Pixelpaare mit der ersten verminderten In­ tensität. Für den nur wenig unter 45° liegenden, in Fig. 2 dar­ gestellten Winkel, sind die Konfigurationen mit dem Punkt der normalen Intensität in Kombination mit dem Pixelpaar aus der ersten und der zweiten verminderten Intensität nur an den Endpunkten vorhanden, während im übrigen die Pixelpaare mit der ersten ver­ minderten Intensität geschrieben werden, während an der unteren Grenze dieses Winkelbereiches nur noch jeweils ein Pixelpaar mit der ersten verminderten Intensität zwischen den für diesen Winkel­ bereich typischen Konfigurationen um die Punkte mit der normalen Intensität herum vorhanden sind. Aufgrund der aufgezeigten Gesetz­ mäßigkeit für diesen Winkelbereich ist es möglich, zusätzlich zu einem Pixelpunkt normaler Intensität sofort die benachbarten Pixel­ paare mit den beiden verminderten Intensitäten sowie zumindest ein weiteres Pixelpaar mit der ersten verminderten Intensität zu setzen, ohne hierfür Rechenschritte ablaufen lassen zu müssen. Zur Zentrierung der Stufung wird die Entscheidungsschwelle für das Setzen eines neues Punktes mit voller Intensität auf (5 dy-3 dx) vorbesetzt, während der Bresenham-Algorithmus die Ent­ scheidungsschwelle (2 dy-dx) vorbesetzt.

Die Fig. 5 bis 7 zeigen den Winkelbereich von < 38° 18,4°. Verwendet werden hier nur Punkte mit normaler Intensität und die Pixelpaare mit der ersten verminderten Intensität. Mit abnehmendem Winkel wird die relative Anzahl der Pixelpaare mit der verminderten ersten Intensität im Vergleich zu den Punkten mit normaler Intensi­ tät vermindert. In Fig. 5 beträgt das Verhältnis 3 : 1, für den mittleren Fall dieses Winkelbereichs in Fig. 6 1 : 1 und für die untere Grenze, die in Fig. 7 dargestellt ist, 1 : 2. Die Fig. 8 und 9 zeigen einen Winkelbereich von < 18,4° bis 14,0°. Zwischen Punkten mit normaler Intensität befinden sich hier cha­ rakteristische Anordnungen eines Pixelpaares mit den beiden ver­ minderten Intensitäten, daran anschließend ein Pixelpunkt mit der verminderten ersten Intensität.

Die Fig. 10 und 11 stellen den Winkelbereich < 14,0° 9,5° dar. Für diese kleineren Winkel ändert sich die charakeristische Konfi­ guration der Pixelanordnungen mit der verminderten Intensität durch zwei antiparallele Paare mit den beiden verminderten Intensitäten. Gegenüber dem in den Fig. 8 und 9 gezeigten Winkelbereich wird demzufolge ein Punkt mit verminderter zweiter Intensität hinzuge­ fügt. Diese charakteristische Anordnung kann zur Verminderung der Rechenzeit ohne zusätzliche Rechenschritte gesetzt werden.

Fig. 12 bis 14 zeigen Fälle aus dem flachen Winkelbereich von < 9,5° 5,7°. Die von den Fig. 10 und 11 bekannte Anordnung der antiparallelen Pixelpaare mit den beiden verminderten Inten­ sitäten ist für diesen Winkelbereich erweitert worden zu einer Konfiguration von zwei antiparallelen Pixelpaaren mit den beiden verminderten Intensitäten. Zwei parallelen Pixelpaaren dieser Art folgen somit zwei antiparallele Pixelpaare. Da anschließend immer wenigstens ein Normalpunkt folgt, kann dieser gleich mitgesetzt werden.

Die in den Fig. 15 bis 17 dargestellten Fälle noch geringerer Steigung verwenden eine Konfiguration aus drei parallelen Pixel­ paaren mit den verminderten Intensitäten, denen sich drei anti­ parallele entsprechende Pixelpaare anschließen. Zu diesen Kon­ figurationen können benachbart gleich drei Normalpunkte mitgesetzt werden, da - wie der Übergang von der Fig. 15 zu Fig. 16 und 17 zeigt, die Anzahl der Normalpunkte mit abnehmendem Winkel ansteigt, bis beim minimalen Winkel, der sich aus dem Höhenabstand dy = 1 für die Endpunkte über die gesamte Breite des Bildschirms ergibt, nur noch eine charakteristische Konfiguration mit den anschließenden Normalpunkten vorhanden ist.

Es ist ohne weiteres ersichtlich, daß für die anderen Winkel­ bereiche dieselben Gesichtspunkte gelten und die Geraden in analoger Weise aufgebaut werden können.

Überraschenderweise hat es sich gezeigt, daß das erfindungsgemäße Verfahren trotz der zusätzlich gesetzten Pixelpunkte regelmäßig eine kürzere Rechenzeit benötigt als der Bresenham-Algorithmus. Nur für ungünstige Einzelfälle kommt es zu einer Rechenzeit, die geringfügig über der Rechenzeit für den Bresenham-Algorithmus liegt.

Ein kommentiertes Programm in der Programmiersprache C ist nachfol­ gend angegeben, aus dem sich die bildlichen Darstellungen der Fig. 1 bis 17 ergeben haben.

Claims (22)

1. Verfahren zur grafischen Darstellung einer zwischen einem Anfangspunkt und einem Endpunkt verlaufenden Geraden unter Verwendung eines die Pixel des Bildschirms ansteuernden Algorithmus, mit dem wenigstens im Bereich von durch die Pixelverteilung entstehenden Stufen der Geraden eine Mehrzahl von Pixelpunkten mit unterschiedlichen Intensitäten angesteuert wird, wobei verschiedene Winkelbereiche unterschieden werden, dadurch gekennzeichnet, daß für die verschiedenen Winkelbereiche verschiedene Pixelkonfigurationen unter Verwendung von Pixelpunkten mit verringerter Intensität festgelegt werden, die im Bereich ermittelter Stufen automatisch anstelle einer Mehrzahl von errechneten Pixelpunkten angesteuert werden.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Ersetzung der normal angesteuerten Pixelpunkte mit Konfi­ gurationen von Pixelpunkten mit verringerter Intensität unter dem Gesichtspunkt der gleichen Helligkeit für unter verschiedenen Winkeln dargestellten Geraden erfolgt.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die verringerte Intensität 65%-80% der normalen In­ tensität beträgt.

4. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekenn­ zeichnet, daß wenigstens zwei unterschiedlich verringerte Intensitäten vorgesehen werden.

5. Verfahren nach Anspruch 3 und 4, dadurch gekennzeichnet, daß die zweite verringerte Intensität 45%-60% der normalen Intensität ausmacht.

6. Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekenn­ zeichnet, daß eine Unterscheidung in mindestens drei, vor­ zugsweise fünf Winkelbereiche zwischen 0° und 45° vorgenommen wird.

7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß die Winkel 0° und 45° gesondert behandelt werden.

8. Verfahren nach einem der Ansprüche 4 bis 7, dadurch gekenn­ zeichnet, daß in einem Winkelbereich zwischen 0° und 5,7° im Bereich einer sonst auftretenden Pixelstufe sechs Pixelpunkte durch paarweise untereinander angeordnete Pixelpunkte mit jeweils der ersten und der zweiten verminderten Intensität gesetzt werden.

9. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß im Anschluß an die paarweisen Punkte verminderter Intensität drei Pixelpunkte normaler Intensität sofort mitgesetzt werden.

10. Verfahren nach einem der Ansprüche 4 bis 9, dadurch gekenn­ zeichnet, daß in einem Winkelbereich zwischen 5,7° und 9,5° im Bereich einer sonst auftretenden Pixelstufe vier Pixelpunkte durch paarweise untereinander angeordnete Pixelpunkte mit jeweils der ersten und zweiten verminderten Intensität gesetzt werden.

11. Verfahren nach Anspruch 10, dadurch gekennzeichnet, daß im Anschluß an die paarweisen Punkte verminderter Intensität zwei Pixelpunkte normaler Intensität sofort mitgesetzt werden.

12. Verfahren nach einem der Ansprüche 4 bis 11, dadurch gekennzeichnet, daß im Winkelbereich zwischen 9,5° und 14° im Bereich einer sonst auftretenden Pixelstufe zwei Pixelpunkte durch paarweise untereinander angeordnete Pixelpunkte mit jeweils der ersten und der zweiten verminderten Intensität gesetzt werden.

13. Verfahren nach Anspruch 12, dadurch gekennzeichnet, daß im Anschluß an die paarweisen Punkte verminderter Intensität ein Pixelpunkt normaler Intensität sofort mitgesetzt wird.

14. Verfahren nach einem der Ansprüche 4 bis 13, dadurch gekennzeichnet, daß im Winkelbereich zwischen 14° und 18,4° im Bereich einer sonst auftretenden Pixelstufe zwei Pixelpunkte durch eine Konfiguration mit einem Punktepaar der beiden verschiedenen verringerten Intensitäten und einem Punkt mit der verringerten ersten Intensität ersetzt werden.

15. Verfahren nach Anspruch 14, dadurch gekennzeichnet, daß neben der Konfiguration der Punkte mit den verringerten Intensitäten sofort ein Pixelpunkt normaler Intensität mitgesetzt wird.

16. Verfahren nach einem der Ansprüche 1 bis 15, dadurch gekennzeichnet, daß im Winkelbereich von 18,4° bis 38° ein Pixelpunkt im Bereich einer sonst auftretenden Pixelstufe durch ein Paar untereinander angeordneter Pixelpunkte mit der verminderten ersten Intensität ersetzt wird.

17. Verfahren nach einem der Ansprüche 4 bis 16, dadurch gekennzeichnet, daß im Winkelbereich von 38° bis 45° neben normalen Pixelpunkten ein Paar übereinander angeordneter Pixelpunkte mit den beiden verminderten Intensitäten und wenigstens ein Paar übereinander angeordneter Pixelpunkte mit der ersten verminderten Intensität angeordnet sind.

18. Verfahren nach einem der Ansprüche 1 bis 17, dadurch gekennzeichnet, daß bei dem Winkel 45° alle Pixelpunkte außer den Endpunkten durch Paare untereinander angeordneter Pixelpunkte mit der verminderten ersten Intensität ersetzt sind.

19. Verfahren nach einem der Ansprüche 1 bis 18, dadurch gekennzeichnet, daß der Algorithmus ohne Multiplikations- und Divisionsschritte ausgebildet wird.

20. Verfahren nach Anspruch 19, dadurch gekennzeichnet, daß die Unterteilung in die verschiedenen Winkelbereiche durch Additionen und Subtraktionen der Abstände von Anfangs- und Endpunkt in X- und Y-Richtung bzw. hieraus durch Addition und/oder Subtraktion gebildeter Hilfsgrößen erfolgt.

21. Verfahren nach einem der Ansprüche 1 bis 20, dadurch gekennzeichnet, daß die Verringerung der Intensität in Abhängigkeit von der jeweiligen Farbe nach Farbtabellen gewählt wird.

22. Verfahren nach einem der Ansprüche 1 bis 21, dadurch gekennzeichnet, daß durch eine geeignete Vorbesetzung einer Entscheidungsschwelle (E) für eine Stufe in X- oder Y-Richtung eine Zentrierung für die eingesetzte Konfiguration aus den Punkten mit der verminderten Intensität vorgenommen wird.