Способы реализации контурной графики

Question

Мне нужно реализовать алгоритм построения контура (в отличие от его использования). Ввод представляет собой (непрерывную) функцию f: R^2 -> R (функция определена по всей области, а не только для определенных входов). Выход должен быть в векторном виде, то есть в наборе сплайнов или сегментов линии.

Я ищу рекомендации относительно того, как реализовать это, предпочтительно в виде (научных) документов.

Я нашел несколько ссылок на алгоритмы, разработанные в 80-х годах («Алгоритм отслеживания уровня»). Были ли какие-либо разработки в этой области за последние 30 лет? Каков стандартный метод (ы), используемый для решения этой проблемы?

Алгоритм будет использоваться для визуализации в реальном времени, поэтому он должен быть быстрым, сохраняя при этом достойные результаты.

(Small, самодостаточная и хорошо протестированы реализации C/C++ будет приветствоваться, а также.)

Answer 1

См, например xfarbe.

Answer 2

Я вспоминаю TI-89 калькулятор использовал очень простую схему, как это:

• сделать сетку, эксперимент с размером ячеек
• Рассчитайте вашу функцию в каждой вершине сетки
• Для каждого квадрат, если есть два значения f с разными знаками, внутри есть что-то интересное. Предположим, что это так:
  • Для каждой «интересной» стороны квадрата (f имеет разные знаки в конечных точках), найдите нуль f на стороне путем деления пополам (или путем линейной интерполяции, если вы по низкому бюджету). Могут быть две или четыре интересные стороны.
  • Если есть две интересные стороны, нарисуйте прямую линию между нулевыми точками.
  • Если есть четыре интересные стороны, нарисуйте крест.

Теперь вы можете уточнить интересные квадраты adaptatively. У TI-89 был проклятый маленький экран (160x120), и это не было необходимо. Точный же метод можно использовать внутри интересного квадрата.

Answer 3

Могу ли я предложить самый простой метод: подумайте, что вы должны найти контур f(x,y) = Z для определенного Z. Тогда семя вашего поля сюжета, D = subset(RxR) с сеткой равностороннего треугольника сетки вершин и ребер, M = (V,E,r), где M - сеткой, V -множества вершин, E - множество ребер, r - треугольник с длиной стороны, в level of detail, LOD. Затем для каждой вершины в V вычислите значение f. Тогда для каждого ребра в E, проверьте, если ребро (e[k]) имеет значение f на его вершинах (v[i] и v[j], например) на разных сторонах о Z, то есть, если f(v[i])>Z и f(v[j])<Z.Если да, то, чем линия контура f(x,y) = Z пересекает эту кромку e[k] в определенной точке (c[k]), который может быть линейно аппроксимирована:

T = (F (V [I]) - Z)/(F (v [I]) - F (V [J]))
с '[к] = V [I] * (1-т) + V [J] * т

в треугольнике с одним пересечение контура края имеет второе пересечение на некоторых из оставшихся двух ребер (доказательство тривиально), получаем второй c'[k]. Таким образом, для каждого треугольника от M мы имеем либо ни один, ни один сегмент линии, аппроксимирующий контурную линию. Рисование всех найденных сегментов предоставит нам приблизительный контурный график f(x,y)=Z с определенным уровнем детализации r. Опускание r будет производить более тонкие контуры, повышение r даст представление.

Answer 4

Я думаю, вам нужно создать массивы данных f [i, j] для вашей функции в некоторой сетке, собрать сегмент линии из каждой ячейки и связать их позже с кривой (-ами). Вы должны иметь в виду возможные круги (т. Е. Наличие нескольких замкнутых кривых в сетке). Именно этот алгоритм используется в MathGL (кросс-платформенная библиотека построения GPL) - см. Реализацию функции mglGraph :: Cont().