Ambigüedades de cubo de marcha versus Tetraedro de marcha

Question

He implementado con éxito el algoritmo de cubos de marcha. Usé los materiales estándar como referencia, pero lo reescribí completamente desde cero. Funciona, pero estoy observando las ambigüedades que conducen a los agujeros en la malla.

Estaba considerando el algoritmo de los tetraedros de marcha, que supuestamente no sufre de ambigüedades. No veo cómo esto es posible.

El algoritmo de los tetraedros marcha utiliza seis tetraedros en lugar de un cubo, con triangulaciones para cada tetraedro. Pero, supongamos que tuviera que implementar el algoritmo de los cubos de marcha, pero para cada una de las 256 triangulaciones, simplemente elija la que es la "suma" (unión) de las triangulaciones del tetraedro del cubo. Por lo que yo sé, esto es lo que marcan los tetraedros - entonces, ¿por qué se arreglan mágicamente las ambigüedades?

Hay 16 casos únicos, creo, y los 240 otros son solo reflejos/rotaciones de esos 16. Recuerdo haber leído en un periódico en alguna parte que para resolver ambigüedades, necesitas 33 casos. ¿Podría esto estar relacionado con por qué los tetraedros marchando de alguna manera no sufren problemas?

Por lo tanto, las preguntas:

1. ¿Por qué marchar tetraedros no sufren de ambigüedades?
2. Si no es así, ¿por qué la gente no usa el algoritmo de los cubos de marcha, sino las triangulaciones de los tetraedros?

Siento que me falta algo aquí. Gracias.

Answer 1

Está bien, acabo de terminar de implementar mi versión de tetraedros marchando, y aunque vi fácilmente que las ambigüedades generan problemas en la malla de los cubos de marcha, la malla de los tetraedros parece ser consistentemente correcta desde el punto de vista topológico. Hay son algunas características molestas a lo largo de puntos muy delgados donde algunos vértices no pueden decidir en qué lado de la división quieren estar, pero la malla siempre es hermética.

En respuesta a mis preguntas:

1. Para resolver ambigüedades en el algoritmo de marching cubes, por lo que yo puedo decir, se evalúa la función con más cuidado en la célula. En el algoritmo de tetraedros, uno muestrea explícitamente el centro de la celda y poligonaliza a que. Sospecho que debido a que la malla tetraédrica incluye este vértice en particular, las ambigüedades se manejan implícitamente. Los otros vértices adicionales del lado probablemente también tengan algo que ver con eso. Como punto clave, la función se está muestreando en más lugares cuando vaya a refinarla.
2. Estoy bastante seguro de que lo hacen. Mi algoritmo de tetraedros de marcha hace precisamente eso, y creo que, internamente, está haciendo lo mismo que el algoritmo clásico de tetraedros de marcha. En mi implementación, los triángulos de los tetraedros están listados para cada cubo posible, lo que sospecho lo hace más rápido que imaginar uno o dos triángulos para cada tetraedro individualmente.

Si tuviera el lapso de tiempo y la atención (ninguno de los cuales yo), que podría ser beneficioso para mallar el interior de cada cubo para usar menos triángulos máximo, lo que me que no estaría de él.

Answer 2

Tome el siguiente ejemplo 2d (que introduce ambigüedades):

Si dividimos esta plaza en dos triángulos, obtendremos resultados diferentes en la diagonal se optó por dividir la plaza. A lo largo de 0-0 diagonal, obtenemos triángulos (010,010) mientras que para la diagonal 1-1, obtenemos triángulos (101,101). Obviamente, diferentes descomposiciones de cuadrados conducen a resultados diferentes. O bien es correcto y esto es lo mismo para cubos 3D.

MT no resuelve las ambigüedades en realidad pero puede producir un resultado consistentemente topológico eligiendo la misma estrategia de descomposición para todos los cubos. Esa es la forma en que se deshace del sufrimiento de las ambigüedades.

Answer 3

Para responder a la pregunta "¿Por qué Marching Tetrahedrons algo tiene ambigüedades?" se requiere entender por qué surgen las ambigüedades en primer lugar en Marching Cubes.

---

Las ambigüedades se puede producir cuando hay dos vértices diagonalmente opuestos "positivas" y dos vértices diagonalmente opuestos "negativas" en un cubo. Me tomó un tiempo entenderlo, pero el problema con las ambigüedades es que teóricamente permiten crear parches isosuperficiales para cubos adyacentes que son incompatibles entre sí. Esa es la parte obvia. La parte interesante es que dos parches isosuperficiales adyacentes de dos configuraciones ambiguas son incompatibles si (y solo si) uno de ellos separa los vértices "negativos", y el otro separa las verticidades "positivas".

Aquí es una cita relevante desde el gran libro de Rephael Wenger "Isosuperficies Geometría, Topología & Algoritmos" (No puede enviar más de 2 enlaces, por lo que hemos fusionado todas las imágenes relevantes del libro en una single one):

la frontera de parche isosurface tridimensional de un cubo define un isocontorno en cada una de las facetas cuadrados del cubo. Si el parche superficial de la configuración de alguna configuración separa los vértices negativos de la faceta, mientras que un parche isosuperficie de la configuración adyacente separa los positivos, , entonces los bordes isosuperficiales en la faceta común no se alinearán. Los parches isosuperficiales en la Figura 2.16 no separan los vértices positivos en ninguna faceta. Además, los parches de la superficie isosuperficial derivada en cualquier rotación o reflexión de las configuraciones tampoco son vértices positivos separados en ninguna faceta. Por lo tanto, los parches isosuperficiales en dos cubos adyacentes están alineados correctamente en sus límites. Una tabla isosurface igualmente válida, pero combinatoriamente distinta, puede ser generada mediante el uso de parches isosuperficiales que no separan los vértices negativos en cualquier faceta cuadrada.

Lo que esto significa es que si todos configuraciones ambiguos utilizados siguen el mismo patrón (es decir, siempre separados vértices "negativas"), entonces es imposible para producir una superficie topológicamente incorrecta. Y surgirán problemas si usa configuraciones "de ambos mundos" para una única superficie terrestre.

La superficie que se construyó utilizando el mismo patrón de resolución de ambigüedad todavía pueden contener errores no deseados como this (tomado de "La ejecución eficiente de los casos Marching Cubes' con garantías topológicos" artículo de Thomas Lewiner Helio Lopes, Antonio Wilson Vieira y Geovan Tavares), pero será, como usted dijo, hermético.

Para lograr esto, deberá usar la tabla de búsqueda basada en las 22 configuraciones únicas (no las estándar 14 o 15) que se muestran en la Figura 2.16.

---

Ahora, de vuelta a la pregunta original, por fin, ¿por qué Marching Tetrahedrons no sufre de ambigüedades? Por la misma razón, no habrá ambigüedades en los Cubos de marcha, si se hace como se describió anteriormente, porque usted elige arbitrariamente usar una de las dos variantes disponibles de resolución de configuración ambigua. En Marching Cubes no es del todo obvio (al menos para mí, tuve que investigar mucho) que esta es incluso una opción, pero en Marching Tetrahedrons está hecho para ti por el algoritmo en sí. Aquí hay otra cita del libro de Rephael Wenger:

Los cubos de malla regular tienen configuraciones fi ambiguas mientras que el descomposición tetraédrica no lo hace. ¿Qué pasó con las configu- raciones ambiguas? Estas configuraciones se resuelven mediante la opción de triangulación . Por ejemplo, en la figura 2.31, la primera triangulación proporciona un parche isosuperficie con dos componentes correspondientes a 2B-II en la figura 2.22, mientras que el segundo da un parche isosuperficie con un componente correspondiente a 2B-I.

Observe cómo los cubos se cortan en tetraedros de dos maneras diferentes en la Figura 2.31. La elección de este corte o el otro es la salsa secreta que resuelve las ambigüedades.

Uno se puede preguntar a sí mismo: si el problema de ambigüedad puede resolverse simplemente utilizando el mismo patrón para todos los cubos, ¿por qué hay tantos libros y artículos sobre soluciones más complicadas? ¿Por qué necesito Asymptotic Decider y todo eso? Por lo que puedo decir, todo se reduce a lo que necesita lograr. Si la corrección topológica (como en, sin agujeros) es suficiente para ti, entonces no necesitas todas las cosas avanzadas. Si desea resolver problemas como los que se muestran en el artículo "Implementación eficiente de los cubos de marcha" que se muestra arriba, debe profundizar más.

recomiendo encarecidamente la lectura de los capítulos correspondientes del libro de Rephael Wenger "Isosuperficies Geometría, Topología & Algoritmos" para comprender mejor la naturaleza de estos algoritmos, ¿cuáles son los problemas, lugar en el que los problemas vienen y cómo pueden ser resuelto

Como lo señaló Li Xiaosheng, los fundamentos se pueden entender mejor examinando cuidadosamente el algoritmo Marching Squares primero. En realidad, Li Xiaosheng me recomendó toda la respuesta. Acabo de ampliar un poco las explicaciones.