Marcherende terninger

Marching cubes (fra  engelsk  -  "walking cubes") er en algoritme inden for computergrafik , første gang foreslået i 1987 på SIGGRAPH - konferencen af ​​William Laurensen og Harvey Kline [1] , til behandling af et polygonalt gitter af isooverfladen af ​​en tredimensionel skalar felt (oftere kaldet et voxel -gitter ).

En lignende algoritme på flyet kaldes marcherende firkanter .

Sådan virker det

Algoritmen løber gennem det skalære felt, ser ved hver iteration på 8 nabopositioner (hjørnepunkter på terningen parallelt med koordinatakserne) og bestemmer de polygoner , der er nødvendige for at repræsentere den del af isooverfladen, der passerer gennem denne terning. Dernæst vises de polygoner, der danner den specificerede isooverflade, på skærmen.

Da algoritmen kun udvælger polygoner baseret på placeringen af ​​terninghjørnerne i forhold til isooverfladen, er der i alt 256 ( ) mulige polygonkonfigurationer, som kan beregnes på forhånd og lagres i et array. Derfor kan hver terning repræsenteres af et otte-bit tal ved at tildele 1 til hvert toppunkt, hvis værdien af ​​feltet i punktet er større end på isooverfladen, og 0 ellers. Det resulterende tal bruges som indekset for det array-element, der gemmer polygonkonfigurationerne. Til sidst placeres hvert hjørne af den genererede polygon i en passende position på kanten af ​​den terning, hvorpå den oprindeligt lå. Positionen beregnes ved lineær interpolation af værdierne af det skalære felt i enderne af kanten.

Et forudberegnet array af 256 polygonkonfigurationer kan opnås ved at rotere og reflektere 15 forskellige terningkonfigurationer. Brugen af ​​kun 15 grundlæggende konfigurationer garanterer dog ikke en lukket overflade. Grundlæggende konfigurationer uden denne ulempe kan findes i den specialiserede litteratur. .

Den skalære feltgradient ved hvert gitterpunkt er også en normalvektor til den formodede isooverflade, der passerer gennem dette punkt. Derfor er det muligt at interpolere disse normaler langs kanterne af hver terning for at finde normalerne af de genererede hjørner for at vise modellen korrekt, når der bruges belysning.

Denne algoritme er meget udbredt i medicin, for eksempel i computertomografi og magnetisk resonansbilleddannelse , såvel som til tredimensionel modellering af metasfærer eller andre metasurfaces.

Patent

Marching Cubes-algoritmen var det første computergrafikeksempel, der udløste en softwarepatentskandale . Det var patenteret på trods af den relative indlysende løsning på problemet med overfladegenerering. En lignende algoritme blev senere udviklet, kaldet marching tetrahedrons , som bruger tetraedre i stedet for terninger til at omgå patentet. Patentet udløb i 2005, og algoritmen er nu gratis at bruge. (Patent dateret 5. juni 1985 [2] ).

Noter

  1. ↑ William E. Lorensen, Harvey E. Cline: Marching Cubes: En højopløsnings 3D overfladekonstruktionsalgoritme. I: Computer Graphics , Vol. 21, nr. 4 juli 1987
  2. ↑ Marching Cubes, US Patent Office-indgang

Se også

Eksterne links