¿Cómo acelerar los cubos de marcha?

Question

Estoy usando this marching cube algorithm para dibujar isosuperficies 3D (portado en C#, dando como resultado MeshGeomtry3D s, pero por lo demás lo mismo). Las superficies resultantes se ven muy bien, pero tardan mucho tiempo en calcularse.

¿Hay alguna forma de acelerar la marcha de los cubos? El más obvio es simplemente reducir la tasa de muestreo espacial, pero esto reduce la calidad de la malla resultante. Me gustaría evitar esto.

Estoy considerando un sistema de dos pasos, donde el primer pase muestrea el espacio mucho más grueso, eliminando volúmenes donde la intensidad del campo está muy por debajo de mi nivel iso. ¿Es esto sabio? ¿Cuáles son las trampas?

Editar: el código se ha perfilado, y la mayor parte del tiempo de CPU se divide entre la rutina de cubos de marcha y el cálculo de intensidad de campo para cada esquina de celda de la grilla. Los cálculos de campo están fuera de mi control, por lo que agilizar la rutina de cubos es mi única opción ...

Todavía me atrae la idea de intentar eliminar el espacio muerto, ya que esto reduciría el número de llamadas a ambos sistemas considerablemente.

Answer 1

Sé que esto es un poco viejo, pero recientemente implementé Marching Cubes basado en la misma fuente. Hay MUCHA ineficiencia aquí. Como mínimo si estuviera haciendo algo así como

for (int x=0; x<densityArrayWidth; x++) 
    for (int z=0; z<densityArrayLength; z++) 
    for (int y=0; y<densityArrayHeight; y++) 
     Polygonize(Gridcell, isolevel, Triangles) 

vistazo a la cantidad de veces que estaría reasignación de la edgeTable y titulable! Aquellos inmediatamente necesitan mudarse a la clase general. También abandoné el objeto gridCell, yendo directamente de los puntos/valores a los triángulos.

En resumen, no es sólo la complejidad algorítmica, las asignaciones de memoria (y en la base esto hace una gran cantidad de ellas) también toman tiempo.

Answer 2

Por si acaso alguien termina aquí, la eliminación de espacio muerto a través de una tasa de muestreo más gruesa hace que virtualmente no tenga ninguna diferencia. Cualquier remotamente segura (es decir, que permita un borde para artefactos de muestreo), el muestreo más grueso termina capturando la mayor parte de la cuadrícula en cualquier campo remotamente no trivial.

Agilizar la evaluación del campo subyacente (con mucha memoria) parecía en su mayoría resolver los problemas de rendimiento.

Answer 3

Intente marchar tetraedros en su lugar - la matemática es más simple, lo que le permite considerar menos casos por celda.

Answer 4

cada cubo tiene 12 aristas, si revisas cada cubo y encuentras 12 puntos de intersección, estás haciendo 4 veces más cálculos para los puntos de intersección; solo tienes que usar 3 aristas en la esquina inferior izquierda de cada cubo, con una fila adicional en la esquina superior derecha de la zona, y luego use una actualización especial para acceder a todos los valores que ha encontrado. Voy a hacer un tema sobre esto porque necesita ser discutido y es complicado.

También, probando áreas en el espacio que necesitan polígonos, evaluando el nivel ISO usando Octree, y omitiendo áreas lejos del nivel ISO.

Eché un vistazo a la propagación, pero no es tan confiable y eficiente.