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

Question

Предположим, что у нас есть сетка (см. Иллюстрацию изображения от CorelDraw, которая использует ту же технику в «Mesh fill»).

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

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

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

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

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

спасибо.

Answer 1

Я хотел бы начать, добавив на полпути точек на все линии интерполяции (кривые на рисунке являются скорее всего, Bézier curves, поэтому я бы интерполировал их как таковые или использовал билинейную интерполяцию, как предположил Мау) и помещая новые точки на полпути между старыми, давая мне 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 

Answer 2

Звучит как работа для Bilinear Interpolation (где система координат находится на поверхности сферы).

Answer 3

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

Answer 4

Что вы ищете - это гладкий алгоритм сетки. К сожалению, у меня нет никаких ресурсов, поэтому я могу предложить google для «сглаживания сетки». Это огромная область.

EDIT

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

Answer 5

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

Мне кажется, что Мау и ответ martient описывают решение задачи аппроксимации известной формы с polygon mesh (и не имеют известную форму) ,

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

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

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

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

EDIT: После присмотревшись о том, как Corel делает это и при условии, что вы на самом деле знаете, кривые не только точки (!):

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

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

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

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

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