无论如何,在这个阶段,我有一个“连续颜色”渲染器,我非常满意: 渐变是标准的色轮,红色像素表示具有高值的坐标,紫色像素表示低值。
底层数据结构使用一些非常聪明的插值算法,使得可以任意深入地缩放到地图的细节中。
目前,我想画一些地形等高线(使用二次贝塞尔曲线),但我还没有找到任何描述有效算法以找到这些曲线的好文献。
为了让您了解我的想法,这里是一个简陋的实现(当渲染器遇到与等高线相交的像素时,它只使用黑色RGB值):
然而,这种方法存在几个问题:
图表中斜率较陡的区域会导致拓扑线变细(经常出现断裂)。理想情况下,所有拓扑线都应该连续。
图表中斜率较缓的区域会导致拓扑线变宽(并且经常在渲染区域的外围形成整个黑色区域)。
因此,我正在寻找矢量绘图方法来获得漂亮、完美的1像素厚曲线。算法的基本结构将包括以下步骤:
- 在每个离散的高度处,找到一组坐标,使得该坐标的海拔与所需高度非常接近(给定任意epsilon值)。
- 消除冗余点。例如,如果三个点在一条完美直线上,则中心点是冗余的,因为可以消除它而不改变曲线的形状。同样地,对于贝塞尔曲线,通常可以通过调整相邻控制点的位置来消除某些锚点。
- 将剩余点组装成一个序列,使得两个点之间的每个段近似于高程中性轨迹,并且没有两个线段会相交。每个点序列必须创建一个封闭多边形,或者必须与渲染区域的边界框相交。
- 对于每个顶点,找到一对控制点,使得由此产生的曲线相对于步骤#2中消除的冗余点具有最小误差。
- 确保当前渲染比例下可见的地形的所有特征都用适当的拓扑线表示。例如,如果数据包含高海拔但直径极小的尖峰,则仍应绘制拓扑线。只有当其特征直径小于图像的总体渲染粒度时,才应忽略垂直特征。
但即使在这些限制下,我仍然可以想到几种不同的启发式方法来找到这些线:
在渲染边界框内找到最高点。从该高点开始沿着几条不同的轨迹向下行进。每当遍历线穿过高度阈值时,将该点添加到特定高度的存储桶中。当遍历路径到达局部最小值时,改变方向并向上行进。
在渲染区域的矩形边界框上执行高分辨率遍历。在每个高度阈值处(以及曲率反转方向的拐点处),将这些点添加到特定高度的存储桶中。完成边界遍历后,从这些桶中的边界点开始向内进行跟踪。
扫描整个渲染区域,在稀疏的规则间隔处进行高度测量。对于每个测量值,使用其与高度阈值的接近程度作为机制来决定是否对其邻居进行插值测量。使用此技术可以更好地保证整个渲染区域的覆盖范围,但是很难将结果点组装成合理的顺序以构建路径。
所以,这些是我的一些想法...
在深入实现之前,我想看看StackOverflow上是否有其他人有这种问题的经验,并且可以提供准确和高效的实现指针。
编辑:
我特别感兴趣ellisbben提出的“梯度”建议。我的核心数据结构(忽略一些优化插值快捷方式)可以表示为一组二维高斯函数的总和,这是完全可微分的。
我想我需要一个数据结构来表示三维斜坡,以及一个计算任意点的斜率向量的函数。就我目前的想法而言,我不知道如何做到这一点(尽管它似乎应该很容易),但如果您有一篇解释数学的链接,我将不胜感激!更新:
由于ellisbben和Azim的出色贡献,我现在可以计算场中任意点的等高线角度。接下来将绘制真实的地形线!
以下是更新后的渲染图像,带有和不带有我一直在使用的“黑市”光栅化地形渲染器。每个图像包括一千个随机采样点,用红点表示。该点的等高线角度由白线表示。在某些情况下,无法在给定点测量到斜率(基于插值的粒度),因此红点出现时没有相应的等高线角度线。
享受吧!
(注意:这些渲染使用与先前渲染不同的表面地形--因为我在每次迭代时都会随机生成数据结构,当我进行原型设计时--但核心渲染方法是相同的,所以我相信您能理解。) 这里有一个有趣的事实:在这些渲染图像的右侧,您会看到一堆奇怪的轮廓线,呈完美的水平和垂直角度。这些是插值过程的产物,使用插值器网格来减少执行核心渲染操作所需的计算量(约降低了500%)。所有这些奇怪的轮廓线都出现在两个插值器网格单元之间的边界上。
幸运的是,这些产物实际上并不重要。虽然在斜率计算期间可以检测到这些产物,但最终的渲染器不会注意到它们,因为它以不同的位深度操作。
再次更新:
在我睡觉之前,作为最后的放纵,这里有另一组渲染图像,一种是老派的“连续颜色”风格,另一种是具有20,000个渐变样本的。在这组渲染图像中,我已经删除了点采样的红点,因为它会使图像过于混乱。
在这里,您可以真正看到我之前提到的插值伪影,这要归功于插值器集合的网格结构。我应该强调,这些伪影在最终轮廓渲染中将完全不可见(因为任何两个相邻插值器单元之间的差异都小于呈现图像的位深度)。
祝您用餐愉快!