Marssikuutiot

Marssikuutiot (  englanniksi  "  kävelykuutiot") on tietokonegrafiikassa algoritmi , jonka William Laurensen ja Harvey Kline [1] ehdottivat ensimmäisen kerran vuonna 1987 SIGGRAPH - konferenssissa kolmiulotteisen skalaarin isopinnan monikulmion käsittelemiseksi. kenttä (kutsutaan useammin vokseliruudukoksi ).

Vastaavaa algoritmia tasossa kutsutaan marssineliöiksi .

Kuinka se toimii

Algoritmi kulkee skalaarikentän läpi, jokaisessa iteraatiossa tarkastelee 8 vierekkäistä sijaintia ( kuution pisteet, jotka ovat samansuuntaisia ​​koordinaattiakselien kanssa) ja määrittää monikulmiot , jotka ovat tarpeen edustamaan tämän kuution läpi kulkevaa isopinnan osaa. Seuraavaksi monikulmiot, jotka muodostavat määritellyn isopinnan, näytetään näytöllä.

Koska algoritmi valitsee polygonit vain kuution kärkien sijainnin perusteella suhteessa isopintaan, mahdollisia polygonikonfiguraatioita on yhteensä 256 ( ), jotka voidaan laskea etukäteen ja tallentaa taulukkoon. Siksi jokainen kuutio voidaan esittää kahdeksanbittisellä numerolla antamalla jokaiselle kärkipisteelle 1, jos kentän arvo pisteessä on suurempi kuin isopinnalla ja 0 muussa tapauksessa. Saatua numeroa käytetään monikulmiokokoonpanot tallentavan taulukkoelementin indeksinä. Lopuksi generoidun polygonin kukin kärkipiste sijoitetaan sopivaan paikkaan kuution reunalle, jolla se alun perin oli. Sijainti lasketaan lineaarisella interpoloinnilla reunan päissä olevan skalaarikentän arvoista.

Esilaskettu 256 monikulmiokokoonpanon joukko voidaan saada kiertämällä ja heijastamalla 15 erilaista kuutiokonfiguraatiota. Vain 15 peruskokoonpanon käyttö ei kuitenkaan takaa suljettua pintaa. Erikoiskirjallisuudesta löytyy peruskonfiguraatioita, joista puuttuu tämä epäkohta. .

Skalaarikentän gradientti kussakin ruudukkopisteessä on myös normaalivektori tämän pisteen läpi kulkevalle oletetulle tasapinnalle. Siksi on mahdollista interpoloida nämä normaalit kunkin kuution reunoja pitkin generoitujen pisteiden normaalien löytämiseksi, jotta malli saadaan näkyviin oikein valaistusta käytettäessä.

Tätä algoritmia käytetään laajalti lääketieteessä, esimerkiksi tietokonetomografiassa ja magneettikuvauksessa , sekä metapallojen tai muiden metapintojen kolmiulotteisessa mallintamisessa.

Patentti

Marching Cubes -algoritmi oli ensimmäinen tietokonegrafiikkaesimerkki, joka herätti ohjelmistopatenttiskandaalin . Se patentoitiin huolimatta pinnanmuodostusongelman ratkaisun suhteellisen ilmeisyydestä. Myöhemmin kehitettiin samanlainen algoritmi, nimeltään marching tetrahedrons , joka käyttää tetraedria kuutioiden sijasta patentin kiertämiseen. Patentti päättyi vuonna 2005 ja algoritmi on nyt vapaasti käytettävissä. (Patentti päivätty 5. kesäkuuta 1985 [2] ).

Muistiinpanot

  1. ↑ William E. Lorensen, Harvey E. Cline: Marching Cubes: Korkearesoluutioinen 3D-pinnanrakennusalgoritmi. Julkaisussa: Computer Graphics , Voi. 21, ei. 4 heinäkuuta 1987
  2. ↑ Marching Cubes, Yhdysvaltain patenttiviraston merkintä

Katso myös

Ulkoiset linkit