Привіт усім. Я вже одного разу писав про Distance Field і приводив реалізацію «евристичним» кодом, що дає непогану швидкість: «Чесний glow і швидкість».
Навіщо він потрібен?
DField можна застосовувати:
- Для значного підвищення якості шрифтів
- Для ефектів, наприклад, горіння контура. Один з ефектів я наводив у своїй попередній статті
- Для ефекту «metaballs» але в 2д і для будь-яких складних шейпів. (можливо я коли-небудь наведу приклад реалізації цього ефекту)
- А в даний момент DField мені потрібен для якісного згладжування кутів і видалення дрібних деталей.
І якщо в перших двох випадках ми можемо заздалегідь вирахувати DField, то для інших ефектів нам потрібно прораховувати його в реальному часі.
У статті буде розглянуто найбільш популярний, я б сказав класичний Chamfer distance (CDA) з купою картинок, що пояснюють принцип його роботи, а так само розглянуто двопрохідний алгоритм на GPU.
Обидва алгоритми реалізовані в демонстраційних програмах на FPC.
Chamfer класика на CPU
Сьогодні я хотів би звернути увагу на класичний спосіб розрахунку DField. Погратися можна тут (вихідний код в git-і). Алгоритм має неусталену назву: chamfer distance algoritm. Цей спосіб вже описував RPG у своїй топіці. Однак там немає пояснень чому і як працює цей код. Чому виникають похибки, які вони, і як їх зменшити.
upd. У RPG модифікація CDA алгоритму, яка успішно бореться з похибками.
Під капотом у Chamfer
Отже, у нас є монохромне зображення, від якого ми хочемо побудувати Distance Field. Це біла точка на чорному тлі:
Почнемо будувати DField. Для цього спочатку заповнимо наше майбутнє зображення + нескінченністю для пустот, і нулями для об'єкта. Якось так:
Потім починаємо бігти по зображенню (зліва направо і зверху вниз), і для кожного пікселя перевіряти його сусідів. Візьмемо у сусідньому пікселі значення, додамо до цього значення відстань до сусіда. Для пікселів праворуч і ліворуч - це відстань = 1. Для пікселів по діагоналі sqrt (1 * 1 + 1 * 1) = sqrt (2). Запишемо в наш піксель мінімальне значення між поточним, і тільки що обчисленим у сусіда. Після того як зробимо це для всіх сусідів - переходимо до наступного пікселю. У нас вийшла така картина:
Оскільки ми бігли зліва направо і зверху вниз - відстані накопичувалися від попередніх розрахунків, і пікселі позначені червоними стрілками автоматично порахувалися «вірно». Тепер якщо ми пробіжимо в зворотному напрямку (справа наліво, знизу вгору) - то заповниться відсутня частина карти.
Отже, основна ідея - використовувати вже прораховану ранню відстань. Для цього нам не потрібно перевіряти всіх сусідів. Достатньо перевірити пікселі, за якими ми вже пробігли:
Червоним - позначені пікселі сусідів для першого проходу (праворуч, вниз). Синім - для другого (наліво, вгору).
Перший прохід дасть нам красивий шлейф в один бік:
Другий дасть в іншу, а оскільки ми будемо записувати тільки мінімальне значення в обох випадках - то в сумі воно буде виглядати ось так:
Складність алгоритму O (2 * W * H * 5)
Тепер поговоримо про точність. На поточному зображенні не видно проблем, але якщо ви спробуєте побудувати контур (як у цій статті) - то результат буде не самим правдоподібним. Подивимося на distance% 16 контур:
Червоними стрілками я відзначив яскраво виражену віктогональність зображення. Чому ж так відбувається? А все просто, адже наш результат накопичується, і накопичується він неправильно:
Наша відстань буде обчислена по червоній лінії: 1 + sqrt (2), тоді як правильно його обчислюватиме за синьою лінією: sqrt(2*2+1*1)=sqrt(3). Якщо ми будемо в розрахунках брати не тільки сусідів, а й сусідів сусідів:
Результат, звичайно, буде краще. Але обчислювальні складнощі зростають з O (2 * W * H * 5) до O (2 * W * H * 13). Але є і хороші новини, ми можемо викинути частину сусідів, ніяк не вплинувши на результат:
Справа в тому, що викинуті сусіди мають кратну відстань і лежать на одному промені. А значить ми їх можемо викинути, бо значення від найближчих буде коректно накопичуватися. Матрицю сусідів я буду називати ядром. У першому випадку у нас було ядро 3х3. Зараз ядро 5х5. Давайте подивимося на результат:
Наша віктогональність стала помітно «круглішою». (До речі, у фотошопі для шарів є ефект Outer glow з параметром precise. У мене результат в точності збігся після проходу ядром 5х5. Схоже вони використовують саме цей алгоритм для даного ефекту.)
Складність оптимізованого 5x5 = O (2 * W * H * 9)
Можна далі продовжувати підвищувати і підвищувати розмір ядра, якість буде зростати, але один неприємний ефект ми так і не зможемо побороти. Ось зображення для ядра 13 * 13:
На зображенні присутні ступінчасті градієнти. Вони також пов'язані з горезвісною похибкою, і щоб остаточно позбутися від них нам довелося б створити ядро розміром у дві ширини зображення, оскільки діагональ зі сторонами (Багато, 1) може покрити тільки ядро розміром 2 * Багато + 1. (з цими похибками борються різні модифікації CDA, один з варіантів - зберігати в пікселі вектор до найближчого, але я в статті їх зачіпати не буду).
Отже сумарно, плюси алгоритму
- Необмежений Distance Field (що це таке ми зрозуміємо коли розберемося з алгоритмом на GPU).
- Лінійна складність, і висока швидкість для маленьких ядер.
- Простота реалізації.
Мінуси
- Погана точність (особливо для маленьких ядер)
- Залежність від попередніх обчислень (ніяких вам SIMD)
GPU в бій
На жаль, я не знайшов жодних популярних алгоритмів, що лягають на багатопоточну архітектуру GPU. Чи то руки у мене не ті, чи то гугл затиснув. Тому я поділюся з вами своїм «велосипедом». Благо він простий. Погратися можна тут, вихідці лежать в git. Для гри потрібна відеокарточка, що підтримує OpenGL3 і Rect текстури.
Отже, припустимо нам важливо розрахувати Distance Field в радіусі 40 пікселів. Першим проходом ми вважаємо тільки вертикальну дистанцію від 40 сусідів зверху і від 40 сусідів знизу для кожного пікселя. Записуємо мінімальне значення (якщо заповнених сусідів немає - записуємо максимальне значення, 40). Отримуємо ось таку картину:
Після цього робимо другий прохід по горизонталі. Так само 40 сусідів ліворуч, 40 сусідів праворуч. Знаючи відстані до сусіда, + відстань по вертикалі у сусіда - ми легко вважаємо гіпотенузу:
У результат записуємо мінімальну гіпотенузу. Після другого проходу нас чекає красива і правильно побудована картинка:
Складність алгоритму O (2 * W * H * (2 * D + 1)), де W і H - розміри зображення, а D - відстань distance field. Distance field у нас виходить нормалізованим (у зображенні не буде значень більше D).
Точність обчислень відмінна, оскільки похибки не накопичуються:
У додатку до статті є три режими: GL_R8, GL_R16, GL_R32F. Якщо увімкнути GL_R8 і покрутити дистацію, то можна помітити стрибаючі похибки. Справа тут ось у чому. Для проміжного вертикального DField-а текстура для зберігання має розмір 8біт на піксель. Оскільки я нормалізую дистанцію на діапазон [0, 1], то виникають похибки. Потрібно або зберігати не нормалізовану дистанцію (але тоді для восьмибітної текстури вона обмежується 255 пікселями), або підвищувати розрядність текстури. Для текстури R16-ці похибки менші, а для R32F ці похибки взагалі «відстукують», оскільки це float текстура. Враховуйте це, якщо захочете реалізувати подібний distance field.
Отже, плюси:
- Абсолютна точність
- Добре лягає на SIMD.
- Простота реалізації
- Дані відразу лежать на GPU!
Мінуси
- Обмежена дистанція. Ми повинні знати, яка дистанція нам потрібна заздалегідь.
- Складність алгоритму залежить від дистанції
- Дані на GPU (це може вимагати додатково час на отримання, якщо ми плануємо далі працювати з цими даними на CPU)
Висновки?
У мене в домашньому комп'ютері стоїть GF450. Для зображення Hello world і DField = 500 пікселів мій GPU примудряється робити 20 кадрів на секунду, що приблизно дорівнює 50мс на кадр. Все це з відмінною якістю і простим прозорим кодом. На CPU ядром 3х3 Distance field розраховується близько 100мс. 5х5 близько 200мс. Навіть якщо прискорити, оптимізуючи під CPU в 4 рази (що дуже круто), то я отримаю якість помітно гірше за той же час. Використовуйте GPU, якщо алгоритми це дозволяють.
Посилання на тему
- net/projects/dfsamples Власне приклади до статті. Бінарники і вихідці.
- springer.com/cda/content/document/cda_downloaddocument/9780387312019-c1.pdf - відмінний розбір як Chamfer алгоритму, так і його модифікацій. Порівняння похибки і часу виконання.
- valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf - Застосування DField у рендері шрифтів. Мабуть найвідоміша стаття.
- ru/post/215905 - вищезгадана стаття від RPG. Добре показує застосування DField.