Как вы можете сшить несколько карт высот вместе для удаления швов?

Question

Я пытаюсь написать алгоритм (в C#), который будет сшивать две или несколько несвязанных карт высот вместе, чтобы между картами не было видимого шва. В основном я хочу, чтобы имитировать функциональность найти на этой странице: http://www.bundysoft.com/wiki/doku.php?id=tutorials:l3dt:stitching_heightmaps

(Вы можете просто посмотреть на фотографии, чтобы получить суть того, что я говорю о)

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

Любое руководство будет оценено, поскольку я искал и искал решение без успеха. Было бы очень полезно получить простое толчок в правильном направлении! Я понимаю, что многие методы манипулирования изображениями могут применяться к картам высот, но не смогли найти алгоритм обработки изображений, который дает результаты, которые я ищу. Например, image stitching работает только для изображений с перекрывающимися полями зрения, что не относится к несвязанным картам высот.

Будет ли использование низкочастотного фильтра FFT каким-либо образом работать, или это будет полезно только для создания одной плиточной карты высот?

Поскольку алгоритм должен использоваться в Unit3d, любой код C# должен ограничиваться .Net 3.5, так как я считаю, что это последняя версия Unity. Спасибо за любую помощь!

Answer 1

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

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

2) Найти новую высоту точки, используя следующую формулу:

newHeight = oldHeight + (average - oldHeight)*((maxDistance-distance)/maxDistance); 

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

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

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

Главный виновник от старой формулы этой части:

(maxDistance-distance)/maxDistance 

, который производил значение между 0 и 1, линейно в зависимости от расстояния от точки до ближайшего края. По мере того, как расстояние между точками высот и краем увеличивается, точки карты высоты будут использовать меньше и меньше среднего (как определено выше) и все больше смещаются в сторону их первоначальных значений. Эта линейная интерполяция была причиной слишком наклонного шага, но, к счастью, я нашел встроенный метод в классе Mathf API Unity, который допускает квадратичную (я считаю, кубическую) интерполяцию. Это SmoothStep Method.

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

//Using Mathf - Unity only? 
float weight = Mathf.SmoothStep(1f, 0f, distance/maxDistance); 

//Using XNA 
float weight = MathHelper.SmoothStep(1f, 0f, distance/maxDistance); 

//If you can't use either of the two methods above 
float input = distance/maxDistance; 
float weight = 1f + (-1f)*(3f*(float)Math.Pow(input, 2f) - 2f*(float)Math.Pow(input, 3f)); 

//Then calculate the new height using this weight 
newHeight = oldHeight + (average - oldHeight)*weight; 

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

Answer 2

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

Возьмем такой пример - я использую одну строку здесь, чтобы показать идею:

Left = [11,11,11,10,10,10,10] 
Right= [01,01,01,01,02,02,02] 

позволяет сказать, что наше перекрытие 4 пикселей в ширину:

Left = [11,11,11,10,10,10,10] 
Right=   [01,01,01,01,02,02,02] 
       ^^^^ overlap/stitiching region. 

Левое значение слева изображение будет 10 . Самое правое значение правильного изображения будет 1. Теперь мы интерполируем линейно между 10 и 1 в 2 этапа, наша новая область сшивания выглядит следующим образом:

stitch = [10, 07, 04, 01] 

Мы заканчиваем со следующей прошитой линии:

line = [11,11,11,10,07,04,01,02,02,02] 

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