Общий алгоритм вопроса

Предположим, у нас есть какая-то сетка (см. Иллюстративную картинку из CorelDraw, которая использует ту же технику в инструменте "Заполнение сетки").

http://www.sonic.net/mnitepub/pccafe/reviews/coreldraw9/meshfill.jpg

Очевидно, этот тип сетки представлен набором точек, и линии между ними фактически определяются с использованием этого набора точек (возможно, каким-то образом интерполированных). Этот инструмент также имеет кнопки для увеличения разрешения сетки.

Мой вопрос заключается в следующем - как такие вещи вычисляются? Предположим, у меня есть некоторый набор точек, которые фактически представляют сетку (для простого случая давайте даже предположим, что точки на "границе" являются статическими и не могут двигаться). И я хочу увеличить разрешение сетки, например, в 4 раза (чтобы число точек сетки фактически становилось 4 * initial_points_count).

Как мне рассчитать расположение новых точек, если единственными данными, которые у меня есть, является матрица исходных точек?

Мне бы подошел самый быстрый (даже приблизительный) метод, но я не знаю, где искать или как разработать такой алгоритм.

Спасибо.

Источник

5 ответов

Решение

Я бы начал с добавления точек на полпути по всем линиям путем интерполяции (кривые на рисунке, скорее всего, являются кривыми Безье какого-то рода, поэтому я бы интерполировал их как таковые или использовал двухполюсную интерполяцию, как предлагал Мау) и помещая новые точки на полпути между старые, давая мне 3 раза разрешение. Затем я интерполировал бы между этими новыми точками (в обоих направлениях, если точность является ключевой) и помещал новую точку на пересечении (или на полпути). Смотрите "иллюстрацию" ниже.

Initial state  =>  Interpolate  =>  Place points  =>  Interpolate => Final state
  x       x         x-------x        x   x   x         x   x   x      x   x   x
                    |       |                              |    
                    |       |        x       x         x---+---x      x   x   x
                    |       |                              |
  x       x         x-------x        x   x   x         x   x   x      x   x   x
Источник

Комментарии к существующим ответам:

Мне кажется, что ответ Мау и Мартиента описывает решение проблемы аппроксимации известной формы с помощью многоугольной сетки (а у вас нет известной формы).

Алгоритм, который упоминает Дейв, сгладит любую форму, но не обязательно по назначению.

Если вы посмотрите на ответ You, то увидите, что новые точки появляются в результате линейной интерполяции между точками, и, если это достаточно хорошо для вас, все решения сравнимы (кроме решения Дейва).

Такое увеличение плотности сетки не сделает полученную сетку более привлекательной - более похожей на первоначальную форму. Если этого недостаточно, то сначала вы должны решить, какую именно форму / форму вы пытаетесь представить с помощью сетки (если вы могли бы расширить свой пример, это могло бы быть немного более очевидным; этот инструмент создает только круговые сетки). или это может принять любую форму и "заполнить петлей" это?).

Кроме того, вы должны заметить, что вы работаете не с полигональной сеткой, а с сеткой кривых (возможно, безье), что является еще одной причиной, по которой некоторые ответы не будут напрямую относиться к вашей проблеме.

РЕДАКТИРОВАТЬ: После более внимательного изучения того, как corel делает это, и предположения, что вы действительно знаете кривые, а не только точки (!):

  • Вы начинаете с набора кривых, и мне кажется, что у вас есть горизонтальные и вертикальные кривые для начала
  • Если вы хотите увеличить разрешение (например, разрешение по горизонтали), вы можете взять две последовательные вертикальные кривые и разделить каждый сегмент горизонтальных кривых, через которые они проходят, в средней точке, создавая таким образом набор точек, которые определяют новую кривую; Вы также можете интерполировать угол, под которым кривая проходит через точку

http://img706.imageshack.us/img706/5693/path5818.png

На приведенном выше (нарисованном вручную) рисунке показаны попытки проиллюстрировать а) добавление новой кривой (красной), которую вы бы сгенерировали таким образом. б) добавление линейно-интерполированной полилинии (синего цвета), которая больше подходит для подхода с использованием многоугольной сетки (так что вы можете судить, приемлемо ли это для вас)

Примечание. В зависимости от алгоритма, для которого вы готовите сетку, вы можете иметь или не иметь никаких преимуществ, рассматривая линии сетки как кривые (разница между решениями красного и синего может быть незначительной для одного алгоритма и важной для другого). Если алгоритм просто ожидает точки, то вам также следует посмотреть, как аппроксимировать кривые Безье с точками (чтение этого может помочь; хотя вам не нужна точность в пикселях).

Для достижения максимальной точности / наилучших результатов вы должны сначала увеличить плотность кривых и приблизить их с помощью линий.

Источник

Вы смотрели на подразделение? Должно работать для уточнения таких сеток.

Источник

То, что вы ищете, это алгоритм сглаживания сетки. К сожалению, у меня нет никаких ресурсов под рукой, поэтому я могу только предложить Google для "сглаживания сетки". Это огромное поле.

РЕДАКТИРОВАТЬ

Вот краткий обзор нескольких методов / алгоритмов для достижения сглаживания сетки: http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf

Источник

Похоже, работа для билинейной интерполяции (где система координат находится на поверхности сферы).

Источник
Другие вопросы по тегам