使用可变四叉树建立连续LOD场景网格 - 第一部分

鼯鼠

目 录
　　1 问题
　　2 网格

---

　　原 文：Continuous LOD Terrain Meshing Using Adaptive Quadtrees
　　译 者：Glflush_CN
　　版 本：to be continue...

---

　　编辑手记：《雪域骑士 - Soul Ride》这是一个引人入胜的滑雪游戏，你可以由此想象一下那些景色迷人的滑雪胜地。因为游戏中的场景完全依赖全球卫星系统提供的数据资料加以绘制，所以数千平方英里的滑雪场地会使你深深地沉浸其中。最特别的是游戏中的滑雪路线是非线性的开放式地图，你可以向任意方向滑去。因此在这个游戏中赛道显示器就显得更为吸引人了。

---

　　 场景渲染一直是游戏编程世纪的热点。现在我们讨论一种十分有趣的场景技术，因为场景中的多边形的预算远远超过硬件的实时的绘制能力，但是优秀的游戏引擎可以用LOD的方法适度的绘制场景中的多边形。当然，即使LOD可以绘制相当大和复杂的场景，但却必须在这两者间调整，也就是场景面积和细致级别的矛盾。
　　Terrain rendering is a perennial hot issue in the world of game programming. Right now we're at a particularly interesting point in the development of terrain rendering technology, because polygon budgets have risen to the point where, in conjunction with real-time LOD meshing algorithms taken from published academic papers, state-of-the-art game engines are able to draw quite a bit of reasonably detailed terrain. However, the techniques which are currently in common use must compromise either on terrain size or on close-up detail.

　　在我现在开发中的游戏《雪域骑士》中，我在验证了大家都知道的算法以后，发展出了解决场景大小和细致级别的方法。这篇文章就是讲解我的算法的。
　　As part of the R&D for Soul Ride, the game I'm currently working on HERE, I experimented with the published algorithms, and eventually came up with an extension that eliminates the tradeoff between terrain size and close-up detail. This article presents my algorithm, along with its similarities and differences from the above-mentioned algorithms.

　　我将从复习场景渲染的问题开始，并且回顾被［1］、［2］、［3］（文献）解决的问题。然后我解释我的算法解决的问题。（此处略去作者自吹废话若干）
　　I'll start by reviewing the problem of terrain rendering, and describe the problem solved by [1], [2], and [3] (see references at the end of this article). Then I'll explain the additional problem solved by my algorithm. I'll present a detailed description of the algorithm, and discuss some of the problems with it and some of the untapped potential. And last but not least, I'll provide the source code to a demo that implements my algorithm, which you can use to help understand it, evaluate its effectiveness, and incorporate directly into your own projects if you want.
　　This article is not a general tutorial or review of terrain rendering. I'm going to assume some familiarity on your part with the problem. If things aren't making much sense, you may want to consult the excellent references listed at the end of the article.
1、问题（The Problems）
　　我们想从一个场景渲染器中获得什么？我们需要一个没有破裂和T错误的连续网格从眼前一直延伸到地平线。我们希望在不惜声场景的细致级别的情况下获得更大的场景面积。我们希望从我们的脚下一直到遥远的山脉都有凹凸感。为了讨论的方便，我们假设我的场景描绘能力的需求是从1米到100000米，很大吧？
　　What do we want from a terrain renderer? We want a single continuous mesh from the foreground all the way to the horizon, with no cracks or T-junctions. We want to view a large area over a large range of detail levels: we want to see the bumps in front of our feet to the mountains in the background. For the sake of discussion, let's say that we want feature size to range from 1m up to 100000m; five orders of magnitude.

　　我们怎样做？如果我们建立一个100000*100000的表格，每个用16位来存储高度值，然后就这样描绘出网格的话（图1），我们就会被两个大问题。第一，就是三角形的问题，每一帧需要让我们的渲染API绘制20亿的多边形，而现在的绘制能力才开始超过每秒1000万。第二，就是内存问题，我们的高度值需要占用20G的空间，呵呵。
　　How can we do it? The brute-force approach won't work on ordinary computers circa Y2K. If we make a 100000m x 100000m grid of 16-bit height values, and just draw them in a mesh (Figure 1), we'll end up with two big problems.First, the triangle problem: we'll be sending up to 20 billion triangles/frame to our rendering API. Second, the memory problem: our heightfield will consume 20 GB of data. It will be many years before hardware advances to the point where we can just use brute-force and get good results.

图1 Brute force approach to a heightfield mesh.

　　有许多得以有的方法可以解决三角形的问题。用得最多的算法就是使用递归算法（文献［1］、［2］、［3］）。使用这样的算法我们可以使用很少的三角形显示出我们所需的场景（我将会翻译另外的文章讲解这些算法）。但是，我们还有存储器的问题。
　　There are several previously-published methods which successfully tackle the triangle problem. The most widely used ones employ a clever family of recursive meshing algorithms [1], [2], [3]. Using one of these algorithms, we can effectively tame our mesh, and render a seamless terrain with a few thousand triangles, with the vertices intelligently selected on the fly from the 10 billion in the dataset. However, we still have a memory problem, since the heightfield dataset consumes 20 GB (plus some overhead to support the meshing algorithm).

　　一个明显的方法就是减少高度表的长度。1000*1000才是比较适合今天的计算机的能力的。最近的一个叫TREADMARKS的游戏就是使用1000*1000数据集，效果相当的好［4］（文献），当然，1000*1000距离10万*10万还是有很大的差距的。我们的目标是对场景的大小和可视距离没有限制，对前景的细致程度也没有限制。
　　One obvious solution is to compromise on detail by making the heightfield dimensions smaller. 1k x 1k is a good practical size for a heightfield with today's machines. A recently released game called TreadMarks uses a 1k x 1k dataset to excellent effect [4] (see references at the end of the article). Unfortunately, 1k x 1k is still a far cry from 100k x 100k. We end up having to limit either the size of the terrain and the view distance, or the amount of foreground detail.

　　我这里的解决方案就是可变四叉树，用来代替标准的高度表，来表示场景的高度信息。使用这种四叉树，我们可以在场景的不同的地方用不同的方法压缩高度数据。具个例子，在一个驾驶游戏中，你希望马路周围的场景十分的细致，而你永远不会开到的地方就没有这样的必要（其实，大家看看就知道是这样了，但是，驾驶游戏的引擎的实现方法有很多，这是其中一种，其实，LOD不是最适合的方法）。
　　One obvious solution is to compromise on detail by making the heightfield dimensions smaller. 1k x 1k is a good practical size for a heightfield with today's machines. A recently released game called TreadMarks uses a 1k x 1k dataset to excellent effect [4] (see references at the end of the article). Unfortunately, 1k x 1k is still a far cry from 100k x 100k. We end up having to limit either the size of the terrain and the view distance, or the amount of foreground detail.
　　The solution which I cover in this article is to use an adaptive quadtree, instead of a regular grid, to represent the terrain height information. Using this quadtree, we can encode height data at different resolutions in different regions in the terrain. For example, in a driving game, you would want lots of fine detail on and around the roads, ideally showing every bump, but you wouldn't need that much detail for the surrounding wilderness that you can't drive to; you only need enough detail for the general shape of hills and valleys.

　　这种四边形树也可以用来解决内存的问题。方法就是在粗糙的级别上预先定义场景的形态，然后在视觉图像生成时计算机自动计算出良好的细致级别，而在不使用后，从内存中删除。
　　The quadtree can also be used for another attack on the memory problem: procedural detail. The idea is to pre-define the shape of the terrain at a coarse level, and have the computer automatically generate fine detail on the fly for the area immediately around the viewer. Because of the quadtree's adaptive nature, this detail can be discarded when the viewer moves, freeing up memory for creating procedural detail in a different region.

　　分开来讲，四叉树的两维可变表示法和四叉树的递归网格算法都是很有名的。（下面又略去作者的自夸若干，就是自己可以…）
　　Separately, the use of quadtrees for adaptive representation of 2D functions, and the use of quadtrees for recursive meshing [1], [3] are both well-known. However, [1] and [3] both use regular grids for their underlying heightfield representation. Extending their meshing approach to work with a true adaptive quadtree presents numerous complications, and requires some tricky programming. Hence this article and the accompanying demo code.

2、网格（Meshing）
　　网格有两个部分。我定义第一个部分为Update()，另一个部分为Render()，在Update()期间，我们要决定哪些定点要被包括在输出网格中。然后，在Render()时，我们将生成包含这些定点的三角形网格。我们从一个极端简单的高度表（3*3）开始（图2）。在Update()时，我们将观察每一个可选的顶点而决定是否把其包括到网格中。只有一个顶点是“enabled”，我们才使用它来建立网格。
　　My meshing algorithm is based on [1], which has also influenced [2] and [3]. There are a few key modifications, but much of the basic approach is the same, and I borrow a lot of the [1] terminology. There are two parts to meshing. I call the first part Update() and the second part Render(), after [1]. During Update(), we'll decide which vertices to include in the output mesh. Then, during Render() we'll generate a triangle mesh that includes those vertices. I'll start by explaining Update() and Render() for an extremely simple heightfield: a 3x3 grid (Figure 2). To Update() it, we'll look at each of the optional vertices and decide whether to include them in the mesh. Following the terminology of [1], we'll say that if and only if a vertex is "enabled", then we'll use it in the mesh.

图2 A 3x3 heightfield. Dashed lines and vertices are optional in an LOD mesh.

　　我们可以看到，这个简单的高度表的角和中心都是enabled，所以现在就需要计算四个边上的四个顶点的状态，根据一些LOD算法就可以算出。
　　Take as given that the center and corner vertices are enabled. So the task is to calculate the enabled state for each of the four edge vertices, according to some LOD calculation which takes the viewpoint and the vertex attributes into account.

　　在我们了解了哪些顶点是enabled之后，我们可以Render()这个网格。这是非常简单的，就是连成三角形。参看图3。
　　Once we know which vertices are enabled, we can Render() the mesh. It's easy; we just make a triangle fan with the center vertex as the hub, and include each enabled vertex in clockwise order around the outside. See Figure 3 for examples.

图3 Examples of LOD meshes on the 3x3 heightfield. Disabled vertices in black.