Kreis zeichnen...

alzaimar · Verfasst: 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:

markieren

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 · Beiträge: 2684 Erhaltene Danke: 32

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:

markieren

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.

Einloggen, um Attachments anzusehen!

alzaimar · Verfasst: 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

.

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 · Beiträge: 126 WIN 2000 D7 Enterprise

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.

_________________
"...by all means, do not use a hammer." (aus einer IBM Technikerdokumentation ca. 1920)
--->außer es kam von Microsoft<---

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

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 · Verfasst: 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 · Beiträge: 2684 Erhaltene Danke: 32

LineTo zeichnet die Linie bis und ohne das letzte Pixel

alzaimar · Verfasst: Di 31.05.05 09:16

Thema erledigt.

Böner · Beiträge: 39 Win Xp, Win 98, Linux 8.2 D3 Prof + D6 Pers

jo, meine frage is ja eigentlich beantwortet...

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme