Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Signed Distance Field либо как сделать из растра вектор

Anna | 24.06.2014 | нет комментариев

Речь сегодня пойдёт о генерации изображений с картой расстояний (Signed Distance Field). Данный вид изображений знаменателен тем, что реально разрешает получить «векторную» графику на видеоускорителе, причём безвозмездно. Одной из первых данный способ растеризации предложила компания Valve в игре Team Fortress 2 для масштабируемых декалей в 2007 году, но до сих пор он не пользуется специальной популярностью, правда разрешает рендерить очаровательного качества шрифты, применяя текстуру каждого 256х256 точек. Данный способ восхитительно подходит для современных экранов высокой чёткости и разрешает серьёзно сэкономить на текстурах в играх, он не требователен к железу и восхитительно работает на телефонах.

Хитрость заключается в создании такой намеренно подготовленной карты расстояний, что при применении простейшего шейдера получается безупречная векторная картинка. Больше того, с поддержкой шейдеров дозволено получить результаты тени, свечения, объёма и т. п.

Как же создавать такие изображения? Дюже легко, ImageMagick разрешает сделать это одной командой:

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

На этом дозволено было бы поставить точку, но так полновесного топика не получится. Что ж, под катом — изложение стремительного алгорифма расчёта SDF, пример на C и немножко шейдеров для OpenGL.

Что это было за заклинание?

Первая команда в начале данного поста — это рецепт генерации SDF из всякого черно-белого растрового силуэта. Он основан на новой вероятности ImageMagick: морфологии. Среди морфологических реформирований присутствует и вычисление карты расстояний.

Расчёт карты расстояний — примитивный алгорифм. Он работает на монохромных изображениях, где пиксель либо чёрный, либо белый. Один из цветов считаем внутренним, иной — внешним (как огромнее нравится, на этой картинке с гепардом чёрный пиксель будет внутренним). Изредка их называют цветами фона и переднего плана. Для всякого «внутреннего» пикселя изображения необходимо обнаружить ближайший к нему «внешний» пиксель и установить значение яркости этого пикселя как евклидово расстояние до ближайшего «внешнего» пикселя. То есть необходимо вычислить расстояния до всех «внешних» пикселей изображения и предпочесть наименьшее из них. Получившаяся карта расстояний именуется Distance Field (DF), но она пока нам не подходит. Дабы получить SDF (Signed DF), инвертируем изображение, повторяем алгорифм, вновь инвертируем и складываем с предыдущим итогом.

Значение интенсивности не непременно устанавливать верно в значение расстояния: дозволено масштабировать «расплывчатость» изображения в зависимости от надобностей. В частности, для рендеринга чётких силуэтов отменнее применять менее размытую карту, а для таких спецэффектов как тень либо свечение — отменнее увеличить карту расстояний:

И правда ImageMagick не самый стремительный и примитивный метод сделать сходственную карту, я думаю это наилучший вариант, так как ImageMagick присутствует фактически на всех операционных системах и зачастую применяется разработчиками для конвейерной обработки спрайтов. Довольно немножко доделать скрипт и поставить генерацию изображений на поток.

Разглядим, как это работает. Если легко взять и применить операцию morphology к нашему изображению, получим не наилучший итог:

convert nosdf.png -morphology Distance Euclidean sdf.png

Малевич? Нет, легко негры ночью крадут уголь не хватает контрастности, её дозволено стремительно вытянуть параметром -auto-level:

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

Сразу кидается в глаза недочет: карта расстояний генерируется только снаружи. Это следствие того, что сам алгорифм тоже двухпроходный, повторим то же самое для негатива:

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

Сейчас обратная обстановка — не хватает карты снаружи.

Осталось объединить эти два алгорифма, применяя промежуточный слой, докрутить контрастность и получаем зубодробительный скрипт из начала поста:

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

Некоторые пояснения:
-resize 400% — увеличиваем начальное изображение, Дабы устранить зубчатые края. Алгорифм работает только для черно-белых изображений и хотелось бы хоть как-то рассматривать антиалиасинг. Но я бы порекомендовал неизменно иметь под рукой оригинал четырёхкратного размера либо огромнее. Valve, скажем, для демонстрации использует 4K изображение, из которого получает SDF размером 64×64. Это безусловно теснее перебор. Я нахожу приемлемым соотношение 8:1.
-level 45%,55% — дозволено регулировать степень размывания карты расстояний, по умолчанию она уж дюже расплывчатая.
-filter Jinc и -threshold 30% — экспериментально, данный фильтр и порог обеспечивает наилучшее соответствие начальному изображению. Под спойлером скрипт и исходник для желающих проверить.

Скрипт для поиска наилучшей метрики PSNR

Безусловно, единственно правильного варианта быть не может, но я оставил Jinc 30% как особенно средний вариант, дающий приемлемый итог.

Изображение:

Скрипт:

#!/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

Некоторые спорные вопросы.

Есть ли толк «вытягивать» контраст? Вообще теоретически при увеличении контраста возрастает дельта семплов, из которых потом аппаратным способом интерполяции рассчитывается антиалиасинг. Если коротко — вытягивать необходимо, исключительно если планируется выводить чёткие сглаженные силуэты и не так главны результаты как бы теней. Если начальная карта будет не только растягиваться, но и сжиматься, крепко увлекаться не стоит — в отвратном случае при уменьшении картинки будет портиться антиалиасинг, достигаемый за счёт размытых краёв SDF.

Как качество зависит от разрешения SDF-карты? Я постарался возвести график зависимости PSNR от разрешения карты и контрастности. В целом качество возрастает, но ещё крепко зависит от контрастности карты. Оценить зависимости дозволено на графике:


Тут Scale — это масштаб в процентах от исходника, Level — насколько крепко был «вытянут» контраст. Дозволено сделать итог, что от масштаба связанность не дюже уж и линейная, 30% будет крайне компромиссным вариантом, а контрастность достаточно крепко влияет на качество силуэта.

Насколько крепко влияет на качество размер фильтра Euclidean? Увеличение размера фильтра даёт приход в 0,1 дБ – копейки, на мой взор это несущественно.

Насколько крепко дозволено «ужать» начальное изображение? Это крепко зависит от формы. SDF не любит острые углы, а такая плавная картинка как гепард из примера великолепно Ощущает себя даже в крохотном масштабе:

Реализация стремительного алгорифма на C

Алгорифм примитивен, но его реализация «в лоб» будет трудиться часами: по сути необходимо для всякого пикселя просканировать всё изображение. O(N^2) нас абсолютно не устраивает. Но мудрые люди теснее подумали и придумали алгорифм точного (!) расчёта DF, тот, что работает за O(N). Осталось распространить задачу до SDF, что достаточно легко (см. предшествующий пример).

Суть. Взамен того Дабы считать для всякого пикселя расстояние, исполним два последовательных прохода по изображению, легко инкрементируя расстояние при определённых условиях. Это напоминает алгорифм стремительного Box-размывания изображения. Матан дозволено почерпнуть из [2], я же постараюсь объяснить на пальцах.

Пикселем p я буду называть элемент массива N*M, составленный из начального изображения. Пиксель — это дальнейшая конструкция:

{
    x, y - это покоординатное расстояние
    f - квадрат Евклидова расстояния
}

Как видно, тут ничего нет о яркости и т.п. — оно и не необходимо. Массив формируется так:
Если пиксель начального изображения ясный, то

x = y = 9999
f = 9999 * 9999

Если пиксель начального изображения тёмный, то

x = y = f = 0

У всякого пикселя есть 8 соседей, пронумеруем их таким образом:

2 3 4
1 p 5
8 7 6

Дальше введём две вспомогательные функции. Функция h необходима для вычисления расстояния Евклида между пикселем и соседом, функция G — для вычисления нового значения расстояния по компонентам.

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)}
}

1-й проход. Данный проход выполняется в прямом порядке (от левого верхнего угла изображения к правому нижнему). Псевдокод:

для всякого пикселя 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)
        }
    }
}

2-й проход. Данный проход выполняется в обратном порядке (от правого нижнего угла изображения к левому верхнему). Псевдокод:

для всякого пикселя 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)
        }
    }
}

Алгорифм необходимо повторить для негатива начального изображения. Потом для 2-х полученных карт необходимо произвести окончательное вычисление расстояния и вычитание для объединения 2-х карт DF в одну SDF:

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

Первоначально в структуре мы хранили квадрат Евклидова расстояния, следственно необходимо извелчь корень. Для чего необходимо прибавить единицу — не спрашивайте, итог эмпирический и без него получается криво:) Финальная карта SDF — итог вычитания 2-й из первой, дальше необходимо отмасштабировать значение как нравится.

На мой взор даже попытка на пальцах объяснить, как это работает, выглядит дюже запутанной, следственно я приведу начальный код на C . В качестве входного изображения я применял QImage из Qt, Дабы не портить наглядность процесса. Исходник основан на источнике [3], но там есть баги.

Исходник

#include <QPainter>
#include <stdio.h>
#include <math.h>

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;
}

/* macro is a way faster than inline */
#define Compare(offsetx, offsety)                                              
do {                                                                           
    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;                                               
        }                                                                      
    }                                                                          
} while(0)

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(-1,  0);
            Compare( 0, -1);
            Compare(-1, -1);
            Compare( 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( 1,  0);
            Compare( 0,  1);
            Compare(-1,  1);
            Compare( 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);
}

Тут применяется хитрость: так как оба прохода применяют «окно» шириной в 1 пиксель, я добавляю однопиксельный бордюр вкоруг начального изображения, Дабы избежать проверки границ. Для негатива бордюр тоже необходимо изменить на противоположное значение, чего не было учтено в [3].

Полновесный рабочий алгорифм дозволено посмотреть в генераторе растровых шрифтов с открытыи начальным кодом UBFG. Пример итога:

Шейдерим

Дабы увидеть итог применения SDF, без шейдеров обойтись. Примитивный альфа-тест также может использоваться, но он рубит на корню антиалиасинг. Впрочем применяемый шейдер представляет собой каждого пару инструкций и реально не влияет на продуктивность. Больше того, рассматривая что шейдеры теперь дешёвые, а память/кэш дорогие — дозволено получить недурное убыстрение за счёт экономии видеопамяти.

Сейчас посмотрим, как это дело дозволено применять в OpenGL. Все примеры будут даны в виде чистого GLSL начального кода. Опробовать дозволено в любом шейдерном редакторе. Все примеры я те

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB