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

Question

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

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

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

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

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

Поскольку алгоритм должен использоваться в 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.

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

//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;

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

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]

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