Einen antialiasierten Kreis zeichnen, wie von Xaolin Wu beschrieben
Ich tendiere dazu, die "Fast Anti-Aliased Circle Generator" -Routine zu implementieren, die von Xiaolin Wu in seinem Aufsatz "Eine effiziente Antialiasing-Technik" von Siggraph '91 beschrieben wurde.
Dies ist der Code, den ich mit Python 3 und PySDL2 geschrieben habe:
%Vor% Dies ist eine naive Umsetzung dessen, was ich glaube, wird in seinem Artikel beschrieben, mit der Ausnahme, dass ich den Radius-Wert j anstatt i zugewiesen habe, weil entweder ich etwas falsch verstehe oder ein Fehler in seinem Papier ist. Tatsächlich initialisiert er i mit dem Radiuswert, j mit 0 und definiert dann die Schleifenbedingung i <= j , die nur dann wahr sein kann, wenn der Radius 0 ist. Diese Änderung hat mich dazu gebracht, einige kleinere Änderungen an dem, was beschrieben wurde, vorzunehmen, und ich habe auch if d > T in if d < T geändert, einfach weil es anders aussieht.
Diese Implementierung funktioniert am besten, außer am Anfang und am Ende jedes Oktanten, wo einige Störungen auftreten.
Der Kreis oben hat einen Radius von 1. Wie Sie am Anfang jedes Oktanten (wie im (0, 1) -Bereich) sehen können, sind die in der Schleife gezeichneten Pixel nicht auf das erste Pixel ausgerichtet gezeichnet, bevor die Schleife beginnt. Gegen Ende jedes Oktanten läuft auch etwas sehr schief (zB im Bereich (sqrt(2) / 2, sqrt(2) / 2) ). Ich habe es geschafft, dieses letzte Problem verschwinden zu lassen, indem ich die Bedingung if d < T auf if d <= T ändere, aber das gleiche Problem taucht dann am Anfang jedes Oktanten auf.
Frage 1 : Was mache ich falsch?
Frage 2 Würde es irgendwelche Probleme geben, wenn die Eingabeposition und der Radius Gleitkommawerte wären?
2 Antworten
Lassen Sie uns Ihre Implementierung dekonstruieren, um herauszufinden, welche Fehler Sie gemacht haben:
%Vor% Erste Frage, was bedeutet radius ? Es ist unmöglich, einen Kreis zu zeichnen, man kann nur einen Ring (einen Ring / Donut) zeichnen, denn wenn man keine Dicke hat, kann man sie nicht sehen. Daher ist der Radius nicht eindeutig, ist es der innere Radius, der mittlere Radius oder der äußere Radius? Wenn Sie nicht im Variablennamen angeben, wird es verwirrend. Vielleicht können wir es herausfinden.
OK, wir zeichnen vier Stellen gleichzeitig, da der Kreis symmetrisch ist. Warum nicht 8 Orte gleichzeitig?
%Vor% OK, i auf 0 und j auf Radius initialisieren, dies müssen die Koordinaten x und y sein. Was sind d und T ? Nicht unterstützt durch nicht beschreibbare Variablennamen. Es ist in Ordnung, die Algorithmen der Wissenschaftler zu kopieren, um sie mit längeren Variablennamen, die Sie kennen, verständlich zu machen!
Huh? Wir zeichnen einen Sonderfall? Warum machen wir das? Nicht sicher. Was bedeutet das aber? Es bedeutet, das Quadrat in (0, radius) mit voller Deckkraft auszufüllen. Nun wissen wir, was radius ist, es ist der äußere Radius des Rings und die Breite des Rings ist offensichtlich ein Pixel. Oder zumindest sagt uns dieser Spezialfall ... mal sehen, ob das im generischen Code hält.
Wir werden eine Schleife machen, bis wir den Punkt auf dem Kreis mit i > j erreichen, und dann stoppen. I.e. wir zeichnen einen Oktanten.
Also haben wir schon alle Pixel, die uns interessiert, in der i = 0 Position gezeichnet, gehen wir zur nächsten.
i.e. s ist eine Gleitkommazahl, die die y-Komponente des Oktanten am Punkt i auf der x-Achse ist. I.e. die Höhe über der X-Achse. Aus irgendeinem Grund haben wir max drin, vielleicht sorgen wir uns um sehr kleine Kreise ... aber das sagt uns nicht, ob der Punkt noch auf dem äußeren / inneren Radius liegt.
Unterbrochen, (math.ceil(s) - s) gibt uns eine Zahl zwischen 0 und 1.0. Diese Zahl wird zunehmen, wenn s abnimmt, so wie i zunimmt, und wenn sie einmal 1,0 erreicht hat, wird sie auf 0.0 zurückgesetzt, also in einem Sägezahnmuster.
sdl2.SDL_ALPHA_OPAQUE * (math.ceil(s) - s) Hinweise Wir verwenden die Sägezahn-Eingabe, um ein Maß an Undurchsichtigkeit zu erzeugen, d. h. um den Kreis mit Anti-Aliasing zu versehen. Die 0,5-fache Addition erscheint unnötig. % Co_de% legt nahe, dass wir nur an ganzzahligen Werten interessiert sind - wahrscheinlich verwendet die API nur ganzzahlige Werte. All dies zeigt, dass floor() eine ganzzahlige Ebene zwischen 0 und d ist, die anfänglich bei 0 beginnt und sich dann langsam aufbaut, wenn SDL_ALPHA_OPAQUE zunimmt, und wenn i von 1 zurück auf 0 springt. es fällt auch wieder tief.
Welchen Wert hat das am Anfang? ceil(s) - s ist fast s , da radius 1 ist (unter der Annahme eines nicht-trivial großen Kreises), also unter der Annahme, dass wir einen ganzzahligen Radius haben (was der erste Spezialfall eindeutig angenommen hat) i ist 0
Hier sehen wir, dass sich ceil(s) - s von hoch nach niedrig bewegt hat, und wir bewegen uns auf dem Bildschirm nach unten, so dass unsere d -Position in der Nähe bleibt, wo der Ring theoretisch sein sollte.
Aber auch jetzt erkennen wir, dass der Boden von der vorherigen Gleichung falsch ist. Stellen Sie sich vor, dass j in einer Iteration 100,9 beträgt. Dann ist es auf der nächsten Iteration gefallen, aber nur zu 100.1. Weil d und d gleich sind, da die Untergrenze ihre Differenz beseitigt hat, verringern wir in diesem Fall nicht T , und das ist entscheidend. Ich denke, wahrscheinlich erklärt die seltsamen Kurven an den Enden Ihres Oktanten.
Nur eine Optimierung, die nicht gezeichnet wird, wenn wir einen Alpha-Wert von 0 verwenden wollen
%Vor% Aber hoppla, in der ersten Iteration ist j niedrig, und deshalb zeichnet dies d ein fast vollständig transparentes Element. Aber der spezielle Fall, mit dem ich anfing, zeichnete ein völlig undurchsichtiges Element auf (1, radius) , also wird es hier eindeutig einen grafischen Fehler geben. Was du siehst.
Weitermachen:
%Vor%Eine weitere kleine Optimierung, bei der wir nicht mehr zeichnen, wenn wir an denselben Ort zeichnen würden
%Vor% Und das erklärt, warum wir nur 4 Punkte in (0, radius) zeichnen, weil Sie hier die andere Symmetrie machen. Es würde deinen Code vereinfachen, das nicht zu tun.
Eine weitere Optimierung (Sie sollten Ihren Code nicht vorzeitig optimieren!):
%Vor%Also schreiben wir in der ersten Iteration auf die obige Position, aber bei voller Opazität. Dies impliziert, dass es tatsächlich der innere Radius ist, den wir verwenden, nicht der äußere Radius, wie er vom Sonderfallfehler verwendet wird. I.e. eine Art von Einzel-Fehler.
Meine Implementierung (Ich hatte die Bibliothek nicht installiert, aber Sie können sehen, dass die Ausgabe die Randbedingungen überprüft, die sinnvoll sind):
%Vor%Schließlich, würde es gotchas geben, wenn Sie einen Gleitkomma-Ursprung übergeben möchten?
Ja, würde es. Der Algorithmus geht davon aus, dass der Ursprung an einer ganzzahligen / ganzzahligen Position liegt, und ignoriert ihn ansonsten vollständig.Wie wir gesehen haben, wenn Sie eine Ganzzahl _draw_point() übergeben, zeichnet der Algorithmus ein 100% undurchsichtiges Quadrat an der Stelle outer_radius . Wenn Sie jedoch eine Transformation in den Speicherort (0, outer_radius - 1) wünschen, möchten Sie wahrscheinlich, dass der Kreis an den Stellen (0, 0.5) und (0, outer_radius - 1) glatt bis zu einer Deckkraft von 50% abgeglichen wird, was Ihnen dieser Algorithmus nicht bietet weil es den Ursprung ignoriert. Wenn Sie diesen Algorithmus also genau verwenden möchten, müssen Sie Ihren Ursprung runden, bevor Sie ihn übergeben, so dass durch die Verwendung von Floats nichts gewonnen werden kann.
Ich habe folgendes an meinem Rechner:
%Vor%Das obige ist eine einfache Implementierung des Diagramms unten.
Es gibt einen Fehler in diesem Diagramm: der unterste Test sollte D(r,j) < T nicht D(r,j) > T sein, was erklären könnte, warum Sie ein bisschen verwirrt wurden.
Um Ihre zweite Frage zu beantworten, bezweifle ich, dass Sie eine float -Nummer als Position und Radius übergeben können, da letztlich die C-Funktion SDL_RenderDrawPoint expect int -Parameter ist.
Sie könnten einige Gleitkommazahlen an Ihre Python-Funktion übergeben, aber Sie müssen sie in int umsetzen, bevor Sie SDL_RenderDrawPoint verwenden. Es gibt leider noch nichts wie ein halber Pixel;)