Vorzeichenbehaftetes Distanzfeld oder wie man aus einem Raster einen Vektor macht

    Heute geht es darum, Bilder mit einer Entfernungskarte (Signed Distance Field) zu generieren. Diese Art von Bild ist insofern bemerkenswert, als Sie tatsächlich "Vektorgrafiken" auf einem Videobeschleuniger erhalten können, und das umsonst. Valve war eines der ersten Unternehmen, das diese Rasterungsmethode 2007 in Team Fortress 2 für skalierbare Abziehbilder anbot. Es ist jedoch immer noch nicht sehr beliebt, obwohl es das Rendern von Schriftarten von ausgezeichneter Qualität mit einer Textur von nur 256 x 256 Pixel ermöglicht. Diese Methode eignet sich perfekt für moderne hochauflösende Bildschirme und ermöglicht es Ihnen, Texturen in Spielen ernsthaft einzusparen. Sie stellt keine Anforderungen an die Hardware und funktioniert hervorragend auf Smartphones.



    Der Trick besteht darin, eine so speziell vorbereitete Entfernungskarte zu erstellen, dass bei Verwendung des einfachsten Shaders eine ideale Vektorillustration erhalten wird. Darüber hinaus können Sie mithilfe von Shadern die Auswirkungen von Schatten, Glühen, Lautstärke usw. erzielen.

    Wie werden solche Bilder erstellt? Mit ImageMagick können Sie dies ganz einfach mit einem Befehl ausführen :

    convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png
    

    Wir könnten dem ein Ende setzen, aber ein vollwertiges Thema wird nicht funktionieren. Nun, unter dem Schnitt - eine Beschreibung des schnellen SDF-Berechnungsalgorithmus, ein Beispiel in C ++ und einige Shader für OpenGL.

    Was war das für ein Zauber?


    Der erste Befehl am Anfang dieses Beitrags ist das Rezept zum Generieren von SDF aus einem beliebigen Schwarz-Weiß-Rasterumriss. Es basiert auf der neuen Funktion von ImageMagick: der Morphologie . Unter den morphologischen Transformationen gibt es auch die Berechnung einer Entfernungskarte .

    Die Berechnung der Entfernungskarte ist der einfachste Algorithmus. Es funktioniert mit monochromen Bildern, bei denen das Pixel entweder schwarz oder weiß ist. Wir betrachten eine der Farben intern und die andere extern (wie Sie möchten, ist das schwarze Pixel in diesem Bild mit dem Geparden intern). Manchmal werden sie Hintergrund- und Vordergrundfarben genannt. Für jedes „interne“ Pixel des Bildes müssen Sie das nächstgelegene „externe“ Pixel finden und den Helligkeitswert dieses Pixels als euklidischen Abstand festlegenauf das nächste "externe" Pixel. Das heißt, Sie müssen die Abstände zu allen "externen" Pixeln des Bildes berechnen und das kleinste davon auswählen. Die resultierende Entfernungskarte heißt Distance Field (DF), passt aber bisher nicht zu uns. Um SDF (Signed DF) zu erhalten, invertieren Sie das Bild, wiederholen Sie den Algorithmus, invertieren Sie erneut und fügen Sie das vorherige Ergebnis hinzu.

    Der Intensitätswert muss nicht genau auf den Entfernungswert eingestellt werden: Sie können das „verschwommene“ Bild je nach Bedarf skalieren. Insbesondere ist es besser, eine weniger verschwommene Karte zum Rendern klarer Konturen zu verwenden, und für Spezialeffekte wie Schatten oder Glühen ist es besser, die Entfernungskarte zu vergrößern:



    Obwohl ImageMagick nicht der schnellste und einfachste Weg ist, eine solche Karte zu erstellen, halte ich dies für die beste Option, da ImageMagick auf fast allen Betriebssystemen vorhanden ist und häufig von Entwicklern für Pipelining-Sprites verwendet wird. Es reicht aus, das Skript ein wenig zu vervollständigen und die Bilderzeugung in den Stream zu stellen.

    Mal sehen, wie es funktioniert. Wenn wir einfach die Morphologieoperation auf unser Bild anwenden, erhalten wir nicht das beste Ergebnis:

    convert nosdf.png -morphology Distance Euclidean sdf.png
    



    Malewitsch? Nein, nur Schwarze stehlen nachts Kohle, es gibt nicht genug Kontrast, es kann schnell mit dem Parameter herausgezogen werden -auto-level:

    convert nosdf.png -morphology Distance Euclidean -auto-level sdf.png
    



    Ein Fehler ist sofort erkennbar: Eine Entfernungskarte wird nur von außen erstellt. Dies ist eine Folge der Tatsache, dass der Algorithmus selbst auch zwei Durchgänge ist. Wir wiederholen dasselbe für das Negativ:

    convert nosdf.png -negate -morphology Distance Euclidean -auto-level sdf.png
    



    Jetzt ist die gegenteilige Situation - es gibt nicht genug Karte draußen.

    Es bleibt, diese beiden Algorithmen unter Verwendung einer Zwischenschicht zu kombinieren, den Kontrast zu verschärfen und vom Anfang des Beitrags an ein wütendes Skript zu erhalten:

    convert in.png -filter Jinc -resize 400% -threshold 30%  \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png
    

    Einige Erklärungen:
    -resize 400%- Vergrößern Sie das Originalbild, um die gezackten Kanten zu beseitigen. Der Algorithmus funktioniert nur für Schwarzweißbilder und ich möchte zumindest irgendwie Anti-Aliasing in Betracht ziehen. Aber ich würde immer empfehlen, das Original viermal so groß oder mehr zur Hand zu haben. Valve verwendet zum Beispiel ein 4K-Image zur Demonstration, von dem es eine 64x64-SDF empfängt. Das ist natürlich schon zu viel. Ich finde das Verhältnis 8: 1 akzeptabel.
    -level 45%,55%- Sie können den Grad der Unschärfe der Entfernungskarte anpassen, standardmäßig ist sie bereits sehr vage.
    -filter Jincund -threshold 30%- experimentell bieten dieser Filter und dieser Schwellenwert die beste Anpassung an das Originalbild. Unter dem Spoiler das Skript und die Quelle für diejenigen, die überprüfen möchten.
    Skript zum Finden der besten PSNR-Metrik
    Natürlich kann es keine echte Option geben, aber ich habe Jinc 30% als die durchschnittlichste Option belassen, was ein akzeptables Ergebnis ergibt.

    Bild:

    Skript:
    #!/bin/sh
    convert orig.png -resize 25% .orig-downscaled.png
    convert orig.png -threshold 50% .orig-threshold.png
    SIZE=$(identify orig.png| cut -d' ' -f3)
    MAX=0.0
    MAXRES=""
    for filter in $(convert -list filter)
    do
    	for threshold in $(seq 1 99)
    	do
    		convert .orig-downscaled.png -filter $filter -resize $SIZE! -threshold $threshold% .tmp.png
    		PSNR=$(compare -metric PSNR .orig-threshold.png .tmp.png /dev/null 2>&1)
    		if [ "$(echo "$MAX < $PSNR" | bc -l)" = "1" ]
    		then
    			MAXRES="$PSNR $filter $threshold"
    			echo $MAXRES
    			MAX=$PSNR
    		fi
    		rm .tmp.png
    	done
    done
    rm .orig-threshold.png .orig-downscaled.png
    



    Nun, wenn es ein Original mit einer höheren Auflösung gibt, können Sie auf einen Trick verzichten, indem Sie den Maßstab vergrößern und den Maßstab bereits nur auf eine kleinere Seite skalieren:
    convert in.png -threshold 50%  \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -filter Jinc -resize 10% out.png
    

    Bitte beachten Sie, dass der Jinc-Filter an das Ende der Kette „verschoben“ wurde, da dies die Qualität der Probenahme verbessern und gleichzeitig die Größe der Karte verringern soll. Bereinigen Sie auch nicht -threshold 50%- Euklidisch funktioniert bei nicht monochromen Bildern nicht richtig.

    Einige kontroverse Themen .

    Ist es sinnvoll, den Kontrast zu „dehnen“?Im Allgemeinen nimmt theoretisch mit zunehmendem Kontrast das Delta der Abtastwerte zu, woraus dann das Antialiasing unter Verwendung des Hardware-Interpolationsverfahrens berechnet wird. Kurz gesagt - Sie müssen sich dehnen, insbesondere wenn Sie klare, glatte Konturen anzeigen möchten und Effekte wie Schatten nicht so wichtig sind. Wenn sich die Originalkarte nicht nur dehnt, sondern auch schrumpft, sollten Sie sich nicht zu sehr mitreißen lassen. Andernfalls verschlechtert sich das Anti-Aliasing aufgrund der verschwommenen Kanten des SDF, wenn Sie die Bildgröße verringern.

    Wie hängt die Qualität von der Auflösung der SDF-Karte ab? Ich habe versucht, das PSNR gegen die Kartenauflösung und den Kontrast zu zeichnen. Im Allgemeinen steigt die Qualität, hängt jedoch stark vom Kontrast der Karte ab. Sie können die Abhängigkeiten im Diagramm auswerten:


    Hier ist Skalierung die Skalierung als Prozentsatz der Quelle, Ebene - wie stark der Kontrast „gedehnt“ wurde. Wir können daraus schließen, dass die Abhängigkeit von der Skala nicht sehr linear ist, 30% eine sehr kompromittierende Option darstellen und der Kontrast die Qualität der Kontur ziemlich stark beeinflusst.

    Wie stark beeinflusst die Größe des euklidischen Filters die Qualität ? Das Erhöhen der Filtergröße ergibt eine Erhöhung von 0,1 dB + - ein Penny, meiner Meinung nach ist dies nicht signifikant.

    Wie viel können Sie das Originalbild „verkleinern“? Es kommt sehr auf die Form an. SDF mag keine scharfen Ecken, und ein so glattes Bild wie der Gepard aus dem Beispiel fühlt sich auch im Miniaturmaßstab großartig an:



    Implementierung eines schnellen C ++ - Algorithmus


    Der Algorithmus ist einfach, aber seine "Stirn" -Implementierung funktioniert stundenlang: Tatsächlich müssen Sie das gesamte Bild für jedes Pixel scannen. O (N ^ 2) passt überhaupt nicht zu uns. Aber kluge Leute haben bereits nachgedacht und einen Algorithmus für die genaue (!) DF-Berechnung entwickelt, der für O (N) funktioniert. Es bleibt die Aufgabe, die Aufgabe auf SDF zu erweitern, was recht einfach ist (siehe vorheriges Beispiel).

    Das Endergebnis. Anstatt die Entfernung für jedes Pixel zu zählen, führen wir zwei aufeinanderfolgende Durchgänge durch das Bild durch und erhöhen die Entfernung unter bestimmten Bedingungen einfach. Dies erinnert an den schnellen Box-Blur-Algorithmus. Matan kann aus [2] entnommen werden, aber ich werde versuchen, es an den Fingern zu erklären.

    Ich werde das Pixel p das Element des Arrays N * M nennen, das aus dem Originalbild besteht. Ein Pixel hat die folgende Struktur:
    {
        x, y - это покоординатное расстояние
        f - квадрат Евклидова расстояния
    }
    

    Wie Sie sehen können, gibt es nichts über Helligkeit usw. - Es ist nicht notwendig. Das Array wird wie folgt gebildet:
    Wenn das Pixel des Quellbildes hell ist, dann
    x = y = 9999
    f = 9999 * 9999
    

    Wenn das Pixel im Originalbild dunkel ist, dann
    x = y = f = 0
    

    Jedes Pixel hat 8 Nachbarn, wir nummerieren sie folgendermaßen:
    2 3 4
    1 p 5
    8 7 6
    

    Als nächstes stellen wir zwei Hilfsfunktionen vor. Die Funktion h wird benötigt, um den euklidischen Abstand zwischen dem Pixel und dem Nachbarn zu berechnen, die Funktion G wird benötigt, um den neuen Abstandswert zwischen den Komponenten zu berechnen.
    h(p, q) {
        if q - сосед 1 или 5 {return 2 * q.x + 1}
        if q - сосед 3 или 7 {return 2 * q.y + 1}
        в остальных случаях {return 2 * (q.x + q.y + 1)}
    }
    

    G(p, q) {
        if q - сосед 1 или 5 {return (1, 0)}
        if q - сосед 3 или 7 {return (0, 1)}
        в остальных случаях {return (1, 1)}
    }
    

    Erster Durchgang . Diese Passage wird in direkter Reihenfolge ausgeführt (von der oberen linken Ecke des Bildes nach rechts unten). Pseudocode:
    для каждого пикселя p изображения {
        для каждого соседа q от 1 до 4 {
            if (h(p, q) + q.f < p.f) {
                p.f = h(p, q) + q.f
                (p.x, p.y) = (q.x + q.y) + G(p, q)
            }
        }
    }
    

    Zweiter Durchgang . Dieser Durchgang erfolgt in umgekehrter Reihenfolge (von der unteren rechten Ecke des Bildes nach links oben). Pseudocode:
    для каждого пикселя p изображения {
        для каждого соседа q от 5 до 8 {
            if (h(p, q) + q.f < p.f) {
                p.f = h(p, q) + q.f
                (p.x, p.y) = (q.x + q.y) + G(p, q)
            }
        }
    }
    

    Der Algorithmus muss für das Negativ des Originalbildes wiederholt werden. Dann müssen Sie für die zwei empfangenen Karten die endgültige Entfernungsberechnung und Subtraktion durchführen, um die beiden DF-Karten zu einer SDF zu kombinieren:

    d1 = sqrt(p1.f + 1);
    d2 = sqrt(p2.f + 1);
    d = d1 - d2;
    

    Anfangs haben wir das euklidische Distanzquadrat in der Struktur beibehalten, also müssen wir die Wurzel schleifen. Warum Sie eine hinzufügen müssen - fragen Sie nicht, das Ergebnis ist empirisch und ohne es stellt sich heraus, dass es schief ist :) Die endgültige SDF-Karte ist das Ergebnis des Subtrahierens der zweiten von der ersten, dann müssen Sie den Wert nach Ihren Wünschen skalieren.

    Meiner Meinung nach scheint sogar ein Versuch zu erklären, wie es an den Fingern funktioniert, sehr verwirrend, daher werde ich den Quellcode in C ++ angeben. Als Eingabebild habe ich QImage von Qt verwendet, um die Sichtbarkeit des Prozesses nicht zu beeinträchtigen. Die Quelle basiert auf der Quelle [3], aber es gibt dort Fehler.

    Quellcode
    #include 
    #include 
    #include 
    struct Point
    {
        short dx, dy;
        int f;
    };
    struct Grid
    {
        int w, h;
        Point *grid;
    };
    Point pointInside = { 0, 0, 0 };
    Point pointEmpty = { 9999, 9999, 9999*9999 };
    Grid grid[2];
    static inline Point Get(Grid &g, int x, int y)
    {
        return g.grid[y * (g.w + 2) + x];
    }
    static inline void Put(Grid &g, int x, int y, const Point &p)
    {
        g.grid[y * (g.w + 2) + x] = p;
    }
    static inline void Compare(Grid &g, Point &p, int x, int y, int offsetx, int offsety)
    {
        int add;
        Point other = Get(g, x + offsetx, y + offsety);
        if(offsety == 0) {
            add = 2 * other.dx + 1;
        }
        else if(offsetx == 0) {
            add = 2 * other.dy + 1;
        }
        else {
            add = 2 * (other.dy + other.dx + 1);
        }
        other.f += add;
        if (other.f < p.f)
        {
            p.f = other.f;
            if(offsety == 0) {
                p.dx = other.dx + 1;
                p.dy = other.dy;
            }
            else if(offsetx == 0) {
                p.dy = other.dy + 1;
                p.dx = other.dx;
            }
            else {
                p.dy = other.dy + 1;
                p.dx = other.dx + 1;
            }
        }
    }
    static void GenerateSDF(Grid &g)
    {
        for (int y = 1; y <= g.h; y++)
        {
            for (int x = 1; x <= g.w; x++)
            {
                Point p = Get(g, x, y);
                Compare(g, p, x, y, -1,  0);
                Compare(g, p, x, y,  0, -1);
                Compare(g, p, x, y, -1, -1);
                Compare(g, p, x, y,  1, -1);
                Put(g, x, y, p);
            }
        }
        for(int y = g.h; y > 0; y--)
        {
            for(int x = g.w; x > 0; x--)
            {
                Point p = Get(g, x, y);
                Compare(g, p, x, y,  1,  0);
                Compare(g, p, x, y,  0,  1);
                Compare(g, p, x, y, -1,  1);
                Compare(g, p, x, y,  1,  1);
                Put(g, x, y, p);
            }
        }
    }
    static void dfcalculate(QImage *img, int distanceFieldScale)
    {
        int x, y;
        int w = img->width(), h = img->height();
        grid[0].w = grid[1].w = w;
        grid[0].h = grid[1].h = h;
        grid[0].grid = (Point*)malloc(sizeof(Point) * (w + 2) * (h + 2));
        grid[1].grid = (Point*)malloc(sizeof(Point) * (w + 2) * (h + 2));
        /* create 1-pixel gap */
        for(x = 0; x < w + 2; x++)
        {
            Put(grid[0], x, 0, pointInside);
            Put(grid[1], x, 0, pointEmpty);
        }
        for(y = 1; y <= h; y++)
        {
            Put(grid[0], 0, y, pointInside);
            Put(grid[1], 0, y, pointEmpty);
            for(x = 1; x <= w; x++)
            {
                if(qGreen(img->pixel(x - 1, y - 1)) > 128)
                {
                    Put(grid[0], x, y, pointEmpty);
                    Put(grid[1], x, y, pointInside);
                }
                else
                {
                    Put(grid[0], x, y, pointInside);
                    Put(grid[1], x, y, pointEmpty);
                }
            }
            Put(grid[0], w + 1, y, pointInside);
            Put(grid[1], w + 1, y, pointEmpty);
        }
        for(x = 0; x < w + 2; x++)
        {
            Put(grid[0], x, h + 1, pointInside);
            Put(grid[1], x, h + 1, pointEmpty);
        }
        GenerateSDF(grid[0]);
        GenerateSDF(grid[1]);
        for(y = 1; y <= h; y++)
            for(x = 1; x <= w; x++)
            {
                double dist1 = sqrt((double)(Get(grid[0], x, y).f + 1));
                double dist2 = sqrt((double)(Get(grid[1], x, y).f + 1));
                double dist = dist1 - dist2;
                // Clamp and scale
                int c = dist * 64 / distanceFieldScale + 128;
                if(c < 0) c = 0;
                if(c > 255) c = 255;
                img->setPixel(x - 1, y - 1, qRgb(c,c,c));
            }
        free(grid[0].grid);
        free(grid[1].grid);
    }
    


    Hier wird ein Trick verwendet: Da beide Durchgänge ein 1 Pixel breites „Fenster“ verwenden, füge ich dem Originalbild einen Einzelpixelrand hinzu, um ein Überprüfen der Ränder zu vermeiden. Für Negative muss die Grenze ebenfalls auf den entgegengesetzten Wert geändert werden, der in [3] nicht berücksichtigt wurde.

    Einen vollständigen Arbeitsalgorithmus finden Sie im Open Source Raster Font Generator UBFG . Beispielergebnis:



    Shaderim


    Die Idee der inversen Transformation (von SDF zu Rasterkontur) basiert darauf, den Kontrast so weit zu erhöhen, dass verschwommene Kanten nicht sichtbar sind. Durch Ändern des Kontrasts des SDF können Sie verschiedene Effekte erzielen und die Qualität des Anti-Aliasing des Bildes anpassen. Nehmen Sie als Beispiel die Quelle:



    Dies ist auch eine SDF, nur sehr komprimiert und verkleinert. Erhöhen Sie ihn um das 16-fache:



    Erhöhen Sie jetzt den Kontrast, um einen schönen Umriss zu erhalten. Ich habe GIMP für folgende Zwecke verwendet:



    Um das Ergebnis der Verwendung von SDF in Echtzeit zu sehen, sind Shader unverzichtbar. Der einfachste Alpha-Test kann ebenfalls verwendet werden, schneidet jedoch das Anti-Aliasing an seiner Wurzel ab. Der verwendete Shader besteht jedoch nur aus ein paar Anweisungen und hat keinen Einfluss auf die Leistung. Wenn man bedenkt, dass Shader jetzt billig und Speicher / Cache teuer sind, kann man durch das Speichern von Videospeicher eine gute Beschleunigung erzielen.

    Nun wollen wir sehen, wie dieses Geschäft in OpenGL verwendet werden kann. Alle Beispiele werden als reiner GLSL-Quellcode angegeben. Sie können es in jedem Shader-Editor versuchen. Ich habe alle Beispiele im Kick.js-Editor getestet , da dies der einzige Editor ist, mit dem Sie Ihre Texturen laden können.

    Die einfachste schnelle Option

    precision highp float;
    uniform sampler2D tex;
    const float contrast = 40.;
    void main(void)
    {
    	vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.3).xxx;
    	gl_FragColor = vec4((c-0.5)*contrast,1.0);
    }
    

    Hier zeichnen wir einfach den Kontrast relativ zum Mittelwert (0,5). Die Stärke des Kontrasts sollte abhängig vom Maßstab der Textur und dem Abstrich der DF-Karte variieren - der Parameter wird experimentell ausgewählt und durch einheitlich mit einem Skalierungsfaktor eingestellt.

    Mit einem Filter können Sie die Qualität leicht verbessern smoothstep:

    precision highp float;
    uniform sampler2D tex;
    const float threshold = .01;
    void main(void)
    {
    	vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.3).xxx;
    	vec3 res = smoothstep(.5-threshold, .5+threshold, c);
    	gl_FragColor = vec4(res,1.0);
    }
    

    Hier muss auch der Schwellenwert ausgewählt werden. smoothstepetwas langsamer bei älteren Grafikkarten und Handys.

    Gliederungseffekt

    Um diesen Effekt zu erzielen, müssen Sie zwei Schwellenwerte festlegen und die Farbe umkehren:
    precision highp float;
    uniform sampler2D tex;
    const float contrast = 20.;
    void main(void)
    {
    	vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35).xxx;
    	vec3 c1 = (c-.45) * contrast;
    	vec3 c2 = 1.-(c-.5) * contrast;
    	vec3 res = mix(c1, c2, (c-.5)*contrast);
    	gl_FragColor = vec4(res,1.0);
    }
    

    Ergebnis:

    Glüh- und Schatteneffekt

    Etwas mehr Chemie als im vorherigen Beispiel - und wir erhalten den Glow-Effekt:
    precision highp float;
    uniform sampler2D tex;
    const float contrast = 20.;
    const float glow = 2.;
    void main(void)
    {
        vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35).xxx;
        vec3 c1 = clamp((c-.5)*contrast,0.,1.);
        vec3 c2 = clamp(1.-(c-.5)/glow, 0., 1.);
        vec3 res = 1.-mix(c1, c2, (c-.5)*contrast);
        gl_FragColor = vec4(res,1.0);
    }
    

    Um einen Schatten zu erhalten, müssen Sie eine Farbe für das Leuchten mit einem Versatz verwenden:
    precision highp float;
    uniform sampler2D tex;
    const float contrast = 20.;
    const float glow = 2.;
    void main(void)
    {
        vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35).xxx;
        vec3 gc = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35 + vec2(-0.02,0.02)).xxx;
        vec3 c1 = clamp((c-.5)*contrast,0.,1.);
        vec3 c2 = clamp(1.-(gc-.5)/glow, 0., 1.);
        vec3 res = 1.-mix(c1, c2, (c-.5)*contrast);
        gl_FragColor = vec4(res,1.0);
    }
    

    Ergebnis:


    Das Ergebnis scheint nicht so heiß zu sein, aber das liegt daran, dass ich eine zu kleine Karte verwendet habe:



    Referenzen


    [1] Verbesserte Alpha-getestete Vergrößerung für Vektortexturen und Spezialeffekte ist der gleiche Artikel von Valve.
    [2] Frank Y. Shih, Yi-Ta Wu. Schnelle euklidische Entfernungstransformation in zwei Scans mit einer 3x3-Nachbarschaft - Chinesisch? Nein, nur eine Universität von New Jersey.
    [3] www.codersnotes.com/notes/signed-distance-fields - Dies ist ebenfalls ein ziemlich schneller Algorithmus, aber leider hat der Autor mehrere Fehler gemacht und es liegt eine Multiplikation vor, die etwas langsamer ist als der in diesem Artikel vorgestellte Algorithmus.
    [4] contourtextures.wikidot.com- Eine weitere Implementierung der SDF-Berechnung, deren Vorteil jedoch darin besteht, dass die Glättung der Kanten berücksichtigt werden kann, um die nächsten Punkte zu bestimmen. Über die Leistung wird nichts gesagt, aber es ist gut, wenn es keine Möglichkeit gibt, ein hochauflösendes Original zu erhalten (andererseits können Sie einfach den gehobenen Trick ausführen). Wenn Sie Erfahrung damit haben, melden Sie sich in den Kommentaren ab.
    [5] gpuhacks.wordpress.com/2013/07/08/signed-distance-field-rendering-of-color-bit-planes - eine Methode zum Rendern von Farbvektorbildern (geeignet für eine kleine Anzahl von Farben).
    [6] distance.sourceforge.net ist eine interessante Ressource, mit der verschiedene SDF-Berechnungsalgorithmen verglichen werden.

    upd. Спасибо замечанию Bas1l, алгоритм всё-таки не совсем точный и может давать ошибки на вычислении расстояния до ближайших соседей из-за ошибки в доказательстве. В этой статье представлена улучшенная версия алгоритма.

    upd2. От пользователя achkasov замечание по части шейдеров. В случае резких переходов на SDF карте могут появляться заплывы и неравномерный антиалиасинг. Подробнее об эффекте и о том, как с этим бороться: iquilezles.org/www/articles/distance/distance.htm

    Изменив шейдр, получаем значительное улучшение в области, кхм, хвоста:



    Код GLSL
    precision highp float;
    uniform sampler2D tex;
    const float contrast = 2.;
    float f(vec2 p)
    {
    	return texture2D(tex,p).x - 0.5;
    }
    vec2 grad(vec2 p)
    {
        vec2 h = vec2( 4./256.0, 0.0 );
        return vec2( f(p+h.xy) - f(p-h.xy),
                     f(p+h.yx) - f(p-h.yx) )/(2.0*h.x);
    }
    void main(void)
    {
    	vec2 p = gl_FragCoord.xy/vec2(256., 128.)*.35;
        //float c = texture2D(tex,p).x;
        float v = f(p);
        vec2  g = grad(p);
        float c = (v)/length(g);
        float res = c * 300.;
        gl_FragColor = vec4(res,res,res, 1.0);
    }
    


    Jetzt auch beliebt: