绘制地形图

我一直致力于二维连续数据的可视化项目.这是您可以用来研究2D地图上的高程数据或温度模式的类型.从本质上讲,它实际上是一种将三维平面化为二维加彩色的方法.在我的特定研究领域,我实际上并没有处理地理高程数据,但这是一个很好的比喻,所以我会在这篇文章中坚持下去.

无论如何,在这一点上,我有一个"连续颜色"渲染器,我很满意:

渐变是标准色轮,其中红色像素表示具有高值的坐标,紫色像素表示低值.

底层数据结构使用了一些非常聪明的(如果我自己这么说的话)插值算法,可以任意深度缩放到地图的细节.

在这一点上,我想绘制一些地形轮廓线(使用二次贝塞尔曲线),但我还没有找到任何描述找到这些曲线的有效算法的好文献.

为了让您了解我正在考虑的内容,这里是一个穷人的实现(渲染器只要遇到与轮廓线相交的像素就使用黑色RGB值):

但是,这种方法存在一些问题:

具有更陡峭斜率的图形区域导致更薄(并且经常断裂)的拓扑线.理想情况下,所有拓扑线应该是连续的.

具有更平坦斜率的图形区域导致更宽的拓扑线(并且通常是整个黑度区域,尤其是在渲染区域的外周边处).

因此,我正在研究一种矢量绘制方法,以获得那些漂亮,完美的1像素厚曲线.算法的基本结构必须包括以下步骤:

在我想要绘制地形线的每个离散高程处,找到一组坐标,其中该坐标处的高程非常接近(给定任意epsilon值)到所需高程.

消除冗余点.例如,如果三个点处于完全直线,则中心点是多余的,因为可以在不改变曲线形状的情况下消除它.同样,对于贝塞尔曲线,通常可以通过调整相邻控制点的位置来消除cetain锚点.

将剩余的点组装成序列,使得两个点之间的每个段近似于高程中性轨迹,并且使得没有两个线段跨越路径.每个点序列必须创建一个闭合多边形,或者必须与渲染区域的边界框相交.

对于每个顶点,找到一对控制点,使得结果曲线相对于步骤#2中消除的冗余点呈现最小误差.

确保在当前渲染比例下可见的地形的所有要素都由适当的拓扑线表示.例如,如果数据包含高海拔的尖峰,但直径极小,则仍应绘制拓扑线.如果垂直特征的特征直径小于图像的整体渲染粒度,则只应忽略垂直特征.

但即使在这些限制条件下,我仍然可以想到几种不同的启发式方法来寻找线条:

在渲染边界框中找到高点.从那个高点开始,沿着几条不同的轨迹下坡.只要遍历线超过高程阈值,请将该点添加到特定于高程的存储桶.当遍历路径达到局部最小值时,改变航向并向上行驶.

沿着渲染区域的矩形边界框执行高分辨率遍历.在每个海拔阈值处(以及在拐点处,斜坡反转方向的任何位置),将这些点添加到特定于海拔的铲斗中.完成边界遍历后,从这些桶中的边界点开始向内追踪.

扫描整个渲染区域,以稀疏的规则间隔进行高程测量.对于每次测量,使用它与高程阈值的接近度作为决定是否对其邻居进行插值测量的机制.使用这种技术可以更好地保证整个渲染区域的覆盖范围,但是很难将结果点组合成一个合理的构造路径的顺序.

所以,这些是我的一些想法......

在深入研究实现之前,我想看看StackOverflow上是否有其他人遇到过这类问题的经验,并且可以为准确有效的实现提供指导.

编辑:

我对ellisbben提出的"Gradient"建议特别感兴趣.而我的核心数据结构(忽略一些优化插值快捷键)可以表示为一组2D高斯函数的总和,这是完全可微的.

我想我需要一个数据结构来表示一个三维斜率,以及一个用于计算任意点的斜率矢量的函数.在我的头顶,我不知道该怎么做(虽然它看起来应该很容易),但如果你有一个解释数学的链接,我会非常感激!

更新:

由于ellisbben和Azim的出色贡献,我现在可以计算场中任意点的轮廓角.绘制真正的地形线将很快跟随!

这里有更新的渲染图,有和没有我一直在使用的基于ghetto栅格的topo-renderer.每个图像包括一千个随机采样点,由红点表示.该点处的轮廓角由白线表示.在某些情况下,在给定点处不能测量斜率(基于插值的粒度),因此红点在没有相应的轮廓线的情况下发生.

请享用!

(注意:这些渲染使用与之前渲染不同的表面形貌 - 因为我在每次迭代时随机生成数据结构,而我是原型 - 但核心渲染方法是相同的,所以我相信你会得到这个想法.)

这是一个有趣的事实:在这些渲染的右侧,你会看到一堆完美的水平和垂直角度的奇怪轮廓线.这些是插值过程的伪像,它使用插值器网格来减少执行核心渲染操作所需的计算次数(约500%).所有这些奇怪的轮廓线出现在两个插值器网格单元之间的边界上.

幸运的是,这些文物实际上并不重要.尽管在斜率计算期间可检测到伪像,但最终渲染器将不会注意到它们,因为它在不同的位深度处操作.

再次更新:

Aaaaaaaand,作为我睡觉前的最后一次放纵,这里是另一对效果图,一个是老式的"连续色彩"风格,另一个是20,000个渐变样本.在这组渲染中,我已经消除了点样本的红点,因为它不必要地使图像混乱.

在这里,由于插补器集合的网格结构,您可以真正看到我之前提到的那些插值工件.我应该强调的是,这些伪像在最终轮廓渲染中将是完全不可见的(因为任何两个相邻内插器单元之间的幅度差异小于渲染图像的位深度).

好胃口!!

该梯度是一个数学运算符可以帮助你.

如果您可以将插值转换为可微函数,则高度的渐变始终指向最陡上升的方向.所有相等高度的曲线都垂直于在该点评估的高度梯度.

您从最高点开始的想法是明智的,但如果有多个局部最大值,可能会错过功能.

我建议

选择要绘制线条的高度值

在精细的,规则间隔的网格上创建一堆点,然后在渐变方向上以小步长走向每个点,朝向您想要绘制线的最近高度

通过踩踏垂直于渐变的每个点来创建曲线; 当另一条曲线太靠近它时,通过杀死一个点来消除多余的点 - 但为了避免破坏像沙漏一样的沙漏中心,你可能需要检查垂直于两个点的渐变的定向矢量之间的角度.(当我说定向时,我的意思是确保渐变和你计算的垂直值之间的角度在同一方向上总是90度.)