mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Darstellung eines Kreises auf einem LCD Graphikdisplay


Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Ich habe folgende Frage.
ich muß für ein Projekt ein LCD Graphik display ansteuern (128x160
pixel)

Sämtliche Treiber muß ich selber schreiben. d.h ich kann nur die
einzelnen Pixel ansprechen. das ganze wird mit einem µController
angesteuert.
gibt es einen codesparenden algorythmus mit dem man koordinaten für
einen Kreis in einer beliebigen Grösse berechnen kann? damit meine ich
wirklich pixel für pixel berechnen?

lg
P

Autor: Martin S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ui, das hab ich mal "vor dem Krieg" im Informatik-Studium gemacht. Das
Problem ist daß Kreise trigonometrische Funktionen benötigen, welche auf
Real-Zahlen basieren, und ein Pixel-Display halt Integere Werte
benötigt.

Da gabs so mindestens 2-3 verschiedene algorithmische Ansätze, damit
der Kreis nicht zu zerrissen aussieht.

In welcher Sprache / Prozessortyp soll denn das ganze sein ?

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
soll in C/C++ entwickelt werden,
16Bit Prozessor

Autor: Uwe (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hat Hagen sowas nicht in seiner glib für das Nokia-Display?
http://www.mikrocontroller.net/forum/read-4-71176.html

Autor: Ingo Henze (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gab es da nicht was, wo nur 1/4 Kreissegment (oder sogar nur 1/8)
berechnet wurde, und der Rest der Pixel durch Spiegelung an den Achsen
durch den Mittelpunkt (also nur Addition und Subtraktion) erzeugt
wurde?

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, in der GLCD ist eine Routine um Ellipsen zu zeichnen, also auch
Kreise. Diese benötigt keine Trigometrischen Funktionen und auch keine
Fließkommaarithmetik. Sie berechnet ein 1/4 Segment und spiegelt
dieses.
In der neuen GLCD ist der Code in Assembler, hoch optimiert. Das wird
dir aber höchstwahrscheinlich nicht direkt helfen. Mein alte Lib
enthält aber auch C Code (WiNAVR GCC).
Du kannst nun die neue GLCD Library downloaden und mit nachfolgendem C
Source vergleichen. Auf alle Fälle lässt sich die Effizienz in
Assembler verfünffachen.

Gruß Hagen



/* Hilfsfunktion für Ellipsen */
void glcdDoPixelLine(int16_t x1, int16_t x2, const int16_t y, const
uint8_t fill) {

    if ((y >= glcd_Clip.Y1 ) & (y <= glcd_Clip.Y2)) {
      if (x1 < glcd_Clip.X1) {x1 = glcd_Clip.X1;} else {
        if (x1 > glcd_Clip.X2) {return;} else {
          if (glcdFgColor != NONE) {
            glcdSetPixel(x1, y, glcdFgColor);
          }
          x1++;
        }
      }
      if (x2 < glcd_Clip.X1) {return;} else {
        if (x2 > glcd_Clip.X2) {x2 = glcd_Clip.X2;} else {
          if (glcdFgColor != NONE) {
            glcdSetPixel(x2, y, glcdFgColor);
          }
          x2--;
        }
      }
      if ((fill) & (glcdBkColor != NONE) & (x1 <= x2)) {
        glcdDoFillRect(x1, y, x2, y, glcdBkColor);
      }
    }
}

void glcdCircle(glcdCoord_t x, glcdCoord_t y, glcdCoord_t r) {

    glcdEllipse(x, y, r, r);
}

void glcdEllipse(glcdCoord_t x, glcdCoord_t y, glcdCoord_t a,
glcdCoord_t b) {

   if ((a == 0) | (b == 0)) {return;}
   if ((a > 180) | (b > 180)) {
     if (glcdBkColor != NONE) {
       glcdFillRect(0, 0, SCREEN_WIDTH -1, SCREEN_HEIGHT -1,
glcdBkColor);
     }
     return;
   }

   glcdCoord2_t aa = a * a;
   glcdCoord2_t bb = b * b;
   int32_t er, cr, ir;
   int16_t ys,ye,xs,xe;

   cr = bb >> 1;
   cr = cr * (a + a -1);
   ir = aa >> 1;
   ir = -ir;
   er = 0;

   xs = x;
   xs = xs - a;
   xe = x;
   xe = xe + a;
   ys = y;
   ye = y;
   while (cr >= ir) {
     glcdDoPixelLine(xs, xe, ys, 1);
     if (ys != ye) {
       glcdDoPixelLine(xs, xe, ye, 1);
     }
     ys--;
     ye++;
     ir += aa;
     er += ir;
     if (2 * er > cr) {
       er -= cr;
       cr -= bb;
       xs++;
       xe--;
     }
   }

   cr = aa >> 1;
   cr = cr * (b + b -1);
   ir = bb >> 1;
   ir = -ir;
   er = 0;

   xs = x;
   xe = x;
   ys = y;
   ys = ys - b;
   ye = y;
   ye = ye + b;
   uint8_t fill = 1;
   while (ir <= cr) {
     glcdDoPixelLine(xs, xe, ys, fill);
     if (ys != ye) {
       glcdDoPixelLine(xs, xe, ye, fill);
     }
     fill = 0;
     ir += bb;
     er += ir;
     if (2 * er > cr) {
       er -= cr;
       cr -= aa;
       ys++;
       ye--;
       fill = 1;
     }
     xs--;
     xe++;
   }
}

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
dankesehr für die schnelle hilfe, ich denke das hilft mir schoon weiter
thx

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielen dank an euch funktioniert tadellos

lg
P

Autor: ---- (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Google mal nach 'Bresenham'. Der hat einen schönen Algorithmus
entwickelt - platzsparend und ohne trigon. Funktionen.
Deutlich kürzer und einfacher als obiger Code.

----, (QuadDash).

Autor: Khani (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Öh QuadDash,

schon mal den Bresenham implementiert ?
Wenn ja, dann weißt Du ja schon, dass der ziemlich spaghettiartig
ausschaut und schnell ist. Wenn nicht, dann vergleiche einfach mal den
Pseudocode einer Algorithmusbeschreibung mit dem obigen Code - ich
wette die Unterschiede werden verschwinden ;-)

MfG, Khani

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Korrekt, denn obiger Algo. IST Bresenham ;) Allerdings in einigen Teilem
weit mehr optimiert als der originale Bresenham.
Ich würde mal gerne von ---- eine bessere und effizientere
Implementation der Ellipse sehen wollen.

Gruß Hagen

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Achso, zur Erklärung des Sources:
Er zeichnet Ellipsen ;) aber enthält ein Clipping der Ausgabe in einem
rechteckigen Bereich. Zudem füllt er die Ellipsen je nach
Hintergrundfarbe und zeichnet einen 1 Pixel Rahmen drumherum. Wird die
Hintergrundfarbe auf TRANSTAPENT gesetzt so zeichnet er einfach eine
transparente Ellipse. Sogesehen hat obiger Source 3 Aufgaben
- Ellipse zeichnen
- je nach Hintergrund/Vordergrund Farbe ausfüllen und Rahmen zeichnen
- die Ausgabe in einem Clippingrect beschneiden

Wichtig! die Zahlenbereiche unterstützen Koordinaten von 0 bis 254
Pixeln. Das ist ausreichend für ein 254x254 Pixel Display.

Gruß Hagen

Autor: ---- (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Achso, das IST Bresenham - hab das garnicht erkannt :)
Habe den Bresenham-Algorithmus mal vor einiger Zeit als C-Code ausm
Netz gezogen und benutze ihn in einer seitdem nie mehr be(tr)achteten
Funktion (so wie es sein muß).
Ich habe nur in Erinnerung, daß der Source deutlich kürzer und
einfacher war/aussah. Um ((auf die Schnelle)) zu erkennen, daß Hagens
Code ein optimierter Bresenham ist, fehlt mir die Kompetenz.
Zudem bezog sich meine Aussage auf den 'Kreis', nachdem ja
ursprünglich auch gefragt war.

----, (QuadDash).

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stimmt, der Kreis Algorithmus ist wesentlich einfacher als eine Ellipse.
Die Pixel-Performance obiger Source ist aber mit einem gut optimierten
Kreis-Bresenham Algo. vergleichbar.

Ein Kreis-Bresenham ist eventuell deutlich kürzer im Source, von der
nötigen Komplexität der Berechnungen aber nicht wesentlich effizienter
als obige Ellipsenroutine. Einzigst die Iterationsanzahl muß bei
Ellipsen höher sein, auf Grund ihrer Komplexität.

Ein Kreis kann mit 1/8 des Umfanges erzeugt werden. Die restlichen
Punkte werden durch Spiegelungen erzeugt. Bei Ellipsen benötigt man 1/4
des Umfanges, so wie im obigen Source. D.h. die Iterationstiefe ist
doppelt so hoch. Allerdings ist die Komplexität der
Itererationsschritte bei beiden Algos. fast identisch, mal abgesehen
von den zwei zusätzliche Additionen.

Würde man aber nun den Kreis-Bresenham so abändern das er auch Kreise
füllen kann, dann stellt man fest das obige Ellipsen Funktion im
Vergleich an Performance zugewinnt. Denn die Füllroutine bei Kreisen
benötigte 4 mal mehr Aufrufe als bei Ellipsen. Aber exakt da steckt
Performance dahinter. In meinem Source greife ich bewusst auf
glcdDoFillRect() zu, obwohl ja nur eine Line mit 1 Pixel Breite
gezeichnet wird. Dies macht man weil auf den meisten GCLD Conrollern
das Füllen von rechteckigen Speicherbereichen speziell unterstützt
wird. Diese speziellen Funktionen der Controller benötigen aber einen
zusätzlichen Overhead zu Einstellung der Koordinaten. Nun, bei Kreisen
a 1/8 Segmenten würden somit 4 mal mehr solche extra Controller Befehle
notwendig.

Aus diesem Grunde, und eben auch wegen der Code-Ersparnis, sollte man
nur die Ellipsen Routine implementieren, und die Kreisroutine darauf
aufsetzen lassen.

Gruß Hagen

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Appropo Spaghetti-Code, Zb. die Source Zeilen wie

   cr = bb >> 1;
   cr = cr * (a + a -1);

   ir = aa >> 1;
   ir = -ir;

   xs = x;
   xs = xs - a;

   xe = x;
   xe = xe + a;

könnte man bei einem cleveren Compiler auch als 1 Zeile schreiben.
Allerdings um auf Nummer sicher zu gehen, weil unterschiedliche
Datentypen betroffen sind, und eben auf Grund der Übersichtlichkeit,
habe ich dies so gecodet.

Gruß Hagen

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.