Marching cubes

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Powierzchnia głowy odtworzona algorytmem marching-cubes ze 150 obrazów z rezonansu magnetycznego (około 150 tys. trójkątów)

Marching cubes (dosłownie: maszerujące sześciany) – algorytm z dziedziny grafiki komputerowej, który dla zadanego przestrzennego pola skalarnego tworzy siatkę wielokątów przybliżającą powierzchnię ekwipotencjalną o wybranej wartości granicznej potencjału. Analogiczny algorytm na płaszczyźnie nosi nazwę marching squares (maszerujące kwadraty).

Algorytm został opracowany przez Williama E. Lorensena i Harvey E. Cline, jego opis opublikowano w 1987 roku, w artykule pt. Marching Cubes: A high resolution 3D surface construction algorithm.

Jednym z zastosowań tej metody jest przestrzenna wizualizacja danych medycznych na podstawie szeregu dwuwymiarowych obrazów przekroju ciała pacjenta (patrz ilustracja). Natomiast w programach graficznych używana jest do wizualizacji tzw. metaballs, tj. obrazów pól skalarnych w których źródłami pola są punkty, odcinki lub płaszczyzny rozmieszczane przez grafika.

Algorytm[edytuj | edytuj kod]

Przybliżenia powierzchni wielokątami dla 15 kanonicznych orientacji sześcianu

Przestrzeń dzielona jest na regularną siatkę sześcianów; od gęstości podziału zależy dokładność zrekonstruowanego obrazu oraz czas potrzebny na wykonanie algorytmu.

Pojedynczy krok algorytmu rozpatruje jeden wirtualny sześcian. W każdym jego wierzchołku wyznaczana jest wartość pola skalarnego i porównywana z wartością graniczną – istotna jest tutaj wyłącznie relacja liczb, tj. większy lub mniejszy. Istnieje zatem 256 orientacji sześcianu względem powierzchni, jednak można wyróżnić 15 kanonicznych orientacji (patrz ilustracja), które powtarzają się jako odbicia symetryczne.

Jeśli wszystkie wartości są mniejsze od wartości granicznej, taki sześcian nie formuje żadnego wielokąta. W przeciwnym razie na krawędziach przecinających powierzchnię wyznacza się (zwykle metodą interpolacji liniowej) wierzchołki wielokąta.

Efektywność[edytuj | edytuj kod]

Ze względu na fakt współdzielenia wierzchołków i krawędzi przez sąsiednie sześciany, część obliczeń nie musi być powtarzana.

Ponadto można zastosować technikę śledzenia powierzchni (ang. surface tracking). W praktyce okazuje się, że zwykle niewielka część sześcianów może formować wielokąty. Dlatego po znalezieniu takiego, który nie jest pusty testuje się tylko sąsiednie sześciany, które też potencjalnie nie będą puste.

Bibliografia[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]