Marching cubes

Marching cubes (крокуючі кубики) — алгоритм комп'ютерної графіки, вперше опублікований SIGGRAPH у 1987 розроблений Лоренсеном та Кляйном, для виділення полігональної сітки ізоповерхні з тривимірного скалярного поля (яке іноді називають вокселями). Еквівалентний двовимірний метод називають алгоритмом ^[en].

Голова зроблена з 150 магнітно-резонансних знімків перероблених алгоритмом marching cubes (близько 150 000 трикутників)

Застосування цього алгоритму в основному пов'язані з медичними візуалізаціями, такими як комп'ютерна томографія та магнітно-резонасний знімок, та метакулі.

Алгоритм

Цей алгоритм проходиться по скалярному полю, бере вісім сусідніх точок (формуючи уявний куб), потім визначає які полігони потрібні щоб представити частину ізоповерхні, що проходить крізь цей куб. Потім всі полігони з'єднуються в бажану поверхню.

Це робиться за допомогою створення індексу до обчисленого попередньо масиву з 256 можливих конфігурацій многокутників (${\displaystyle 2^{8}=256}$) всередині куба. Індекси утворюються, якщо брати значення у кожній з восьми точок, як біт у восьмибітному цілому. Якщо скалярне значення більше ніж ізо-значення (значення всередині поверхні), то відповідний біт прирівнюється одиничці, а коли воно менше (ззовні), то встановлюється в нуль. Конкатенація всіх восьми значень і є індексом полігону в масиві можливих конфігурацій.

Потім кожна вершина створених полігонів розміщується у своїй позиції на ребрі куба, яка обраховується за допомогою лінійної інтерполяції двох скалярних значень, що з'єднані тим ребром.

15 унікальних конфігурацій куба

Попередньо обчислений масив з 256 конфігурацій може бути отриманий за допомогою симетричних відображень та поворотів 15 оригінальних випадків. Тим не менш, якщо використовувати лише ці 15 конфігурацій, то отримати суцільну поверхню неможливо.

Градієнт скалярного поля в кожній точці сітки також є нормаллю ізоповерхні, що проходить крізь ту точку. Тому, ми можемо інтерполювати ці нормалі вздовж ребер кожного куба, щоб знайти нормалі згенерованих вершин, що є важливим для освітлення кінцевої моделі.

Патент

Алгоритм Marching Cubes був основним прикладом бід від патентів на програмне забезпечення, і запатентований незважаючи на доволі очевидне рішення проблеми генерації поверхні. Розроблений подібний алгоритм, названий , щоб обійти патент та незначну проблему неоднозначності в деяких конфігураціях. Дія цього патенту закінчилась у 2005, тому зараз можна законно використовувати алгоритм без патентних відрахувань. (June 5, 1985).

Зноски

1. Переклад терміну запропоновано науковим керівником курсової роботи на цю тему, тому думаю варто його впровадити.
2. William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
3. Marching Cubes, US Patent Office entry

Посилання

• 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. .