Dibujando una línea iso de un campo escalar implícito 2D

Question

Tengo un campo escalar implícito definido en 2D, por cada punto en 2D puedo hacer que calcule un valor escalar exacto, pero es un cálculo algo complejo.
Me gustaría dibujar una línea iso de esa superficie, digamos la línea del valor '0'. La función en sí es continua, pero la línea iso '0' puede tener múltiples instancias continuas y no se garantiza que todas estén conectadas.
Calcular el valor para cada píxel no es una opción porque tomaría mucho tiempo, en el orden de unos pocos segundos, y esto debe ser lo más real posible.

Lo que estoy usando actualmente es una división recursiva del espacio que puede considerarse como una especie de árbol cuádruple. Tomo una muestra inicial muy gruesa del espacio y si encuentro un cuadrado que contiene una transición de valores positivos a negativos, lo divido recursivamente en 4 cuadrados más pequeños y los verifico nuevamente, deteniéndome en el nivel de píxeles. La transición positiva-negativa se detecta mediante el muestreo de un cuadrado en sus 4 esquinas. Esto funciona bastante bien, excepto cuando no lo hace. Las iso-líneas que se dibujan a veces se cortan porque la detección de transición falla para las transiciones que ocurren en un área pequeña de un borde y que no se cruzan en una esquina de un cuadrado.

¿Hay una mejor manera de hacer un dibujo de iso-línea en esta configuración?

Answer 1

He tenido mucho éxito con los algoritmos descritos aquí http://web.archive.org/web/20140718130446/http://members.bellatlantic.net/~vze2vrva/thesis.html que analizan el contorno adaptativo (similar al que usted describe), y también algunos otros problemas con el trazado de contornos en general.

No hay una manera general de garantizar la búsqueda de todos los contornos de una función, sin mirar cada píxel. Podría haber un contorno cerrado muy pequeño, donde una región solo tiene el tamaño de un píxel en el que la función es positiva, en una región donde la función es generalmente negativa. A menos que muestre con la suficiente precisión que coloca una muestra dentro de la región positiva, no hay una forma general de saber que está allí.

Si su función es lo suficientemente suave, puede adivinar dónde se encuentran los contornos cerrados tan pequeños, porque el módulo de la función se reduce en una región que los rodea. El muestreo podría entonces refinarse solo en estas regiones.