Как вычислить местоположения сетчатых точек, когда разрешение увеличено?
Предположим, что у нас есть некоторая сетка (см. изображение иллюстрирования от CorelDraw, который использует ту же технику в инструменте "Сетчатой заливки").
(источник: sonic.net)
Очевидно, этот вид сетки представлен рядом точек, и строки между ними на самом деле определяются с помощью того набора точек (вероятно, так или иначе интерполированный). Этот инструмент также имеет кнопки для увеличения сетчатого разрешения.
Мой вопрос следующий - как такой вид вещей вычисляется? Предположим, что у меня есть некоторый набор точек, которые на самом деле представляют сетку (для легкого случая, давайте даже примем, это указывает на "границе", статичны и не может переместиться). И я хочу увеличить сетчатое разрешение, например, в 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
Вы смотрели на подразделы? Должно сработать для уточнения таких сеток.
Вам нужен алгоритм сглаживания сетки. К сожалению, у меня нет никаких ресурсов, поэтому я могу предложить Google только для «сглаживания сетки». Это огромное поле.
РЕДАКТИРОВАТЬВот хороший краткий обзор пары методов / алгоритмов для достижения сглаживания сетки: http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf
Похоже на задание для Билинейной интерполяции (где система координат находится на поверхность сферы).
Комментарии к существующим ответам:
Мне кажется, что ответы Мау и martient'а описывают решение проблемы аппроксимации известной формы с помощью полигональной сетки (а у вас нет известной формы).
Алгоритм, о котором упоминает Дейв, сгладит любую форму, но не обязательно так, как задумано.
Если вы посмотрите на ответ You's, то увидите, что новые точки получаются в результате линейной интерполяции между точками, и если это достаточно хорошо для вас, то все решения сравнимы (кроме решения Дейва).
Такое увеличение плотности сетки не сделает полученную сетку более "красивой" - более похожей на исходную форму. Если этого недостаточно, то вам сначала нужно решить, какую форму/фигуру вы пытаетесь изобразить с помощью сетки (если бы вы могли расширить ваш пример, это могло бы быть немного более очевидно; этот инструмент создает только круговые сетки или он может взять любую форму и "заполнить" ее сеткой).
Также следует заметить, что вы работаете не с полигональной сеткой, а с сеткой кривых (вероятно, безье), что является еще одной причиной, по которой некоторые ответы не будут напрямую относиться к вашей проблеме.
EDIT: После более детального изучения того, как corel делает это, и предполагая, что вы действительно знаете кривые, а не только точки(! ):
- Вы начинаете с набора кривых, и мне кажется, что у вас есть горизонтальные и вертикальные кривые для начала
- Если вы хотите увеличить разрешение (например, горизонтальное разрешение), вы можете взять две последовательные вертикальные кривые и разделить каждый сегмент горизонтальных кривых, через которые они проходят, в средней точке, создавая набор точек, которые определяют новую кривую; вы также можете интерполировать угол, под которым кривая проходит через точку
alt text http://img706. imageshack.us/img706/5693/path5818.png
Приведенный выше (нарисованный вручную) рисунок пытается проиллюстрировать a) добавление новой кривой (красной), которую можно сгенерировать таким образом. b) добавление линейно интерполированной полилинии (синяя), которая больше подходит к подходу полигональной сетки (так что вы можете судить, приемлемо ли это для вас)
Примечание: В зависимости от алгоритма, для которого вы готовите сетку, вы можете иметь или не иметь никаких преимуществ в рассмотрении линий сетки как кривых (разница между красным и синим решениями может быть незначительной для одного алгоритма и важной для другого). Если алгоритм просто ожидает точки, то вам также следует посмотреть, как аппроксимировать кривые Безье точками (чтение здесь может помочь; хотя вам не нужна пиксельная точность).
Для достижения максимальной точности/лучших результатов следует сначала увеличить плотность кривых, а затем аппроксимировать их линиями.