CPU vs GPU. Distance field

Привіт всім. Я вже якось писав про Distance Field, і приводив реалізацію «евристичним» кодом дає непогану швидкість: habrahabr.ru/post/186482/

Навіщо він потрібен?

DField можна застосовувати:
  • Для значного підвищення якості шрифтів
  • Для ефектів наприклад горіння контуру. Один з ефектів я наводив у своїй попередній статті
  • Для ефекту «metaballs» але в 2д і для будь-яких складних шейп. (можливо я коли-небудь приведу приклад реалізації цього ефекту)
  • А в даний момент DField мені потрібен для якісного згладжування кутів і видалення дрібних деталей.
І якщо в перших двох випадках ми можемо заздалегідь обчислити DField, то для інших ефектів нам потрібно прораховувати його в реальному часі.
У статті буде розглянуто найбільш популярний, я б сказав класичний Chamfer distance (CDA) з купою картинок, що пояснюють принцип його роботи, а так само розглянуто двухпроходний алгоритм на GPU.
Обидва алгоритму реалізовані в демонстраційних програмах на FPC.


Chamfer класика на CPU

Сьогодні я хотів би звернути увагу на класичний спосіб розрахунку DField. Погратися можна тут (вихідний код в git-е). У алгоритму є нестабільний назва: chamfer distance algoritm. Цей спосіб вже описував RPG у своєму топіку
Однак там немає пояснень, чому і як працює цей код. Чому виникають похибки, які вони і як їх зменшити.

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


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.