我一直在研究二维连续数据的可视化项目。这是您可以用来研究 2D 地图上的海拔数据或温度模式的东西。从本质上讲,这实际上是将 3 维扁平化为二维加色的一种方法。在我的特定研究领域中,我实际上并没有使用地理海拔数据,但这是一个很好的比喻,因此我将在整个帖子中坚持使用它。
无论如何,在这一点上,我有一个“连续颜色”渲染器,我很高兴:
渐变是标准色轮,其中红色像素表示具有高值的坐标,紫色像素表示低值。
底层数据结构使用一些非常聪明的(如果我自己这么说的话)插值算法来实现对地图细节的任意深度缩放。
在这一点上,我想画一些地形等高线(使用二次贝塞尔曲线),但我还没有找到任何好的文献描述寻找这些曲线的有效算法。
为了给你一个想法,我在想什么,这里是一个穷人的实现(渲染器只是使用一个黑色的 RGB 值,每当它遇到一个像素相交的轮廓线):
不过,这种方法有几个问题:
具有较陡斜率的图形区域会导致较薄(并且经常断开)的地形图线。理想情况下,所有地形图线都应该是连续的。
具有较平坦斜率的图的区域导致较宽的地形图线 (并且通常是黑色的整个区域,特别是在渲染区域的外周边处)。
因此,我正在研究一种矢量绘制方法,以获取那些漂亮,完美的 1 像素厚曲线。该算法的基本结构必须包括以下步骤:
在我想要绘制地形图线的每个离散高程处,找到一组坐标,其中该坐标处的高程与所需高程非常接近(给定任意 ε 值)。
消除冗余点。例如,如果三个点在一条完美的直线上,那么中心点就是冗余的,因为它可以在不改变曲线形状的情况下消除。同样,对于贝塞尔曲线,通常可以通过调整相邻控制点的位置来消除 cetain 锚点。
将其余的点组合到一个序列中,以使两个点之间的每一段都近似于高程中性轨迹,并且不会有两条线段交叉路径。每个点序列必须创建一个封闭的多边形,或者必须与渲染区域的边界框相交。
对于每个顶点,找到一对控制点,以使所得曲线相对于步骤 # 2 中消除的冗余点具有最小误差。
确保在当前渲染比例下可见的地形的所有特征都由适当的地形图线表示。例如,如果数据包含高度较高但直径极小的尖峰,则仍应绘制地形图线。仅当垂直特征的特征直径小于图像的整体渲染粒度时,才应忽略垂直特征。
但即使在这些限制下,我仍然可以想到几种不同的启发式方法来查找行:
在渲染边界框内找到高点。从该高点开始,沿着几个不同的轨迹下坡。每当遍历线越过高程阈值时,将该点添加到特定于高程的桶中。当遍历路径达到局部最小值时,更改路线并向上移动。
沿渲染区域的矩形边界框执行高分辨率遍历。在每个高程阈值处(以及坡度反转方向的拐点处),将这些点添加到特定于高程的存储桶中。完成边界遍历后,从这些存储桶中的边界点开始向内跟踪。
扫描整个渲染区域,以稀疏的规则间隔进行高程测量。对于每个测量,使用它与高程阈值的接近度作为一种机制来决定是否对其邻居进行插值测量。使用这种技术可以更好地保证整个渲染区域的覆盖范围,但是很难将结果点组合成合理的顺序来构建路径。
所以,这些是我的一些想法...
在深入实施之前,我想看看 StackOverflow 上的其他人是否有这种问题的经验,并且可以为准确和有效的实施提供指针。
Edit:我对 Elisbben 提出的“Gradient”建议特别感兴趣。而我的核心数据结构(忽略一些优化插值快捷方式)可以表示为一组 2D 高斯函数的总和,这是完全可微的。
我想我需要一个数据结构来表示三维斜率,以及一个用于计算任意点的斜率向量的函数。在我的头顶上,我不知道该怎么做(虽然看起来应该很容易),但是如果你有一个解释数学的链接,我会非常感激!
UPDATE:多亏了 ellisbben 和 Azim 的出色贡献,我现在可以计算该领域中任何任意点的轮廓角度。绘制真正的地形图线将很快完成!
在某些情况下,无法在给定点测量斜率 (基于插值粒度),因此红点出现时没有相应的轮廓线角度。
享受
(注意:这些渲染使用与以前的渲染不同的表面形貌-因为我在每次迭代时随机生成数据结构,而我正在制作原型-但核心渲染方法是相同的,所以我相信你明白了。)
这是一个有趣的事实:在这些渲染的右侧,您会看到一堆奇怪的轮廓线,它们处于完美的水平和垂直角度。这些是插值过程的产物,它使用插值器网格来减少执行核心渲染操作所需的计算数量(减少约 500 %)。所有这些奇怪的轮廓线都出现在两个插值器网格单元之间的边界上。
幸运的是,这些工件实际上并不重要。尽管在斜率计算过程中可以检测到工件,但最终的渲染器不会注意到它们,因为它在不同的位深度上运行。
再次更新:
Aaaaaaaaaand,作为我睡觉前的最后一次放纵,这里有另一对效果图,一个是老式的“连续颜色”风格,另一个是 20,000 个渐变样本。在这组效果图中,我已经消除了点样本的红点,因为它不必要地使图像混乱。
在这里,由于插值器集合的网格结构,您可以真正看到我之前提到的那些插值伪影。我应该强调,这些伪影在最终的轮廓渲染中将完全不可见(因为任何两个相邻插值器单元之间的大小差异小于渲染图像的位深度)。
好胃口!!
gradient是一个数算符,可以帮助你。
如果您可以将插值转换为可微函数,则高度的梯度将始终指向最陡峭的上升方向。所有高度相等的曲线都垂直于该点评估的高度梯度。
你的想法从最高点开始是明智的,但可能会错过功能,如果有多个局部最大值。
我建议
拾取您将在其上绘制线条的高度值
在一个精细的,规则间隔的网格上创建一堆点,然后在渐变方向上朝着要绘制线条的最近高度以小步走每个点
通过步进垂直于梯度的每个点来创建曲线;当另一条曲线离它太近时,通过杀死一个点来消除多余的点-但是为了避免像数字一样沙漏的中心,您可能需要检查垂直于两个点的梯度的定向矢量之间的角度。(当我说定向时,我的意思是确保梯度与您计算的垂直值之间的角度始终为同一方向的 90 度。)
为了回应您对 @ erickson 的评论,并回答关于计算函数梯度的问题。而不是计算你的 300 项函数的导数,你可以做一个数字微分如下。
给定一个点 [x,y] 在你的图像中,你可以计算梯度(最陡峭的方向)
g={ ( f(x+dx,y)-f(x-dx,y) )/(2*dx),
{ ( f(x,y+dy)-f(x,y-dy) )/(2*dy)
where dx and dy could be the spacing in your grid.The contour line will run vertical to the gradient.So,to get the contour direction,c,we can multiply g = [v,w] by matrix,A = [0-1,1 0] giving
c = [-w,v]
或者,有marching squares算法似乎适合你的问题,虽然你可能想平滑的结果,如果你使用一个粗略的网格。
您要绘制的地形曲线是二维标量场的isosuces。对于三维等值面,有marching cubes算法。
我自己想要这样的东西,但还没有找到一个基于向量的解决方案。
但是,基于光栅的解决方案并不是那么糟糕,特别是如果您的数据是基于光栅的,如果您的数据也是基于矢量的(换句话说,您有一个表面的 3D 模型),您应该能够做一些真正的数算来找到不同高度的水平面的相交曲线。
对于基于光栅的方法,我查看每对相邻像素。如果一个在等高线水平之上,一个在等高线水平之下,显然等高线在它们之间延伸。我用来消除等高线混叠的技巧是将等高线颜色混合到两个像素中,与它们与理想等高线的接近程度成比例。
也许一些例子会有所帮助。假设当前像素的“高度”为 12 英尺,相邻像素的高度为 8 英尺,等高线为每 10 英尺。然后,中间有一条等高线;用 50% 不透明度的等高线颜色绘制当前像素。另一个像素在 11 英尺处,邻居在 6 英尺处。以 80% 不透明度为当前像素着色。
alpha = (contour - neighbor) / (current - neighbor)
不幸的是,我没有方便的代码,并且可能有更多的代码(我隐约记得看着对角线邻居,并通过sqrt(2) / 2
进行调整)。
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(22条)