alt=Un cubo cun vértice interior e sete exteriores contén un triángulo que conecta tres interseccións nas arestas adxacentes ao vértice interior.|miniatura|250x250px|Caso local sinxelo: unha clasificación cun só vértice por un lado do limiar produce un fragmento triangular. As posicións interpólanse nas arestas, non se sitúan obrigatoriamente nos seus puntos medios. Marching cubes é un algoritmo de gráficos por computador que extrae unha malla de triángulos a partir dun campo escalar tridimensional mostreado nunha grella. A malla aproxima unha isosuperficie: o conxunto de puntos nos que o campo alcanza un valor determinado. O método percorre as celas da grella, clasifica os seus vértices respecto dese valor e constrúe pequenos fragmentos de superficie que se ensamblan nun modelo.
Foi presentado por William E. Lorensen e Harvey E. Cline en 1987, cunha motivación destacada na visualización de datos volumétricos médicos. A súa utilización estendeuse á visualización científica, aos campos implícitos, á reconstrución de superficies e á xeometría xerada a partir de volumes. O nome describe o avance sucesivo de cela en cela, non un movemento físico de cubos na escena.
O algoritmo clásico é local e permite implementacións eficientes, pero a clasificación binaria dos vértices non determina sempre unha conectividade única. As ambigüidades xeométricas e topolóxicas motivaron numerosas variantes. Unha implementación que se denomine marching cubes debe especificar as súas regras se se queren garantir propiedades como ausencia de fendas ou concordancia coa topoloxía dun campo interpolado.
Campos escalares e isosuperficies Un campo escalar asigna un número a cada posición do espazo. Pode representar densidade, temperatura, distancia con signo ou outra magnitude. Para un valor , a isosuperficie ideal é
Na práctica, normalmente non se coñece en todos os puntos: só se dispón de mostras. Extraer unha superficie require asumir como se comporta o campo entre elas. A malla depende tanto dos datos como dese modelo de interpolación.
Nunha grella regular de mostras, cada grupo de oito mostras veciñas define unha cela. Hai celas. O termo «cubo» é combinatorio: se a separación entre mostras é diferente en cada eixe, as celas físicas son paralelepípedos rectangulares. Ignorar esa separación deforma a superficie reconstruída.
É frecuente que un volume se describa como unha matriz de vóxeles. Cómpre precisar se os valores se asocian aos centros dos vóxeles ou aos vértices dunha grella. O algoritmo recibe mostras e usa celas entre elas; situar esas mostras cun desprazamento incorrecto cambia a localización da malla. A orientación dos eixes, a orixe e as unidades deben acompañar os datos.
Unha única isosuperficie non conserva toda a información volumétrica. Dous campos diferentes poden compartir a mesma superficie para un limiar. Mostrar varios limiares pode revelar estruturas distintas, pero non substitúe unha análise da magnitude representada. A elección do valor de nivel ten un significado específico no dominio e non é unha decisión xeométrica neutral.
Algoritmo básico
Clasificación dos vértices Para cada cela compáranse os seus oito valores con . A cada vértice asígnaselle un bit segundo estea nun ou noutro lado. Os oito bits forman un índice entre 0 e 255. Se todos os vértices están no mesmo lado, a táboa elemental non xera triángulos nesa cela; nos demais casos, unha táboa indica que arestas deben conectarse.
As simetrías xeométricas e a inversión de signos permiten reducir a presentación dos patróns a un conxunto de casos representativos. A coñecida clasificación elemental de quince casos non resolve por si mesma todas as posibilidades topolóxicas do interpolante. Dous conxuntos de valores poden ter os mesmos signos nos vértices e diferente estrutura entre eles.
O caso de igualdade co limiar necesita unha convención. Empregar «maior» nunha cela e «maior ou igual» noutra pode producir clasificacións contraditorias nun vértice compartido. Os valores non finitos, as máscaras e os límites do dominio tamén requiren políticas explícitas. A táboa de casos non substitúe estas decisións de representación.
Interpolación nas arestas Se unha aresta une e , con valores e a lados opostos do limiar, a interpolación lineal coloca a intersección en
A fracción expresa que proporción da aresta se percorre. Situar sempre a intersección no punto medio desaproveita a magnitude das mostras e crea unha xeometría diferente. A interpolación é exacta para a restrición lineal do modelo á aresta, non necesariamente para un campo físico descoñecido.
Por exemplo, con valores 0 e 4 nunha aresta e limiar 1, a intersección está a unha cuarta parte desde o extremo de valor 0. Se a aresta mide dúas unidades físicas, a distancia correspondente é media unidade. Esta operación é un cálculo local; os triángulos construídos entre interseccións son unha aproximación plana dunha superficie que pode ser curva dentro da cela.
As celas veciñas comparten arestas e deben producir a mesma intersección para elas. Unha implementación pode gardar un índice por aresta e reutilizar o vértice xa calculado. Sen reutilización, a malla pode conter coordenadas duplicadas que visualmente coinciden, pero non comparten conectividade; iso afecta operacións posteriores de veciñanza, suavizado ou análise topolóxica.
Triángulos e normais A táboa de casos expresa conexións entre as arestas cruzadas. Os índices da táboa substitúense polos vértices interpolados para emitir triángulos. A orde dos seus vértices define unha orientación e debe ser coherente co lado considerado interior. Invertela cambia a dirección das normais xeométricas e pode afectar tanto o sombreado como os cálculos de volume orientado.
As normais poden calcularse a partir dos propios triángulos ou do gradiente do campo. Se é non nulo, é perpendicular á isosuperficie. Aproximar o gradiente nas mostras e interpolalo nos vértices pode producir un sombreado suave. Unha aparencia suave non converte os triángulos en superficies curvas nin elimina o erro de aproximación xeométrica.
Nunha grella anisótropa, as diferenzas finitas deben dividirse polas separacións físicas dos eixes. Usar só diferenzas entre índices cambia a dirección estimada do gradiente. Ademais, unha normal non está definida da maneira habitual nun punto onde o gradiente se anula; iso require un tratamento numérico apropiado, especialmente preto de puntos críticos do campo.
Ambigüidades e topoloxía
Ambigüidade dunha cara alt=Dous cadrados cos mesmos signos alternados mostran conexións distintas entre os catro puntos de intersección.|miniatura|Os signos dos catro vértices dunha cara non determinan por si sós a conexión do contorno. Os valores do interpolante permiten resolver a ambigüidade segundo o modelo escollido. Unha cara cadrada pode ter dous vértices positivos e dous negativos alternados. Os catro bordos están cruzados, pero hai dúas formas de emparellar as interseccións. Se dúas celas veciñas escollen solucións incompatibles para a cara compartida, poden aparecer fendas ou conexións incorrectas. A decisión non debe depender só da orde en que se visiten as celas.
O decisor asintótico considera o interpolante bilinear da cara, utilizando os valores e non só os signos. Para un nivel determinado, a forma dese interpolante permite decidir como se conectan as ramas do contorno. É unha regra compartida polas dúas celas que contén a mesma cara, o que resolve a incompatibilidade local asociada a ese caso.
Ambigüidade no interior Resolver as caras non resolve necesariamente a conectividade dentro de toda a cela. O interpolante trilinear pode ter estruturas interiores que non quedan determinadas polas decisións tomadas no bordo. Marching Cubes 33 ampliou a clasificación e incorporou probas para distinguir configuracións topolóxicas relevantes.
Lewiner e colaboradores presentaron unha implementación de casos con garantías topolóxicas. O obxectivo é que a triangulación sexa coherente coa topoloxía do interpolante que se decidiu representar. Esta garantía debe entenderse dentro das hipóteses e regras da variante: non afirma recuperar automaticamente a topoloxía dun obxecto real mostreado con resolución insuficiente.
Custodio, Etiene, Pesco e Silva analizaron en 2013 problemas da descrición e implementación de MC33 e presentaron correccións. O seu traballo destaca que unha garantía matemática necesita corresponder ao código realmente executado. A avaliación con campos sintéticos que exercitan casos ambiguos é distinta dunha inspección visual de superficies suaves e aparentemente correctas.
Resolución e obxecto representado A topoloxía do interpolante non é necesariamente a do campo continuo do que procederon as mostras. Un detalle situado entre mostras pode non deixar indicio nos valores gardados. Aumentar a resolución da malla sen adquirir máis información non recupera de maneira garantida ese detalle. Cómpre separar o erro de mostraxe, o de interpolación e o de triangulación.
Tamén poden aparecer triángulos de área nula cando varias interseccións coinciden ou o limiar atravesa exactamente certos vértices. Eliminar eses triángulos pode ser necesario para algoritmos posteriores, pero debe facerse preservando a conectividade que corresponda. As bibliotecas poden ofrecer opcións para permitir ou retirar elementos dexenerados.
Complexidade e implementación Nun percorrido completo, o algoritmo examina todas as celas, cun traballo local acoutado para cada unha nas variantes de táboa fixa. Se hai celas e triángulos xerados, unha descrición habitual do custo é . O almacenamento depende de se se conserva o volume enteiro, cantas capas se procesan á vez e como se gardan os vértices compartidos.
Un volume grande pode conter poucas celas activas para un limiar concreto. Estruturas que gardan mínimos e máximos por rexión permiten descartar zonas nas que o nivel non pode aparecer. O beneficio debe compararse co custo de construír e manter esas estruturas, sobre todo cando se cambian os datos ou só se vai extraer unha superficie.
As celas poden clasificarse en paralelo. A dificultade é asignar espazo de saída e evitar que varios fíos creen duplicados para a mesma aresta. Os métodos de varias pasadas contan primeiro os elementos necesarios, calculan posicións de escritura e emiten despois a xeometría. Esta organización reduce asignacións dinámicas e permite escrituras máis previsibles.
Flying Edges reformula a traversía para reducir traballo redundante nas arestas e organizar o proceso en varias fases. O seu rendemento non pode resumirse cun único factor de aceleración independente da máquina e dos datos. A contribución é a organización do cálculo e da memoria para facilitar unha execución escalable.
Variantes e métodos relacionados Marching squares é o análogo bidimensional que extrae liñas de nivel en celas cadradas. É útil para entender a clasificación dos vértices e a ambigüidade dunha cara. Marching tetrahedra divide o volume en tetraedros, nos que un interpolante lineal ten casos máis simples; cambia o modelo de interpolación e pode introducir máis triángulos e dependencia da subdivisión escollida.
O contornado dual de datos de Hermite utiliza información de intersección e normais para situar vértices asociados ás celas e conectar a superficie segundo outra organización. Pode preservar características agudas mellor ca certas triangulacións elementais, pero require datos e procedementos adicionais. Non é unha simple substitución da táboa de marching cubes.
Os métodos adaptativos empregan celas de tamaños diferentes para concentrar resolución. A unión entre niveis require regras para evitar fendas. Outros algoritmos xeran unha superficie inicial e simplifícana posteriormente; reducir triángulos pode mellorar o almacenamento e a visualización, pero introduce outro criterio de erro e pode alterar detalles ou topoloxía se non se restrinxe.