Marching cubes
Marching cubes (крокуючі кубики[1]) — алгоритм комп'ютерної графіки, вперше опублікований SIGGRAPH у 1987 розроблений Лоренсеном та Кляйном,[2] для виділення полігональної сітки ізоповерхні з тривимірного скалярного поля (яке іноді називають вокселями). Еквівалентний двовимірний метод називають алгоритмом marching squares[en].
Застосування цього алгоритму в основному пов'язані з медичними візуалізаціями, такими як комп'ютерна томографія та магнітно-резонасний знімок, та метакулі.
Алгоритм[ред. | ред. код]
Цей алгоритм проходиться по скалярному полю, бере вісім сусідніх точок (формуючи уявний куб), потім визначає які полігони потрібні щоб представити частину ізоповерхні, що проходить крізь цей куб. Потім всі полігони з'єднуються в бажану поверхню.
Це робиться за допомогою створення індексу до обчисленого попередньо масиву з 256 можливих конфігурацій многокутників () всередині куба. Індекси утворюються, якщо брати значення у кожній з восьми точок, як біт у восьмибітному цілому. Якщо скалярне значення більше ніж ізо-значення (значення всередині поверхні), то відповідний біт прирівнюється одиничці, а коли воно менше (ззовні), то встановлюється в нуль. Конкатенація всіх восьми значень і є індексом полігону в масиві можливих конфігурацій.
Потім кожна вершина створених полігонів розміщується у своїй позиції на ребрі куба, яка обраховується за допомогою лінійної інтерполяції двох скалярних значень, що з'єднані тим ребром.
Попередньо обчислений масив з 256 конфігурацій може бути отриманий за допомогою симетричних відображень та поворотів 15 оригінальних випадків. Тим не менш, якщо використовувати лише ці 15 конфігурацій, то отримати суцільну поверхню неможливо.
Градієнт скалярного поля в кожній точці сітки також є нормаллю ізоповерхні, що проходить крізь ту точку. Тому, ми можемо інтерполювати ці нормалі вздовж ребер кожного куба, щоб знайти нормалі згенерованих вершин, що є важливим для освітлення кінцевої моделі.
Патент[ред. | ред. код]
Алгоритм Marching Cubes був основним прикладом бід від патентів на програмне забезпечення, і запатентований незважаючи на доволі очевидне рішення проблеми генерації поверхні. Розроблений подібний алгоритм, названий marching tetrahedra, щоб обійти патент та незначну проблему неоднозначності в деяких конфігураціях. Дія цього патенту закінчилась у 2005, тому зараз можна законно використовувати алгоритм без патентних відрахувань. (June 5, 1985[3]).
Зноски[ред. | ред. код]
- ↑ Переклад терміну запропоновано науковим керівником курсової роботи на цю тему, тому думаю варто його впровадити.
- ↑ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
- ↑ Marching Cubes, US Patent Office entry
Посилання[ред. | ред. код]
- Overview and source code by Paul Bourke
- GameDev overview by Matthew Ward of Worcester Polytechnic Institute
- Introductory description with additional graphics [Архівовано 18 серпня 2019 у Wayback Machine.]
- Some of the early history of Marching Cubes [Архівовано 27 травня 2019 у Wayback Machine.]
- Timothy S. Newman and Hong Yia. Marching Cubes survey article.