By Нове рішення старої проблеми геометрії рисунка. Коло 60 років тому інфоматематичка Рут Вайс із BellLabs опублікувала піонерський алгоритм перетворення тривимірних обʼєктів, бачених під будь-яким кутом, у двовимірні рисунки. Однак вона наштовхнулася на проблему, повʼязану з представленням контурів, яка давно вже була загадкою обчислювальної геометрії. Ця так звана проблема прихованих ліній стала пекучою з огляду на поширення компʼютерної анімації – пише Лінді Чьоу у часописі Scientific American.
Найважчою частиною рендерингу моделі 3D в образ 2D – ключового кроку в компʼютерній анімації – є проста на перший погляд справа представлення контуру, тобто обводу обʼєкту 3D в 2D. В ідеальному світі контур можна визначити із нескінченною точністю, але реальність вимагає скінченних величин. Тож сучасні алгоритми починають від покриття моделі 3D мережею маленьких трикутних «плиток» і окреслення того, якою стороною кожна плитка буде обернута до спостерігача. Потім алгоритми використовують ті плитки для утворення фрагментів ліній, що становлять контур. Але в обмеженій анімації ефектом стають хибні, мерехтливі лінії, а науковці не були певні, чому так відбувається.
Виявилося, що неможливо згенерувати достатньо точну мережу трикутників без уникнення такого типу помилки. Як твердить номінований на Оскара за спеціальні ефекти Стівен Ґреблі із Meta Reality Labs: «Здавалось, що при достатньо густій мережі отримання точної видимості контурів буде можливим. На жаль ні, а помилки, котрі у звʼязку з цим виникають, обмежують цілісність нефотореалістичних образів».
Нещодавно на сторінках ACM Transactions on Graphics група інформатички Ченксі Лью з Університету Британської Колумбії запропонувала рішення, яке стосується стабілізації контуру, а не мережі. Збільшуючи 1600-кратно контури згенеровані алгоритмом, Лью зауважила невеликі згини, що спричиняло неправильне перехрещення контурних ліній, а в результаті неможливість ідентифікації розташування плиток щодо спостерігача. «Алгоритм підводив з більшістю поверхонь, з якими я експериментувала» – зауважує Лью.
Дослідники розробили новий алгоритм, котрий спочатку визначає межі форми 3D за допомогою фрагментів ліній, а потім сплющує той приблизний контур до 2D і намагається покрити його середину трикутниками. Скрізь там, де помилково появляється перетинання мережі, алгоритм модифікує фрагмент контура, випростовуючи його або додаючи дрібні частинки ліній. Потім відтворена мережа з виправленим контуром знову проектується на обʼєкт 3D з метою остаточної перевірки видимості.
Інновацією було відкриття того, що проблема міститься в самому контурі. «Раніше не брали до уваги того, що неправильність контурів взагалі є можливою, тому намагалися «лікувати» мерехтіння ліній, тобто прояви, а не причину» – зауважує Лью. «Зі статті випливає, чому попередні рішення не були ефективними» – додає Ґреблі.
