英语原文共 14 页

使用WebGL进行体积地形渲染

Raoul van Ruuml;schen, Simon McCallum, Stefan Kim, and Reiner Creutzburg

摘要：

自2011年推出WebGL以来，Web浏览器已发展成为一个新的，有前途的高性能3D游戏平台。最常见的游戏元素之一是基于高度图的地形，但由于这种方法的表达能力有限，因此对更复杂解决方案的需求变得明显。存在许多可以将隐式表面转换为近似多边形网格的技术。然而，在文献中尚未充分研究这种算法在实时环境中的实际应用，特别是在移动设备上，其中渲染时间是最重要的。目前的工作概述了使用3D渲染框架Three.js实现多线程体积地形引擎，并阐明了在实际环境中频繁的用户交互改变模型时轮廓方法的应用。最终系统使用双轮廓曲面提取技术，并在相邻单元格中维护离散体积数据——可使用构造实体几何体在运行中进行修改。此外，评估引擎的性能以确定其对移动设备的适用性。

介绍：

WebGL是一种新兴而令人兴奋的技术，用于创建Web浏览器游戏和动画。 许多游戏的核心部分是地形，传统方法使用高度图来提升规则细分平面网格的顶点。 基于高度图的地形相当有限，因为地形网格中的每个顶点只能向上或向下移动。 它不能用于复制洞穴，悬垂物，弯曲地形和其他有趣的自然特征。 现代地形实现使用高级算法基于体积数据构建表面。 这样的体积解决方案可以完全取代高度图方法并提供更多的自由度，但它本身需要更多的内存，因为它在3D数据而不是2D纹理上运行。 此类地形的细节层次（LOD）算法也比高度图变体更复杂，具体取决于所选择的网格构造技术

事实上，目前没有用于WebGL的开源地形引擎，更不用说地形编辑器，无论是基于体积还是基于高度图，意味着尽管有前面提到的优点，但这样的实现可行性不高。因此，出现以下中心问题：

1. 体积地形解决方案的性能是否可行？

2. 可以在移动设备上使用这样的方案吗？

这项工作的主要目标是使用JavaScript和WebGL实现体积地形引擎。创建这样的引擎，挑战在于，在浏览器内的实时体积地形渲染领域中仍然存在未开发的方面，例如管理大量体积数据以及在运行时期间地形网格的有效和动态构造。

贡献

这项工作提供了以下贡献，可作为未来研究的基础：

1. JavaScript中完全记录的开源地形引擎实现，包括双轮廓（DC）算法和二次误差函数（QEF）求解器。

2. 基于八叉树的空间分区解决方案，可用于管理大量的体积数据。

3. 多线程构造实体几何（CSG），用于基于符号距离函数（SDF）的离散体数据修改。

4. 内存消耗和处理时间的性能测量。

相关工作

大多数相关文献更多地关注现有或新开发的体积轮廓技术的特征，而不是实时环境中的实际应用。[1]描述了一种基于体素的地形可视化系统，该系统依赖于光线跟踪进行渲染。 [2]描述了一种基于体素的遮挡技术，用于改进基于高度图的地形渲染。 [3]描述了以“基于粒子的特征近似”的形式计算DC技术的特征点的替代解决方案。这种方法取代了QEF计算并交换了性能的准确性，同时也使得在GPU上执行轮廓绘制过程变得更加容易。 [4]介绍了Marching Cubes（MC）轮廓绘制技术的实际实现，该技术专为实时桌面游戏中基于体素的地形而设计。后者的一个重要贡献是Transvoxel算法，它扩展了具有LOD功能的MC技术。 [5]为MC技术提供了另一种扩展，它使用最长边对分（LEB）来支持LOD。 [6]是最近的相关工作，它解决了将DC技术实时应用于一组体积块的问题，同时还提出了一种可能的接缝修补解决方案。

有一些值得一提的网络博客提供了关于基于体积的地形系统主题的鼓舞人心的信息：[7]发表了一系列关于商业Voxel农场引擎的文章。 这些文章中的许多见解都影响了当前工作中的设计决策。 [8]讨论了DC的实现，并提供了关于如何处理多个相邻的体数据单元之间的接缝的具体信息，而[9]更详细地解释了体积生成。 此外，[10]提供了MC，Marching Tetrahedra（MT）和Surface Nets（SN）的基本JavaScript实现，并在性能和多边形数量方面对这三种技术进行了比较。

高级Web浏览器功能

现代网络浏览器采用了先进技术，可用于当今的高性能3D游戏。 虽然WebGL授予对图形处理单元（GPU）的访问权限并提供实现硬件加速3D动画的方法，但Web Worker API在浏览器中实现了真正的多线程。 这些功能可通过JavaScript获得，JavaScript是在虚拟机中运行的动态类型的高级编程语言，使用即时（JIT）编译并依赖于自动垃圾收集。

由于JavaScript引擎在过去几十年中经过了大量优化，因此JavaScript的执行速度非常接近本机性能。 虽然JavaScript在物理模拟等要求较高的任务时仍然比本机应用程序慢，但它已经足够快，可以构建丰富的交互式动画和3D游戏。 根据[11]，该语言的创建者，未来版本的JavaScript将通过支持更多低级编程功能（如类型对象，并行数组和SIMD指令）来进一步解决JavaScript的性能问题。 该语言的新更新计划要小得多，并且将更快发布，以允许浏览器供应商更快地实现新功能。

WebAssembly（WASM）是一个新的实验性功能，其灵感来自Emscripten项目和JavaScript子集asm.js. 它提供了一种将C 代码编译为汇编语言的方法，该语言可以在浏览器中以接近本机的速度运行。 像Unity和Unreal这样的游戏引擎早就依赖这项技术来支持HTML5作为目标平台。 WASM旨在与JavaScript一起运行以运行性能敏感的代码。 此工作中提供的地形引擎目前不使用WASM，因为此功能仍存在一些未解决的问题。 可以尝试用编译的WASM模块替换当前系统的关键部分，但这超出了该项目的范围。

初步措施

根据[12]，有符号距离函数属于隐式曲面的子集，描述了到体积表面的带符号欧几里德距离，有效地描述了它在3D空间中每个点的密度。 它可以定义为f：R³→R，并且对于位于体积内的点和外部点的正值产生负值。 该值在卷的确切边界处为零。

CSG是一种用于表示基于数学集符号的实体的设计方法。 它“为人类和自动机提供了简单，精确和简洁的方法来定义特定的固体物体”[13]。 在隐式曲面的上下文中，该方法用于将SDF组合成卷的复杂描述。 图1显示了三个布尔CSG操作Union（cup;），Difference（\）和Intersection（cap;）的效果。 “CSG方案具有有限且通常很小的紧凑实体基元[13]。 例如，Persistence of Vision Raytracer仅提供以下原始实体：盒子，圆锥体，圆柱体，平面和环面。 但是，仅使用这些原语就可以使用CSG创建高度复杂的实体。 另一个使用这种方法的项目是OpenCSG，它遵循基于图像的渲染方法而不是光线跟踪，并依赖于图形硬件的深度和模板缓冲来渲染实体。

等值面表示隐式曲面f（x，y，z）= c的轮廓，其中c是表示SDF边界的常数等值。 尽管可以使用光线跟踪方法渲染隐式曲面，但性能损失可能过高，尤其是在移动设备上。 由于3D硬件针对传统的基于多边形的渲染进行了优化，因此必须将隐式曲面转换为可以有效处理和可视化的显式多边形网格。 存在密切相关的各种等值面轮廓技术，但是以不同方式执行转换。

轮廓技术

最古老和最突出的等值面轮廓技术之一是由[14]发表的MC算法。它将SDF的连续值转换为均匀分布的材料指数的离散网格。该3D网格被细分为体素单元。正如该技术的名称所示，MC在这些立方体细胞上游行，并在每个细胞角落评估SDF。根据SDF返回的密度，网格点将设置为空气或固体材料。所有八个角的信息用作手头案例的标识符。由于每个单元的可能材料配置数量有限，每种情况都可以映射到具体的三角形设置。在最后一步中，所有多边形都绑在一起。图2示出了具有示例性材料配置的体素单元以及与其相邻的生成的三角形。 MC提取方法并非没有缺陷：它经常产生退化的三角形，不能保留尖锐的特征。此外，该算法不支持其基本形式的LOD。

[4]以Transvoxel算法的形式提出了LOD问题的解决方案，该算法为过渡单元引入了另一组多边形配置，以连接不同LOD的网格。

[16]提出的扩展行进立方体（EMC）算法引入了一种利用QEF进行清晰特征保存的机制。对于表现出材料变化的每个体素单元边缘，近似与隐式表面的交点。另外，在所识别的点处计算表面的法向矢量，然后评估该法线矢量以确定细胞中是否存在尖锐特征。法线和交叉点一起描述了用作线性方程组的输入的平面。求解系统产生平面的交点，实际上是所寻求的特征点。然而，隐式表面可能与体素单元相交，使得存在少于三个平面，这导致线性系统变得不确定。为了解决这样的系统，使用QEF，其在体素内找到一个点，该点最小化到由交叉点和法线定义的平面的距离的平方和。在检测到尖锐特征的情况下，EMC解决QEF以获得最小二乘解，在所识别的特征点处创建三角扇并将其与边交叉点连接。除此之外，该算法像MC一样运行。

根据保留体积表面不同细节的想法，[17]发表了直接的直流技术，该技术采用[18]提出的SN方法，与EMC一样，依赖于用QEF获得的特征点。 然而，与先前的方法不同，DC不会尝试将体素单元材料配置映射到某些三角形设置。 相反，它为每个单元创建一个顶点并将其与相邻体素单元的顶点连接。 此外，该方法使用八叉树数据结构来组织和遍历体素单元。 这种方法的副作用是该算法支持LOD而无需额外的努力，因为它允许体素具有任何大小。

图3显示了MC和DC如何生成多边形的比较，并突出了后者的优越性。最左边的图像显示了2D体积网格的一部分，其由等间距材料指数，边缘处具有材料变化的表面交叉点和源自它们的表面法线组成。这种边缘数据通常称为Hermite数据。 MC只能粗略地近似表面，如中央图像所示，而DC设法保留表面的锐利特征。在后来的出版物中，[19]指出“双轮廓产生的表面很少是无交叉的”，并且提出了MC和DC的混合，它使用三角形风扇以牺牲性能和增加复杂性为代价来产生无交叉网格。 DC与MC共享的另一个问题是它们都可能产生非流形网格。拓扑歧管网不具有孔并完全包围体积。实质上，每个边缘都需要与两个面相邻。 [20]通过提出Manifold Dual Contouring（MDC）算法解决了这个问题，该算法允许每个体素单元有多个顶点，并实现了顶点聚类的基本标准，然而，这会导致计算复杂性略有增加。在早期的出版物中，[21]还提出了双行进立方体（DMC）算法，该算法引入了双网格的概念，用于使用MC保存锐利特征。

Cubical Marching Squares（CMS）是[22]提出的另一种独特的轮廓方法。 它基于MC，但工作方式不同，它展开体素单元并使用更简单的2D行进方（MS）算法处理单元面以形成线。 Hermite数据用于保留尖锐特征，算法通过划分具有模糊边缘的面来保证拓扑一致性。 将面折回到立方体中，然后用于构建网格。 [23]提供了CMS轮廓绘制技术的部分实现，证明了该技术的可行性，但缺乏诸如锐边保留的关键特征。

密度数据的空间采样

等值面提取方法通过叠加具有固定量的等间距材料指数的三维网格来产生连续SDF的离散近似。 根据材料指数是位于体积的内部还是外部，它们要么设置为空气（由零值表示），要么设置为固体材料，可以是任何其他无符号整数。 通过在各个网格点世界位置处对SDF进行采样来确定每种材料的值。 如果SDF返回密度值dle;c，其中c是等值，则网格点位于体积内并表示固体材料。

两个相邻网格点之间的边缘，其中一个是实心的而另一个是空气，表现出材料变化并且包含由SDF描述的体积轮廓。 只有这些边缘很重要，需要使用从SDF获得的附加表面交叉点数据进行标记。 图4描绘了左侧分辨率为8的2D示例网格和单个3D体素单元，其中四个边缘包含以红色显示的表面。 零交叉位置处的表面交点法线描绘为蓝色箭头，并且计算的顶点显示为黄色点。 在3D中，分辨率n转换为n个体素单元和每个维度中的n 1个材料索引。 因此，存在（n 1）3个材料指数和总共3times;（n 1）2times;n个边缘，但实际包含体积表面的边缘的数量通常要低得多。 通过过零近似获得边缘交叉点数据。

虽然高网格分辨率允许表面提取过程获取隐式表面的更多细节，但是它还导致生成的顶点数量增加并且对处理时间具有负面影响。

零交叉近似

表现出从固体材料到空气或相反材料的材料变化的边缘与体积的等值面相交。 他们需要仔细检查以找到零交叉——这是SDF假设等值c = 0的点。鉴于边缘起点和终点的世界位置是已知的，问题可以简化为一般的根发现问题 形式为f（x）= 0，其中f是SDF，x是未知根。 该问题可以进一步简化为找到值tisin;[0,1]，其表示沿边缘的相对交叉点。

实际上，可以沿着边缘以离散步骤对SDF进行采样，以找到等值最接近零的点。然而，这种天真的方法将结果限制在非常小的一组可能值。即使有五个采样步骤，零交叉也只能假设值{0,0.25,0.5,0.75,1}，这是不必要的信息丢失。因此，需要更先进的方法，其可以更准确地近似交叉点并且仍然提供相当高的性能。 “找到连续函数的真正零点的最好，最有效的方法之一是二分法”^[24]。该方法也称为二分搜索算法，并通过计算中点x3将初始间隔[x1，x2]切成两

资料编号：[4772]