Marching cubes

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een hoofd opgebouwd met behulp van 150 MRI-scans en het Marching Cubes algoritme.
15 unieke situaties.

Marching cubes is een computergraphics algoritme voor volume rendering. Het algoritme geeft een driedimensionaal object weer als een verzameling verbonden polygonen (meestal driehoekjes). Het algoritme is voor het eerst uitgebracht in 1987 door William E. Lorensen en Harvey E. Cline.

Algoritme[bewerken]

Wat doet het?[bewerken]

Men moet ervan uitgaan dat een 3D object opgedeeld is in een driedimensionaal raster, met vele cellen. Het algoritme bouwt nu een mesh op van het 3D object uit vele driehoekjes. Hiertoe worden in eerste instantie alle cellen die aan de buitenkant van het object liggen gemarkeerd. Voor iedere "buitencel", zal nu een of meerdere driehoekjes getekend worden.

Het belangrijkste werk van het algoritme is om nu te bepalen hoeveel driekhoekjes per cel getekend moeten worden, welke vorm en welke oriëntatie ten opzichte van de kijker de driehoekjes krijgen. Hiertoe stelt men een cel voor als een kubus (Marching cube). Deze kubus wordt doorsneden door een deel van het 3D object. Het snijvlak dat het 3D object creëert in de Marching cube wordt opgebouwd uit enkele driehoekjes. Eenvoudig gezegd zal het algoritme nu het snijvlak vormen door de snijpunten van het snijvlak met de kubus te verschuiven langs de zijden van de kubus, zodat de driehoekjes waaruit het snijvlak is opgebouwd de juiste vorm krijgen. De vorm van het snijvlak wordt gedefinieerd als een verzameling van punten. De oriëntatie van het snijvlak wordt bepaald door een set met normaal vectoren. De snijpunten en de oriëntatie worden opgeslagen, alvorens naar de volgende Marching Cube te gaan.

Omdat gebruikgemaakt wordt van eenvoudige polygonen kan de grafische hardware hier makkelijk mee overweg en zal het 3D object snel kunnen worden weergegeven.

Een kubus doorsnijden[bewerken]

Men kan op vele manieren vlakken aangeven die een kubus doorsnijden, waarbij bepaalde hoekpunten van de kubus aan de "binnenkant" of aan de "buitenkant" van de doorsnede liggen. Als nu bekend is hoeveel en welke hoekpunten van een kubus binnen/ buiten een doorsnede van de kubus liggen, is eenvoudig na te gaan wat voor snijvlakken hiervoor verantwoordelijk zijn. Te berekenen is dat er 256 mogelijkheden om doorsnedes te maken van een kubus, waarbij een gegeven aantal hoekpunten aan de "binnenkant" of aan de "buitenkant" van de doorsnede liggen. Sterker nog, door gebruik te maken van de symmetrie van de kubus, kunnen 15 gevallen onderscheiden worden, die alle 256 doorsnedes kunnen vormen. Deze gevallen kan men opslaan in een zgn. Triangle lookup table (TLT). Wanneer nu bekend is hoeveel en welke knopen er nu aan de buitenkant van een kubus liggen, kan via de TLT snel het bijhorende doorsnede geval bepalen.

Proces[bewerken]

Voor iedere cel in het 3D object wordt het volgende gedaan:

  1. Kubus bouwen. Stel een denkbeeldige kubus samen uit 4 datapunten uit laag k en 4 datapunten uit laag k+1 van het 3D object. De 8 datapunten functioneren als de 8 knopen van een kubus (v1..v8).
  2. Hoekpunten classificeren. Het 3D object zal deze denkbeeldige kubus doorsnijden. Bepaal nu welke hoekpunten van de denkbeeldige kubus nu binnen of buiten het 3D object vallen.
  3. Index berekenen. Creëer een index tussen 0 en 255 (1 byte). Ieder bit in de byte stelt een hoekpunt voor. Wanneer een hoekpunt buiten het 3D object valt, zoals bepaald in stap 2, dan zal het betreffende bit '1' worden, anders '0'.
  4. Zijden bepalen. Via de index kan nu uit de TLT, een snijvlak gekozen worden. Ieder snijvlak is samengesteld uit een of meerdere driehoeken.
  5. Snijpunten van het snijvlak bepalen via interpolatie. De exacte snijpunten van de doorsnee met de denkbeeldige kubus, worden bepaald via interpoleren met de hoekpunten van de denkbeeldige kubus.
  6. Normaalvectoren berekenen en interpoleren. Voor iedere zijde van de denkbeeldige kubus wordt een normaalvector berekend. Interpoleer nu de normaalvectoren van de snijpunten via lineaire interpolatie tussen de normaalvectoren van de hoekpunten van de kubus.