Рисование изо-линии двумерного неявного скалярного поля

Question

У меня есть неявное скалярное поле, определенное в 2D, для каждой точки в 2D я могу заставить его вычислить точное скалярное значение, но это довольно сложное вычисление.
Я хотел бы нарисовать изо-линию этой поверхности, скажем, линию значения «0». Сама функция является непрерывной, но изо-линия '0' может иметь несколько непрерывных экземпляров, и не гарантируется, что все они связаны.
Вычисление значения для каждого пикселя не вариант, потому что это займет слишком много времени - порядка нескольких секунд, и это должно быть как можно в реальном времени.

В настоящее время я использую рекурсивное деление пространства, которое можно рассматривать как своего рода квад-дерево. Я беру первоначальную, очень грубую выборку пространства и, если я нахожу квадрат, содержащий переход от положительных к отрицательным значениям, я рекурсивно делю его на 4 меньших квадрата и снова проверяю, останавливаясь на уровне пикселей. Положительно-отрицательный переход обнаруживается путем выборки квадратуры в четырех углах. Это работает довольно хорошо, за исключением случаев, когда это не так. Рисованные изо-линии иногда обрезаются, потому что не удается обнаружить переходы для переходов, которые происходят в небольшой области ребра и не пересекают угол квадрата.

Есть ли лучший способ сделать изо-линию в этих настройках?

Answer 1

У меня был большой успех с алгоритмами, описанными здесь http://web.archive.org/web/20140718130446/http://members.bellatlantic.net/~vze2vrva/thesis.html которые обсуждают адаптивное контурирование (аналогично тому, которое вы описываете), а также некоторые другие вопросы с контурным построением в целом.

Нет общего способа гарантировать нахождение всех контуров функции, не глядя на каждый пиксель. Там может быть очень маленький замкнутый контур, где область только размером с пиксель, где функция положительная, в области, где функция, как правило, отрицательная. Если вы не произведете достаточно точную выборку, чтобы поместить образец в положительную область, нет никакого общего способа узнать, что она есть.

Если ваша функция достаточно гладкая, вы можете догадаться, где лежат такие маленькие замкнутые контуры, потому что модуль функции становится небольшим в области, окружающей их. Затем выборка может быть уточнена только в этих регионах.