Autor |
Beitrag |
Böner
      
Beiträge: 39
Win Xp, Win 98, Linux 8.2
D3 Prof + D6 Pers
|
Verfasst: Sa 14.05.05 00:31
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
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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
      
Beiträge: 126
WIN 2000
D7 Enterprise
|
Verfasst: 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..
_________________ "...by all means, do not use a hammer." (aus einer IBM Technikerdokumentation ca. 1920)
--->außer es kam von Microsoft<---
|
|
Heiko
      
Beiträge: 3169
Erhaltene Danke: 11
|
Verfasst: 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  Kreis. Man braucht ja auch nicht den ganzen Kreis zeichnen, sondern nur einen Abschnitt und den dann spiegeln.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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
      
Beiträge: 3169
Erhaltene Danke: 11
|
Verfasst: Mi 25.05.05 17:07
Aso. Ich kenne den Bresenham Kreisnicht. Hatten wir um Unterricht noch nicht behandelt.
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mi 25.05.05 20:42
Hi Heiko: Trotzdem gibt es den Bresenham-Kreis, auch wenn ihr ihn noch nicht im Unterricht hattet:
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
Hält's aus hier
Beiträge: 1
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 28.05.05 17:00
Bzw., da der Kreis von Oben nach unten gezeichnet wird, einfach vom Mittelpunkt aus Horizontalen ziehen.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: So 29.05.05 09:34
@Zitroneneis: Kreis zeichnen und anschliessend füllen per 'Floodfill'. Floodfill
|
|
XMagic
Hält's aus hier
Beiträge: 12
Delphi 7
|
Verfasst: 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
      
Beiträge: 126
WIN 2000
D7 Enterprise
|
Verfasst: Mo 30.05.05 06:45
ähm.... warum benutzt du in dem code 4 mal ein und die selbe for-schleife?
_________________ "...by all means, do not use a hammer." (aus einer IBM Technikerdokumentation ca. 1920)
--->außer es kam von Microsoft<---
|
|
Heiko
      
Beiträge: 3169
Erhaltene Danke: 11
|
Verfasst: 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
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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
      
Beiträge: 3169
Erhaltene Danke: 11
|
Verfasst: Mo 30.05.05 09:28
Ich habe ja nur XMagic Code auf NCortexs Wunsch gekürzt  .
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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
Hält's aus hier
Beiträge: 12
Delphi 7
|
Verfasst: 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
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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.
|
|