Prozedur für schönere Kreise

Einen echten Kreis auf einem quadratischen Raster, wie es bei Bildschirm- und Druckerausgabe vorliegt, zu zeichnen, ist unmöglich. Es besteht nur die Möglichkeit, die einzelnen Punkte des Kreisumfangs im Raster so zu setzen, dass die Abweichung von der idealen Linie möglichst gering ist. Zur Lösung dieses Problems wurden im Lauf der Zeit verschiedene Algorithmen benutzt. Der Algorithmus, der in der VDI-Kreisroutine Verwendung gefunden hat, besitzt zwei Merkmale, die sofort ins Auge stechen: die Kreise werden unheimlich schnell und unheimlich hässlich gezeichnet.

Leider habe ich keine Informationen über den benutzten Algorithmus, aber, betrachtet man den Kreisbogen bei bestimmten Radien, so drängt sich die Vermutung auf, daß in Wirklichkeit Polygone gezeichnet werden. Das würde auch die hohe Geschwindigkeit erklären, denn ein paar Polygonecken sind schneller zu berechnen als jeder einzelne Punkt auf dem Kreisumfang. Die durchgezogenen Linien der VDI-Darstellung sind schon schlimm genug, aber bei Verwendung verschiedener Linienmuster packt einen das Grauen. Genau diese Anforderung (die Kreise, nicht das Grauen) stellte aber eine von mir zu programmierende Routine: es sollten u.a. konzentrische Kreise mit einem gepunkteten Linienmuster ausgegeben werden.

Es blieb also nichts anderes übrig, als bessere Kreise durch das Setzen einzelner Pixel zu generieren. Der folgende Algorithmus basiert auf Horns Algorithmus und zeichnet sich dadurch aus, daß zur Berechnung nur Additionen, Subtraktionen und binäre Schiebeoperationen benutzt werden. Wer also eine höhere Geschwindigkeit benötigt, dem sollte es nicht allzu schwer fallen, die Kreisroutine in Assembler zu programmieren. Auch die Konvertierung von GFA-BASIC in andere Sprachen ist ohne weiteres möglich. Für Konvertierer sei noch angemerkt, daß der Befehl PRED den um eins verminderten, und der Befehl SUCC den um eins erhöhten Wert der übergebenen Variablen zurückliefert.

Der Routine werden die x- und y-Koordinaten des Kreismittelpunktes, der Radius und ein 16-Bit-Wort, welches das Linienmuster bestimmt, übergeben. Zum Setzen der einzelnen Punkte wird der PLOT-Befehl benutzt. Dadurch ist garantiert, daß das VDI-Clipping-Rechteck berücksichtigt wird und auf Bildschirmen mit anderer Auflösung keine Probleme auftreten.

Der Kreis wird in acht Oktanten unterteilt, deren Kreisbogen nacheinander gezeichnet werden. Vor dem Setzen eines Punktes wird geprüft, ob das Bit 0 im Linienmuster-Wort gesetzt ist. Danach wird das Linienmuster einfach durch einen ROL&-Befehl weiterrotiert, man spart sich dadurch aufwendige Bit-Zählerei.

Das Ergebnis läßt sich in der abgebildeten Hardcopy begutachten. Beim den Kreisen mit durchgezogener Linie fällt auf, daß selbst Kreise mit einem Radius von 2 Pixeln (kleinster Kreis) noch kreisähnliche Objekte ergeben, wogegen man bei VDI-’Kreisen’ mit derart kleinen Radien schon Sterne sieht.

Beim gepunkteten VDI-’Kreis’ kleben teilweise einige Pixel in Gruppen zusammen, als Ausgleich dafür läßt VDI aber an anderen Stellen etwas größere Lücken ... Horns Algorithmus zeigt solche Effekte nicht und setzt die Punkte in gleichmäßigen Abständen.

Literatur
Computer Graphics and Image Processing
1979 Marek Doros
Incremental Circle Generator

' *********************************************** 
' * Programm: inkrementaler Kreisgenerator
' * Autor:    Andreas Hollmann
' * Sprache:  GFA-BASIC
' * Copyright 1991 MAXON Computer GmbH
' ***********************************************
'
' Linienmuster definieren:
CARD{V:type&}=&X1111111111111111    ! durchgezogen
' CARD{V:type&}=&X1010101010101010  ! gepunktet 
' CARD{V:type&}=&X1110111011101110  ! gestrichelt
'
FOR r&=2 TO 80 STEP 5       ! konzentrische Kreise
    DEFLINE 1               ! weil DEFLINE auch auf PLOT wirkt
    circle(160,199,r&,types) ! echter Kreis
    DEFLINE -CARD{V:types}  !
    CIRCLE 480,199,r&       ! VDI-'Kreis'
NEXT r&
'
END
'
PROCEDURE circle(x0&,y0&,r&,type&)
    ' Parameter:
    ' x0&,y0&   = Kreismittelpunkt-Koordinaten
    ' r&        = Kreisradius
    ' type&     = Linienmuster (16 Bits)
    '
    LOCAL octant&,x&,y&
    '
    x&=r&
    '
    FOR octant&=1 TO 8
        IF ODD(octant&)     ! Oktant 1,3,5,7
            SUB r&,SHL&(x&,1)
            DO UNTIL y&>x&
                IF BTST(types,0)    ! Muster-Bit gesetzt
                    SELECT octant&  ! Punkt setzen 
                    CASE 1
                        PLOT ADD(x0&,x&),ADD(y0&,x&)
                    CASE 3
                        PLOT SUB(x0&,y&),ADD(y0&,x&)
                    CASE 5
                        PLOT SUB(x0&,x&),SUB(y0&,y&)
                    CASE 7
                        PLOT ADD(x0&,y&),SUB(y0&,x&)
                    ENDSELECT
                ENDIF
                type&=ROR&(types,1) ! Muster weitersetzen
                ADD r&,SUCC(SHL&(y&,1))
                INC y& 
                IF r&>=0
                    SUB r&,SUB(SHL&(x&,1) ,2)
                    DEC x& 
                ENDIF 
            LOOP
        ELSE                        ! Oktant 2,4,6,8
            ADD r&,SHL&(x&,1)
            DO UNTIL y&<0
                SUB r&,PRED(SHL&(y&,1))
                DEC y& 
                IF r&<0
                    ADD r&,ADD(SHL&(x&,1),2)
                    INC x& 
                ENDIF
                IF x&<>y& ! Diagonalen-Linien vermeiden 
                    IF BTST(type&,0)   ! Muster-Bit gesetzt
                        SELECT octant& ! Punkt setzen 
                        CASE 2
                            PLOT ADD(x0&,y&),ADD(y0&,x&)
                        CASE 4
                            PLOT SUB(x0&,x&),ADD(y0&,y&)
                        CASE 6
                            PLOT SUB(x0&,y&),SUB(y0&,x&)
                        CASE 8
                            PLOT ADD(x0&,x&),SUB(y0&,y&) 
                        ENDSELECT 
                    ENDIF
                    type&=ROR&(type&,1) ! Muster weitersetzen
                ENDIF
            LOOP
            type&=ROR&(type&,1) ! Muster weitersetzen
        ENDIF
        '
    NEXT octant&
    '
RETURN