Методы реализации контурной прорисовки - PullRequest
Новая
       13

Методы реализации контурной прорисовки

3 голосов
/ 30 ноября 2010

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

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

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

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

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

Ответы [ 4 ]

5 голосов
/ 11 января 2011

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

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

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

2 голосов
/ 30 ноября 2010

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

1 голос
/ 15 января 2011

Позвольте мне предложить самый простой метод: подумайте, что вы должны найти контур 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]))
c '[k] = v [i] * (1-t) + v [j] * t

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

0 голосов
/ 08 июня 2011

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

...