Генерация поверхности по изолиниям

[Marchtomcat]

Имеется набор точек в пространстве (x,y,z), которые задают поверхность земли. Пусть XY - плоскость земли ,а Z - высота, т.е. Z - функция от (x,y). Задача - найти значение Z в произвольной точке (x,y). Исходные точки могут быть как отдельными, так и объединены в последовательности, которые задают изолинии (точки с одинаковой высотой).

Расскажу как решал задачу.

1. По исходному набору точек строится триангуляция - то есть область разбивается на треугольники. Потом линейной интерполяцией можно найти значение высоты в любой точке. Результат был не очень - на ребрах треугольников естественно были видны изломы, т.е. поверхность не была гладкой.

2. Заменил треугольники на элементы поверхности Безье. Вычислил нормали к плоскости каждого треугольника, потом усреднил их, получил нормали к поверхности в каждой вершине. Имея нормаль, можно построить касательные и получить дополнительные
контрольные точки для сплайнов.

Поверхность получилась гладкой, но все равно результат сильно зависит от качества исходной триангулции. Там где получались длинные узкие треугольники - были хорошо заметны артефакты на сгенерированой поверхности.

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

[worm2]

Попробуйте покопать здесь:
http://en.wikipedia.org/wiki/Category:Multivariate_interpolation

[Zai]

Marchtomcat писал(а):

Исходные точки объединены в последовательности, которые задают изолинии (точки с одинаковой высотой).

Свойство точек и их определенную последовательность в изолиниях обязательно нужно использовать и возможно без триангуляции. Изолинии нужно предстаить в виде сплайнов. Из точки где нужно определить высоту Z можно рассчитать расстояние до ближлежащих сплайновых кривых и по весу расстояний определить требуемую высоту. Такая интерполяция даст гладкость поверхности между двумя изолиниями. Учет расстояния до следующих рядом находящихся изолиний с их значениями высоты даст гладкость и в перпендикулярном направлении к касательным изолиний по всей поверхности.

[Marchtomcat]

Насчет искользования изолиний без триангуляции далеко не все так просто.
Я это пытался сделать как раз первым вариантом.
Вопрос такой - к примеру хотим сделать самую простую линейную интерполяцию, значит задача состоит в том, чтобы найти ДВЕ ближайших точки с РАЗНЫМИ высотами.



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

1 - внутри замкнутого контура с одной высотой - вторая высота получится совершенно от другой изолинии, которая не имеет никакого отношения к данной точке.

2 - должен быть плавный переход между интерполяцией под двум точкам к интерполяции по трем, иначе опять таки получим артефакт - плоский участок, а потом излом.


Реально получалось сделать так - сделать дискретную карту высот с некоторым разрешением, записать в нее высоты изолиний, а потом запустить нечто типа волнового алгоритма, т.е. от точек с известной высотой распространяется волна в соседние клетки.
Я делал так что в каждую клетку может быть записано до 4 разных высот, одновременно пишется расстояние до источника волны. Потом интерполируется по найденым высотам с весом обратно пропорциональным расстоянию. В принципе получалось, но при низкой дискретности карты качество было плохим, а при высокой - время вычислений слишком велико.

Добавлено спустя 5 минут 12 секунд:

worm2 писал(а):

Попробуйте покопать здесь:
http://en.wikipedia.org/wiki/Category:Multivariate_interpolation

Спасибо! Вопрос пока еще не решил, но Ваша ссылка помогла.

[Zai]

В зонах 1 и 2 по всей видимости лучше использовать интерполяцию в какой-то модифицированной полярной системе координат. Основной проблемой будет сшивка этой интерполяции с интерполяцией в зоне 3.