【转】Google Earth究竟是怎样工作的
|
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明 [更新]于09年01月23日翻译完毕 google了半天，并没有找到有人干过这件事情，所以开始翻译，这是一篇不短的文章，看起来不错，但郁闷的是，至今只找到这文章的第一部分，不知道是作者没有继续写呢还是咋地 因为比较长，我又比较懒，所以只能分几段译 原文见此： http://www.realityprime.com/articles/how-google-earth-really-works
译文：
介绍 在看了HowStuffWorks.com站点的一篇叫做“Google Earth究竟是怎样工作的”的文章之后，我发现这文章主要是在说“GE有多棒”以及“怎样使用它”，而不是“GE[究竟]是怎么工作的” 所以我想，这事儿可能涉及一些利益，那且不管这些个知识产权，这儿，让我们来看看，至少GE的一部分究竟是怎么工作的 注意，这些个知识产权的问题是确实存在的。Keyhole(GE之前的名字)项目曾经被人攻击，说它剽窃了某些人的下等的（“下等”这只是我作者个人观点阿）技术。该诉讼最终被法官给完全撤销，但这已经是纠结了许多年之后的了。这说明，直到现在，即便只是谈论这类事情都会引发一个问题，你说的随便什么话，都可以被有心的人拿作把柄，来说什么你做的都是他发明的，因为这些“听起来很像”。负责裁决Skyline和Google之间这场纠纷的法官知道，“听起来很像”是不足以证明侵权的，但可惜不是所有的法官都这么想 不管怎么说，谈论“GE究竟是怎么工作的”的方式，是始终只涉及已经以各种形式被披露的信息，尤其是体现在 Google的专利里头的，这类的信息相对还是较少的。通常更少的软件专利对大家更有利。但在这件事情上，更多的专利将意味着我们可以更公开地讨论这里头的技术，这一点，顺便说一下，算是发明专利保护的最初的一个目标之一——用受限的专利权交换真正的公众利益：技术的公开（刚才搜了一下专利法，里面规定获得专利的一方必须公开其技术内容），恩恩，我跑题了。。。 从最技术的角度，你可能还是打算直接看一下这些专利技术文档。友情提示：律师和技术专家有时候会在言辞上捣浆糊（原文：sometimes emulsify to form a sort of linguistic mayonnaise，mayonnaise常被用来指男汁或者白人所认为的nb的东西），以一种让人没头脑的方式，就是所谓的专利英语（Patent English），或者缩写成Painglish_-，如果你很勇敢，或喜欢自虐，那么看这里： 还有一些不是那么相关的Google专利，我不知道为啥这些也要申请（原文：I don’t know why these are shouting），但也许它们对于相关领域都很重要。我希望以后能就这些写一些更具体的东西： 3. 然后，这有来自于SGI的著名的文章，关于硬件“clipmapping”，这部分我们会在后面涉及。顺便说，Michael Jones，是GE幕后的黑手之一，作为CTO，他还在致力于推进这项技术 严正告诫：自从我参与到Keyhole这项目以来，GE的底层代码可能已经被重写了好几次，甚至可能在这些专利都被提交了之后。可以确定的是，最新的版本已经有了很大的变化。即便是我的解释也会显得如此泛泛（并且可能过时）以至于你别指望用这文章来干什么事情，除了满足求知欲和对相应技术的了解 另外请注意：我将把整个过程反过来讲述，看起来可能有些奇怪，一上来就讲你屏幕上的那个3D的地球，然后后面再回头去看供应和维护数据的部分。我相信这将有助于解释为什么这些事情是现在这样赞的，以及为何其他的一些技术却不能如此地赞
第一部分，成果：绘制一个三维的虚拟地球 在Google Maps和Google Earth之间，有两个原则性的不同，反映了表象背后事物应该怎样才能理想地运作。第一个不同之处，是GM的固定的二维视角（通常是顶视图）和GE的自由操控的三维透视。第二个不同，是实时渲染和预渲染。这两个差别，随着项目的不断进行，随着两者的逐渐融合，而越来越淡化。但这两个差别，即便在今天看来，也能反映出两种服务的重要差异来 两者共同的地方是，它们都是基于传统的数字照片——大量的照片——基本上，反映地球表面的极高精度的照片（或者是多重精度的）。它们不同的地方主要是在如何渲染这些照片数据 想一下：地球在赤道位置的周长大约是4万公里。那些说咱这是多小的世界的，多少有点装腔作势。如果你要把每平方公里的地表，都存储成一个彩色像素的话，一整个地球的图像（比如说，以墨卡托映射法平展开的话）将会长为4万像素，宽为大约一半。这比今日绝大多数的3D显卡所能应付的要远远地多。我们这儿说的是一张80亿像素，占用至少2.4G存储空间的图片。今日的许多PC甚至都没有2G的内存。并且说到显存，今日常见的PC有128M，而高端的游戏PC可以达到512M 记住，这仅仅是最基本的，效果很一般的，每公里一像素的全球图像。这样的图像所能表现的最小的细节大约是两公里范围（要感谢奈奎斯特先生）——没有建筑、河流、道路，或者人物可被清楚地表现出来。但是，对于美国多数主要站点来说，GE提供的图像精度可再现小到半米甚至更小的物体，这至少是上面这一图片的精度的4000倍，或者占用1600万倍存储空间 我们这儿说的是看起来需要占用无数G空间来存储的图像。没有任何的办法可以让这样的东西在眼下的PC上被渲染出来，尤其是在实时的情况下 然而，每次你运行GE，都是实时的 想想这个：在一个真3D虚拟的地球上，你可以随意倾向转动你的视角，来观看几乎任何地方（可能除了地底——但如果我们有数据，这也是可能的）。在各种3D地球模拟技术中，都需要一些源数据，通常，是一张反映整个地球表面的极高精度图片，或者至少是该公司所购买的部分。这些源数据需要传送到你的显示器上，贴覆到一些虚拟球体上或者比较理想的是，贴覆到小巧的3D表面上（三角形，等等）来摸拟真实的地形，山岳，河流等 如果，作为一个软件设计师的你，不打算实现倾斜或旋转地观看地球的方式，那恭喜你，你简化了软件工程，节约了时间开支。不过你就没法做出GE来了 现在，存在多种方案可以让你“漫游”在这大得离谱的图像的某些部分。其他的虚拟地图软件用它们自己的方式来解决这个问题，并且常常有着显著的限制或者图像看起来很shi。它们中的多数，只是简单地把巨大的地球划分为许多寻常的小块，可能通过四叉树来索引，然后在任何给定的时间，在你的屏幕上渲染出一定数量的小块，可以是2D的（像Google 但是GE解决这个问题的方式是真正传奇性的，值得专门申请一个软件专利（虽然一般而言我反对软件专利）。为了解释清楚，我们必须先明确一些核心概念。如果了解一些数字信息技术原理和计算机图形学的背景，那自然没什么坏处，但我希望我的解释会足够容易理解，而不需要事先知道这些 我将不会去解释3D渲染是如何运作的——这其实在别处也都有。但我将主要围绕texture mapping(纹理映射)和texture
基本概念 将基本的2D图像进行缩放、旋转、扭曲的方法，在很久以前就已经有了。最常见的方案是“Bilinear Filtering(双线性过滤)”。这个做法实际上就是，对于每个你想要绘制的新像素（旋转过、缩放过的……），从原始图像中取4个像素并将它们混合。之所以叫做“双线性”是因为，它先沿着一个轴线性混合两对像素，然后沿着另一个轴对上面这步获得的两个结果进一步线性混合，从而得出最终的结果 [如果，所谓“线性混合”的意思还不太明确的话，那么简单来说，比如，从A点拿40%的色彩，从B点拿60%，然后放到一起。这个40/60的比例只是举个例子，实际是可变的，取决于每个作出贡献的像素点的“重要度”，只要总的百分比是100%即可] 这年头的显卡都已经内建有这方面的功能，每秒可以进行字面上看数十亿次的这类计算。所以，别问我为啥你最爱用的绘图软件还是那么慢 问题已被发现，其实也很明显——这也是为啥我喜欢计算机图形技术，这问题就是，任何时候我们将原始像素映射到各种不同的输出像素上（旋转过、缩放过、倾斜过的，等等），视觉信息都会失真 这问题就叫做“aliasing(走样，比如锯齿)”，之所以发生，是因为我们先对原始图像，以一定的频率（通常对于图像我们用“分辨率”一词）进行数字化取样以获得数字化图像，然后，在进行映射的时候，以另一种方式对数字图像数据再次取样，这两次的频率可能不一致（原文now we’re re-sampling that digital data in some other way that doesn’t quite match up.我为了便于理解擅自加入“频率不一致”，但其实我觉得这只是一方面的原因，不是这方面的专家，见谅）
1，一张简单的低像素（11×11像素）图像，将要被旋转（网格线只是用来区分这些像素）
2，旋转之后，在目标网格上的每个像素将覆盖新图像的多个像素
3，近距离观察目标网格上的一个像素。双线性插值将取四个“最大的”像素（如带白角的黑边框所涵盖的）并作平均化（基于它们各自的权重）来产生这个新像素（这是个典型的局部区域）
4，在双线性插值之后，旋转的图像看起来很清楚（或者应该说很模糊）地反映了问题 此刻，当我们谈论输出的像素和目标图像时，目标图像究竟是绘图软件里的一张位图还是3D软件里显示的地球，其实并无所谓。任何时候当输出像素和原始图像的取样间隔（频率，分辨率）不一致的时候，锯齿就会产生。而锯齿导致图像看起来很糟糕。贴图映射技术有一半是关于如何对付锯齿的，剩下的基本上就是关于内存管理了。这两件事情所反映的限制，就是决定GE究竟如何工作的地方了 这儿的任务就是如何通过聪明的完美的设计，来尽量减少锯齿。最好的办法，就是尽可能地让输出像素和输入像素之间接近1:1的对应，或者至少生成大量额外像素以便可以安全地down-sample(向下取样)来获得输出图像并最小化锯齿的程度（这就是常见的“反锯齿”）。很多时候，两种方式我们都得用 思考一下：改变图像尺寸，只会让结果变糟——目标图像的每个像素，可能对应于原始图像的数百个像素，或反过来。记住，双线性插值，只会选择相关像素中“最大的”四个像素而忽略剩余的。所以，有时候会错过一些重要的像素，比如边缘、阴影，或高光。如果这些重要像素在某一帧被选择来做混合，而下一帧又被忽略，那你就会得到一个“像素闪现（pixel-popping）”或者闪烁的效果。我确信你一定在某些视频游戏里见过，现在你知道这是为啥了 倾斜的图像（或者任何3D变换）会有更多的问题，不仅因为有缩放和旋转的因素，还因为在被渲染的不同表面上，还有像素浓度的巨大差异。比如，在场景的“近处”，那些高分辨率的地表图像可能会被放大到如此的程度，以至于每个像素看起来都很粗。而在场景的“远处”，图像会出现一些闪烁（如上所述），因为2×2的双线性插值，可以很容易地时不时地错过一些重要的图像细节
微软版权所有，Virtual Earth 这儿有个例子，反映了某种纹理滤波技术所导致的不佳效果。图像上的文字标签几乎无从辨认（至于为啥要把这些文字和地表贴图做在一起，那是另一个问题了。译者按：不厚道阿，在这里还不忘b4一下微软）
说说更好的纹理过滤 绝大多数面向用户的3D硬件已经支持三线性过滤。使用三线性过滤及一种密切相关的技术mip-mapping,硬件计算和储存一系列比原始图像或者贴图分辨率一次降低的版本。每级mip-map自动缩小为上一级的1/4，如此，直到最后一级为1×1像素的图像，它反映了整个原始图像的平均色彩 那么，举例来说，如果你给硬件一张512×512的原始图像，它会计算并储存下8个额外的mip图层（256,128,64,32,16,8,4,2,1）。如果将这些mip图垂直堆起来，可以更形象地将“mip堆栈”看作一个上下颠倒的金子塔，其中每一级（水平切面）总是上一级的1/2宽度。
金字塔的一个简单示意 打叉的位置上，三线性过滤针对这个位于两层mip之间的像素，取上下这两层进行过滤以减少锯齿 在3D渲染中，mip-mapping和三线性过滤，针对每个目标像素，选择两个最合适的mip图层，基本上来说就是对每个进行一次双线性插值，然后再对获得的结果再进行一次线性混合，从而获得最终的图像 举例来说，比如原始图像即便只有覆盖47.5像素的辨识度，过滤后产生的像素也不会有什么锯齿。该系统事先存储了2的次方的mip map(16,32,64…)，所以硬件会很明智地选择64×64和32×32这两个最为接近所需的47.5的版本，对每个进行双线性插值（每目标像素取4像素样本），然后将获得的两个结果进行第三次的混合 这就是三线性过滤的简单的情况，包括mip-mapping, 对于许多普通情况下的3D变换，该系统在尽量减少锯齿方面，有了长足的进步 记住：目前为止，我们都是在讨论精致、小巧的图像，比如512×512像素的。而我们反映整个地球表面的图像，会需要达到数百万像素这个级别。那有人就会想，不如给一整个地球的图像制作一套巨大的mip-map吧，比如说精度到米。听着没有问题，对吧？但是你很快会意识到这将需要有26层之多的mip-map金字塔，其中，最高精度的mip图像，将有六千六百万像素。这显然不可能放入市面上的任何3D显卡显存中，至少在本世代来说 我猜测微软的Virtual Earth通过把巨大的地球表面贴图切分成许多小块来回避这个问题，比如说切成256像素边长的方形，每一个都有自己的mip-map。这样的处理可以一定程度地满足运作，但运行起来会相对比较慢，还产生一些画面上的缺陷，比如上面我们看到的模糊，以及当你推拉镜头时，大块方形区域的突然显示和突然消失 在我们开始涉及问题的核心之前，还有最后一个关于mip-map的概念需要理解。暂时设想一下mip-map金字塔的每层像素都是用彩色表示的，一层整个是红的，另一层是黄的，如此等等。。。把这样的像素绘制在倾斜的平面上（像GE的地表“平面”），看起来就像从一个有趣的角度“切过”金字塔，仅使用了对于当前视野所需的那一部分（按：这句话可能乍一看不好理解，其实就是说，斜着看的时候，近距离上调用高精度的mip-map，对应的位置是近距离上的像素，远距离上用低级别的对应远距离位置的mip-map像素） 就是这个mip-map的特点，让GE得以产生，我们马上就会具体说到
一个典型的倾斜的GE地表图像
同样位置上，使用颜色来标记每个像素分别对应什么mip级别 上边图片显示的是GE中的一个普通的3D场景，以及用一个简单的色谱图来显示，如果mip-map各级用不同的颜色标出，那3D硬件系统会从mip堆栈的什么位置来找最佳的原始像素来用 近的区域用最高精度的mip（红色表示），当从镜头位置逐渐远离，使用的精度就越来越低。这样避免了前面我们说到的闪烁和其他失真的问题，看起来效果就颇为不俗。我们尽可能地做到了原始图像和目标图像的1：1对应，所谓点对点，这样锯齿之流就被最小化了 还有更好的，支持三线性过滤的3D图形硬件已经支持一种叫做各向异性过滤（在GE里面对应一个“偏好”选项）的技术，基本上，和之前的例子有着一样的核心思路，但却是以非方形的过滤，来突破基本的2×2的过滤方式。这对于图像质量来说，非常重要，因为，即便使用华丽的mip-map，如果你将一个映射了贴图的三角面倾斜到非常斜的角度，硬件还是得选择一个低精度的mip级别来避免在该三角面狭窄方向的闪烁。这样，就意味着整个三角面总体而言使用了过低的mip-map精度，而此时其实只有一个方向适合低精度。可以很保险地说，如果你的硬件支持各向异性过滤，将其打开就可以获得最佳的效果。这是物有所值的。
好，戏肉来了 我们还是需要解决一个问题，就是如何对每个轴向上都有数百万像素的图像进行mip-map处理。Universal Texture(GE的专利)在解决这个问题的同时还保持了高质量的纹理过滤。它以一种非常聪明的方式，创建了一张巨大的、数T字节的、表现整个地球地表的虚拟贴图。因为实际上并非我发明的这一技术，所以我可以称赞一番。Chris Tanner找到了一个办法，可以让你的PC也能进行此类计算，而以往只有在昂贵的超级图形计算机外加定制的电路上，才能实现这样的效果，这个技术就叫做Clip Mapping(看SCI的PDF,同样由Chris、Michael以及其他一些人攥写，从中你可以看到最初的硬件实现思路)。该技术基本上就是GE之所以可以存在的基础所在。回头看的话，我在这个项目最开始的工作，就是让该技术可以在互联网上运作。（按：md，绕了半天就是clipmap，早说不就完了么） 那么它究竟是怎么工作的呢？ 唔，不是一次性载入和绘制整个巨大地球表面的贴图——这在绝大多数当前的硬件上是根本不可能的，也不是将这个大图切成数百万的方块，这将损失纹理过滤的质量以及我们想要的效率。回想一下我们前面讲过的，通常我们仅使用整个mip-map金字塔的狭窄的一个切片或者一条。这虚拟切片或者条带的角度和高度，会因为当前镜头位置的变化而发生很大的变化。这一使用上的常见情况，对于nb的程序来说，太简单了，可以直接计算或推断出，你镜头当前的位置以及软件需要绘制的部分 于是这套nb的程序，计算出在任何时候所需要的是这张巨大虚拟贴图的什么部位，并仅将这些从系统内存中搬入你显卡的纹理专用的显存单元，在那里，即便是实时状态下，绘制起来也是非常快的 从概念层面来说，对于传统mip-map技术的主要改动在于，那个上下颠倒的金字塔，不再是一个金字塔，而是要高许多许多，包含堆栈起来的贴图，名字很奇怪，叫做“clip stack”，高度可能达到16层到30层甚至更多。这就好比，你有一个巨大的16-30层的mip-map金字塔，宽度达到数百万甚至数十亿像素，但是你将边缘部分都切掉——那些你在某一时刻并不需要看到的部分
Universal Texture即是一个mip-map系统，也是一个软件模拟的clip stack系统，就是说它可以模拟一个比任何硬件通常所能承受的级别多得多像素大得多的mip-map 想象一下华盛顿纪念碑，上下颠倒，你就会明白了（按：华盛顿纪念碑是华盛顿的地标，是个方形截面的长柱子，头顶还是个尖，倒过来看的确很像标准的clip stack）。实际上，设想一下该碑朝这儿或者那儿倾斜，如同比萨斜塔那样，这样你就会有个进一步的形象的概念。这个碑以这样的方式倾斜，其内部的像素就是你当前所需要的，而其余的就统统忽略掉 每一级clip都是其下一级的两倍精度，如同mip-map，高质量的纹理过滤在这里还是一样有效的。但是因为clip stack被限制在一个固定的但是可以漫游的“足迹”上，比如说512×512像素宽（GE的另一个自定义选项），这意味着每级clip都是前一级的两倍精度而仅覆盖一半的区域（按：老实说我不是非常理解，这里的512×512是对应屏幕的） 换个方式来说，GE很智能地逐渐地载入位于视野焦点位置（如上面图片中的红色部分）的高精度的图像信息，从该位置往外，精度以逐倍降低。当你倾斜、飞越并同时观察地表朝着地平线消失而去的时候，Universal Texture系统将以最佳的方式，在任何一刻把最好的最有用的图像细节送交你本地的硬件。而不需要的部分，就碰都不碰。这事让GE可以如此地高效 而且它在内存占用上也同样高效。现在，一整个地球的贴图所占用的显存（假设这儿用的是512像素长宽的最底层mip-map，加上20层额外的clip层数据），大约只有17M，完全不是以前我们所面对的数十数百T的数据。这样就可行了，即便在1999年左右的32M显存的图形硬件上。而别的技术，只有在当前有了越来越大的3D显卡之后，才变得可行 实际上，用只有20层的clip（加上9层基础mip-map），就可以发现这2的29次方可以产出的虚拟地表图像，在两个轴向的任一个上最高可达5亿3千6百万像素。垂直方向乘上1/2，获得的虚拟图像，在面积上覆盖数百万亿像素（按：这句话不是很理解，虾米要垂直地乘以1/2，是说地球表面平展成一张贴图的话，短边是长边的1/2？原文： Multiply that by 1/2 vertically, gives an virtual image of a few hundred terapixels in area.），或者说可以绰绰有余地表现地球表面上0.15米（大约5英寸）尺度的细节，只要有相应地点的卫星图数据即可。而这都并非实际的限制，我只是简单地选了20层作为一个合理的数值，你会觉得往数码相机里面塞进去更多的百万级别的像素是很困难的，但是把这个乘以一百万，才大约到达表现行星表面的级别 幸运的是，目前来说，Google只需要存储数打百万亿像素的图像。该系统的另一个华丽的地方在于，不需要到处都有最高级别的精度也能让系统正常运作。在任何精度有限制的地点，在任何有空缺，数据不全等问题的地点，该系统都只画手头已有的。如果更高精度的数据有了，那就会被读取并渲染。如果没有，系统就使用相邻的精度低一些的数据（参考上面说到的mip-map）而不是留下一块空白。这就是为何，在某些地区，你放大进去看，只能看到糊糊的一片，而在别的地区，则非常精美和细致。这些都只是因为数据是否到位，而非任何3D渲染上的硬性限制。只要有数据，你可以在茫茫大海的中央看清楚厘米级别的东西 要让这一套运作起来的关键在于，当你在3D的地球表面漫游的时候，系统得高效地将新的贴图数据从你的本地硬盘缓存和系统内存中，读取到显存中。（下一次我们会讲述如何将数据放到你的本地缓存中）。你可以通过文字信息看到贴图数据正在被载入，但并不需要直观地体会到。现在你一定会对该系统如此流畅所需的大量幕后工作感激不已——这些就好像通过麦管逐点逐块地流淌出整个地表的信息 要在大多数的硬件上获得稳定的60fps，贴图的载入需要被切分成小块，以迅速地使用源数据针对你所观察的区域更新显存，应该能在你需要看到之前就完成，但即便最糟的情况下，也可以在刚需要之后一点点就完成。有一点很赞的是，该系统只需要载入所需的贴图的最小的部分，并且这过程不需要任何的等待。这意味着渲染可以很平顺而用户交互可以尽可能地流畅。没有这些异步处理的话，就别想那些美妙的在景点之间的作抛物线般切换的效果了（按：原文是forget about those nice parabolic arcs from coast 现在，其他的虚拟地球技术也可以虚拟整个地球表面的贴图，它们可能是将它切成许多小块，或者使用多层2的次方的不同精度（如同GE那样）。但没有Universal Texture这部分技术或更好的技术的话，它们要么被限制在2D顶视图下，或者只能做些效果不太令人满意的3D渲染，有模糊，闪烁。并且，把数据从缓存读入显存来进行渲染，也会不是那么地高效 以上这些，比起你想了解的，在屏幕上渲染出地球的每一祯的情况，已经要多了 |