Autor Beitrag
Böner
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 39

Win Xp, Win 98, Linux 8.2
D3 Prof + D6 Pers
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 126

WIN 2000
D7 Enterprise
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3169
Erhaltene Danke: 11



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3169
Erhaltene Danke: 11



BeitragVerfasst: Mi 25.05.05 17:07 
Aso. Ich kenne den Bresenham Kreisnicht. Hatten wir um Unterricht noch nicht behandelt.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mi 25.05.05 20:42 
Hi Heiko: Trotzdem gibt es den Bresenham-Kreis, auch wenn ihr ihn noch nicht im Unterricht hattet:
ausblenden volle Höhe 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);
{
Bresenham's Line Algorithm
Bresenham's Circle Algorithm
fra denne side:
http://www.funducode.com/freec/graphics/graphics2.htm
}

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



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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
BeitragVerfasst: So 29.05.05 19:01 
Ist relativ leicht zu realisieren mit 4 Images mit jeweils einem Viertelkreissektor:

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 126

WIN 2000
D7 Enterprise
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3169
Erhaltene Danke: 11



BeitragVerfasst: Mo 30.05.05 07:26 
Dürfte man dazu kürzen können:

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Mo 30.05.05 09:24 
Wenn schon mit Floatingpoint-Arithmetik, dann bitte so:
ausblenden 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-1to r-1 do
   begin
    x := round(sqrt(sqr(r)-sqr(y)));
    MoveTo(-x+x0, y+y0);
    Lineto(x+x0, y+y0);
   end;
end;
Heiko
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3169
Erhaltene Danke: 11



BeitragVerfasst: Mo 30.05.05 09:28 
Ich habe ja nur XMagic Code auf NCortexs Wunsch gekürzt :wink: .
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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
BeitragVerfasst: Mo 30.05.05 15:05 
user profile iconNCortex 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Mo 30.05.05 15:07 
user profile iconalzaimar 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.