Marschterning - Marching cubes

Image
Huvud- och cerebrala strukturer (dolda) extraherade från 150 MR- skivor med hjälp av marschbitar (cirka 150 000 trianglar)

Marschera kuber är en datorgrafik -algoritm , som publicerades i 1987 SIGGRAPH förfarandet genom Lorensen och Cline, för att extrahera en polygonal mesh av en isosurface från en tredimensionell diskret skalärt fält (de element av vilka ibland kallas voxlar ). Tillämpningarna av denna algoritm handlar främst om medicinska visualiseringar som CT- och MR- skanningsdatabilder och specialeffekter eller 3D -modellering med vad som vanligtvis kallas metaballereller andra metasytor. Algoritmen för marscherande kuber är avsedd att användas för 3D, 2-D-versionen av denna algoritm kallas marschruta- algoritmen.

Historia

Algoritmen utvecklades av William E. Lorensen (1946-2019) och Harvey E. Cline som ett resultat av deras forskning för General Electric . På General Electric arbetade de med ett sätt att effektivt visualisera data från CT- och MR -enheter.

Algoritmens utgångspunkt är att dela ingångsvolymen i en diskret uppsättning kuber. Genom att anta linjär rekonstruktionsfiltrering kan varje kub, som innehåller en bit av en given isosyta , lätt identifieras eftersom provvärdena vid kubens hörn måste sträcka sig över isosytans målvärde. För varje kub som innehåller en sektion av isosytan genereras ett triangulärt nät som approximerar beteendet hos den trekantiga interpolanten i den inre kuben.

Den första publicerade versionen av algoritmen utnyttjade rotations- och reflekterande symmetri och signerade också förändringar för att bygga bordet med 15 unika fall. På grund av förekomsten av oklarheter i det trekantiga interpolanta beteendet i kubytorna och insidan, presenterade maskorna som extraherades av Marching Cubes diskontinuiteter och topologiska problem. Med tanke på en kub i rutnätet uppstår en ansiktstydighet när dess ansiktshörn har alternerande tecken. Det vill säga att hörnen på en diagonal på detta ansikte är positiva och hörnen på den andra är negativa. Observera att i detta fall är tecknen på ansiktshornen otillräckliga för att bestämma det korrekta sättet att triangulera isosytan. På samma sätt inträffar en inre oklarhet när tecknen på kubens hörn är otillräckliga för att bestämma den korrekta trianguleringen av ytan , dvs när flera trianguleringar är möjliga för samma kubkonfiguration.

Populariteten hos Marching Cubes och dess utbredda användning resulterade i flera förbättringar av algoritmen för att hantera oklarheterna och för att korrekt spåra interpolantens beteende. Durst 1988 var den första som noterade att trianguleringstabellen som Lorensen och Cline föreslog var ofullständig, och att vissa fall i Marching Cubes tillåter flera trianguleringar. Dursts "ytterligare referens" var till en tidigare, mer effektiv (se de Araujo) isosurface polygoniseringsalgoritm av Wyvill, Wyvill och McPheeters. Senare observerade Nielson och Hamann 1991 förekomsten av oklarheter i det interpolanta beteendet på kubens yta. De föreslog ett test som heter Asymptotic Decider för att korrekt spåra interpolanten på kubens ytor. I själva verket, som observerats av Natarajan 1994, uppstår detta tvetydighetsproblem också inuti kuben. I sitt arbete föreslog författaren ett disambigueringstest baserat på de interpolanta kritiska punkterna och lade till fyra nya fall i trianguleringstabellen för Marching Cubes (delfas av fallen 3, 4, 6 och 7). Vid denna tidpunkt, även med alla förbättringar som föreslagits till algoritmen och dess trianguleringstabell, hade de maskor som genererades av Marching Cubes fortfarande topologiska inkoherenser.

The Marching Cubes 33, som föreslogs av Chernyaev 1995, är en av de första isosurface -extraktionsalgoritmerna som är avsedda att bevara topologin för den trekantiga interpolanten. I sitt arbete utökar Chernyajev till 33 antalet fall i trianguleringssökningstabellen. Han föreslår sedan ett annat tillvägagångssätt för att lösa de inre oklarheterna, som bygger på Asymptotic Decider. Senare, 2003, bevisade Nielson att Chernyaevs uppslagstabell är komplett och kan representera alla möjliga beteenden hos den trilinära interpolanten, och Lewiner et al. föreslog en implementering av algoritmen. Även 2003 förlängde Lopes och Brodlie de tester som Natarajan föreslog. 2013, Custodio et al. noterade och korrigerade algoritmiska felaktigheter som äventyrade den topologiska korrektheten hos nätet som genererades av Marching Cubes 33 -algoritmen som föreslogs av Chernyaev.

Image
De ursprungligen publicerade 15 kubkonfigurationerna

Algoritm

Algoritmen fortsätter genom skalarfältet, tar åtta grannplatser åt gången (bildar därmed en imaginär kub) och bestämmer sedan polygonen som behövs för att representera den del av isosytan som passerar genom denna kub. De enskilda polygonerna smälts sedan in i den önskade ytan.

Detta görs genom att skapa ett index till en förberäknad grupp med 256 möjliga polygonkonfigurationer (2 8 = 256) inom kuben, genom att behandla vart och ett av de 8 skalära värdena som en bit i ett 8-bitars heltal. Om skalärens värde är högre än iso-värdet (dvs det är inuti ytan) sätts den lämpliga biten till en, medan den är lägre (utanför), är den inställd på noll. Slutvärdet, efter att alla åtta skalarna har kontrollerats, är det faktiska indexet för polygonindexmatrisen.

Slutligen placeras varje hörn av de genererade polygonerna på lämplig position längs kubens kant genom att linjärt interpolera de två skalärvärdena som är anslutna med den kanten.

Den gradient av den skalära fältet vid varje rutnätspunkt är också den normala vektorn av en hypotetisk isosurface passerar från den punkten. Därför kan dessa normer interpoleras längs kanterna på varje kub för att hitta normalerna för de genererade hörnen som är väsentliga för att skugga det resulterande nätet med någon belysningsmodell .

Källor

  1. ^ Lorensen, William E .; Cline, Harvey E. (1 augusti 1987). "Marschterning: En algoritm för 3D -konstruktion med hög upplösning". ACM SIGGRAPH Datorgrafik . 21 (4): 163–169. CiteSeerX  10.1.1.545.613 . doi : 10.1145/37402.37422 .
  2. ^ "System och metod för visning av ytstrukturer som finns i det inre området av en fast kropp" . 5 juni 1985. Citera journal kräver |journal=( hjälp )
  3. ^ Dürst, Martin J. (1988-10-01). "Bokstäver: ytterligare referens till marscherande kuber". ACM SIGGRAPH Datorgrafik . 22 (5): 243. doi : 10.1145/378267.378271 . ISSN  0097-8930 . S2CID  36741734 .
  4. ^ de Araujo, Bruno; Lopes, Daniel; Jepp, Pauline; Jorge, Joaquim; Wyvill, Brian (2015). "En undersökning om implicit ytpolygonisering". ACM Computing Surveys . 47 (4): 60: 1–60: 39. doi : 10.1145/2732197 . S2CID  14395359 .
  5. ^ Wyvill, Geoff; Wyvill, Brian; McPheeters, Craig (1986). "Datastrukturer för mjuka föremål". Den visuella datorn . 2 (4): 227–234. doi : 10.1007/BF01900346 . S2CID  18993002 .
  6. ^ Nielson, GM; Hamann, B. (1991). "Den asymptotiska avgöraren: Lös tvetydigheten i marscherande kuber". Fortsätter visualisering '91 . s. 83–91. doi : 10.1109/visual.1991.175782 . ISBN 978-0818622458. S2CID  35739150 .
  7. ^ a b Natarajan, BK (januari 1994). "Om att skapa topologiskt konsekventa isosytor från enhetliga prover". Den visuella datorn . 11 (1): 52–62. doi : 10.1007/bf01900699 . ISSN  0178-2789 . S2CID  526698 .
  8. ^ a b V., Chernyaev, E. (1995). Marching Cubes 33: konstruktion av topologiskt korrekta isosytor: presenteras på GRAPHICON '95, Sankt Petersburg, Ryssland, 03-07.07.1995 . CERN. Datorer och nätverk. OCLC  897851506 .
  9. ^ Nielson, GM (2003). "På marscherande kuber". IEEE -transaktioner om visualisering och datorgrafik . 9 (3): 283–297. doi : 10.1109/TVCG.2003.1207437 .
  10. ^ Lewiner, Thomas; Lopes, Hélio; Vieira, Antônio Wilson; Tavares, Geovan (januari 2003). "Effektiv implementering av marschkubers fall med topologiska garantier". Journal of Graphics Tools . 8 (2): 1–15. doi : 10.1080/10867651.2003.10487582 . ISSN  1086-7651 . S2CID  6195034 .
  11. ^ Lopes, A .; Brodlie, K. (2003). "Förbättra robustheten och noggrannheten hos algoritmen för marscherande kuber för isosurfacing" (PDF) . IEEE -transaktioner om visualisering och datorgrafik . 9 : 16–29. doi : 10.1109/tvcg.2003.1175094 . hdl : 10316/12925 .
  12. ^ Custodio, Lis; Etiene, Tiago; Pesco, Sinesio; Silva, Claudio (november 2013). "Praktiska överväganden om Marching Cubes 33 topologisk korrekthet". Datorer & grafik . 37 (7): 840–850. CiteSeerX  10.1.1.361.3074 . doi : 10.1016/j.cag.2013.04.004 . ISSN  0097-8493 .

Se även

externa länkar