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

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Реута А.В.


ALGORITHM OF SHAPE VISUALIZATION OF 3D OBJECT PRESENTED BY ITS MATRIX MODEL

An algorithm of a space body visualization on base of its matrix model is proposed. The algorithm uses a triangular mesh built from an intermediate voxel model of the body surface. The algorithm uses the Marching cubes approach with the following differences: it considers only voxels of the body surface, fragment of the triangular mesh presented the voxel based on the state of voxel faces, not vertices. The proposed algorithm reduces the total amount of computation and eliminates certain kinds of ambiguity.


Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва: 2016


    Журнал: Вісник Херсонського національного технічного університету


    Наукова стаття на тему 'АЛГОРИТМ ВІЗУАЛІЗАЦІЇ ФОРМИ просторових об'єктів, представлених ЙОГО матричної моделі'

    Текст наукової роботи на тему «Алгоритм візуалізації ФОРМИ просторових об'єктів, представлених ЙОГО матричної моделі»

    ?УДК 515.2: 528.71

    О.В. Реутов

    Дншропетровській нацюнальній ушверсітет iM. Олеся Гончара

    АЛГОРИТМ В1ЗУАЛВАЩ1 ФОРМИ просторова ОБ'СКТА, поданих ЙОГО матричних МОДЕЛЛЮ

    Предложено алгоритм вгзуалгзаці просторова тиа за его дискретних матричних моделлю, Який передбачало побудову пром1жноЧ воксельног модел1 поверхш тша i визначення на І основi підлогу ^ ональног аткі з трикутна гранями. Алгоритм вікорістовуе пiдхiд Marching cubes з Наступний вiдмiнностямі: розглядаються тшькі вокселi поверхт, фрагмент підлогу ^ ональног аткі для Подання вокселя визначаеться станом его граней, а не вершин, что зменшуе ОБСЯГИ Обчислення i усувае співали види неоднозначностi.

    Ключовi слова: геометрична форма, вiзуалiзацiя, матричної моделі, воксельного модель, поверхня просторова про 'єкту, алгоритм Marching cubes, полшональна стка

    А.В. Реутов

    Дніпропетровський національний університет ім. Олеся Гончара

    АЛГОРИТМ ВІЗУАЛІЗАЦІЇ ФОРМИ просторових об'єктів, представлених ЙОГО матричної моделі

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

    Ключові слова: форма, візуалізація, матрична модель, воксельного модель, поверхня просторового об'єкта, алгоритм Marching cubes, полигональная сітка

    O.V. REUTA

    Dnipropetrovsk National University of Oles Honchar

    ALGORITHM OF SHAPE VISUALIZATION OF 3D OBJECT PRESENTED BY ITS MATRIX MODEL

    An algorithm of a space body visualization on base of its matrix model is proposed. The algorithm uses a triangular mesh built from an intermediate voxel model of the body surface. The algorithm uses the Marching cubes approach with the following differences: it considers only voxels of the body surface, fragment of the triangular mesh presented the voxel based on the state of voxel faces, not vertices. The proposed algorithm reduces the total amount of computation and eliminates certain kinds of ambiguity.

    Keywords: shape, visualization, matrix model, voxel model, surface of the space body, Marching cubes algorithm, triangular mesh

    постановка проблеми

    Розв'язання загально! проблеми вдентіфшацп просторова об'екпв за! х фотограмметрічнімі зображеннями (ФЗ) передбачало побудову (синтез) Еталон моделей об'екпв, вдентіфшащя якіх включае реконструкцш моделi дослвджуваного об'єктах за ФЗ, ствставлення реконструйовано! моделi з Еталон для визначення множини кандидата, синтез збережений моделей-кандідапв i сшвставлення сінтезованого зображення з віхвднім ФЗ та Прийняття ршення про результат щентіфжацп. Для матричних моделей, яш складають основу зазначеним тдходу [1], на Данії годину ввдсутш процедури! Х вiзуалiзацil, что унеможлівлюе реалiзацiю останшх двох еташв предложено! схеми.

    Аналiз останшх дослвджень i публжацш

    Одним з дере i найпошірешшіх в наш час алгорітмш вiзуалiзацil Даних, что вікорістовуе воксельш мо ^ е Marching cubes [2], Який знайшов Широке! Застосування в медічнш дiагностіцi, зокрема, в комп'ютернш, магшто-резонанснш та позитрон-емiсiйнiй томографп. Хоча цею алгоритм допускає певнi невізначеностi в побудовi поверхнi дослiджуваного об'єктах, но iснують модіфшацп, якi розв'язують Дану проблему [3]. До ^ м того, яшсть вiзуалiзацil может буті пiдвіщена Шляхом штерполяцп поверхнi в об'емi воксель НЕ трикутна підлогу ^ онами, як в оріпнальному варiантi, а шматками поверхонь іншого порядку [4].

    Незважаючі на шірош можлівосп алгоритму Marching cubes i его модіфжацш, ВШ оперуе iнформацieю, яка е надлишково для Подання поверхш дослiджуваного об'єктах, i НЕ враховуе особливо віхвдніх Даних, за Якими будует его матричної моделі.

    Мета дослщження

    Слiд Розробити алгоритм вiзуалiзацil просторова об'єктах за его матричних моделлю, Який бі враховував особлівосп Подання поверхнi об'єктах в діскретнш формi.

    Основна частина

    Матричної моделі (ММ) просторова об'єктах е ефективного способом Опису его геометрично! форми для задач аналiзу i реконструкці [1]. ММ будует на основi габаритного контейнера (ГК) i сшввщносіться з воксельного моделлю (ВМ) об'єктах, як показано на рис. 1, а. Вона складаеться з шести

    матриць рельєфу Mp, p = 0,5 (далi просто "матриць"). На рис. 1, б показаша! Х фрагменти та порядок

    формирование iндексiв. Значення елементiв матриць е ввдсташ м1ж вiдповiдно гранями вокселiв ВМ i поверхнею ГК [1]. Далi розглядаються лишь вокселі у формi прямокутна паралелепiпеда, орiентацiя

    граней Fp, p = 0,5 окремий воксель ствпадае з орiентацiею граней ГК i показана на рис. 1, в.

    а Б В)

    Мал. 1. Спшввдношення ВМ просторова об'єктах та его ММ

    Введемо наступш визначення. Вважаемо, что грань воксель eidKpuma, если вона Належить тiльки Йому i НЕ подiляеться з будь-Якім сусвдшм воксель. Наявнiсть ввдкрітіх граней у воксель зумовлюе, что для него юнуе Подання прінаймнi на однш матріцi ММ у виглядi li елемента. Вокселi без вщкрітіх граней це має належати поверхнi об'єктах i тому iгноруються ММ.

    Осшлькі для визначення вокселя у просторi достаточно тiльки одше! матріцi ММ з вщповвднім Йому елементом, то травні мюце Певна надмiрнiсть шформацп у матричному поданнi просторова об'єктах, яка, однак, загаль НЕ Робить ММ Менш економна у порiвняннi з ВМ [5]. Надалi воксел ^ поданi бiльш нiж на однш матриць ММ, назвемо надлишково, на ввдшну вiд базових, для визначення якіх в ММ томиться тшькі одна матриця.

    Як приклад, на рис. 2 показань фрагмент ВМ тора (рис. 1, а), на якому темним кольори відшеш воксел ^ положення якіх может буті визначене за матрицею M q (рис. 2, а), одночасно за матрицею M qi M4 (рис. 2, б) , одночасно за матрицею M q, M 4 i M2 (рис. 2, в) та одночасно матриці Mq, M 4, M2 i M 3 (рис. 2, г). Видно, что, як i позначають, для шкірного з відшеніх вокселiв шльшсть матриць, за Якими может буті визначене его положення у простір ^ зумовлюється кшьшстю в1дкрітіх граней.

    а Б В Г)

    Мал. 2. Фрагмент воксельноК модел1 тора i3 надлишково воксель

    Если мiрою надлішковостi вокселя вважаті число на 1 менше за кшьшсть матриць, за Якими ВШ визначаеться, або его вщкрітіх граней, то вокселi, відiленi на рис. 2, г ма ють надлішковють 3, на рис. 2, в до них додали вокселi з надлішковютю 2, а на рис. 2, б - ще й п, что ма ють надлішковють 1. На рис. 2, а, до вах зазначеним Дода ще базовi вокселi, положення якіх визначаеться плькі за M q .

    Врахування надлішковосп вокселiв дае можливiсть Вилучити з аналiзу neBHi елементи матриць, скорочуючі тім самим годину реконструкцп форми об'єктах.

    Розглянемо процес вiзуалiзацii просторова об'єктах, поданого своєю ММ. В основу его покладаючи щдхвд, запропонованій в алгоритм Marching cubes (MC), перевага которого е незалежна обробка шкірного елемента моделi об'єктах, простота создания натовпів-онального! сiткі з трикутна граней для Подання его поверхнi, а такоже наявнiсть ефективних реалiзацiй [2 - 4].

    Процес передбачало наступи кроки.

    1 °. Вибiр матріцi ММ.

    2 °. Вибiр елемента звертаючись! матріщ.

    3 °. Визначення вокселя, что ввдповщае обраних елементів.

    4 °. Визначення стану граней вокселя: вщкріта або закрита.

    5 °. Визначення елементiв iнших матриць, что подаються Розглянуто воксель, i вилучення! Х з Подальшого РОЗГЛЯДУ.

    6 °. Створення шдексу на основi комбiнацii сташв граней вокселя.

    7 °. Вибiр iз табліцi варiантiв за отриманий Iндекс конфiгурацii, яка спiвставляе воксель фрагмент натовпів-онального! сiткі, склад! з трикутна граней.

    8 °. Вибiр следующего елемента звертаючись! матріцi i Виконання для него крошв 3 ° - 7 °, поки всi елементи звертаючись! матріщ НЕ БУДУТЬ оглянутi.

    9 °. Вибiр Наступний! матріцi i Виконання для нє! крошв 2 ° - 8 °, поки вс матріщ ММ Чи не будуть озирнутися

    10 °. Визначення поверхш просторова тша Шляхом об'єднання отриманий на попереднiх кроках фрагментiв сггкі.

    Розглянемо кроки запропонованого алгоритму бшьш детально.

    Вибiр матріцi, як i вибiр елемента в матріцi, (кроки 1 ° i 2 °, вiдповiдно) віконуеться в порядку зростання вiдповiдно iндексiв p - для матриць, i, j - для! Х елементiв. Дiапазоні змiни iндексiв i та j залежався вiд розмiрностi звертаючись! на даного кроцi матріщ i визначаються нижчих (див. такоже табл. 1).

    Розглянемо, Яким чином здшснюеться визначення координат вокселя, что вщповвдае Певна елементи ММ (крок 3 °). Зазначімо, что в робот [6] розв'язується оберніть завдання, коли за координатами точки простору (x, y, z) визначаються Iндекс матріщ ММ. ГК е паралелетпедом, что визначаеться площинах

    х = Xmin, х = Xmax, y = Ymin, y = Ymax, z = Zmin, z = Zmax. (1)

    Кожний воксель визначаеться координатами центру (хс, yc, zc) i травні лшшш розмiру вздовж вiдповiдно осей координат Ах, Ay i Az. Координати его вершин е комбшащямі віразiв:

    Xc ± A xl 2, Ус ± Ay j 2, Zc ± A J 2. (2)

    Вщповвдно до цього, розмiрностi матриць ММ визначаються як:

    N = (Xmax - Xmm VAx, И = (Ymax - ^ mm) / Ay i K = (Zmax - ^ m) / Az. (3)

    Елементи матриць ММ задають положення вокселiв ВМ у просторi (рис. 1). Спiввiдношення, як дозволяють за Певної елементом mp [i, j] матріцi Mp, p = 0,5 візначіті положення вiдповiдно вокселя v (xc, yc, zc), наведе у табл. 1.

    Таблиця 1

    Визначення координат (xc, yc, zc) вокселя v за елементом mp [i, j] матріщ M p

    Мат-ріця Розмiрнiсть матріцi Координати вокселя v

    xc Ус zc

    M про КуИ Xmax - (m0 k j] + V2) AX Ymn + (j + 1/2) A y Zmax - (i + 1/2) Az

    M! KxN Xmax - (j + 1/2) Ax Ymax - (m1 [i, j] + V2) Ay Zmax - (j + 1/2) Az

    M 2 MyN X min + (j + 1/2) A x Ymax - (j + 1/2) Ay Zmax - (m2 k j] + V2) Az

    M 3 КуИ Xmin + (m3 ^ j] + V2) Ax Ymax - (j + 1/2) Ay Zmax - (i + 1/2) Az

    M 4 KyN X min + (j + 1/2) A x Ymin + (m4 ^ j] + V2) Ay Zmax - (i + 1/2) Az

    M 5 MyN Xmax - (j + 1/2) Ax Ymax - (i + 1/2) Ay Zmin + (m5 ^ j] + V2) Az

    Визначення стану граней вокселя (крок 4 °) здшснюеться Шляхом аналiзу оточення ввдповвдного елемента матриця Мета аналiзу - з'ясувагі, чи е воксель базовим i если ш, го якi его Гранi е ввдкрітімі.

    Факт того, что елемент матріщ визначавши базовий воксель, Встановлюється за виконання умов:

    mp ^ j]> mp [i, j +1],

    mp [i, j]> mp [i, j -1],

    mp ^ j]> mp [i +1, j], mp ^ j]> mp [i -1, j],

    (5)

    де p = 0,5; i = 1, K i j = 1, M для p = 0 або p = 3; i = 1, K i j = 1, N для p = 1 або p = 4; i = 1, M i j = 1, N для p = 2 або p = 5 .

    А також умів, записаних окремо для кожного значення p = 0,5:

    для p = 0: mo [i, j]< N - m3 [i, M - j -1], де i = 1, K i j = 1, M,

    для p = 1: m1 [i, j]<M - m4 [i, N - j -1], де i = 1, K i j = 1, N,

    для p = 2: m2 [i, j]< K - m5 [i, N - j - 1], де i = 1, M i j = 1, N ,

    для p = 3: m3 [i, j]< N - m0 [i, M - j -1], де i = 1, K i j = 1, M,

    для p = 4: m4 [i, j] <M - m1 [i, N - j -1], де i = 1, K i j = 1, N ,

    для p = 5: m5 [i, j]< K - m3 [i, N - j -1], де i = 1, M i j = 1, N .

    Зазначімо, что умови (4) для кожного p = 0,5 могут Виконувати б або не Виконувати Незалежності одна вщ одно1 i невиконання будь-яко1 з них додають воксель, что визначаеться елементом mp [i, j], ще одну ввдкріту грань, сумiжну до граш Fp. Якщо не віконуеться Умова (5), тобто вщповщна

    нерiвнiсть перетворюеться на рiвнiсть (шшій випадок означае Порушення цшсносп ВМ [7]), тодi воксель травні вщкріту грань протилежних до граш Fp.

    Як було зазначилися, один i той самий воксель может буті визначеня за двома i бшьше матриці (рис. 2). Тому, щоб запобкті дублюванню вокселя при его візначенш за одшею з матриць, слщ проаналiзуваті iншi матріщ, i ri ix елементи, яш так само визначаються Сейчас воксель, віключіті з Подальшого РОЗГЛЯДУ (крок 5 °). Розглянемо Цю процедуру детальнше.

    Если через Порушення будь-яюн з умов (4) або (5) встановлен, что воксель не базовою, то слщ з'ясувати, чи е ВШ надлишково, тобто яш елементи якіх матриць такоже визначаються его, ^ м елемента, что розглядаеться на Данії момент. Таю елементи, если смороду будут знайдеш, необхщно Вилучити з Подальшого РОЗГЛЯДУ, например, пам'ятаю 1х у вщповщніх матриці як озирнутися

    Для визначення того, чи е не базовою воксель надлишково, змшімо умови (4) Наступний чином:

    mp ^ j]> mp ^ j + k],

    mp [i, j]> mp [i, j - k],

    (6)

    mp ^ j]> mp [i + k, j],

    mp [i, j]> mp [i - k, j],

    де до > 0 .

    Тодi воксель, визначених за елементом [i, j], буде надлишково, если при невіконанш першо1 умови (4) перша нерiвнiсть (6) віконуеться для вах к = 1, Кр, де ^ 0 = ^ 3 = M, К1 = К2 = К4 = К5 = N; при невіконанш другоi умови (4) одного нерiвнiсть (6) віконуеться для вах к = 1, j; при невіконанш

    третьоi умови (4) третя нерiвнiсть (6) віконуеться для всix к = 1, К p, де К0 = К = ^ 3 = ^ 4 = K,

    К2 = К5 = M; а при невіконанш останньоi умови (4) остання нерiвнiсгь (6) віконуеться для вах к = 1, i.

    Значення p, для которого за Порушення певноi умови (4) віконуеться вщповвдна ш нерiвнiсть (6), дае можлівють НЕ тшькі візначіті матрицю з надлишково шформащею про воксель, что розглядаеться, а й

    з'ясувати, Який самє ii елемент Цю шформацш мiстить. Нижчих вказанi такi елементи, візначенi за

    V [

    елементом шр [i, j] для Певного p при невіконанш умів (4), вiдповiдно:

    - при p = 0:

    - при p = 1:

    - при p = 2

    - при p = 3

    - при p = 4

    та

    m1 [i, mQ & j]], m4 [i, N - mQ [i, j] - 1], m5 [M - j - 1 mQ j]] m2 [M - j - 1, N - mQ [i, j] -1] ;

    тз [i, m1 [i, j]], mQ [i, M - m ^ [i, j] - 1], m5 Ц [i, j] j] та m2 Ц [i, j] N - j - 1]; mQ [m2 [i, j], M - i - 1], m3 [m2 [i, j], i], m4 [i, m2 [i, j]] та m ^ [i, j], N - j -1];

    m4 [i, m3k j]], m1 N - m3j] - 1], m5 [j N - m3k j] - 1] та m2 [j m3 ^ j]]; mQ [i, m4 [i, j]], m3 [i, M - m4 [i, j] -1], m5 [M - m4 [i, j] -1, N - j -1] та m2 [ M - m4 [i, j] -1, j];

    - при p = 5: m3 [K - m5 [i, j] -1, i], mQ [K - m5 [i, j] - 1, M - i -1],

    m4 [N - i -1, K - m2 [i, j] -1] та m1 [K - m5 [i, j] -1, j]. Як позначають, елементи, что мютять надлишково iнформацiя, ма ють буті віключеш з Подальшого РОЗГЛЯДУ як для заощадження ресурсiв процесса аналiзу, так i для запобiгання дублюванню вокселiв.

    Коли стани граней вокселя візначеш (крок 4 °), з'являється можливiсть создания Iндекс (крок 6 °), Який дасть можлівють вібрато варiант Подання вокселя фрагментом поліюнально! сiткі, склад! з трикутна граней. Цей крок е модіфжащею такого в алгорітмi МС. Основна ввдмшшсть полягае в тому, что в оріпнальному алгорітмi аналiзуеться стан вершин вокселя (стан вершини означае, чи Належить вершина

    8

    внутршнш чи зовнiшнiй областi, тобто розташована в межах просторово об'єктах чи ш), что дае 2 = 256 варiантiв конфiгурацiй поліюнально! сiткі, з якіх з урахуванням сіметрil залиша тiльки 15 віпадшв (cases - в термiнологil МС) [2, 3]. В алгоритм ^ что пропонуеться, враховуеться стан граней вокселя, что в загально випадка зумовлюе 26 = 64 варiантiв. Мiж тім, оскiльки ММ просторова об'єктах за самим способом своє! Побудова визначавши лишь зв'язного ВМ, то прінаймш одна грань шкірного вокселя травні буті закритою. Таким чином, лишь 5 граней могут буті ввдкрітімі, что зменшуе Загальну кшьшсть варiантiв до 25 = 32, а з урахуванням симетрії! Х лішаеться лишь 8 (что почти вдвiчi менше, нiж в алгорштш МС). Цi варiанті разом з прикладами ввдкрітіх граней показанi на рис. 3 (граш позначенi за рис. 1, в).

    Fq f2f 3 Варiант 4

    Fq F1F2 F 3 Варiант 6

    FqF 2 F3 F 5 Варiант 7

    Мал. 3. Ввдкріп гран1 вокселя (відалет темним): можлів1 вар1анті з урахуванням симетрії

    Таким чином, значення шдексу обіраеться iз дiапазону 1 - 8, в залежносп в1д варiанту Розташування Вiдкрите граней у вокселя, что розглядаеться.

    Наступний крок (крок 7 °) передбачало вибiр конфiгурацil трикутна граней полiгональноl сггкі, что подати фрагмент поверхнi, якш вiдповiдае Сейчас воксель.

    Алгоритм МС пропонуе випадки 0 - 2, 8 та 9 (рис. 4) як найбліжчi аналоги для варiантiв, что вінікають в алгорітмi, что розглядаеться (рис. 3). На рис. 4 для віпадшв 1 та 9 граш поліюнально! стки показаша тд рiзнімі кутамі: спершись ^ ВШЕ) так, что смороду повнiстю вщповвдають Певна варiанту Розташування Вiдкрите граней, показання на рис. 3, а попм (правiше) бiльш наочно. Лiве зображення випадки 8 на рис. 4 вщповвдае варiанту 2 (рис. 3), а праві - варiанту 8 (рис. 3).

    Мал. 4. Конф1гураці фрагменпв пол1гонально1 с1ткі в алгоритм! Marching cubes, "найбліжчГ 'до вар1антш запропонованого алгоритму (рис. 3)

    Загаль можна Зазначити, что у варiантах 2, 4, 6 - 8 (рис. 3) ва вершини вокселя належати вщкрітім гранях. У алгоршш MC всiм! М вiдповiдае один випадок Q (рис. 4). Варiант 5 на рис. 3 з точки зору алгоритму MC можна штерпретуваті двома випадки 1 i 9 (рис. 4). Варiанту 1 (рис. 3) ввдповщае

    випадок 8 (рис. 4) алгоритму МС. Так само можна трактуваті i варiант 8 (рис. 3), хоча, як позначають вищє, Йому такоже пiдходіть випадок 0 (рис. 4). Однозначно штерпретуеться плькі варiант 3 (рис. 3) - Йому вiдповiдае випадок 2 (рис. 4) алгоритму МС. Таким чином, можна констатуваті, что схема вiзуалiзацii, прийнятя в алгорітмi МС, які не вщповщае Вимоги запропонованого підходу i травні буті змiнена.

    Пропонуеться скористати конф ^ ращямі натовпів-онального! сiткі, показання на рис. 5, яш однозначно вщповвдають варiантам конфiгурацiй Вiдкрите граней (рис. 3).

    Мал. 5. ВарЬпмі конф1гурацш фрагменпв підлогу ^ ональноТ аткі для Подання воксел1в з в1дкрітімі гранями (рис. 3)

    Безпосередно использование запропонованіх конфпурацш (рис. 5) может віклікаті змші в станах граней вокселiв, что оточують воксель, Який замiнюеться конф ^ ращею. Це вiдбуваеться для тих варiантiв, в якіх присутности хоч одна закрита грань вокселя, яка при замш вокселя фрагментом підлогу ^ ональних! стки перетінаеться ребром і трикутна! Гранi. Така грань зграї частково Вiдкрите, при тому что iншi гран свого стану НЕ змiнюють. Порiвнюючі рис. 3 i 5, візначімо так варiанті i! Х закріп Гранi, что стають частково вщкрітімі: варiант 3 - Гранi F2, F5; варiант 4 - Гранi F [, F4; варiант 5 - Гранi F5, F4 i варiант 6 - грань F4. Для ціх варiантiв слiд переглянутi сусiднi воксел ^ что роздiляють зазначенi Гранi, i, онов! Х стан, вібрато шшій варiант конф ^ рацп Вiдкрите граней, включаючи в! Х перелiк Гранi, что стали частково вщкрітімі.

    Кроки 8 ° i 9 ° запропонованого алгоритму очевідш, крок 10 ° Вимагаю Додатковий пояснень. Множини вокселiв, что вібіраються на крощ 3 °, утворюе ВМ поверхш просторова об'єктах. Замiна! Х ввдповщнімі фрагментами натовпів-онального! сiткі (крок 7 °) автоматично виробляти до з'явиться каркасно! моделi об'єктах у виглядi натовпів-онального! сiткі з трикутна гранями, что i е результатом роботи алгоритму. При цьом зауважімо, что кшьшсть вершин сiткі, ЯК-1 слiд візначіті Шляхом обчислення, суттево менше, н1ж в сiтцi, побудованiй за алгоритмом МС. Це пов'язане iз тім, что останнш призначення для побудова iзометрічноl поверхнi, яка НЕ ​​может включать вершини вокселiв, i, таким чином, шкірні вершина сiткі винна окремо розраховуватісь (рис. 4). У тій же година, запропонованій алгоритм такого обмеження НЕ травні i бшьшють вершин сiткі в ньом обіраеться з наперед визначених вершин вокселiв (2). Так, з УАХ вершин трикутна граней (рис. 5) тшькі 5 з 43 (что Складанний 11,6%) вімагають окремий обчислення.

    Висновки

    Запропонованій алгоритм вiзуалiзацil, розв'язуючі подане завдання, травні наступнi Переваги, порiвняно з вiдомімі алгоритмами на основi МС: враховуеться факт вiзуалiзацii поверхнi, что зменшуе ОБСЯГИ промiжніх Даних; усуваються неоднозначностi; скорочуеться процес обчислення.

    Список вікорістаноТ л1тературі

    1. Реута О.В. Матричний дискретна модель трівімiрного тiла для задачi аналiзу его тiнеутворення / О.В. Реута // геометричність та комп'ютерне моделювання.-Х .: ХДУХТ, 2009. - Вип. 25. -С.68-72.

    2. Lorensen W.E. Marching cubes: a high resolution 3D surface construction algorithm / W.E. Lorensen, H.E. Cline // SIGGRAPH. - 1987. - Vol. 21 (4). - P. 163-169.

    3. Charles D. Hansen. The Visualization Handbook / Charles D. Hansen, Chris R. Johnson. - Elsevier Inc., 2005. - 982 p.

    4. Lopes and K. Brodlie. Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing / Lopes and K. Brodlie // IEEE Transactions on Visualization and Computer Graphics. - 2003. -Vol. 9. - № 1. - P. 16-29,

    5. Реута О.В. Порiвняння матрично! i воксельного! моделей трівімiрного тша для задач его реконструкцп / О.В. Реута // Прикладна геометрiя та iнженерна графжа. - К .: КНУБА, 2009. - Вип. 82. - С. 203-207.

    6. Реута О.В. Взаємозв'язок мiж матричних моделлю трівімiрного об'єктах та моделлю на основi R-функцш / О.В. Реута // пращі Тавршського державного агротехшчного ушверсітету. Прикладна геометрiя та шженерна графша - Меліополь: ТДАТУ, 2010. - Вип. 4. - Т. 46. - С. 99-104.

    7. Реута О.В. Контроль i ввдновлення цшсносп дискретних моделей трівімiрніх об'екпв в задачах реконструкцп форми / О.В. Реута // Прикладна геометрiя та iнженерна графжа. - К .: КНУБА, 2011. - Вип. 88. - С. 278-282.


    Ключові слова: ФОРМА /SHAPE /ВІЗУАЛІЗАЦІЯ /VISUALIZATION /МАТРИЧНА МОДЕЛЬ /MATRIX MODEL /воксельного МОДЕЛЬ /VOXEL MODEL /Поверхность просторових ОБ'ЄКТА /SURFACE OF THE SPACE BODY /АЛГОРИТМ MARCHING CUBES /MARCHING CUBES ALGORITHM /полігональна Сітка /TRIANGULAR MESH

    Завантажити оригінал статті:

    Завантажити