Entwickler-Ecke
Multimedia / Grafik - Kreis zeichnen...
Böner - Sa 14.05.05 00:31
Titel: Kreis zeichnen...
Ich habe mich mal gefragt wie das eigentlich programmiertechnisch aussieht wenn man einen Kreis zeichnen will. Nicht über eine Funktion, sondern einfach indem jeder eizelne Pixel gesetzt wird.
Ich hatte mir überlegt das man über sin/cos/tan Punkte vom Kreis berechnen könnte, aber selbst wenn man in 1-Grad-Schritten vorgeht, hat der Kreis ab bestimmten größen Lücken.
Weiß jemand wie das normalerweise gemacht wird ?
gruß böner
alzaimar - Sa 14.05.05 10:22
Ja, weiss ich. Googel mach nach 'Breshenham' oder 'Bresenham' Circle Algorithm.
Das Verfahren zeichnet (nur mit Integer-Mathematik) einen 8tel-Kreis. Der wird gespiegelt und fertig.
Der Line-Algorithmus von ihm ist, meine ich, *der Standard* im Bereich der Pixelrenderer. Allerdings habe ich schon Renderer gesehen, die mit anderen, vielleicht schnelleren, aber in jedem Fall ungenaueren Verfahren arbeiten.
Bres(h)enham ist auf jeden Fall die richtige Wahl.
delfiphan - Sa 14.05.05 11:22
Der Bresenham Kreis ist, wenn ich mich nicht täusche, nur eine Näherung an den Kreis (es gibt verschiedene Varianten mit verschiedenen Genauigkeiten).
Die Bresenhamlinie ist hingegen "exakt" (bzw. optimal genau).
alzaimar - Sa 14.05.05 16:31
Na ja, ich wüsste auch nicht, wie ich mit reiner Integermathematik sinus und cosinus exakt hinbekäme. Insofern ist der Kreis-Algorithmus natürlich ungenau, aber wen kümmerts: Auf Pixelebene ist ein Kreis IMHO genau dann ein Kreis, wenn er wie Einer aussieht. Aber das nur am Rande.
Die Resultate des Verfahrens sind -insbesondere bei kleinen Auflösungen- genau, wie man es erwartet. Inwieweit der Kreis bei einem Radius von 1000 noch kreisförmig ist, habe ich noch nicht ausprobiert.
Ich kann jedem angehenden SW-Entwickler nur dringend raten, diese Basisalgorithmen nachzuprogrammieren und -zumindest im Ansatz- zu verstehen.
NCortex - Mi 25.05.05 01:55
wenn man ganz viel spaß hat, könnte man ja einen korrektur faktor einbauen, zum beispiel je länger der Radius, desto mehr Punkte werden berechnet. ein kleiner Kreis kommt auch schon mit 48 punkten zurecht und man sieht an, dass es ein kreis ist, ein größerer braucht entsprechend mehr punkte..
Heiko - Mi 25.05.05 07:00
Mann könnte zum Zeichnen doch auch die Kreisgleichung nehmen: x²+y²=r². Wenn man dort Pixelweise durchgeht und das Ergebnis immer rundet, hat man auch einen geintegerten :wink: Kreis. Man braucht ja auch nicht den ganzen Kreis zeichnen, sondern nur einen Abschnitt und den dann spiegeln.
delfiphan - Mi 25.05.05 11:34
Der Bresenham Kreis bzw. die Bresenham Linie ist nichts anderes als eine Umformulierung deines "Float&Runden"-Algorithmus; er verwendet einfach nur Integers. Das ist ja der Witz der Sache. ;)
Heiko - Mi 25.05.05 17:07
Aso. Ich kenne den Bresenham Kreisnicht. Hatten wir um Unterricht noch nicht behandelt.
alzaimar - Mi 25.05.05 20:42
Hi Heiko: Trotzdem gibt es den Bresenham-Kreis, auch wenn ihr ihn noch nicht im Unterricht hattet:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
| procedure BresenhamCircle(CenterX, CenterY, Radius: Integer; Canvas: TCanvas; Color: TColor);
procedure PlotCircle(x, y, x1, y1: Integer);
begin
Canvas.Pixels[x + x1, y + y1] := Color;
Canvas.Pixels[x - x1, y + y1] := Color;
Canvas.Pixels[x + x1, y - y1] := Color;
Canvas.Pixels[x - x1, y - y1] := Color;
Canvas.Pixels[x + y1, y + x1] := Color;
Canvas.Pixels[x - y1, y + x1] := Color;
Canvas.Pixels[x + y1, y - x1] := Color;
Canvas.Pixels[x - y1, y - x1] := Color;
end;
var
x, y, r: Integer;
x1, y1, p: Integer;
begin
x := CenterX;
y := CenterY;
r := Radius;
x1 := 0;
y1 := r;
p := 3 - 2 * r;
while ( x1 < y1 ) do
begin
plotcircle ( x, y, x1, y1) ;
if ( p < 0 ) then
p := p + 4 * x1 + 6
else
begin
p := p + 4 * ( x1 - y1 ) + 10 ;
y1 := y1 - 1 ;
end;
x1 := x1 + 1 ;
end;
if ( x1 = y1 ) then
plotcircle ( x, y, x1, y1) ;
end; |
Das coole hierdran ist doch gerade, das kein sin, kein cos, keine wurzl und kein hochzwei drin vorkommt.
Zitroneneis - Sa 28.05.05 11:55
ich hab jetzt auchmal mit dem bensenham-kreis gearbeitet. fuer einen ausgefuellten kreis lass ich einfach nach einander immer groesser werdende kreise zeichnen und mach nicht nur den randpunkt sondern eine linie vom mittelpunkt bis zum rand. funktioniert ganz gut is leider nur ein bissel langsam. gibts da vll ne schnellere variante?
danke
BenBE - Sa 28.05.05 17:00
Bzw., da der Kreis von Oben nach unten gezeichnet wird, einfach vom Mittelpunkt aus Horizontalen ziehen.
alzaimar - So 29.05.05 09:34
@Zitroneneis: Kreis zeichnen und anschliessend füllen per 'Floodfill'. Floodfill
XMagic - So 29.05.05 19:01
Ist relativ leicht zu realisieren mit 4 Images mit jeweils einem Viertelkreissektor:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
| for y:=1 to Image1.Height DO
for x:=1 to Image1.Width DO
begin
if sqrt(sqr(x)+sqr(y)) <= r then
Image1.Canvas.Pixels[x,y]:=clBlack;
end;
for y:=1 to Image1.Height DO
for x:=1 to Image1.Width DO
begin
if sqrt(sqr(x)+sqr(y)) <= r then
Image2.Canvas.Pixels[x,Image2.Height-y]:=clBlack;
end;
for y:=1 to Image1.Height DO
for x:=1 to Image1.Width DO
begin
if sqrt(sqr(x)+sqr(y)) <= r then
Image3.Canvas.Pixels[Image3.Width-x,y]:=clBlack;
end;
for y:=1 to Image1.Height DO
for x:=1 to Image1.Width DO
begin
if sqrt(sqr(x)+sqr(y)) <= r then
Image4.Canvas.Pixels[Image4.Width-x,Image4.Height-y]:=clBlack;
end; |
r ist der Radius des Kreises ;).
Wird halt einfach a²+b² = c² genutzt um den Abstand des Punktes zu berechnen.
Übrigens müssen alle 4 Sektoren gleich groß sein... aber das ist ja eh klar bei einem Kreis.
NCortex - Mo 30.05.05 06:45
ähm.... warum benutzt du in dem code 4 mal ein und die selbe for-schleife?
Heiko - Mo 30.05.05 07:26
Dürfte man dazu kürzen können:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| for y:=1 to Image1.Height do
begin
for x:=1 to Image1.Width do
begin
if sqrt(sqr(x)+sqr(y)) <= r then
begin
Image1.Canvas.Pixels[x,y]:=clBlack;
Image2.Canvas.Pixels[x,Image2.Height-y]:=clBlack;
Image3.Canvas.Pixels[Image3.Width-x,y]:=clBlack;
Image4.Canvas.Pixels[Image4.Width-x,Image4.Height-y]:=clBlack;
end
end
end; |
delfiphan - Mo 30.05.05 09:24
Wenn schon mit Floatingpoint-Arithmetik, dann bitte so:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| procedure FilledCircle(Canvas: TCanvas; x0, y0, r: Integer);
var
x, y: Integer;
begin
with Canvas do
for y := -(r-1) to r-1 do
begin
x := round(sqrt(sqr(r)-sqr(y)));
MoveTo(-x+x0, y+y0);
Lineto(x+x0, y+y0);
end;
end; |
Heiko - Mo 30.05.05 09:28
Ich habe ja nur XMagic Code auf NCortexs Wunsch gekürzt :wink: .
alzaimar - Mo 30.05.05 10:32
Das wird so nichts, jedenfalls nicht, wenn man pixelgenaue Kreise will. Wenn ich auf Pixelebene mit real-Mathematik arbeite, dann kommt es infolge Rundungsfehlern zu assymmetrischen Kreisen, bzw. dem Effekt, das z.B. ein Kreis bei Koordinate (4,5) mit dem Radius von 3 nicht genauso aussieht wie ein Kreis bei Koordinate (-10,1). Zudem ist die Implementierung mit sin/cos oder gar mit 'sqrt' sehr ineffizient.
Aus diesem Grund hat sich 'uns Bresenham' ja mal hingesetzt und richtig nachgedacht.
XMagic - Mo 30.05.05 15:05
 NCortex hat folgendes geschrieben: |
| ähm.... warum benutzt du in dem code 4 mal ein und die selbe for-schleife? |
Weil ich alle 4 Kreissektoren zeiche.
Das von Heiko ist natürlich besser, hatte aber keine Lust darüber nachzudenken :p.
@alzaimar
Wer brauch einen Pixelgenauen Kreis? Es geht nunmal nicht, da sich der Kreis aus Pixeln zusammensetzt, woraus er allerdings nicht besteht.
Deswegen kann man auf einem Computer theoretisch GARKEINEN Kreis zeichnen ;)
delfiphan - Mo 30.05.05 15:07
| alzaimar hat folgendes geschrieben: |
| ... dem Effekt, das z.B. ein Kreis bei Koordinate (4,5) mit dem Radius von 3 nicht genauso aussieht wie ein Kreis bei Koordinate (-10,1). Zudem ist die Implementierung mit sin/cos oder gar mit 'sqrt' sehr ineffizient. |
Kannst du mir erklären, wieso ein Kreis bei (-10,1) mit dem oben genannten Algorithmus anders aussehen sollte wie bei (4,5)?
Zweitens: Die Bresenham-Linie sieht exakt gleich aus wie eine "Float + gerundete" Linie. Das ist ja der Witz der Sache. Er schreibt es einfach um in Integer-Arithmetik und hat so einen schnelleren Algorithmus, jedoch mit dem
selben Resultat. Beim Kreis ist es etwas anders, dort benützt er eine Näherung (für die Ableitung iirc), weil er sonst nicht um die Floatingpoint-Arithmetik drumherum kommt.
Das hat mit richtig nachdenken nichts zu tun: Er nimmt das exakte (Float+Runden) und macht daraus eine Näherung mit Integerarithmetik.
alzaimar - Mo 30.05.05 15:58
@XMagic: Jede Grafikkarte, jeder Drucker, jeder Renderer, jedes Game, jedes Jeder braucht einen pixelgenauen "Kreis". Bzw. etwas, das wie ein Kreis aussieht, schnell zu zeichnen, garantiert symmetrisch und immer gleich aussieht. Ach ja, und ohne Floatingpoint-Arithmetik. So ein Prozessor ist nämlich gleich viel teurer als eine kleine Integer-Maschine.
Des Weiteren wird das mit 4 Viertelkreisen auch nichts, weil eben nicht sicher ist, das das wirklich symmetrisch wird. Wenn, sollte man 8el-Kreise nehmen. Das könnte klappen.
Allerdings nur mit ungeraden Radien. Zeichne doch mal einen Kreis mit dem Radius 2. Das klappt nicht so einfach.
@delfiphan: Dein Code klappt nicht (Der der anderen Teilnehmer auch nicht). Ein 'Kreis' mit dem Radius 1 degeneriert zu einer Linie (3 pixel breit). Bei R=2 wird daraus ein 5x3 Rechteck, R=3 stimmt, R=4 ist wieder assymmetrisch etc. Da der Bresenham Algorithmus hier absolut perfekte Kreise liefert, ist das eben nicht ein und das Selbe...
Deine Annahme, das die Bresenham-Linie exakt so wie eine mit Floatingpoint berechnete Linie aussieht, ist falsch. Bei einer Linie 0, 45 oder 90° Linie hast Du fast recht (und selbst bei 45° Linien würde wg. Floatingpoint eventuell eine Stufe drin sein: Alles schon erlebt), aber sonst erlebst Du leider wg. der Rundungsfehler Stufen, wo Du gar keine erwartest. Bei Bresenham sind die Stufen garantiert gleichmäßig und auf der Linie spiegelsymmetrisch verteilt. Mal dochmal ein paar Linien mit Bresenham und ein paar mit deinem Floatingpoint...
Wenn schon nicht mit Integer, dann bitte mit BCD. Das rechnet wenigstens genau(er)....
Mach doch mal:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| Var
f : Real;
begin
f:=-1;
While f<1 do begin
memo1.lines.Add(FloatToStr(f));
f := f+0.1;
end;
end; |
Dann wirst Du wissen, wieso man mit Realzahlen immer wieder Überraschungen erlebt. Vielleicht beantwortet das auch die Frage, wieso ein Kreis bei z.B. (-10,1) anders aussehen könnte als einer bei (5,4)...
delfiphan - Mo 30.05.05 17:37
alzaimar: Es war nicht bloss eine Annahme, dass die Linie gleich aussieht; ich kenne doch die Herleitung der Bresenhamlinie. Was ich meinte ist exakte Rechnung+Rundung vs. Bresenhamlinie (nicht Float vs. Bresenham). Da hab ich mich wohl falsch ausgedrückt. Du hast Recht, wenn man mit Floats rechnet, werden allfällige Rundungsfehler (in der 16. Nachkommastelle) akkumuliert und kann in seltenen Fällen zu einem anderen Resultat führen. Natürlich muss man als Laufvariable die x Richtung nehmen, wenn die Steigung kleiner als 45° ist; und y als Laufvariable, wenn die Steigung steiler als 45° ist. Das ist ja bei Bresenham auch notwendig!
Beim Kreis, ja, da hattest du recht, die Kreise sind in meinem Code Ellipsen. Da war noch ein Denkfehler von mir drin. Die x-Richtung wird nämlich gerundet nach der 1/2-Regel (ab 0.5 aufgerundet, sonst abgerundet). In y-Richtung ist es quasi immer-abgerundet gerechnet.
Korrektur also:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| procedure FilledCircle(Canvas: TCanvas; x0, y0, r: Integer);
var
x, y: Integer;
begin
with Canvas do
for y := -r to r-1 do
begin
x := round(sqrt(sqr(r)-sqr(y+0.5)));
MoveTo(-x+x0, y+y0);
Lineto(x+x0, y+y0);
end;
end; |
Unten noch der Direktvergleich FilledCircle-Kreise (links) vs. Canvaskreise (rechts). Einige Canvaskreise sehen recht übel aus. Man merkt auch die Näherung beim Canvaskreis, dort ist (iirc) der Radius in Richtung +/- 45° ein kleines bisschen zu klein.
Übrigens: Ich sehe immer noch nicht ein, wieso meine Kreise an verschiedenen Positionen anders aussehen sollten.
alzaimar - Mo 30.05.05 18:10
Dein Algo zeichnet keine Kreise, sondern Ellipsen. Und rotationssymetrisch sind sie auch nicht (bezüglich 90°).
Aber immer noch hübscher als Canvas.Ellipse. Was das zeichnet, weiss ich nicht, jedenfalls keine 'Kreise'. Das sieht ja grässlich aus. Vermutlich liegt das daran, das Ellipsen nicht so einfach analytisch zu beschreiben sind. Oder, weil es von MS-Fricklern aus Redmond zwischen einigen Whiskysessions gecoded wurde.
Bresenham dagegen... eine Augenweide.
Und was meine Behauptung anbelangt, Dein Verfahren sei abhängig vom Kreismittelpunkt: Vergiss es. So wie du das implementiert hast, natürlich nicht. Aber du malst ja auch keine Kreise, he he. Und fordere mich bloss nicht heraus: Ich würde das auch nicht hinbekommen :P.
An dieser Stelle sei mal auf 'Metafont' von Donald Knuth hingewiesen. Kennst Du das? Ein Programm zum Designen und Rendern von Fonts anhand von Outlines. Killer! Der muss ja auch irgendwie Kreise zeichnen. Tut er aber nicht. Er zeichnet Bezierkurven, die fast so schön wie Kreise sind. Die Rotationssymmetrie bekommt er nur hin, wenn er sog. Hints in seine Fontbeschreibungen einbaut, ähnlich wie Truetype (die haben das von Knuth abgekupfert). Seine Bezierkurven sind analytisch besser in den Griff zu bekommen, aber auch hier bricht man sich einen ab, einen 100% rotationssymetrischen 'Kreis' hinzubekommen.
Du siehst: Auf Pixelebene ist das Alles nicht trivial.
NCortex - Mo 30.05.05 18:19
ich stimme delphiphan absolut zu, der algorithmus ist mal echt genial und funktioniert einwandfrei. Außerdem, wozu bruach man einen "absolut" korrekten kreis, wenns danach geht, kann man den gar nicht entwickeln, weil allein schon die begrenzung auf einen raum, der durch ECKIGE pixel dargestellt wird, bringt schon fehler mit sich. keiner soll mir erzählen, dass er einen unterschied sieht zwischen dem bersenheim kreis und einem gerundeten kreis.
delfiphan - Mo 30.05.05 19:10
| alzaimar hat folgendes geschrieben: |
| Dein Algo zeichnet keine Kreise, sondern Ellipsen. Und rotationssymetrisch sind sie auch nicht (bezüglich 90°). ... |
:?: Die Gif-Datei hast du ja gesehen. Die Kreise kannst du 90° drehen, dann sehen sie genau gleich aus.
alzaimar - Mo 30.05.05 19:21
Wenn ich deinen Algo kopiere und in ein Stringgrid zeichnen lasse, dann sieht das Anders aus, als das MoveTo-LineTo. Ich nehme Also alles zurück...
delfiphan - Mo 30.05.05 19:34
LineTo zeichnet die Linie bis und ohne das letzte Pixel :)
alzaimar - Di 31.05.05 09:16
:oops:
Thema erledigt.
Böner - Di 31.05.05 13:11
jo, meine frage is ja eigentlich beantwortet...
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!