Punkte eines Kreises berechnen

In der CodeLib findest du einige Grafikroutinen für diverse LCDs, die 
enthalten ASM und C Source um Kreise, Ellipsen und abgerundete Rechtecke 
zu zeichnen. Fast alle benutzen Bresenham.

Gruß Hagen

weil das langsammer ist und nicht Pixelgenau hinzubekommen ist. Entweder 
bei zu geringer Rechengenauigkeit ist die Kreislinie nich geschlossen 
oder bei zu hoher Genauigkeit berechnet man die selben Pixel mehrfach.

Wenn es nur darum geht solche Kreis und Ellipsen auf einem Rasterdevice 
zu zeichnen dann ist Bresenham das Beste. Mit diesen Alogs. berechnet 
man nur 1/4'tel des Kreise und zeichnet die anderen Teile durch 
Spiegelungen. Alle Berechnungen sind nur abhängig von der Auflösung des 
Displays und Integer Operationen, in der innersten Schleifen nur 
Additionen und Subtraktionen.
In jedem Schritt des Algos. wird durchschnittlich 1 Pixel erechnet, aber 
das hängt davon ab was man benötigt.

Gruß Hagen

CodeLib oder schick mir ne PN und ich mail dir meine S65 Library.

Gruß Hagen

Hier gibts die Original-Veröffentlichung von Bresenham 1965:
http://researchweb.watson.ibm.com/journal/sj/041/ibmsjIVRIC.pdf

Bei Answers.com gibts noch mehr Algorithmen:
http://www.answers.com/Bresenham%20algorithm
oder Goertzel, der Tondecoderalgorithmus
http://www.answers.com/topic/goertzel-algorithm

oh answers.com ist ja nur eine Suchmaschine, die betten einfach die 
englische Wikipedia ein, ich dachte das wäre was eigenes, dabei 
schmücken die sich nur mit fremden Federn.

Ja, indem du deinen Bresenham ganz leicht abänderst. Du kannst also die 
Linienstärke direkt mit dem Algo. beeinflussen.

Ich habe das so gemacht das ich kariertes Papier genommen, meinen Kreis 
nach Bresenham eingezeichnet habe, und dann erkenntst du schon wie du 
das ändern musst.

Zb. statt einen Pixel auch ein Pixel groß zu machen, kannst du einen 
Pixel als Block aus 4 Pixel zusammenbauen. Das bringt aber nicht so gute 
Ergebnisse.

Gruß hagen

zb. einen 1.5 Pixel breiten Kreis baust du indem du in deinem Besenham 
bei einem Schritt in dem X und Y Koordinate sich verändern, zusätzlich 
Pixel zeichnest.

Gruß Hagen

if f >= 0

machst du 2. Schritte, einmal in Y und danach in X Richtung. Af deinem 
karierten Papier würden sich der alte und neue Pixel nur an einer Ecke 
berühren. Das ist der richtige Zeitpunkt um zb. SetPixel(x0 - x -1, y0 - 
y -1) aufzurufen. Die entstehende Linie würde alle Pixel an deren Kanten 
verbunden zeichnen. Das erscheint dann dem Auge als 1.5 Pixel Linie.

Gruß hagen

nachfolgend ein Ausschnitt meine S65 GLCD Library.
Im Gegensatz zu deiner Kreisfunktion bauen meine Kreis,Ellipsen und 
RoundRect Funktionen auf der gleichen basisfunktion auf.

Man kann also einen Kreis zeichnen per Mittelpunk + Radius, oder 
innerhalb eines Quadrates. Wäre es ein beliebiges Rechteck so entsteht 
eine Ellipse.

Der Source zeichnet aber auch nur ein 1. Pixel breites Objekt. Da aber 
die Koordinaten des Objektes als Rechteck/Quadrat angegeben werden kann 
man hier mit 2 mal nacheinander das Quadrat als Kreis gezeichnet 
unterschiedliche Stärken zeichnen.

Und noch eines, der Source unterstützt das Ausfüllen der Objekte. 
Deshalb ist er ein bischen komplexer.

Gruß Hagen

1

void glcdSetPixel4(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdColor_t color) {

2

3

    glcdSetPixel(x1, y1, color);

4

    glcdSetPixel(x2, y1, color);

5

    glcdSetPixel(x1, y2, color);

6

    glcdSetPixel(x2, y2, color);

7

}

8

9

void glcdLine2(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdColor_t color) {

10

11

    glcdFillRect(x1, y1, x2, y1, color);

12

    glcdFillRect(x1, y2, x2, y2, color);

13

}

14

15

void glcdRoundRect(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdCoord_t a, glcdCoord_t b, glcdColor_t fgcolor, glcdColor_t bkcolor) {

16

17

    if (x1 > x2) glcdSwapCoord(x1, x2);

18

    if (y1 > y2) glcdSwapCoord(y1, y2);

19

    glcdCoord_t t;

20

    t = x2 - x1;

21

    t >>= 1;

22

    if (a > t) a = t;

23

    t = y2 - y1;

24

    t >>= 1;

25

    if (b > t) b = t;

26

    x1 += a;

27

    x2 -= a;

28

    if (fgcolor != NONE) glcdLine2(x1, y1, x2, y2, fgcolor);

29

    uint16_t as = a * a, bs = b * b;

30

    int32_t dx = 0, dy = as, ee = bs;

31

    dy *= b;

32

    ee += as / 4;

33

    ee -= dy;

34

    dy += dy;

35

    while (dx < dy) {

36

      if (fgcolor != NONE) glcdSetPixel4(x1, y1, x2, y2, fgcolor);

37

      x1--;

38

      x2++;

39

      if (ee >= 0) {

40

        y1++;

41

        y2--;

42

        dy -= as;

43

        dy -= as;

44

        ee -= dy;

45

        if (bkcolor != NONE) glcdLine2(x1, y1, x2, y2, bkcolor);

46

      }

47

      dx += bs;

48

      dx += bs;

49

      ee += bs;

50

      ee += dx;

51

  }

52

  int32_t tt = as;

53

    tt -= bs;

54

  tt *= 3;

55

  tt >>= 1;

56

  tt -= dx;

57

  tt -= dy;

58

  tt >>= 1;

59

    ee += tt;

60

    while (y1 <= y2) {

61

      if (bkcolor != NONE) glcdLine2(x1, y1, x2, y2, bkcolor);

62

      if (fgcolor != NONE) glcdSetPixel4(x1, y1, x2, y2, fgcolor);

63

      y1++;

64

      y2--;

65

      if (ee < 0) {

66

        x1--;

67

        x2++;

68

        a++;

69

        dx += bs;

70

        dx += bs;

71

        ee += dx;

72

      }

73

      dy -= as;

74

      dy -= as;

75

      ee += as;

76

      ee -= dy;

77

    }

78

}

79

80

void glcdEllipse(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdColor_t fgcolor, glcdColor_t bkcolor) {

81

82

    if (x1 > x2) glcdSwapCoord(x1, x2);

83

    if (y1 > y2) glcdSwapCoord(y1, y2);

84

    glcdRoundRect(x1, y1, x2, y2, (x2 - x1) / 2, (y2 - y1) / 2, fgcolor, bkcolor);

85

}

86

87

void glcdCircle(glcdCoord_t x, glcdCoord_t y, glcdCoord_t r, glcdColor_t fgcolor, glcdColor_t bkcolor) {

88

89

    glcdRoundRect(x - r, y - r, x + r, y + r, r, r, fgcolor, bkcolor);

90

}

Naja, die Frage ist was will man daran kommentieren ?
Das glcdEllipse() eine Ellipse zeichnet ?

Der Rest ist eben ein abgewandelter Bresenham und dessen Funktionsweise 
sollte man kennen wenn man den Source verändern möchte.

1.) du zeichnest ja deine 8'tel Segmente, alle deine SetPixel() 
Funktionen machen das.

2.) man berechnet einen fortlaufenden Fehlerwert der angibt wie weit man 
mit den zu zeichnenden Pixelkoordinaten von der Ideallinie entfernt ist. 
Überschreitet dieser Wert eine Differenz von 1 Pixel müssen die 
Koordinaten angepasst werden.

3.) man berechnet ausgehend von einer linearen X Koordinaten Erhöhung um 
+1 den Fehler in der Y Koordinaten

4.) deshalb reicht der Vergleich der X Y Koordinaten als while Bedingung 
aus

5.) versteht man den Source so versteht man Bresenham

6.) der einzigst fehlende Kommentar wäre demnach "das ist Bresenham der 
Variante X", der Rest sucht der Programmierer im WEB, Wikipedia, Bücher 
oä.

7.) die Aufgabe des Sources besteht also darin diese Objekte zu zeichnen 
und nicht daraus ein lehrbuch zu machen


Gruß Hagen

Achso ganz vergesssen:

Dein Source geht in 8'tel Segmenten vor meiner in 4'tel Segmenten. Damit 
ist dein Code zum Zeichnen von Kreisen doppelt so effizient, aber nicht 
zwangsläufig doppelt so schnell. Der Unterschied besteht darin das dein 
Code nur Kreise zeichnen kann, also alle 8 Segmente haben die gleiche 
Krümmung. Bei meinem Code gibt es 2 unterschieldiche Krümmungen, was 
auch notwendig ist um Ellipsen zeichnen zu können.

Gruß Hagen

Johannes wrote:
> Es mag ja sein das diese Funktion super funktioniert, jedoch sieht sie
> sehr undurchsichtig aus, da kein Komentar in Deinem Quellcode vorhanden
> ist.

Kommentare helfen beim Bresenham nicht viel.
Entweder man hat verstanden wie der Bresenham grundsätzlich
funktioniert, oder man muss durch die Herleitung des Verfahrens
durch. Aus dem Quellcode ist das so nicht ersichtlich, warum
der Bresenham überhaupt funktioniert. Wenn man ein paar
Beispiele am Rasterpapier durchspielt, gehts so halbwegs.

Aber am einfachsten ist, man sieht sich die Herleitung an.
zb. hier
http://www.hdm-stuttgart.de/~rk020/Files/Computeranimation/rastergraphics/printable_version.html

Das muesste man dann auch alles als Block-Kommentar einfügen
und das ist nun mal ein bischen viel (und auch nicht sinnvoll).

vielleicht noch eine Erklärung warum mein Source so anderst aussieht als 
die herkömmlichen Bresenham Implementierung.

Meistens arbeitet man Mittelpunktzentriert. In deiner Kreisfunktion zb. 
arbeitest du ausgehend von X0,Y0 und bei jedem Schritt errechnest du die 
Koordinaten der SetPixel() Funktonen neu.

In meinem Code arbeite ich die Koordinaten des umschließenden Rechteckes 
ab. Das bedeutet das ich in den Zwischenschritten nicht nur die Radien 
berechne sondern alle 4 Koordinaten updaten muß. Das ist doppelt mehr an 
Aufwand. Da wir aber dann die SetPixel(), Line() Funktionen aufrufen 
wollen und diese mit absoluten Koordinaten arbeiten, ersparen wir uns so 
das ständig Umrechnen in absolute Koordinaten. Das beschleunigt dann 
einiges diese Routine.

Das hat aber noch ganz andere Vorteile. Wenn wir zb. ein Clipping 
einbauen wollen, also eine globale Variable eines Rechteckes das einen 
Bildschirmausschnitt darstellt in das gezeichnet werden darf. Die 
Beschneidung unserer Zeichenroutinen kann man mit meinem Source viel 
einfacher durchführen, da wir ja immer die absoluten statt relativen 
Koordinaten berechnen.

Ich weiß leider selber nicht wie meine Variante heist, bzw. ob es 
überhaupt dafür einen Namen gibt. Das dürfte wohl eher nicht der Fall 
sein da es im Grunde ganz trviale Optimierungen sind. Da ich schon zu 
Uralt DOS Zeiten solche Grafikfunktionen implementiert habe weiß ich 
auch nicht mehr woher ich das habe.

Das einzisgste was ich mir quasi ausgedacht habe ist der Punkt das man 
bei der Angabe von kleinen Radien für A und B auch Rechtecke mit 
abgerundeten Ecken zeichnen kann. Zb. auch eine Art Rechteck das 
aussieht wie ein Faß.

Gruß Hagen