Marching Cube ambiguità Versus Marching Tetraedro

Question

ho implementato con successo l'algoritmo marching cubes. Ho usato i materiali standard come riferimento, ma l'ho riscritto interamente da zero. Funziona, ma sto osservando le ambiguità che portano ai buchi nella mesh.

Stavo considerando l'algoritmo di tetraedri di marcia, che presumibilmente non soffre di ambiguità. Non riesco a vedere come sia possibile.

L'algoritmo di tetraedri marcia utilizza sei tetraedri al posto di un cubo, con triangolazioni per ogni tetraedro. Ma, supponiamo che dovessi implementare l'algoritmo dei cubi marching, ma per ognuna delle 256 triangolazioni, scegli semplicemente quella che è la "somma" (unione) delle triangolazioni del tetraedro del cubo? Per quanto ne so, questo è ciò che tetraedri marcia fa --quindi Perché che magicamente risolvere le ambiguità?

Ci sono 16 casi unici, penso, e gli altri 240 sono solo riflessioni/rotazioni di quelli 16. Ricordo di aver letto su qualche foglio da qualche parte che per risolvere le ambiguità, sono necessari 33 casi. Questo potrebbe essere collegato al motivo per cui i tetraedoni in marcia non soffrono in qualche modo di problemi?

Quindi, domande:

1. Perché marciare tetraedri non soffre di ambiguità?
2. Se così non fosse, perché non la gente basta usare l'algoritmo marching cubes, ma con triangolazioni tetraedri invece?

mi sento come mi manca qualcosa qui. Grazie.

Answer 1

Ok, ho appena finito di attuazione la mia versione di tetraedri marcia, e mentre io facilmente visto ambiguità portare a problemi di mesh della marching cubes, mesh della tetraedri marcia sembra essere costantemente topologicamente corretto. Lì sono alcune caratteristiche fastidiose lungo punti molto sottili dove alcuni vertici non riescono a decidere quale lato della divisione vogliono essere, ma la rete è sempre a tenuta stagna.

In risposta alle mie domande:

1. Per risolvere ambiguità l'algoritmo marching cubes, per quanto posso dire, si valuta la funzione con più attenzione nella cella. Nell'algoritmo tetraedri, uno campiona esplicitamente il centro della cella e poligonizza a che. Sospetto che, poiché la maglia tetraedrica include in particolare questo vertice, le ambiguità vengono gestite implicitamente. Probabilmente anche gli altri vertici in più sul lato hanno qualcosa a che fare con esso. Come punto chiave, la funzione viene effettivamente campionata in più punti quando si perfeziona.
2. Sono abbastanza sicuro che lo facciano. Il mio algoritmo di tetraedri marcia fa proprio questo, e penso che, internamente, stia facendo la stessa cosa del classico algoritmo di tetraedri in marcia. Nella mia implementazione, i triangoli dei tetraedri sono tutti elencati per ogni possibile cubo, il che, a mio avviso, lo rende più veloce di calcolare individualmente uno o due triangoli per ogni singolo tetraedro.

Se ho avuto il periodo di tempo e l'attenzione (nessuno dei quali faccio io), potrebbe essere utile per ricreare la mesh l'interno di ogni cubo di utilizzare meno triangoli massimo, che io credo non sarebbe male esso.

Answer 2

l'esempio seguente 2d (che introduce ambiguità):

Se dividiamo questo quadrata in due triangoli, otterremo risultati diversi in diagonale abbiamo scelto di dividere la piazza. Lungo la diagonale 0-0, otteniamo triangoli (010,010) mentre per la diagonale 1-1 otteniamo triangoli (101,101). Ovviamente, una diversa scomposizione del quadrato porta a risultati diversi. O è corretto e questo è lo stesso per i cubi 3D.

MT non risolve realmente le ambiguità ma può produrre risultati topologicamente consistenti scegliendo la stessa strategia di scomposizione per tutti i cubi. Che il modo in cui si sbarazza di soffrire di ambiguità.

Answer 3

Per rispondere alla domanda "Perché i tetraedri di Marching lasciano le ambiguità?" è necessario capire perché le ambiguità sorgono in primo luogo nei Cubi Marching.

---

ambiguità può verificarsi quando vi sono due diagonalmente opposti vertici "positivi" e due vertici diagonalmente opposti "negativi" in un cubo. Mi ci è voluto del tempo per avvolgere la mia mente intorno ad esso, ma il problema con le ambiguità è che teoricamente permettono di creare patch isosuperficiali per cubi adiacenti che sono incompatibili tra loro. Questa è la parte ovvia. La parte interessante è che due patch isosurface adiacenti da due configurazioni ambigue sono incompatibili se (e solo se) uno di questi separa i vertici "negativi" e l'altro separa i vertici "positivi".

Ecco una citazione rilevante dal grande libro di Refael Wenger "isosuperfici Geometria, Topologia & algoritmi" (non può inviare più di 2 collegamenti, così mi sono stati presi tutti le immagini rilevanti dal libro in una single one):

il bordo del cerotto isosurface tridimensionale di un cubo definisce una isocontour su ciascuna delle faccette quadrati del cubo. Se la patch isosuperficie di qualche con gurazione separa i vertici negativi sulla faccetta mentre una patch isosuperficie della confinazione separa quelli positivi, allora i bordi di isosurface sulla facc comune non si allineano. Le patch di isosuperficie nella Figura 2.16 non separano i vertici positivi su qualsiasi faccetta. Inoltre, le superfici di superficie isosuperficiale derivate in qualsiasi rotazione o ri fl essione delle con fi gurazioni, inoltre, non rappresentano vertici positivi separati su qualsiasi faccetta. Pertanto i patch di isosuperficie in qualsiasi due cubi adiacenti sono allineati correttamente sui loro confini. Un ugualmente valido, ma la tabella isosuperficiale distinta combinatoria potrebbe essere generata utilizzando le patch isosuperficie che non separano i vertici negativi su qualsiasi faccetta quadrata.

Ciò significa che se tutti configurazioni ambigue utilizzati seguono lo stesso modello (cioè sempre separati vertici "negativi"), allora è impossibile produrre una superficie topologicamente corretto. E i problemi sorgono se si utilizzano le configurazioni "di entrambi i mondi" per una singola isosuperficie.

La superficie che è stato costruito secondo la stessa sequenza risoluzione dell'ambiguità ancora possono contenere errori indesiderati come this (tratto da "Efficient attuazione dei casi da Marcia cubi garanzie topologici" articolo di Thomas Lewiner Helio Lopes, Antonio Wilson Vieira e Geovan Tavares), ma sarà, come hai detto, stagna.

Per ottenere ciò, è necessario utilizzare la tabella di look-up basato su 22 configurazioni uniche (non lo standard 14 o 15) mostrato in Figura 2.16.

---

Ora, tornando alla domanda iniziale, finalmente - Perché Marching tetraedri non soffre di ambiguità? Per lo stesso motivo non ci saranno ambiguità nei Cubi in marcia, se fatto come descritto sopra - perché hai arbitrariamente scelto di usare una delle due varianti disponibili di ambigua risoluzione di configurazione. In Marching Cubes non è evidente a tutti (almeno per me, ha dovuto fare un sacco di scavare) che questo è nemmeno un'opzione, ma in Marcia tetraedri è fatto per voi dallo stesso algoritmo. Ecco un'altra citazione dal libro di Refael Wenger:

I cubi griglia regolare hanno ambigui configurazioni fi mentre il decomposizione tetraedrica non lo fa. Cosa è successo alle ambigue configurazioni ? Queste con fi gurazioni vengono risolte dalla scelta della triangolazione . Ad esempio, nella Figura 2.31, la prima triangolazione fornisce una patch isosurface con due componenti corrispondenti a 2B-II nella Figura 2.22 mentre la seconda dà una patch isosurface con un componente corrispondente a 2B-I.

Nota come i cubi sono suddivisi in tetraedri in due modi diversi nella Figura 2.31. La scelta di questo affettare o l'altro è la salsa segreta che risolve le ambiguità.

Ci si potrebbe chiedere: se il problema dell'ambiguità può essere risolto utilizzando lo stesso modello per tutti i cubi, perché ci sono così tanti libri e documenti su soluzioni più complicate? Perché ho bisogno di Asymptotic Decider e tutta quella roba? Per quanto posso dire, tutto si riduce a ciò che è necessario raggiungere. Se la correttezza topologica (come in, nessun buco) è sufficiente per te, allora non hai bisogno di tutte le cose avanzate. Se si vuole risolvere i problemi come quelli mostrati in "efficace attuazione del Marching Cubes" articolo mostrato sopra, allora avete bisogno di immergersi a profondità.

mi raccomando di leggere i capitoli del libro di Refael Wenger "isosuperfici Geometria, Topologia & Algoritmi" per capire meglio la natura di questi algoritmi, quali sono i problemi, da dove i problemi provengono e come possono essere risolto.

Come ricordato da Li Xiaosheng, le basi possono essere meglio compresi dalla esaminando attentamente le Piazze Marching algo prima. In realtà, l'intera risposta è stata dettata da Li Xiaosheng, ho appena espanso un po 'le spiegazioni.