Algorytm maszerujących sześcianów

Algorytm maszerujących sześcianów

Algorytm maszerujących sześcianów (Marching cubes algorithm) to metoda stosowana w grafice komputerowej, która generuje siatkę wielokątów na podstawie danego przestrzennego pola skalarnego. Celem jest przybliżenie powierzchni ekwipotencjalnej o określonej wartości granicznej potencjału. Podobny algorytm działający w dwóch wymiarach nosi nazwę marching squares algorithm.

Opracowanie algorytmu jest dziełem Willliama E. Lorensena oraz Harveya E. Cline’a, a jego szczegóły zostały opublikowane w 1987 roku w artykule pt. „Marching Cubes: A high resolution 3D surface construction algorithm”.

Jednym z praktycznych zastosowań tej metody jest przestrzenna wizualizacja danych medycznych, która opiera się na analizie serii dwuwymiarowych obrazów przekrojów ciała pacjenta (zobacz ilustrację). W programach graficznych algorytm jest używany do wizualizacji tzw. metaballs, co oznacza obrazy pól skalarnych, w których źródłami pola są różne punkty, odcinki lub płaszczyzny rozmieszczone przez grafika.

Algorytm

W tej metodzie przestrzeń jest podzielona na regularną siatkę sześcianów. Dokładność zrekonstruowanego obrazu oraz czas realizacji algorytmu zależą od gęstości podziału, co wpływa na czas uzyskania trójwymiarowego obrazu.

Każdy krok algorytmu analizuje jeden wirtualny sześcian. Wartości pola skalarnego są obliczane dla każdego wierzchołka sześcianu i porównywane z wartością graniczną. Kluczowa jest relacja pomiędzy tymi wartościami – istotne jest, czy są większe czy mniejsze. Z 256 możliwych orientacji sześcianu można wyróżnić 15 kanonicznych orientacji (zobacz ilustrację), które występują w postaci symetrycznych odbić.

Jeżeli wszystkie wartości są niższe od wartości granicznej, dany sześcian nie wytwarza żadnego wielokąta. W przeciwnym przypadku, na krawędziach, które przecinają powierzchnię, ustala się wierzchołki wielokąta, zazwyczaj przy użyciu metod interpolacji liniowej.

Efektywność

Ze względu na współdzielenie wierzchołków i krawędzi przez sąsiednie sześciany, niektóre obliczenia mogą być pomijane. Dodatkowo, można zastosować technikę znaną jako śledzenie powierzchni (surface tracking). W praktyce okazuje się, że tylko niewielka liczba sześcianów może wytwarzać wielokąty. Po zidentyfikowaniu sześcianu, który nie jest pusty, badane są jedynie sąsiednie sześciany, które również mogą nie być puste.

Zobacz też

• woksel
• modelowanie

Bibliografia

Grafika PC bez tajemnic. Warszawa: Intersoftland, 1995. ISBN 83-86389-79-6. Brak numerów stron w książce.