Algorithmus für Anti-Aliasing



  • Hallo, für meinen Rasterizer habe ich eine Funktion zum Füllen von Dreiecken geschrieben, die auch ganz gut funktioniert. Jetzt würde ich die Dreiecke gerne auch mit Anti-Aliasing rastern lassen, allerdings weiß ich nicht, wie ich das machen soll. Zuerst kam mir die Idee, alles in einen größeren Buffer zu rendern und den zu verkleinern, um Anti-Aliasing zu erreichen. Nur leider ist das viel zu langsam.
    Das Dreieck wird in Scanlines gerastert, von oben nach unten. An den Kanten müssten also links und rechts Farbabstufungen für jede Linie angepasst werden, damit Anti-Aliasing entsteht.
    Kann mir jemand einen Rat geben, wie man das am besten anstellt?


  • Mod

    das vorgehen ist schon korrekt, in groesserer aufloesung rendern und dann runterskalieren.



  • Danke für deine Antwort, rapso.
    Aber gibt es keine andere Möglichkeit? Das Rastern soll in Echtzeit ablaufen und dafür ist das Supersampling leider zu langsam.
    Wie wird das z.B. bei GDI+ oder Cairo gemacht? Da werden Objekte immer direkt mit AA gerastert, wenn ich mich nicht irre.


  • Mod

    wenn du nur einfache schwarz/weiss 2d dinge rasterisieren willst, z.b. linien, dann gibt es einige algorithmen http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm

    bedenke: sobald farbe im spiel ist, oder tiefe, klappt das jedoch nicht mehr (rightig).



  • Hm, farbige Objekte sollten schon funktionieren. Warum geht das mit dem Wu-Algorithmus nicht?


  • Mod

    weil der algorithmuss die abdeckung von der aktuellen linie berechnet und mit dem hintergrund blended, es bestehen keine informationen darueber was vom hintergrund verdeckt wird, das sieht nur bei zwei farben einigermassen aus (ist auch nicht 100% korrekt).
    zeichnest du z.b. eine blaue linie genau auf eine rote, wuerdest du bei einem korrekten algorithmus nur die blaue sehen, blendet man jedoch nur die blaue gegen den hintergrund der zum teil rot ist, wirst du ne purpur farbende linie bekommen.

    der einzig richtige weg ist deshalb mit genauerer abtastung zu zeichen, sprich: supersampling.



  • Hm.
    Es müsste irgendwie möglich sein, das ganze für grössere Dreiecke irgendwie zu optimieren. So dass der Algorithmus checkt, dass er jetzt "im inneren" eines Dreiecks ist. Also dass das aktuelle Sample, sowie alle benachbarten Samples innerhalb des Dreiecks liegen. Dann könnte man denke ich einfach alle Samples die dann beim runterskalieren zu einem Pixel zusammengefasst werden mit der gleichen Farbe füllen. Die Frage ist bloss, ob der Overhead den die dazu nötigen Tests verursachen nicht grösser als der Performance-Gewinn ist.

    Bei sehr kleinen Dreiecken zahlt es sich sicher nicht aus. Bei grösseren könnte es denke ich was bringen. Ist aber wahrscheinlich auch nicht ganz trivial zu implementieren.

    @rapso:
    Gibt es denn keine "Schummel" Algorithmen, die in sagen wir 90% der Fälle gut aussehen, in den restlichen 10% noch akzeptabel, und deutlich schneller laufen als "brute-force" Supersampling?

    Oder... lässt sich AA mit dem Quincunx Pattern in Software vernünftig implementieren? Das Rendern selbst müsste damit ja halbwegs schnell gehen - bloss wie lange das Runterskalieren dann braucht kann ich überhaupt nicht abschätzen.

    p.S.: wie wird das am DS normalerweise gemacht? Final Fantasy IV (DS) hat zumindest irgendwas AA-ähnliches. Auf jeden Fall sind die Kanten von Objekten dort nicht komplett "hart". Es sieht nicht perfekt aus (sieht aus als ob's nur ein Zwischenschritt wäre), aber IMO besser als ganz ohne AA. Bei der geringen Leistung der CPU (ARM9 @ 66 MHz) würde es mich fast wundern, wenn die dort mit Supersampling zeichnen.



  • Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Rund um die Programmierung in das Forum Spiele-/Grafikprogrammierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.


  • Mod

    hustbaer schrieb:

    Hm.
    Es müsste irgendwie möglich sein, das ganze für grössere Dreiecke irgendwie zu optimieren.

    bevor man optimiert, sollte man immer erstmal profilen, sonst optimiert man an der falschen stelle, z.b. inner loops, obwohl man memory limitiert ist.

    So dass der Algorithmus checkt, dass er jetzt "im inneren" eines Dreiecks ist.

    klar, gibt viele optimierungen fuer verschiedene faelle, in anderen faellen wirken sie sich dann nur als overhead aus und geben nichts. man muss also genau wissen was gemacht wird. das aendert am grundsaetzlichen antialiasing nichts.

    Also dass das aktuelle Sample, sowie alle benachbarten Samples innerhalb des Dreiecks liegen. Dann könnte man denke ich einfach alle Samples die dann beim runterskalieren zu einem Pixel zusammengefasst werden mit der gleichen Farbe füllen.

    das haengt vom rasterisierungsalgorithmus ab. zeichnest du scanlines, weisst du sofort start und endpunkt und musst nur noch sau schnell fuellen. testest du samples gegens dreieck, kannst du sicher hierarchisch vorgehen, falls die dreiecke gross sind.

    Die Frage ist bloss, ob der Overhead den die dazu nötigen Tests verursachen nicht grösser als der Performance-Gewinn ist.

    das haengt vom einzelnen fall ab.

    @rapso:
    Gibt es denn keine "Schummel" Algorithmen, die in sagen wir 90% der Fälle gut aussehen, in den restlichen 10% noch akzeptabel, und deutlich schneller laufen als "brute-force" Supersampling?

    nein, eine loesung die fast immer geht kann man fast nie nennen. beschreibe ganz genau deinen anwendungsfall, dann kann man eventuell was finden. ansonsten schick ich dich mit 10'tollen' ideen 9mal in die wueste 😉 (screenshot kann helfen).

    Oder... lässt sich AA mit dem Quincunx Pattern in Software vernünftig implementieren? Das Rendern selbst müsste damit ja halbwegs schnell gehen - bloss wie lange das Runterskalieren dann braucht kann ich überhaupt nicht abschätzen.

    runterskalieren muss man immer wenn es korrekt sein soll, das sollte aber nicht dramatisch langsam sein. mach dir einen test mit for(int y...)for(int x...) bei dem du dann die werte von einem hochskalierten int-array in ein kleineres mittels, das ist in 5min implementiert und gibt die grobe anhaltspunkte.

    p.S.: wie wird das am DS normalerweise gemacht? Final Fantasy IV (DS) hat zumindest irgendwas AA-ähnliches. Auf jeden Fall sind die Kanten von Objekten dort nicht komplett "hart". Es sieht nicht perfekt aus (sieht aus als ob's nur ein Zwischenschritt wäre), aber IMO besser als ganz ohne AA. Bei der geringen Leistung der CPU (ARM9 @ 66 MHz) würde es mich fast wundern, wenn die dort mit Supersampling zeichnen.

    der ds benutzt dafuer 3d hardware, nicht eine der cpus.
    Edge antialiasing in dem fall, zum testen kannst du 3linien an den raendern mit xialin wu zeichnen und dann dein dreieck drueber.



  • rapso schrieb:

    weil der algorithmuss die abdeckung von der aktuellen linie berechnet und mit dem hintergrund blended, es bestehen keine informationen darueber was vom hintergrund verdeckt wird, das sieht nur bei zwei farben einigermassen aus

    Man kann durchaus die Kanten eines Polygons als Wu-Lines betrachten und den Raum dazwischen herkoemmlich fuellen. Das Problem ist die Transparenz der Kanten die voraussetzt dass der Hintergrund schon existiert (sonst ist's schlecht mit blenden), was dem ueblichen Konzept von ZBuffering widerspricht.
    Man muss also entweder Polygone sortieren (ggf unmoeglich) oder gegeneinander Clippen. In verhaeltnismaessig kleinen Bereichen ist das durchaus loesbar - schau mal nach Tile-Based Rendering.
    Diese Technik wird zb im Mobile-Bereich wieder zunehmend interessant weil man sich den groesseren Speicherbedarf spart.



  • rapso schrieb:

    @rapso:
    Gibt es denn keine "Schummel" Algorithmen, die in sagen wir 90% der Fälle gut aussehen, in den restlichen 10% noch akzeptabel, und deutlich schneller laufen als "brute-force" Supersampling?

    nein, eine loesung die fast immer geht kann man fast nie nennen. beschreibe ganz genau deinen anwendungsfall, dann kann man eventuell was finden. ansonsten schick ich dich mit 10'tollen' ideen 9mal in die wueste 😉 (screenshot kann helfen).

    Schaaade 🙂
    BTW: ich habe keinen Anwendungsfall. Ist bloss ein Thema was mich interessiert, und wo mir noch etwas (sprich: sehr) die Erfahrung fehlt. Daher frag' ich gerne mal Leute die mehr Erfahrung haben so allgemeine Dinge wie eben diese Frage da oben.

    Oder... lässt sich AA mit dem Quincunx Pattern in Software vernünftig implementieren? Das Rendern selbst müsste damit ja halbwegs schnell gehen - bloss wie lange das Runterskalieren dann braucht kann ich überhaupt nicht abschätzen.

    runterskalieren muss man immer wenn es korrekt sein soll, das sollte aber nicht dramatisch langsam sein. mach dir einen test mit for(int y...)for(int x...) bei dem du dann die werte von einem hochskalierten int-array in ein kleineres mittels, das ist in 5min implementiert und gibt die grobe anhaltspunkte.[/quote]

    Wollte eigentlich nur wissen mit welchem Supersampling-Pattern man üblicherweise arbeitet, wenn man in Software rendert, und nicht allzuviel CPU Power zu verschenken hat. Da ist mir das Quincunx Pattern eingefallen, weil das mal in diversen Graka Treibern als Option angeboten wurde.

    p.S.: wie wird das am DS normalerweise gemacht? Final Fantasy IV (DS) hat zumindest irgendwas AA-ähnliches. Auf jeden Fall sind die Kanten von Objekten dort nicht komplett "hart". Es sieht nicht perfekt aus (sieht aus als ob's nur ein Zwischenschritt wäre), aber IMO besser als ganz ohne AA. Bei der geringen Leistung der CPU (ARM9 @ 66 MHz) würde es mich fast wundern, wenn die dort mit Supersampling zeichnen.

    der ds benutzt dafuer 3d hardware, nicht eine der cpus.
    Edge antialiasing in dem fall, zum testen kannst du 3linien an den raendern mit xialin wu zeichnen und dann dein dreieck drueber.

    Huch. Da hätte ich mal genauer die Hardware-Beschreibung durchgucken sollen. Ich dachte wirklich der DS rendert in Software. Dabei sehen die 3D Geschichten am DS nur Kacke aus, weil der durchaus vorhandene 3D Chip nicht filtern kann 🙂
    Auch interessant. Und schade. Gefiltert würden die meisten Spiele viel besser aussehen.


  • Mod

    hustbaer schrieb:

    Oder... lässt sich AA mit dem Quincunx Pattern in Software vernünftig implementieren? Das Rendern selbst müsste damit ja halbwegs schnell gehen - bloss wie lange das Runterskalieren dann braucht kann ich überhaupt nicht abschätzen.

    runterskalieren muss man immer wenn es korrekt sein soll, das sollte aber nicht dramatisch langsam sein. mach dir einen test mit for(int y...)for(int x...) bei dem du dann die werte von einem hochskalierten int-array in ein kleineres mittels, das ist in 5min implementiert und gibt die grobe anhaltspunkte.

    Wollte eigentlich nur wissen mit welchem Supersampling-Pattern man üblicherweise arbeitet, wenn man in Software rendert, und nicht allzuviel CPU Power zu verschenken hat. Da ist mir das Quincunx Pattern eingefallen, weil das mal in diversen Graka Treibern als Option angeboten wurde.[/quote]
    "damals" als es noch kein hardware AA gab und man das mit opengl mit accumulation buffern machte, gab es einige jitter pattern die gut funzten, siehe: http://www.opengl.org/resources/code/samples/advanced/advanced97/notes/node63.html

    p.S.: wie wird das am DS normalerweise gemacht? Final Fantasy IV (DS) hat zumindest irgendwas AA-ähnliches. Auf jeden Fall sind die Kanten von Objekten dort nicht komplett "hart". Es sieht nicht perfekt aus (sieht aus als ob's nur ein Zwischenschritt wäre), aber IMO besser als ganz ohne AA. Bei der geringen Leistung der CPU (ARM9 @ 66 MHz) würde es mich fast wundern, wenn die dort mit Supersampling zeichnen.

    der ds benutzt dafuer 3d hardware, nicht eine der cpus.
    Edge antialiasing in dem fall, zum testen kannst du 3linien an den raendern mit xialin wu zeichnen und dann dein dreieck drueber.

    Huch. Da hätte ich mal genauer die Hardware-Beschreibung durchgucken sollen. Ich dachte wirklich der DS rendert in Software. Dabei sehen die 3D Geschichten am DS nur Kacke aus, weil der durchaus vorhandene 3D Chip nicht filtern kann 🙂
    Auch interessant. Und schade. Gefiltert würden die meisten Spiele viel besser aussehen.

    jo, schaut recht duerftig aus was die hardware angeht, ist an sich nichts anderes als deren sprite zeichner vom gameboy, lediglich auf dreieckige statt quadratisch flaechen umgemoddelt.
    ich glaube mit filtering wuerde es erst wirklich auffallen wie mager die graphik ist, mit point filtering hat es noch ein wenig flair. zumal oft die models/texturen das beste draus machen.


Log in to reply