Сітка з трикутників — це тип полігональної сітки, яка використовується у комп'ютерній графіці. Вона включає в себе набір трикутників (як правило, в тривимірному просторі), які мають спільні ребра або вершини.
Багато графічних програмних пакетів і апаратних пристроїв можуть працювати більш ефективно з трикутниками, які згруповані в сітку, аніж коли опрацьовуються окремо. Це пов'язано з тим, що застосунки в комп'ютерній графіці виконують операції над спільними вершинами трикутників. У випадку окремих трикутників, система повинна опрацювати три вершини для кожного трикутника. Велика сітка може налічувати вісім або й більшу кількість трикутників, які мають спільну вершину — завдяки обробці однієї такої вершини лишень за один раз можна виконати частину роботи і досягти такого ж ефекту, як і при обробці вершин окремо. Багато застосунків комп'ютерної графіки використовують сітку з трикутників. Складовими сітки є вершини, ребра і трикутники. При виконанні застосунку може знадобитися знання різних з'єднань між компонентами сітки. Ці сполуки можуть оброблятись незалежно від фактичних координат вершин. Використовуються різні структури даних, вибір яких залежить від типу операцій над сіткою.
Представлення
Можливі різні методи зберігання та роботи з сіткою в комп'ютерній пам'яті. В OpenGL і DirectX API існує два основних способи проходження сітки з трикутників за допомогою графічного апаратного забезпечення: [en] і індексація масивів.
Смуга з трикутників
Один із способів спільного використання даних про вершини між трикутниками є [en]. У смузі з трикутників кожен трикутник ділиться на одну повну грань з однією сусідньою і іншою із наступної. Іншим способом є віяло трикутників, яке представляє собою набір з'єднаних трикутників, які мають спільну центральну вершину. За допомогою цих методів вершини опрацьовуються ефективно, що призводить до необхідності обробляти лише N + 2 вершин, щоб намалювати N трикутників.
Смуги з трикутників є ефективними, проте недоліком є те, що не може бути тривіальним факт, яким чином зручно переводити довільну сітку з трикутників в смуги.
Структура даних
Структура даних, що представляє сітку, забезпечує підтримку двох основних операцій: вставки і видалення трикутників. Він також підтримує операцію руйнування грані, яка буде корисна в схемах проріджування трикутників. Структура не забезпечує підтримку позиції вершин, передбачається, що кожній вершині присвоюється унікальний цілочисельний ідентифікатор, як правило, індекс цієї вершини в масиві суміжних позицій вершин. Сітка з вершин визначається одним цілим числом і позначається як hvi. Сітка з граней визначається парою цілих чисел hv0,v1i, кожне є цілим числом, відповідним кінцевій точці ребра. Для формування відображення граней, грані зберігаються так, що v0 = min(v0,v1). Компонент трикутник визначається трійкою цілих чисел hv0,v1,v2i, кожне — ціле число, відповідне вершині трикутника. Для підтримки відображень трикутників, трикутники зберігаються так, що v0 = min(v0,v1,v2). Зауважимо, що hv0,v1,v2i та hv0,v2,v1i розглядаються як різні трикутники. В додаток двостороння трикутників, через що необхідно вставити обидві трійки в структуру даних. Заради уникнення постійних нагадувань щодо порядку індексів пари/трійки в іншій частині документа інформація не означає, що вершини впорядковані будь-яким чином (хоча реалізація обробляє порядок).
Зв'язок між компонентами повністю залежить від трійок, що представляють трикутники. Трикутник t = hv0,v1,v2i має вершини v0, v1, та v2. Йому належать грані e0 = hv0,v1i, e1 = hv1,v2i, та e2 = hv2,v0i. Відомі також зворотні зв'язки. Вершина v0 примикає до ребер е0 і е2 і до трикутнику t. Вершина v1 примикає до ребер e0 і e1 і до трикутнику t. Вершина v2 примикає до ребер e1 і e2 і до трикутнику t. Усі три грані e0, e1, e2 примикають до t.
Кількість інформації, що зберігається, в структурі даних залежить від потреб програми. Крім того, додаток може потребувати додаткової інформації, що зберігається в компонентах. Інформація, що зберігається в вершині, грані або трикутнику, називається атрибутом вершини, ребра або атрибут трикутника. Їх абстрактне представлення для простої структури даних, описані тут
Vertex = <integer>; // v Edge = <integer,integer>; // v0, v1 Triangle <integer,integer,integer>; // v0, v1, v2 VData = <application-specific vertex data>; EData = <application-specific edge data>; TData = <application-specific triangle data>; VAttribute = <VData,set<Edge>,set<Triangle>>; // data, eset, tset EAttribute = <EData,set<Triangle>>; // data, tset TAttribute = <TData>; // data VPair = pair<Vertex,VAttribute>; EPair = pair<Edge,EAttribute>; TPair = pair<Triangle,TAttribute>; VMap = map<VPair>; EMap = map<EPair>; TMap = map<TPair>; Mesh = <VMap,EMap,TMap>; // vmap, emap, tmap
Відображення підтримують стандартні функції вставки і видалення для хеш-таблиці. Вставка відбувається тільки якщо деталь вже не існує. Видалення відбувається тільки тоді, коли деталь існує.
Руйнування грані
Ця операція включає в себе визначення ребра hvk, vti, де vk називається зберігаючою вершиною, vt — направляючою. Трикутники, які містять ребро, видаляються з сітки. Вершина vt також видаляється з сітки. Спільна для будь-яких трикутників вершина vt буде замінена на vk.
Індексація масиву
За допомогою індексації масивів, сітка представлена двома окремими масивами: один масив містить вершини, а інший зберігає набори з трьох індексів в цьому масиві, які визначають трикутник. Графічна система обробляє вершини першого масиву і потім робить трикутники, використовуючи набори індексів, які працюють на перетворених даних.
Див. також
- Полігональна сітка
- [en]
- Неоднорідний раціональний B-сплайн
- Хмара точок
- [en] для променів трикутнику перетину
- Гіперграф
Це незавершена стаття про комп'ютерну графіку. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Sitka z trikutnikiv ce tip poligonalnoyi sitki yaka vikoristovuyetsya u komp yuternij grafici Vona vklyuchaye v sebe nabir trikutnikiv yak pravilo v trivimirnomu prostori yaki mayut spilni rebra abo vershini Model delfina stvorena za dopomogoyu sitki z trikutnikiv Bagato grafichnih programnih paketiv i aparatnih pristroyiv mozhut pracyuvati bilsh efektivno z trikutnikami yaki zgrupovani v sitku anizh koli opracovuyutsya okremo Ce pov yazano z tim sho zastosunki v komp yuternij grafici vikonuyut operaciyi nad spilnimi vershinami trikutnikiv U vipadku okremih trikutnikiv sistema povinna opracyuvati tri vershini dlya kozhnogo trikutnika Velika sitka mozhe nalichuvati visim abo j bilshu kilkist trikutnikiv yaki mayut spilnu vershinu zavdyaki obrobci odniyeyi takoyi vershini lishen za odin raz mozhna vikonati chastinu roboti i dosyagti takogo zh efektu yak i pri obrobci vershin okremo Bagato zastosunkiv komp yuternoyi grafiki vikoristovuyut sitku z trikutnikiv Skladovimi sitki ye vershini rebra i trikutniki Pri vikonanni zastosunku mozhe znadobitisya znannya riznih z yednan mizh komponentami sitki Ci spoluki mozhut obroblyatis nezalezhno vid faktichnih koordinat vershin Vikoristovuyutsya rizni strukturi danih vibir yakih zalezhit vid tipu operacij nad sitkoyu PredstavlennyaMozhlivi rizni metodi zberigannya ta roboti z sitkoyu v komp yuternij pam yati V OpenGL i DirectX API isnuye dva osnovnih sposobi prohodzhennya sitki z trikutnikiv za dopomogoyu grafichnogo aparatnogo zabezpechennya en i indeksaciya masiviv Smuga z trikutnikiv Odin iz sposobiv spilnogo vikoristannya danih pro vershini mizh trikutnikami ye en U smuzi z trikutnikiv kozhen trikutnik dilitsya na odnu povnu gran z odniyeyu susidnoyu i inshoyu iz nastupnoyi Inshim sposobom ye viyalo trikutnikiv yake predstavlyaye soboyu nabir z yednanih trikutnikiv yaki mayut spilnu centralnu vershinu Za dopomogoyu cih metodiv vershini opracovuyutsya efektivno sho prizvodit do neobhidnosti obroblyati lishe N 2 vershin shob namalyuvati N trikutnikiv Smugi z trikutnikiv ye efektivnimi prote nedolikom ye te sho ne mozhe buti trivialnim fakt yakim chinom zruchno perevoditi dovilnu sitku z trikutnikiv v smugi Struktura danih Struktura danih sho predstavlyaye sitku zabezpechuye pidtrimku dvoh osnovnih operacij vstavki i vidalennya trikutnikiv Vin takozh pidtrimuye operaciyu rujnuvannya grani yaka bude korisna v shemah proridzhuvannya trikutnikiv Struktura ne zabezpechuye pidtrimku poziciyi vershin peredbachayetsya sho kozhnij vershini prisvoyuyetsya unikalnij cilochiselnij identifikator yak pravilo indeks ciyeyi vershini v masivi sumizhnih pozicij vershin Sitka z vershin viznachayetsya odnim cilim chislom i poznachayetsya yak hvi Sitka z granej viznachayetsya paroyu cilih chisel hv0 v1i kozhne ye cilim chislom vidpovidnim kincevij tochci rebra Dlya formuvannya vidobrazhennya granej grani zberigayutsya tak sho v0 min v0 v1 Komponent trikutnik viznachayetsya trijkoyu cilih chisel hv0 v1 v2i kozhne cile chislo vidpovidne vershini trikutnika Dlya pidtrimki vidobrazhen trikutnikiv trikutniki zberigayutsya tak sho v0 min v0 v1 v2 Zauvazhimo sho hv0 v1 v2i ta hv0 v2 v1i rozglyadayutsya yak rizni trikutniki V dodatok dvostoronnya trikutnikiv cherez sho neobhidno vstaviti obidvi trijki v strukturu danih Zaradi uniknennya postijnih nagaduvan shodo poryadku indeksiv pari trijki v inshij chastini dokumenta informaciya ne oznachaye sho vershini vporyadkovani bud yakim chinom hocha realizaciya obroblyaye poryadok Zv yazok mizh komponentami povnistyu zalezhit vid trijok sho predstavlyayut trikutniki Trikutnik t hv0 v1 v2i maye vershini v0 v1 ta v2 Jomu nalezhat grani e0 hv0 v1i e1 hv1 v2i ta e2 hv2 v0i Vidomi takozh zvorotni zv yazki Vershina v0 primikaye do reber e0 i e2 i do trikutniku t Vershina v1 primikaye do reber e0 i e1 i do trikutniku t Vershina v2 primikaye do reber e1 i e2 i do trikutniku t Usi tri grani e0 e1 e2 primikayut do t Kilkist informaciyi sho zberigayetsya v strukturi danih zalezhit vid potreb programi Krim togo dodatok mozhe potrebuvati dodatkovoyi informaciyi sho zberigayetsya v komponentah Informaciya sho zberigayetsya v vershini grani abo trikutniku nazivayetsya atributom vershini rebra abo atribut trikutnika Yih abstraktne predstavlennya dlya prostoyi strukturi danih opisani tut Vertex lt integer gt v Edge lt integer integer gt v0 v1 Triangle lt integer integer integer gt v0 v1 v2 VData lt application specific vertex data gt EData lt application specific edge data gt TData lt application specific triangle data gt VAttribute lt VData set lt Edge gt set lt Triangle gt gt data eset tset EAttribute lt EData set lt Triangle gt gt data tset TAttribute lt TData gt data VPair pair lt Vertex VAttribute gt EPair pair lt Edge EAttribute gt TPair pair lt Triangle TAttribute gt VMap map lt VPair gt EMap map lt EPair gt TMap map lt TPair gt Mesh lt VMap EMap TMap gt vmap emap tmap Vidobrazhennya pidtrimuyut standartni funkciyi vstavki i vidalennya dlya hesh tablici Vstavka vidbuvayetsya tilki yaksho detal vzhe ne isnuye Vidalennya vidbuvayetsya tilki todi koli detal isnuye Rujnuvannya grani Cya operaciya vklyuchaye v sebe viznachennya rebra hvk vti de vk nazivayetsya zberigayuchoyu vershinoyu vt napravlyayuchoyu Trikutniki yaki mistyat rebro vidalyayutsya z sitki Vershina vt takozh vidalyayetsya z sitki Spilna dlya bud yakih trikutnikiv vershina vt bude zaminena na vk Indeksaciya masivu Za dopomogoyu indeksaciyi masiviv sitka predstavlena dvoma okremimi masivami odin masiv mistit vershini a inshij zberigaye nabori z troh indeksiv v comu masivi yaki viznachayut trikutnik Grafichna sistema obroblyaye vershini pershogo masivu i potim robit trikutniki vikoristovuyuchi nabori indeksiv yaki pracyuyut na peretvorenih danih Div takozhPoligonalna sitka en Neodnoridnij racionalnij B splajn Hmara tochok en dlya promeniv trikutniku peretinu Gipergraf Ce nezavershena stattya pro komp yuternu grafiku Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi