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
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 ?
soll in C/C++ entwickelt werden, 16Bit Prozessor
Hat Hagen sowas nicht in seiner glib für das Nokia-Display? http://www.mikrocontroller.net/forum/read-4-71176.html
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?
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++; } }
dankesehr für die schnelle hilfe, ich denke das hilft mir schoon weiter thx
Vielen dank an euch funktioniert tadellos lg P
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).
Ö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
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
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
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).
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
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
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.