mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Punkte eines Kreises berechnen


Autor: Johannes (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Moin

Ich möchte die Punkte von einem Kreis berechnen. Hierzu verwende ich 
folgende Formel:

r^2 = x^2 + y^2

nach x umgestellt:

x = (r^2 - y^2)^1/2

Demnach muss ich die Wurzel ziehen. Kann dies ein µC überhaupt?

x =sqrt(r^2 - y^2);

Ist das ein Problem für den µC?

Ich benutze einen SAM7 von Atmel

Grüsse

Johannes

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Demnach muss ich die Wurzel ziehen. Kann dies ein µC überhaupt?

Ja, wieso nicht ;)
Such mal nach Bresenham da gehts ohne Wurzel.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Jean Meyer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit dem iterativen Heron-Verfahren kriegst du die Wurzel so genau 
angenähert wie du willst: http://de.wikipedia.org/wiki/Heron-Verfahren

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenns darum geht, den Kreis bzw Teile/Punkte davon zu zeichnen, wieso 
gehst du nicht über Sinus/Kosinus?


x =  R_x * SIN ( phi )
y =  R_y * COS ( phi )

R_x, R_y: Radius in x, y Richtung (Gleich für Kreis)
phi     : WInkel

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Sebastian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gibt es dazu auch einen guten Quellcode in C?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
CodeLib oder schick mir ne PN und ich mail dir meine S65 Library.

Gruß Hagen

Autor: Aleksandar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo!

Kreis Zeichnen geht VIEEEEEEL schneller. Sieh Dir folgendes an, ist 
relativ gut beschrieben:

http://de.wikipedia.org/wiki/Bresenham-Algorithmus

Das grundlegende Prinzip besteht darin, dass der naechste Punkt bei 
einer Aufteilung des Kreises in 8 Oktanten nur um einen Pixel oder 
keinen Punkt nach unten (oder halt oben) gehen kann. Es reicht aus, 
auszurechnen, ob beim naechten Schritt die Abweichung groesser ist, wenn 
man den Punkt um einen Pixel verschiebt oder nicht.

x^2 + y^2 = r^2

Bei einem Schritt von x auf x+1 andert sich die Summe links um 2*x + 1. 
Du braucht jetzt nur festzustellen ob (x+1)^2 + (y+1)^2 naeher als 
(unveraendertes y) (x+1)^2 + y^2 an r^2 kommt.

Selbstlob muss auch sein: ;)
Damit habe ich auf ZX-Spectrum gefuellte Kreise mit Schraffur im 
Assembler etwa 20 mal schneller gezeichnet als Original-BASIC nur Kreise 
malte. Die haben woll Sinus/Cosinus benutzt :(

Viel Erfolg!
Aleks

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier gibts die Original-Veröffentlichung von Bresenham 1965:
http://researchweb.watson.ibm.com/journal/sj/041/i...

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

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johannes (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe es so implementiert wie im Beispiel bei Wikipedia.

http://de.wikipedia.org/wiki/Bresenham-Algorithmus

Es funktioniert auch gut. Jedoch ist die Strichstärke mit einem Pixel zu 
dünn, deshalb wollte ich 2 Kreise zeichen. Den 1. mit einem Radius von 
20 und den 2. mit einem Radius von 21. Jedoch entstehen dabei minimale 
lücken zwischen den beiden Kreisen. Kann ich dies verhindern?

Grüsse

Johannes

Autor: l00k (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Einfach an die berechnete Position statt eines einzelnen Pixels 4 Pixel 
(2x2) setzen. Sollte dann einen sauberen Kreis mit 2 Pixeln Stärke 
ergeben.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Johannes (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das habe ich jetzt nicht ganz verstanden. Soll ich einen Kreis mit 20.5 
Pixel Radius zeichen oder wie ist das gemeint.


 void rasterCircle(int x0, int y0, int radius)
 {
   int f = 1 - radius;
   int ddF_x = 0;
   int ddF_y = -2 * radius;
   int x = 0;
   int y = radius;

   setPixel(x0, y0 + radius);
   setPixel(x0, y0 - radius);
   setPixel(x0 + radius, y0);
   setPixel(x0 - radius, y0);

   while(x < y)
   {
     if(f >= 0)
     {
       y--;
       ddF_y += 2;
       f += ddF_y;
     }
     x++;
     ddF_x += 2;
     f += ddF_x + 1;

     setPixel(x0 + x, y0 + y);
     setPixel(x0 - x, y0 + y);
     setPixel(x0 + x, y0 - y);
     setPixel(x0 - x, y0 - y);
     setPixel(x0 + y, y0 + x);
     setPixel(x0 - y, y0 + x);
     setPixel(x0 + y, y0 - x);
     setPixel(x0 - y, y0 - x);
   }
 }


Grüsse

Johannes

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
void glcdSetPixel4(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdColor_t color) {

    glcdSetPixel(x1, y1, color);
    glcdSetPixel(x2, y1, color);
    glcdSetPixel(x1, y2, color);
    glcdSetPixel(x2, y2, color);
}

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

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

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) {

    if (x1 > x2) glcdSwapCoord(x1, x2);
    if (y1 > y2) glcdSwapCoord(y1, y2);
    glcdCoord_t t;
    t = x2 - x1;
    t >>= 1;
    if (a > t) a = t;
    t = y2 - y1;
    t >>= 1;
    if (b > t) b = t;
    x1 += a;
    x2 -= a;
    if (fgcolor != NONE) glcdLine2(x1, y1, x2, y2, fgcolor);
    uint16_t as = a * a, bs = b * b;
    int32_t dx = 0, dy = as, ee = bs;
    dy *= b;
    ee += as / 4;
    ee -= dy;
    dy += dy;
    while (dx < dy) {
      if (fgcolor != NONE) glcdSetPixel4(x1, y1, x2, y2, fgcolor);
      x1--;
      x2++;
      if (ee >= 0) {
        y1++;
        y2--;
        dy -= as;
        dy -= as;
        ee -= dy;
        if (bkcolor != NONE) glcdLine2(x1, y1, x2, y2, bkcolor);
      }
      dx += bs;
      dx += bs;
      ee += bs;
      ee += dx;
  }
  int32_t tt = as;
    tt -= bs;
  tt *= 3;
  tt >>= 1;
  tt -= dx;
  tt -= dy;
  tt >>= 1;
    ee += tt;
    while (y1 <= y2) {
      if (bkcolor != NONE) glcdLine2(x1, y1, x2, y2, bkcolor);
      if (fgcolor != NONE) glcdSetPixel4(x1, y1, x2, y2, fgcolor);
      y1++;
      y2--;
      if (ee < 0) {
        x1--;
        x2++;
        a++;
        dx += bs;
        dx += bs;
        ee += dx;
      }
      dy -= as;
      dy -= as;
      ee += as;
      ee -= dy;
    }
}

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

    if (x1 > x2) glcdSwapCoord(x1, x2);
    if (y1 > y2) glcdSwapCoord(y1, y2);
    glcdRoundRect(x1, y1, x2, y2, (x2 - x1) / 2, (y2 - y1) / 2, fgcolor, bkcolor);
}

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

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

Autor: Johannes (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es mag ja sein das diese Funktion super funktioniert, jedoch sieht sie 
sehr undurchsichtig aus, da kein Komentar in Deinem Quellcode vorhanden 
ist.

Genau das gleich Problem habe ich beim Wikipediaquellcode.

ich versuche immer diesen Teil zu verstehen:

while(x < y)
   {
     if(f >= 0)
     {
       y--;
       ddF_y += 2;
       f += ddF_y;
     }
     x++;
     ddF_x += 2;
     f += ddF_x + 1;
   }

x ist zu Beginn ja 0 und y = radius. Dies ist noch nachfolziehbar. 
Jedoch hört es hier schon auf

   int f = 1 - radius;
   int ddF_x = 0;
   int ddF_y = -2 * radius;

Dies verstehe ich z.B. schon nicht mehr.

Was mich noch mehr wundert ist die While-Scheife, diese läuft solange x 
< Y. Ich dachte man rechnet nur 45° aus und den rechts durch 
Punktsynmetrie

Grüsse

Johannes

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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/Computera...

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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Johannes (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Erst ma vielen Dank für Eure Hilfe.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.