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
>Demnach muss ich die Wurzel ziehen. Kann dies ein µC überhaupt?
Ja, wieso nicht ;)
Such mal nach Bresenham da gehts ohne Wurzel.
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
Mit dem iterativen Heron-Verfahren kriegst du die Wurzel so genau angenähert wie du willst: http://de.wikipedia.org/wiki/Heron-Verfahren
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
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
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
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.
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
Einfach an die berechnete Position statt eines einzelnen Pixels 4 Pixel (2x2) setzen. Sollte dann einen sauberen Kreis mit 2 Pixeln Stärke ergeben.
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
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
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 | }
|
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
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
Thread beobachten
Seitenaufteilung abschaltenBitte 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.