Marching cubes

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Голова зроблена з 150 магнітно-резонансних знімків перероблених алгоритмом marching cubes (близько 150 000 трикутників)

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

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

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

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

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

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

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

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

Патент[ред.ред. код]

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

Зноски[ред.ред. код]

  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

Посилання[ред.ред. код]