Zeichnen eines Kreises nach Bresenhan auf Graphig Display

[Paul (Gast)]

Hallo
Mit dem folgenden Programm kann ich ohne Probleme einen Kreis auf einem 
Graphigdisplay zeichen.

void LCD_Plot_Circle(int8_t x0, int8_t y0, int8_t radius1)
  {
  int8_t radius;  
  if (radius1 > 50)    // Kontrolle Radius begrenzt auf max 50
    {
      radius  = 50;  
    }   
  else 
    {
    radius = radius1;
    }  
  int8_t f = 1 - radius;
  int8_t ddF_x = 0;
  int8_t ddF_y = -2 * radius;
  int8_t x = 0;
  int8_t y = radius;
  LCD_Set_Point(x0, y0 + radius);
  LCD_Set_Point(x0, y0 - radius);
  LCD_Set_Point(x0 + radius, y0);
  LCD_Set_Point(x0 - radius, y0);
  while(x < y)
    {
    if(f >= 0)
      {
      y--;
      ddF_y += 2;
      f += ddF_y;
      }
    x++;
    ddF_x += 2;
    f += ddF_x + 1;
    LCD_Set_Point(x0 + x, y0 + y);
    LCD_Set_Point(x0 - x, y0 + y);
    LCD_Set_Point(x0 + x, y0 - y);
    LCD_Set_Point(x0 - x, y0 - y);
    LCD_Set_Point(x0 + y, y0 + x);
    LCD_Set_Point(x0 - y, y0 + x);
    LCD_Set_Point(x0 + y, y0 - x);
    LCD_Set_Point(x0 - y, y0 - x);
    }
  }

Damit kann ich einen Kreis zeichnen mit einer Breite von einem Pixel.
Wie kann ich das Programm ändern um einen Kreisring mit einer 
einstellbaren Breite zu zeichnen?

Paul

[STK500-Besitzer (Gast)]

Paul schrieb:
> Damit kann ich einen Kreis zeichnen mit einer Breite von einem Pixel.
> Wie kann ich das Programm ändern um einen Kreisring mit einer
> einstellbaren Breite zu zeichnen?

Indem du nur den Radius änderst?!

[c-hater (Gast)]

Paul schrieb:

> Wie kann ich das Programm ändern um einen Kreisring mit einer
> einstellbaren Breite zu zeichnen?

Hausaufgabe.

Du musst einfach nur verstehen, was das Programm tut und es entsprechend 
ergänzen.

Übrigens hieß der Mann Bresenham und Graphik schreibt sich mit k am 
Ende...

[MaWin (Gast)]

Paul schrieb:
> Wie kann ich das Programm ändern um einen Kreisring mit einer
> einstellbaren Breite zu zeichnen?

Es gibt sehr unterschiedliche Ansätze.

Der sauberste ist mit Regions: man erzeugt die äussere Umrandung mit dem 
Kreisalgorithmus, eine innere Umrandung und subtrahiert die Regionen, 
stanzt also ein Loch in die Scheibe.

Das funktioniert gut, wenn die Graphiklibrary schon Regionen hat, wie 
Windows.

Alternativ zeichnet man eine Linie (der Dicke 5 oder so) Stück für Stück 
im 36-eck, so macht es z.B. GEM, das keine Regionen kennt.

Wer gar nichts hat, zeichnet einen Kreis im Radius (z.B. 36) dann einen 
35 dann einen 34, dann einen 33 dann einen 32 hinein. Kann, wenn man 
Pech hat, pixelgrosse Löcher ergeben.

Wieder andere nutzen Cordic und zeichen Schritt um Schritt einen Punkt 
von 5 Pixeln Durchmesser (bitblt eines Icons) bis der Kreis durchlaufen 
wurde.

Der schnellste und schönste, wohl aber auch aufwändigste Algorithmus 
dürfte sweepline sein, der von oben nach unten je eine (oberer unteter 
Kreisabschluss) oder 2 (inmitten des Kreises) horizontale Linien von 1 
Pixel Höhe zeichnet und dabei der Kontur des Kreises folgt, in dem 
stückweise 4 Bresenham-Gleichungen ausgewertet werden: aussen links 
Anfang, (innen links Ende, innen rechts Anfang), aussen rechts Ende.
Das geht schnell, erlaubt direktes clipping, und setzt jeden Pixel nur 1 
mal.

Du wirst Verfahren 3 nutzen ...

[c-hater (Gast)]

MaWin schrieb:

> Du wirst Verfahren 3 nutzen ...

Mal abgesehen davon, dass er es wohl nicht gebacken bekommen wird, hast 
du offensichtlich von dem besten Algorithmus (zumindest unter dem 
anzunehmenden Umstand, dass nur SetPixel() bzw. Äquivalent als 
Supportfunktion existiert) noch nix gehört. Dabei ist es so einfach, 
wenn man sich die Eigenschaften des Bresenham vergegenwärtigt.

Aber OK, in einer Beziehung ist dieser Algorithmus suboptimal: An den 
Berührungspunkten der vier Quadranten werden Pixel mehrfach gesetzt. 
Drauf geschissen. Nur bei kleinen Kreisen und im Verhältnis großer 
Strichstärke könnte das signifikant werden, ansonsten überwiegt 
definitiv der Vorteil durch den trivialen Algorithmus.

[Nils (Gast)]

c-hater schrieb:
> Übrigens hieß der Mann Bresenham und Graphik schreibt sich mit k am
> Ende...

Jack Bresenham lebt noch.

[c-hater (Gast)]

Nils schrieb:

> Jack Bresenham lebt noch.

Hätte ich nicht gedacht.

Aber schön für ihn, ich gönne ihm noch viele weitere Jahre. Wenn sich 
irgendwer das verdient hat, dann er.

[Paul (Gast)]

MaWin schrieb:
> Wer gar nichts hat, zeichnet einen Kreis im Radius (z.B. 36) dann einen
> 35 dann einen 34, dann einen 33 dann einen 32 hinein. Kann, wenn man
> Pech hat, pixelgrosse Löcher ergeben.

Meinst du diese Version?

c-hater schrieb:
> Mal abgesehen davon, dass er es wohl nicht gebacken bekommen wird, hast
> du offensichtlich von dem besten Algorithmus (zumindest unter dem
> anzunehmenden Umstand, dass nur SetPixel() bzw. Äquivalent als
> Supportfunktion existiert) noch nix gehört.

Ja, du hast recht, das bekomme ich nicht hin. Da ich keinen 
entsprechenden Titel wie Dr. oder Ing. habe klappt das nicht.
Warum werden normal sterbliche, die nicht so viel Ahnung da von haben 
immer so niedergemacht. Wenn dir diese niedere Unterhaltung zu wieder 
ist, mach was besseres. Beispiel: Im September wird ein angesehener 
Posten in Berlin frei. Bewirb dich einfach.

c-hater schrieb:
> Dabei ist es so einfach,
> wenn man sich die Eigenschaften des Bresenham vergegenwärtigt.

Dazu reicht mein Kenntnis nicht. Geb ich offen zu. Nicht jeder kann ein 
Genie sein.
LG Paul

[Gerd (Gast)]

>Warum werden normal sterbliche, die nicht so viel Ahnung da von haben
>immer so niedergemacht.

Das ist hier normal und hängt mit den sozialen Defiziten zusammen, die 
hier viele haben. Einfach ignorieren und auf der rein fachlichen Ebene 
bleiben. Dann wird's denen meist irgendwann langweilig und sie 
verschwinden.

[A. S. (Gast)]

Paul schrieb:
> .
> Wie kann ich das Programm ändern um einen Kreisring mit einer
> einstellbaren Breite zu zeichnen?

Du hast die Aufgabe bekommen, um dich mit dem Algorithmus zu 
beschäftigen.

Was davon hast Du schon verstanden? Ich denke, dass Du nur einen 
Achtelkreis zeichnest, ist klar.

Wenn Du weißt, wie Du statt des Punktes einer Rechnung, Linien zwischen 
2 Rechnungen zeichnet, dann bleibt nur noch eine Sonderbehandlung an den 
45° trennstellen.

Wenn Du den Algorithmus nicht verstehst, dann einfach eine Tabelle der 
Werte für einen Kreis anlegen und die Linien bis dahin zeichnen. Du 
speicherst für jeden y-Wert, bis zu welchem x Du die Linie ziehst.

[c-hater (Gast)]

A. S. schrieb:

> Was davon hast Du schon verstanden? Ich denke, dass Du nur einen
> Achtelkreis zeichnet, ist klar.

Oops. Natürlich. Deswegen muß ich diese meine Aussage aus
Beitrag "Re: Zeichnen eines Kreises nach Bresenhan auf Graphig Display"
noch korrigieren:

> An den
> Berührungspunkten der vier Quadranten werden Pixel mehrfach gesetzt.

Hier wollte ich natürlich eigentlich Oktanten statt Quadranten 
schreiben. Mist.

[c-hater (Gast)]

Paul schrieb:

> Ja, du hast recht, das bekomme ich nicht hin. Da ich keinen
> entsprechenden Titel wie Dr. oder Ing. habe klappt das nicht.

Öhemm nö, die Ausrede lasse ich hier nicht gelten. Der Algorithmus ist 
dermaßen einfach und der Code zeigt so offensichtlich die nötigen 
Stellen zum Eingreifen, da braucht man echt keinen akademischen Titel 
für.

Man muss nur grob verstanden haben, was der Algorithums in dieser 
Anwendung liefert und die Tatsache, dass da ein Kreis aus acht 
Einzelteilen entsteht. Der Rest ist super-trivial.

Zumindest eine suboptimale Umsetzung (die also nicht nur an den 
Berührungspunkten der Oktanten mehrfach Pixel setzt) sollte sogar 
problemlos gelingen, wenn man den Algorithmus selber und seine 
Eigenschaften nicht verstanden hat.

[Paul (Gast)]

MaWin schrieb:
> Wer gar nichts hat, zeichnet einen Kreis im Radius (z.B. 36) dann einen
> 35 dann einen 34, dann einen 33 dann einen 32 hinein. Kann, wenn man
> Pech hat, pixelgrosse Löcher ergeben.

Du hast Recht. Habe es so gemacht und sieht nicht gut aus. Die Löcher 
aus dem äusseren Kreis sind auch bis zum inneren Kreis zu sehen und das 
sieht nicht wirklich wie ein Kreisring aus. So wie es aussieht kann ich 
das Projekt vergessen. Die anderen genannten Möglichkeiten kann ich 
nicht machen, bin zu doof dazu. Versuche was anderes.
Paul

[Heiner (Gast)]

Hallo Paul

Lass Dich nicht entmutigen - siehe Bild ;-)

[A. S. (Gast)]

Paul schrieb:
> Die anderen genannten Möglichkeiten kann ich
> nicht machen, bin zu doof dazu. Versuche was anderes.

Deshalb die Frage, in wie weit Du den Algorithmus verstehst?

Ich nahm an, es ist Dir klar, dass hier 8 Kreisstücke gleichzeitig 
gezeichnet werden, also nur 1/8-Kreis berechnet wird.

Im Code ist X die Variable, in jeder Schleife im 1 incrementiert wird. 
D.h., X ändert sich jede Schleife, Y ändert sich ggf. nicht.

Dein höchster Radius ist 50. Lege ein globales Array Y2[50] an (vorerst 
mit 0 initialisiert).
Zudem brauchst Du jetzt eine Routine, die Linien Zeichnet, nicht Punkte. 
Mach Dir also eine Routine LCD_Draw_Line(x1,y1,x2,y2), die von x1/y1 bis 
x2/y2 zeichnet (eine ganz einfache, es werden keine schrägen benötigt, 
entweder x oder y ist jeweils konstant)

Mache aus jedem LCD_Set_Point(a,b) ein LCD_Drwa_Line(a,b,a,b). Also aus 
der ersten Zeile:

    LCD_Set_Point(x0, y0 + radius);
--> LCD_Draw_Line(x0, y0 + radius, x0, y0 + radius);

Aus der ersten Zeile in der Schleife:

    LCD_Set_Point(x0 + x, y0 + y);
--> LCD_Draw_Line(x0 + x, y0 + y, x0 + x, y0 + y);

Der Code sollte jetzt genauso laufen ;-) Prüfen! Haken drann, Bier 
aufmachen!

Dann ändere jeweils das zweite y (bzw. radius) auf Y2[x];

Der Code sollte jetzt einen Vollkreis zeichnen. Prüfen! Haken drann, mit 
dem Bier prosten!

Jetzt geht es nur noch darum, Y2 für den inneren Kreis auszurechnen.

Kopiere die ganze Funktion und nenne die Kopie "Fill_Y2(int8_t x0, 
int8_t y0, int8_t radius1);". Die rechnet Dir zugehörige Y2 aus.

Statt der 4 x LCD_Set_Point schreibst Du einmal Y2[x]=y;
In der Schleife genauso: Statt der 8 x LCD_Set_Point einmal Y2[x]=y;

Diese Funktion rufst Du vorab mit dem kleineren Radius auf.

Wenn das funktioniert, machst Du aus den 2 Funktionen eine, mit Prüfung 
dass der erste Radius wirklich kleiner ist, mit Y2[50] lokal, ggf. als 
VLA, mit .... besser geht immer, da hilft jetzt das Bier!