Kolmiulotteisen pinnanmuodostuksen asettamista

vaatimuksista 3-D digitoinnin suorittamiseen

Jos aluksi oletetaan pisteaineisto järjestämättömäksi eli ei voida sanoa varmuudella mikä piste on minkin pisteen naapuri tai pinnan piste. Yleensä näin jos mittaukset on tehty useasta suunnasta ja pisteaineistot on yhdistetty. Peräkkäisten ja järjestettyjen pisteitten muuntaminen pinnaksi on yksinkertainen tehtävä, jota tässä ei käsitellä.

Kunpiste aineisto on koottu useasta eri suunnasta täytyy piste aineiso ensin koota yhdeksi ja järjestää 3D avaruuteen. Samalla voidaan karsia myös häiriö pisteet mallilta.

Koska näytteenottotiheyden ja pinnan mallin oletetaan olevan suhteessa toisiinsa, käytetään parametria r + d useaan eri tarkoitukseen pintamallia muodostettaessa. Parametri määritää pisteitten tiheyden ja tiheyden vaihtelun.

· Se määrittelee pisteiden naapuruuden Nbhd(x_i) estimoitaessa tangenttitasoja pinnalle.

· Sitä käytetään tangenttipintojen yhdistämiseen toisiinsa Riemanin graafissa.

· Se määrittää onko, arvioitaessa määrättyä etäisyysfunktiota , p:n projektio lähimmälle tangenttipinnalle rajan sisällä.

· Sitä käytetään määrittämään pienimpiä kappaleessa esiintyviä muotoja.

Parametrin r + d vaikutus ensimmäisessä vaiheessa muodostettuun verkkoon

Tangenttipinnan estimointi

Ensimmäiseksi lasketaan orientoitu tangenttipinta jokaiselle pisteelle. Valitaan pisteen läheisyydestä k pistettä joukosta X ja pienimmän neliösumman menetelmällä etsitään parhaiten sopiva tangenttipinta pisteelle. Samalla tehdään myös läheisten pintojen keskinäinen orientointi.

Lähekkäisten tangenttipintojen keskinäinen orientointi

Orientointia varten jokaiselle pinnalle määrätään painoarvo, jossa n on pinnan tangenttivektori. Jos ,ovat tangenttipinnat lähes toistensa suuntaisia. Pintojen keskinäiseen orientointiin muodostetaan graafin optimointitehtävä, joka ratkaistaan käyttämällä "ahne"(greedy) -algoritmiä. Algoritmi pyrkii levittämään orientoinnin aina siihen suuntaan, jossa pinnat ovat lähes toistensa suuntaisia ja välttämään alueita, joilla orientointi on vaikeampaa.

Määrätty etäisyysfunktio

Määrätty etäisyysfunktio on mielivaltaisen pisteen ja pinnan välinen lyhin etäisyys kerrottuna ± 1:llä. Jos piste on kauempana pinnasta kuin r + d , se ei voi olla pinnan piste, koska pinnalla pisteiden etäisyys toisistaan on r ja virhemittauksessa d .

Kolmiopinnan muodostaminen

Marching cubes on William E. Lorensen ja Harvey E. Clinen kehittämä pinnansovitusalgoritmi 3D mallien muodostukseen Edellisessä vaiheessa muodostettua tangentti pintaa voidaan käytää kappaleen pinnan rajaukseen.

Toteutus on kuvattu 2D ja 3D muodossa koska asian hahmottaminen on paljon helpompaa, jos se esitetään ensin 2D tilassa.

2D marching cubes

Jos pisteellä, joka on pienempi kuin raja-arvo on naapuripiste, joka on suurempi kuin raja arvo on pinnan on oltava pisteitten välissä. Kun käytetään ensimmäisen kuvan data, niin algoritmi määrittää ensin mitkä pisteet ovat sisäpuolella. Seuraavaksi määritetään mitkä neliön sivut ovat sisällä osittain tai kokonaan. Nyt voidaan valita sivut, jotka leikkaavat reunaviivaa. Yksinkertaistuksena oletetaan, että sivu leikkaa reunaviivaa aina sivun keskikohdasta. Tarkempia ja parempia määritysmenetelmiä on olemassa mutta ei vielä käsitellä. Menetelmällä saadaan pisteet, joitten kautta voidaan piirtää reunaviivan aproksimaatio.

3D marching cubes

Sama algoritmi toimii myös 3D tilassa. Tekniikka on sama kuin 2D mallissa, mutta

- neliöt on muutettu kuutioiksi

- tuloksena ei saada viivoja vaan kolmiopintoja.

Kuutiossa on 8 kulmaa, jokainen kulma voi olla joko sisä- tai ulkopuolella pinnasta, eli saadaan 256 vaihtoehtoista tapausta pisteitten sijainnille pinnan suhteen. Koska sivu voi kohdata pinnan vain kerran, saadaan 256 mahdollista pinnan muodostus tapausta kuutiossa

Tapausten määrä voidaan pelkistää 256 tapauksesta 15 tai14 tapaukseen jos jätetään pois tapaukset, joissa yksikään piste ei ole pinnalla. Yksinkertaistus voidaan suoritaa käsittelemällä samana tapauksena tilat joissa tapaus voidaan muodostaa toisesta tapauksesta :

- kiertämällä minkä tahansa x,y,z akselin ympäri

- peilaamalla minkä minkä x,y,z akselin suhteen

- kiertämällä kaikkia pisteitä

Tapausten yhdistäminen vähentää merkittävästi algoritmin monimutkaisuutta, koska kaikki tapaukset voidaan muodostaa 15 perustapauksesta yksinkertaisilla operaatioilla. Kuvassa sininen piste kuvaa pistettä, joka on pinnan sisällä, ja vihreä nuoli pinnan normaalin suuntaa.

Kolmioitten laskentaan voidaan yksinkertaisimmillaan olettaa sivujen leikkavan aina keskikohdassa, mutta se antaa epätarkan tuloksen, koska kolmioitten asennoille on vain rajallinen määrä vaihtoehtoja. Parempaan tulokseen päästään pienentämällä kuutioita tai jakamalla kuution sivu useampaan osaan.

Huonon aproksimaation vaikutukset voidaan korjata vain paremmalla algoritmilla määrittä kolmo pinnat kuution sisällä. Yksi nopeimmista ja käytetyimmistä menetelmistä on linear interpolation. Jokaiselle pinnalle annetaan interpolaatioarvo, jonka jälkeen pinnan asento on helppo määritellä samaksi kuin raja-arvopinnan.

Kolmion nurkka pisteitten gradientit voidaan laskea interpoloimalla kuution nurkkapisteitten gradienteista.

Marchin cubes sovellettuna käytäntöön

Tarkan aproksimaation muodostamiseksi pinnasta ja sen muodosta määritellään pisteistölle kuutio hila, jossa kuution sivun pituuden on oltava £ r + d . Jokaisen kuution sisällä on vähintään yksi piste ja algoritmin nopeuttamiseksi pinnan etsinnässä tutkitaan vain naapurikuutioiden pisteitä. Pinnan määrittämiseksi lasketaan määrätty etäisyys lähimmästä hilapisteestä mitatun pisteen tangenttipinnalle. Jos etäisyys hilapisteestä pinnalle on suurempi kuin r + d , niin piste ei voi olla pinnan piste. Pisteitten etäisyyksistä aproksimoidaan pienimmän neliösumman menetelmällä pinta, jonka muoto jäljittelee alkuperäistä kappaletta.

Ensimmäisen vaiheen tulos on aproksimoitu verkko Z(). Verkko on tiheä ja sillä on sama topologia kuin pinnalla U, mutta se ei ole tarkka malli alkuperäisestä kappaleesta.

Verkon optimointi

Marchin cubes antaa pinnasta hyvän ja tarkan pintamallin, mutta se ei ole optimoinut pintamallia ja verkon optimointi joudutaan tekemään erikseen.

Verkon optimoinnin ratkaisemiseksi minimoidaan energiafunktio (energy function), jossa on vastakkain kompakti verkko ja tarkka malli pinnasta. Käyttämällä 1 vaiheessa saatua verkkoa M₀ lähtökohtana minimoidaan epälineaarinen energiafunktio vaihtelemalla sivujen määrää, pisteiden sijainteja ja niiden välisiä kytkentöjä (ehtona on että alkuperäinen topologia säilyy). Oletuksena on että optimointi käy läpi kaikki verkot, joilla on sama topologia kuin verkolla M₀. Parhaan mahdollisen verkon löytymistä ei voida taata, mutta tulos on kuitenkin riittävän hyvä.

Valinta tarkkuuden ja kompaktiuden välillä

Verkon optimoinnissa valinta tarkkuuden ja kompaktin välillä on käyttäjän määrittelemällä parametrilla c_rep. Suurella c_rep arvolla tulee verkosta karkea ja pienellä kompakti.

Energiafunktion määrittely

Verkon optimoinnin tarkoituksena on tehdä verkko joka on hyvä sovitus mitatuille pisteille X ja jonka sivujen määrä on mahdollisimman pieni. Etsitään ryhmä K ja joukko sivuja V määrittämään verkko M=(K,V), joka minimoi energiafunktion niin että se vastaa asetettuja vaatimuksia.

E(K,V) = E_dist(K,V)+ E_rep(K,V) + E_spring(K,V).

E_dist on pisteiden etäisyyksien neliösumma verkosta M₀ joka rankaisee kun pisteiden topologia poikkeaa verkon topologiasta.

E_rep rankaisee sivujen määrästä ja mahdollistaa sivujen poistamisen.

Optimointi mahdollistaa sivujen poiston ja lisäyksen verkkoon. Kun sivu lisätään, E_dist pienenee. Samalla E_rep rankaisee operaatiosta niin, että sivuja ei lisätä loputtomiin.

Vastaavasti, jos sivu poistetaan, kasvaa E_dist arvo ja E_rep arvo pienenee. Käyttäjä määrittelee arvon, jolla voidaan säädellä verkon tiheyttä ja mallin tarkkuutta.

Minimoimalla E_dist + E_rep yksistään ei tuota haluttua tulosta. Kun minimoidaan vain E_dist, estimoidussa pinnassa on monia lisäyksiä, joita ei ole alkuperäisessä kappaleessa, koska minimiä E_dist + E_rep ei välttämättä ole olemassa.

Minimin olemassaolon takaamiseksi lisätään kolmas termi E_spring. Se asettaa jokaiselle sivulle verkossa 0 pituisen jousen ja jousivakion k .

Minimoimalla E käyttäen lisänä E_spring saadaan paljon stabiilimpi lopputulos.

Jousivoima ei ole tasainen voima. Sen tehtävänä ei ole poistaa teräviä reunoja joita voi esiintyä kappaleessa. Jousivoiman tehtävänä on tasata verkkoa ja helpottaa optimointia.

Tulokset

Jos kolmiulotteisesta mallista halutaan muodostaa pinta malli joka on tarkka ja kolmoi pinta malli on optimoitu niin on lähtö aineiston oltava mahdollisimman tasa laatuinen. Peiniä puuteita mittauksissa voidaan paikata.

- Aukot voidaan peitää jos voidaan varmasti oletaa että aukon kohdalla pinnan normaali on saman tai lähes saman suuntainen kuin ympäröivien pintojen normaalit.

- Häiriö pisteet jotka poikkeavat selvästi verkon muusta topologiasta on helppo suodataa pois.

- Pintojen päälekkäiset pisteet eivät haitaa pinnan muodostusta kunhan piste aineisto on riittävän tiheä

- Jos pisteistön tiheys vaihtelee suuresti on mallin muodostus jaettava osiin jossa tarkemmat alueet mallinnetaan erikseen ja liitetään myöhemmin epätarkkoihin alueisiin.

- Verkon optimoinnilla voidaan poistaa huomattava määrä tarpeetomia kolmio pintoja mutta alkuperäisen pisteistön oltava tarkka.