Cuburi de marș

Cuburi de marș este un algoritm de grafică pe computer , publicat la SIGGRAPH 1987 de Lorensen și Cline ^[1] pentru a extrage o plasă poligonală a unei izosuprafețe dintr-un câmp scalar 3D (uneori numit voxel ). Algoritmul este utilizat în principal în domeniul de radiologie prin imagistica de diagnostic , cum ar fi CT și RMN , dar , de asemenea , în crearea de efecte speciale în domeniul modelării 3D , cu metaballs sau metasurfaces . O metodă analogică bidimensională se numește pătrate de mers .

Structurile capului și creierului (ascunse) extrase din 150 de felii RMN folosind cuburi de mers (aproximativ 150.000 de triunghiuri)

Istorie

Algoritmul a fost dezvoltat de William E. Lorensen și Harvey E. Cline ca urmare a cercetărilor lor la General Electric . La General Electric au lucrat pentru a afișa eficient datele de pe dispozitivele CT și RMN.

15 configurații unice

Prima lor versiune publicată a exploatat simetria rotațională și reflexivă și, de asemenea, modificări particulare în construcția unui tabel cu 15 configurații unice. Cu toate acestea, în procesarea fețelor, există câteva cazuri ambigue. ^[2] Aceste cazuri ambigue pot duce la împletirea cu găuri. Topologic vorbind, corectarea izosuprafețelor poate necesita un efort suplimentar. ^[3]

Problema apare pentru cazurile în prezența unui semn dublu, în care există cel puțin două alegeri corecte pentru care profilul este valid. Alegerea efectivă nu contează, dar trebuie să fie coerentă din punct de vedere topologic. Cazurile primare conduc la alegeri consistente, dar schimbarea semnului poate duce la erori. Tabelul extins din ^[3] prezintă 33 de configurații.

Ambiguitățile au fost îmbunătățite odată cu dezvoltarea de noi algoritmi, cum ar fi în 1991 deciderul asimptotic de către Nielson și Hamann ^[4], care au corectat aceste anomalii.^[5] ^[6] De atunci au fost propuse alte câteva analize de ambiguitate și îmbunătățiri conexe; vezi sondajul din 2005 realizat de Lopes și Bordlie, de exemplu. ^[6]

Descrierea algoritmului

Algoritmul se desfășoară prin câmpul scalar, luând opt locații învecinate la un moment dat (formând astfel un cub imaginar), determinând astfel poligonul sau poligoanele necesare pentru a reprezenta partea izosurfei care trece prin acest cub. Poligoanele individuale sunt apoi fuzionate în suprafața dorită.

Acest lucru se face prin crearea unui index într-o matrice precalculată de 256 de configurații posibile de poligon ( $2^{8}=256$ ${\ displaystyle 2 ^ {8} = 256}$ ${\ displaystyle 2 ^ {8} = 256}$ ) În interiorul cubului, tratând fiecare dintre cele 8 valori scalare ca un bit într-un 8-biți complet . Dacă valoarea scalară este mai mare decât valoarea izo (adică este în interiorul suprafeței), atunci bitul corespunzător este setat la unul, în timp ce dacă este mai mic (extern) este setat la zero. Valoarea finală după verificarea tuturor celor 8 scalari este indexul pentru matricea de configurare a poligonului.

În cele din urmă, fiecare vârf al poligoanelor generate este plasat în poziția corespunzătoare de-a lungul laturii cubului prin interpolare liniară a valorilor celor doi scalari care sunt conectați pe acea parte.

Matricea precalculată a celor 256 de configurații poate fi obținută prin reflecție și rotații simetrice ale singurelor 15 cazuri.

Gradientul câmpului scalar la fiecare punct al grilei este, de asemenea, vectorul normal al unei izosurfete ipotetice din acel punct. Apoi, ar trebui să interpolăm aceste normale de-a lungul balamalelor fiecărui cub pentru a găsi normele vârfurilor generate, care sunt esențiale pentru umbrirea rețelei rezultate cu un anumit model de iluminare.

Probleme de brevet

Algoritmul cuburilor de marș este considerat de către susținătorii software-ului gratuit ca fiind un caz major în domeniul graficii computerizate a relelor software-urilor proprietare. ^{[ fără sursă ]} . Ei susțin că implementarea brevetată (brevetul SUA 4.710.876 ^[7] ) este evidentă în ceea ce privește problema generării suprafeței. Un algoritm similar numit tetraedre de marș a fost dezvoltat pentru a eluda brevetul, precum și pentru a rezolva unele cazuri de ambiguitate cu o anumită configurație a cubului. Licența algoritmului cuburilor de marș a expirat în 2005 și acum este legal ca comunitatea grafică pe computer să utilizeze algoritmul fără drepturi de autor pentru mai mult de 18 ani de la data emiterii sale (1 decembrie 1987 ^[7] ).

Notă

^ William E. Lorensen, Harvey E. Cline: Marching Cubes: Un algoritm de construcție a suprafeței 3D de înaltă rezoluție. În: Computer Graphics , Vol. 21, Nr. 4, iulie 1987
^ The Marching Cubes . Adus la 24 aprilie 2014 (arhivat din original la 18 august 2019) .
^ ^a ^b Cuburi de marș 33: Construcția unor suprafețe topologice corecte .
^ Gregory M. Nielson și B. Hamann, The asymptotic decider: solving the ambiguity in marsing cubes , în Proceeding VIS '91 Proceedings of the 2nd conference on Visualization '91 , 1991.
^ Charles D. Hansen și Chris R. Johnson, Manual de vizualizare , Academic Press, 2004, p. 9, ISBN 978-0-12-387582-2 .
^ ^a ^b A. Lopes și K. Bordlie, Abordări interactive de conturare și izosurfaces pentru gevizualizare , în Jason Dykes, Alan M. MacEachren și MJ Kraak (eds), Explorarea Gevivalizării , Elsevier, 2005, pp. 352–353, ISBN 978-0-08-044531-1 .
^ ^a ^b ( EN ) US4710876 , United States Patent and Trademark Office , Statele Unite ale Americii.

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre cuburile Marching

[Originalpaper-1] William E. Lorensen, Harvey E. Cline: Marching Cubes: Un algoritm de construcție a suprafeței 3D de înaltă rezoluție. În: Computer Graphics , Vol. 21, Nr. 4, iulie 1987

[2] The Marching Cubes . Adus la 24 aprilie 2014 (arhivat din original la 18 august 2019) .

[citeseerx.ist.psu.edu-3] Cuburi de marș 33: Construcția unor suprafețe topologice corecte .

[4] Gregory M. Nielson și B. Hamann, The asymptotic decider: solving the ambiguity in marsing cubes , în Proceeding VIS '91 Proceedings of the 2nd conference on Visualization '91 , 1991.

[HansenJohnson2004-5] Charles D. Hansen și Chris R. Johnson, Manual de vizualizare , Academic Press, 2004, p. 9, ISBN 978-0-12-387582-2 .

[DykesMacEachren2005-6] A. Lopes și K. Bordlie, Abordări interactive de conturare și izosurfaces pentru gevizualizare , în Jason Dykes, Alan M. MacEachren și MJ Kraak (eds), Explorarea Gevivalizării , Elsevier, 2005, pp. 352–353, ISBN 978-0-08-044531-1 .

[patent-7] ( EN ) US4710876 , United States Patent and Trademark Office , Statele Unite ale Americii.

[1]

[2]

[3]

[4],

[5]

[6]

[7]