Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Маршируючі кубики

with 3 comments

Як я і обіцяв – вечірній звіт. З першими фотографіями.

План не виконано. Я ще не до кінця вмію писати скрипти до Блендера. Винен звісно не я, а кривий інтерпретатор 😉 . Самі гляньте:

інтерпретатор

інтерпретатор

Ну, тим не менш, не все так безнадійно. Зате я більш-менш розібрався з інтерфейсом Блендера. Він справді спочатку виглядає як панель приладів у літака. Зате, все під рукою. А до розташування кнопок можна швидко звикнути. Або розставити їх як вам зручніше. Принаймі ніяк не гірше ніж 3ds Max, а враховуючи те, що на повну використовуються всі три кнопки миші, то навіть краще (aaa Autodesk, не вбивайте мене). Тому, за день поклацування, з паралельним гортанням blender3d.org.ua можна розібратись:

перші експерименти

перші експерименти

Можна навіть робити більш-менш людські зображення (земля, до речі, згенерована скриптом Python, що поширюється з програмою):

Нічний будиночок

Нічний будиночок

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

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

Marching cubes

Матеріал з Вікіпедії

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

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

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

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

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

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

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

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

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

Патент

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

Зноски

  1. William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
  2. Marching Cubes, US Patent Office entry

Посилання

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

Далі піду спати, аби завтра таки написати скрипт.

Advertisements

Written by bunyk

Травень 3, 2010 at 23:33

Відповідей: 3

Subscribe to comments with RSS.

  1. Фух! Те, що патент закінчився в 2005-му, ДУЖЕ добре… Бунику, у мене виникли емоції %)

    P.S. Бібліографічні посилання на інтернет-ресурси http://juick.com/johan/616840

    ulidtko

    Травень 4, 2010 at 13:38

  2. Емоції від заголовку розділу? Хах, в мене теж. Він ще в англійській версії статті взагалі називався “Patent issues”, я навіть не здогадався як це перекласти.

    bunyk

    Травень 4, 2010 at 17:59

    • ну, наприклад, «Проблеми з патентами»

      ulidtko

      Травень 4, 2010 at 18:13


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: