Войти
ПрограммированиеФорумГрафика

Генерация SDF символов на GPU (просто делюсь опытом)

Страницы: 1 2 Следующая »
#0
(Правка: 5:54) 5:54, 11 сен. 2019

Для статьи - мало, поэтому просто пост.

Как известно есть всякие способы нагенерить SDF на лету даже на GPU. Обычно рисуют глиф в высоком разрешении, от полученного битмапа генерят SDF, а потом сжимают.

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

Вот мой код пиксельного шейдера, который считает signed distance field для глифа:

struct VS_Output {
    float4 pos : SV_Position;
};

struct PS_Output {
    float4 color : SV_Target0;
};

float GlyphSize;
StructuredBuffer<float4> Glyph : register(t32);

float Cross2D(float2 v1, float2 v2) {
    return v1.x*v2.y - v1.y*v2.x;
}

float DistanceToLine(float4 seg, float2 pt) {
    float2 segdir = seg.zw - seg.xy;
    float2 ptdir = pt - seg.xy;
    float s = Cross2D(segdir, ptdir);
    if (dot(segdir, ptdir) < 0) return length(ptdir);
    ptdir = pt - seg.zw;
    if (dot(segdir, ptdir) > 0) return length(ptdir);
    return sqrt( s*s/dot(segdir,segdir) );
}

const static float2 eps = {0, 0.001};

uint InTriangle(float4 seg, float2 pt) {
    float d = (seg.x-eps.x)*(seg.w-eps.y)-(seg.z-eps.x)*(seg.y-eps.y);
    if (d == 0) return false;
    float l1 = (seg.w-eps.y)*(pt.x-eps.x)-(seg.z-eps.x)*(pt.y-eps.y);
    float l2 = (seg.x-eps.x)*(pt.y-eps.y)-(seg.y-eps.y)*(pt.x-eps.x);
    l1/=d;
    l2/=d;
    if (l1<=0) return false;
    if (l2<=0) return false;
    if (l1+l2>=1) return false;
    return true;
}

PS_Output main(VS_Output In) {
    PS_Output Out;
    Out.color = 0;

    float mind = 100000.0;
    uint inTri = 0;
    [loop]
    for (int i = 0; i < GlyphSize; i++) {
        mind = min(mind, DistanceToLine(Glyph[i], In.pos.xy));
        inTri += InTriangle(Glyph[i], In.pos.xy);
    }
    Out.color.r = inTri%2 ? -mind : mind;

    return Out;
}
В Glyph нужно передавать набор отрезков (xy - один конец отрезка, zw - второй конец)
GlyphSize - количество отрезков в Glyph

Код просто находит минимальную дистанцю до всех отрезков через DistanceToLine.
Чтобы найти знак - проверяем количество вхождений в треугольник через InTriangle.

Весь алфавит (латинский + кириллица) для глифов размером в 32 пикселя с бордером в 8 пикселей (т.е. эффективно каждый глиф до 48 пикселей) у меня генерится меньше чем за миллисекунду.
Так что если надо кому - можете пользоваться, лицензия на шейдер MIT. :)

#1
(Правка: 9:06) 9:03, 11 сен. 2019

MrShoor
Если проекция P на (A,B) перед A (dot(AP,AB)<0) - возвращается AP,
если проекция P на (A,B) за B (dot(AP,AB)>AB^2) - возвращается BP,
Иначе возвращается длина перпендикуляра

// squared dist from point P to line (A,B)
float dist2(Vec2f p,Vec2f a,Vec2f b)
{
  Vec2f l=b-a;p-=a;
  float p2=p.len2(),d=dot(p,l),l2=l.len2();
  if(d<0)  return p2;
  if(d>l2) return p2-d-d+l2;
  return p2-d*d/l2;
}

Ну а отрезки где берешь, если
> Весь алфавит (латинский + кириллица) для глифов размером в 32 пикселя

> генерится меньше чем за миллисекунду
Это хорошо, но я видел статью где Distance field считают за O(N) от числа пикселей, одними целочисленными сложениями

#2
9:14, 11 сен. 2019

Aslan
> Если проекция P на (A,B) перед A (dot(AP,AB)<0) - возвращается AP,
> если проекция P на (A,B) за B (dot(AP,AB)>AB^2) - возвращается BP,
> Иначе возвращается длина перпендикуляра
Так у меня вроде так и есть

> Ну а отрезки где берешь, если
GetGlyphOutlineW

> Это хорошо, но я видел статью где Distance field считают за O(N) от числа пикселей
Да, есть такая статья. Вот: http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf
Я и имплементацию делал: https://github.com/MrShoor/AvalancheProject/blob/master/Common/av… ator.pas#L715
Там не совсем честное линейное время. Там "в среднем" линейное время.
На GPU этот алгоритм плохо ложится из-за особенностей работы с памятью, и разделения памяти. В итоге этот линейный алгоритм проигрывает другому алгоритму, с логарифмической сложностью. Вот этот алгоритм:
https://www.comp.nus.edu.sg/~tants/jfa.html
Отлично параллелится, и я его использую на практике (но не для глифов).

Но как выяснилось генерить глифы быстрее сразу от отрезков. Для глифа у меня выходит не больше 200-300 отрезков. С учетом маленького разрешения глифов такой подход выигрывает.

#3
13:45, 11 сен. 2019

MrShoor
> С учетом маленького разрешения глифов такой подход выигрывает.
Хорошо бы придумать какую-нибудь ускоряющую структуру, чтобы и для больших глифов работало.
Типа: разбить на квадраты и для каждого квадрата выбрать только те отрезки, которые актуальны.

#4
15:21, 11 сен. 2019

MrShoor
>> Иначе возвращается длина перпендикуляра
>Так у меня вроде так и есть
Да, у тебя все верно
Я в этом месте сократил 1 dot за счет сравнения с |AB|^2

Я читал, вот это, 2 прохода по картинке:
"Fast Euclidean distance transformation in two scans using a 3 В 3 neighborhood" Frank Y. Shih and Yi-Ta Wu

#5
16:27, 11 сен. 2019

MrShoor
> это посчитать SDF прямо до сегментов контура сразу в том разрешении, в котором
> надо. Просто и тупо.

Старо как мир. Можно в общем то и не контур брать, а скелет. Дальше усложнять по нарастающей - добавлять ребрам толщины. В общем весь фонт разлагаешь на геометрию и SDF + шейдер.
Получаешь компактный способ хорошо кастомизируемых фонтов. Довести до конца и оформить в виде компонента - будет крутяк.

#6
21:06, 11 сен. 2019

Aslan
> Я в этом месте сократил 1 dot за счет сравнения с |AB|^2
Ага, вижу, круто. Не очень очевиден трюк с return p2-d-d+l2;

> Я читал, вот это, 2 прохода по картинке:
> "Fast Euclidean distance transformation in two scans using a 3 В 3
> neighborhood" Frank Y. Shih and Yi-Ta Wu
Чет какая-то мутная статья. Читал по диагонали, скажи, я правильно понимаю, что это обычный CDA 3 отсюда: http://perso.ensta-paristech.fr/~manzaner/Download/IAD/Grevera_04.pdf ?
Со всеми присущими ему проблемами.

slepov
> Можно в общем то и не контур брать, а скелет.
Если ты про straight skeleton, то у меня нет идей зачем он там нужен. Он же не дает евклидову дистанцию.

#7
21:09, 11 сен. 2019

}:+()___ [Smile]
> Хорошо бы придумать какую-нибудь ускоряющую структуру, чтобы и для больших
> глифов работало.
> Типа: разбить на квадраты и для каждого квадрата выбрать только те отрезки,
> которые актуальны.
Что-то как-то для <300 отрезков есть ощущение бессмысленности такого разбиения. А глифов больше 300 сегментов у меня и нет. С другой стороны если рассматривать не только в контексте глифов, то есть вероятность что обычный рендер полигона с последующим jump flooding-ом и downscale-ом будет быстрее, чем построение таких оптимизирующих структур.
Хотя у меня пока даже идей нет, по поводу того, какой должна быть эта ускоряющая структура.

#8
21:15, 11 сен. 2019

MrShoor
> Если ты про straight skeleton, то у меня нет идей зачем он там нужен.
>

Скелет - тот же набор отрезков. Для него и строишь SDF.

>Он же не дает евклидову дистанцию.

Не понял, почему? те же отрезки

#9
22:33, 11 сен. 2019

MrShoor
> А глифов больше 300 сегментов у меня и нет.
При увеличении размеров глифов растет не только филрейт, но и количество сегментов.
Мне, собственно, интересен рендерер произвольных сплайнов, который на малых размерах вырождается в твой алгоритм, но и на больших размерах работает более-менее быстро.

> Хотя у меня пока даже идей нет, по поводу того, какой должна быть эта ускоряющая структура.
Я думаю в сторону квадтри: каждый сегмент сначала попадает в 1–4 узлов дерева, а потом делается проход вверх и релевантные сегменты выносятся на более крупные уровни иерархии.

#10
(Правка: 23:13) 23:11, 11 сен. 2019

}:+()___ [Smile]
> При увеличении размеров глифов растет не только филрейт, но и количество
> сегментов.
300 - это достаточно детализированный глиф. По крайней мере он выглядит нормально даже если его на весь экран открыть.
Вот в этом символе например всего 134 сегмента.

+ Показать

Или вот уже сложный символ:
+ Показать

Но всего 171 сегмент.
И это Times New Roman, который весь такой с засечками.

> Мне, собственно, интересен рендерер произвольных сплайнов, который на малых
> размерах вырождается в твой алгоритм, но и на больших размерах работает
> более-менее быстро.
Если для более сложных, произвольных сплайнов на тысячи сегментов то да. Только учитывай, если у тебя будет 1К сплайнов по 100 сегментов, и 2 сплайна по 10К - то ты можешь и проиграть на оптимизациях. :)

> Я думаю в сторону квадтри: каждый сегмент сначала попадает в 1–4 узлов дерева,
> а потом делается проход вверх и релевантные сегменты выносятся на более крупные
> уровни иерархии.
Да, я понял идею. Если мы нашли уже минимальную дистанцию в N, то нет смысла проверять узлы дерева, которые лежат дальше чем N. Должно сработать для сложных шейпов, можно попробовать. Тут главный критерий, что дерево должно быть разреженным.

На GPU это можно уложить я думаю как-то так. Берем консервативную растеризацию, и рисуем линии в грид с ячейкой N, потом 2N, потом 4N и так далее. Сами ячейки храним как хешмапу от координат (таким образом получаем "разреженность"), а в хешмапе линкед листы на сегменты в этой ячейке. Думаю может взлететь.

upd. A для случаев когда у нас мало сегментов (скажем <300) мы можем хранить всего один уровень ячейки + линкедлист на все сегменты, и не парится с консервативной растеризацией.

#11
23:28, 11 сен. 2019

slepov
> Не понял, почему? те же отрезки
Потому что вот например:
skeleton | Генерация SDF символов на GPU (просто делюсь опытом)
Красные отрезки - не равны. Хотя по скелетону это 4 "шага" по каждому из ребер.

#12
(Правка: 6:35) 5:48, 12 сен. 2019

MrShoor
> Не очень очевиден трюк с return p2-d-d+l2;
(P-B)^2=(P-A)^2-2*(P-A,B-A)+(B-A)^2

У тебя же сегменты - между соседними пикселами границы?
Т.е. угол наклона 0, 45, 90
А если просто брать минимум расстояния до концов?
И я бы считал sqrt уже от конечного минимума отдельным проходом

#13
7:24, 12 сен. 2019

Aslan
> У тебя же сегменты - между соседними пикселами границы?
Что?

> Т.е. угол наклона 0, 45, 90
Нет конечно

> И я бы считал sqrt уже от конечного минимума отдельным проходом
Точно! Как-то упустил я этот момент

#14
7:26, 12 сен. 2019

MrShoor
А как получаешь сегменты?

Страницы: 1 2 Следующая »
ПрограммированиеФорумГрафика