Dessin d'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 assez 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-line '0' peut avoir plusieurs instances continues et il n'est pas garanti que toutes soient connectées.
Calculer la valeur de chaque pixel n'est pas une option, car cela prendrait trop de temps, de l'ordre de quelques secondes, et ce doit être aussi réel que possible.

Ce que je suis en train d’utiliser est une division récursive de l’espace qui peut être considérée comme une sorte de quad-tree. Je réalise un premier échantillonnage très grossier de l'espace et si je trouve un carré contenant une transition de valeurs positives à négatives, je le divise récursivement en 4 carrés plus petits et vérifie à nouveau, en m'arrêtant au niveau des pixels. La transition positive-négative est détectée en échantillonnant une place dans ses 4 coins. Cela fonctionne assez bien, sauf quand ça ne marche pas. Les iso-lignes tracées sont parfois coupées parce que la détection de transition échoue pour les transitions qui se produisent dans une petite zone d'un bord et qui ne traversent pas un coin d'un carré.

Existe-t-il un meilleur moyen de tracer des lignes iso 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 traitent du contournement adaptatif (similaire à celui que vous décrivez), ainsi que d’autres problèmes liés au tracé des contours en général.

Il n’existe aucun moyen général de garantir la recherche de tous les contours d’une fonction sans examiner chaque pixel. Il pourrait y avoir un très petit contour fermé, où une région seulement 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 suffisamment finement pour placer un échantillon dans la région positive, il n'existe aucun moyen général de savoir qu'il est présent.

Si votre fonction est suffisamment fluide, vous pourrez peut-être deviner où se trouvent de si petits contours fermés, car son module devient petit dans une région les entourant. L'échantillonnage pourrait ensuite être affiné dans ces régions uniquement.