CPU vs GPU. Distance field

CPU vs GPU. Distance field

Привіт усім. Я вже одного разу писав про 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, якщо алгоритми це дозволяють.

Посилання на тему

  1. net/projects/dfsamples Власне приклади до статті. Бінарники і вихідці.
  2. springer.com/cda/content/document/cda_downloaddocument/9780387312019-c1.pdf - відмінний розбір як Chamfer алгоритму, так і його модифікацій. Порівняння похибки і часу виконання.
  3. valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf - Застосування DField у рендері шрифтів. Мабуть найвідоміша стаття.
  4. ru/post/215905 - вищезгадана стаття від RPG. Добре показує застосування DField.
Image