Cuburi de marș

Marching cubes (din  engleză  -  „walking cubes”) este un algoritm în grafica computerizată , propus pentru prima dată în 1987 la conferința SIGGRAPH de William Laurensen și Harvey Kline [1] , pentru procesarea unei grile poligonale a izosuprafeței unui scalar tridimensional . câmp (numit mai des o grilă voxel ).

Un algoritm similar pe plan se numește pătrate de marș .

Cum funcționează

Algoritmul parcurge câmpul scalar, la fiecare iterație se uită la 8 poziții învecinate (vârfurile cubului paralele cu axele de coordonate) și determină poligoanele necesare pentru a reprezenta porțiunea de izosuprafață care trece prin acest cub. Apoi, poligoanele care formează izosuprafața specificată sunt afișate pe ecran.

Deoarece algoritmul selectează poligoane doar pe baza poziției vârfurilor cubului în raport cu izosuprafața, există 256 ( ) configurații posibile de poligoane în total, care pot fi calculate în avans și stocate într-o matrice. Prin urmare, fiecare cub poate fi reprezentat printr-un număr de opt biți atribuind 1 fiecărui vârf dacă valoarea câmpului în punct este mai mare decât pe izosuprafața și 0 în caz contrar. Numărul rezultat este folosit ca index al elementului de matrice care stochează configurațiile poligonului. În cele din urmă, fiecare vârf al poligonului generat este plasat într-o poziție adecvată pe marginea cubului pe care se afla inițial. Poziția este calculată prin interpolarea liniară a valorilor câmpului scalar la capetele muchiei.

O matrice precalculată de 256 de configurații de poligoane poate fi obținută prin rotirea și reflectarea a 15 configurații de cuburi diferite. Cu toate acestea, utilizarea a doar 15 configurații de bază nu garantează o suprafață închisă. Configurații de bază lipsite de acest dezavantaj pot fi găsite în literatura de specialitate. .

Gradientul câmpului scalar la fiecare punct al grilei este, de asemenea, un vector normal pentru izosuprafața presupusă care trece prin acel punct. Prin urmare, este posibil să se interpoleze aceste normale de-a lungul muchiilor fiecărui cub pentru a găsi normalele vârfurilor generate pentru a afișa corect modelul atunci când se folosește iluminarea.

Acest algoritm este utilizat pe scară largă în medicină, de exemplu, în tomografia computerizată și imagistica prin rezonanță magnetică , precum și pentru modelarea tridimensională a metasferelor sau a altor metasuprafețe.

Brevet

Algoritmul Marching Cubes a fost primul exemplu de grafică pe computer care a declanșat un scandal de brevete de software . A fost brevetat în ciuda relativității evidente a soluției la problema generării suprafeței. Ulterior a fost dezvoltat un algoritm similar, numit tetraedre în marș , care folosește tetraedre în loc de cuburi pentru a ocoli brevetul. Brevetul a expirat în 2005, iar algoritmul este acum liber de utilizat. (Brevet din 5 iunie 1985 [2] ).

Note

  1. ↑ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. În: Computer Graphics , Vol. 21, nr. 4 iulie 1987
  2. ↑ Marching Cubes, intrarea Oficiului de Brevete din SUA

Vezi și

Link- uri externe