Dessiner une ligne iso d'un champ scalaire implicite 2D

Question

J'ai un champ scalaire implicite défini en 2D, pour chaque point en 2D je peux lui faire calculer une valeur scalaire exacte mais c'est un calcul un peu complexe.
Je voudrais dessiner une iso-ligne de cette surface, disons la ligne de la valeur '0'. La fonction elle-même est continue mais l'iso-ligne '0' peut avoir plusieurs instances continues et il n'est pas garanti que toutes les connexions soient connectées.
Le calcul de la valeur pour chaque pixel n'est pas une option car cela prendrait trop de temps - de l'ordre de quelques secondes et cela doit être aussi vrai que possible.

Ce que j'utilise actuellement est une division récursive de l'espace qui peut être considérée comme une sorte de quad-tree. Je prends un premier échantillonnage très grossier de l'espace et si je trouve un carré qui contient une transition des valeurs positives aux valeurs négatives, je le divise récursivement en 4 petits carrés et vérifie à nouveau, en s'arrêtant au niveau du pixel. La transition positive-négative est détectée en échantillonnant un sqaure dans ses 4 coins. Cela fonctionne assez bien, sauf quand ce n'est pas le cas. Les iso-lignes qui sont dessinées sont parfois coupées parce que la détection de transition échoue pour des transitions qui se produisent dans une petite zone d'un bord et qui ne traversent pas un coin d'un carré.

Existe-t-il une meilleure façon de faire un dessin iso-line dans ces paramètres?

Answer 1

J'ai eu beaucoup de succès avec les algorithmes décrits ici http://web.archive.org/web/20140718130446/http://members.bellatlantic.net/~vze2vrva/thesis.html qui discutent de contour adaptatif (similaire à celui que vous décrivez), et aussi d'autres problèmes avec le tracé de contour en général.

Il n'y a pas de façon générale de garantir la recherche de tous les contours d'une fonction sans regarder chaque pixel. Il pourrait y avoir un très petit contour fermé, où une région ne serait que de la taille d'un pixel où la fonction est positive, dans une région où la fonction est généralement négative. Sauf si vous échantillonnez finement que vous placez un échantillon dans la région positive, il n'y a pas de moyen général de savoir qu'il est là. Si votre fonction est assez lisse, vous pouvez deviner où se trouvent ces petits contours fermés, car le module de la fonction devient petit dans une région qui les entoure. L'échantillonnage pourrait alors être affiné dans ces régions seulement.