Algorytm maszerujących sześcianów
Algorytm maszerujących sześcianów (ang. Marching cubes algorithm) – 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 algorithm (z ang. algorytm maszerujących kwadratów).
Algorytm został opracowany przez Williama E. Lorensena i Harvey E. Cline, a 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]
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, a tym samym czas otrzymania gotowego obrazu trójwymiarowego.
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 z nich 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 potencjalnie również nie będą puste.
Zobacz też[edytuj | edytuj kod]
Bibliografia[edytuj | edytuj kod]
- Grafika PC bez tajemnic. Warszawa: Intersoftland, 1995. ISBN 83-86389-79-6.