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

Во всяком случае, на данный момент, у меня есть рендерер с «непрерывным цветом», которым я очень доволен

Градиент - это стандартное цветовое колесо, где красные пиксели указывают координаты с высокими значениями, а фиолетовые пиксели указывают низкие значения.

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

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

Чтобы дать вам представление о том, о чем я думаю, вот реализация бедного человека (где средство визуализации просто использует значение RGB черного цвета всякий раз, когда сталкивается с пикселем, который пересекает контурную линию):

Однако у этого подхода есть несколько проблем:

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

Области графика с более плоским наклоном приводят к более широким линиям topo (и часто целым областям черноты, особенно по внешнему периметру области рендеринга).

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

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

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

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

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

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

Но даже при этих ограничениях я все еще могу думать о нескольких различных эвристиках для нахождения линий:

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

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

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

Итак, вот некоторые из моих мыслей ...

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

Редактировать:

Меня особенно интересует предложение "Градиент", сделанное Эллисббеном. И моя основная структура данных (без учета некоторых оптимизирующих ярлыков интерполяции) может быть представлена ​​в виде суммирования набора двумерных гауссовых функций, который полностью дифференцируем.

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

ОБНОВИТЬ:

Благодаря превосходному вкладу Эллисббена и Азима я теперь могу вычислить угол контура для любой произвольной точки в поле. Рисование настоящих топографических линий последует в ближайшее время!

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

Наслаждайтесь!

(ПРИМЕЧАНИЕ. В этих рендерингах используется топография поверхности, отличная от предыдущей, так как я случайным образом генерирую структуры данных на каждой итерации, пока создаю прототип, но основной метод рендеринга тот же, поэтому я уверен, что вы получите идея.)

Вот забавный факт: на правой стороне этих визуализаций вы увидите кучу странных контурных линий под идеальными горизонтальными и вертикальными углами. Это артефакты процесса интерполяции, в котором используется сетка интерполяторов, чтобы уменьшить количество вычислений (примерно на 500%), необходимых для выполнения операций рендеринга ядра. Все эти странные контурные линии происходят на границе между двумя ячейками сетки интерполятора.

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

ОБНОВЛЕНИЕ СНОВА:

А-а-а-а-а-а, в качестве последнего удовольствия перед сном, вот еще одна пара визуализаций, одна в стиле «непрерывного цвета» старой школы, и одна с 20 000 градиентных выборок. В этом наборе визуализаций я убрал красную точку для точечных образцов, так как она излишне загромождает изображение.

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

Приятного аппетита!!