written by : Milo Yip
In addition to being applied to games in the form of minecraft, voxels can also have more detailed performance and become the composition of the next generation of 3D game world. This paper analyzes the principles and related technologies from a technical point of view.

体素除了能应用于像《我的世界（Minecraft）》形式的游戏，还可以有更细致的表现，成为下一代的三维游戏世界构成方式，本文从技术角度分析当中的原理及相关技术。

introduction
At present, mainstream 3d games generally need a large and exquisite game world (game world, or game level, game stage). The so-called game world not only refers to the three-dimensional rendering environment visible to players, but also includes the virtual environment required by game systems (game mechanism, physical collision, artificial intelligence, etc.).

Most 3D games use 3D triangle mesh to construct most of the game world, including terrain, buildings, vegetation and other static objects. Some games focusing on natural outdoor environment, such as most RPG and MoBa games, will use height field to represent terrain; Some indoor games, such as FPS, TPS, act, etc., will use constructive solid geometry (CSG) technology to construct the basic indoor environment (called BSP / binary space partitioning brush in many game engines).

The production of the game world accounts for a large part of the total production cost. With the improvement of the performance of the game platform and the expansion of the demand for game content, the production cost of the game world should continue to increase. The above production methods have their own advantages and disadvantages. 3D mesh is not only a representation of the game world in line with contemporary hardware, but also a relatively free modeling method, and there are mature digital content creation tools, such as 3ds Max and Maya. However, its disadvantages include high modeling cost, only surface representation (it may not be possible to judge whether an arbitrary point is outside or inside), not easy to modify (especially after unfolding UV), not easy to make level of detail (LOD) of continuous or discrete series, etc. The manufacturing cost of height field and BSP is lower than that of grid, and it is easier to modify and implement LOD, but its application is very limited.

Is there a better way to make 3D games? This problem has always been an important exploration direction of game production.

引言
现时，主流三维游戏一般都需要庞大、精致的游戏世界（game world，或称为游戏关卡／game level、游戏舞台／game stage）。所谓的游戏世界，不单指玩家可见的三维渲染环境，也包含游戏性系统（游戏机制、物理碰撞、人工智能等）所需的虚拟环境。

多数三维游戏使用三维三角形网格（3D triangle mesh）建构大部分的游戏世界，包括地形、建筑、植被及其他静态物件。一些以自然户外环境为主的游戏，如大部分RPG、MOBA类型游戏，会使用到高度场（height field）去表示地形；一些室内为主的游戏，如一些FPS、TPS、ACT等，会使用构造实体几何（constructive solid geometry, CSG）技术去建构基本的室内环境（在许多游戏引擎中称为 BSP／binary space partitioning 笔刷）。

游戏世界的制作占总制作成本的一大部分，而随著游戏平台的性能提升，以及游戏内容需求的膨胀，游戏世界的制作成本也因应不断提高。以上的制作方法都各有优缺点。三维网格是合乎当代硬件的游戏世界表示方式，也是较自由的建模方式，而且有成熟的数字创作工具（digital content creation tool）如 3ds Max 和 Maya。但其缺点包括建模成本高、仅为表面表示方式（可能无法判断一个任意点在其外还是其内）、不容易修改（尤其是在展开UV之后）、不容易做连续或离散级数的细致程度（level of detail, LOD）等。高度场和 BSP 的制作成本较网格低，而且较容易修改和实现 LOD，但其适用场合就非常局限。

有没有更好的三维游戏界的制作方式？此问题一直是游戏制作的重要探索方向。


Voxel

Since the unprecedented success of minecraft, according to ign's report , minecraft has sold a total of 33 million copies on all platforms. Voxels enter the eyes of developers and become another feasible way to construct the game world, as shown in Figure 1 and 2.

体素

自《我的世界（Minecraft）》的空前成功，根据IGN的报道，Minecraft 在所有平台上已售出共三千三百万份。体素（voxel）进入开发者的眼球，成为另一种建构游戏世界的可行方式，见图1、2。

Figure 1: screenshot of my world game.图1:《我的世界》游戏截屏。

更多精彩图片 请登录

Figure 2: King's landing city in the song of ice and fire produced by gamers of my world.图2: 《我的世界》游戏玩家合作制作的《冰与火之歌》中的君临城。

In a simple analogy, voxels are three-dimensional versions of pixels. In two-dimensional, we can use a two-dimensional array of colors to represent an image; In 3D, a rasterized 3D space can also be represented by a 3D array of voxels, and each voxel stores a bit to indicate whether the space is solid or hollow, as shown in Figure 3. This binary voxel is the simplest voxel form, but voxels can also store other attributes. For example, the voxels in my world will store the materials of the space (soil, stone, water, etc.), while in medicine, the X-ray opacity obtained from CT scanning will be stored in the voxels, as shown in Figure 4.

Compared with the height field terrain and BSP, voxels can make general solid surfaces, caves, buildings and so on at the same time.

简单类比，体素就是像素的三维版本。在二维中，我们可使用颜色的二维数组表示一个影像（image）；在三维中也可以用体素的三维数组表示一个栅格化的三维空间，每个体素储存一个比特，表示该空间是实心还是空心的，如图3。这种二元体素（binary voxel）是最简单的体素形式，但体素还可以储存其他属性。例如《我的世界》的体素会储存让空间的材质（泥土、石、水等），而在医学上会把CT扫描得来的X射线不透光性（opacity）储存在体素中，如图4。
相对于高度场地形及BSP，体素可以同时制作一般地表、山洞、建筑物等固体。

更多精彩图片 请登录

Figure 3: stack some voxels. The gray cube is one of them. (Wikipedia pictures)图3：把一些体素叠起来，灰色立方体是其中之一个体素。（维基百科图片）

更多精彩图片 请登录

Figure 4: visualization of voxel data of CT scan by volume diffusion method. (Wikipedia pictures)图4：以体积宣染方法去可视化CT扫瞄的体素数据。（维基百科图片）

Destruction and construction
Because the structure of voxel data is simple and uniform, it is easier to modify than mesh. Therefore, the game can allow players to build the game world (this is a user generated content, UGC), and can also allow game rules to dynamically change the game world, such as destructible objects, terrain morphing, etc. It is not only possible to modify, but also possible to create something out of nothing - games such as my world and cube world (Figure 5) contain procedurally generated content, and the latter can generate a large RPG map and game content. Of course, the content generated purely automatically may not meet the requirements of game designers, but a certain degree of procedural generation function can greatly reduce the production cost.

破坏与建设
由于体素数据的结构简单而均匀，它相对于网格来说更容易修改。因此，游戏可以让玩家建设游戏世界（这是一种用户生成内容／user-generated content, UGC），也可以让游戏规则动态改变游戏世界，例如可破坏物件（destructible object）、地形变形（terrain morphing）等。不单止修改，无中生有也是可能的──《我的世界》和《魔方世界（Cube World）》（图5）等游戏都包含程序式生成内容（procedurally generated content），后者更可以生成一个大型的RPG地图及游戏性内容。当然，纯粹自动生成的内容不一定合乎游戏设计师的要求，但某程度的程序式生成功能可以大幅降低制作成本。

更多精彩图片 请登录

Figure 5: Rubik's cube world completely generates content randomly by program, so that players can constantly explore the infinite world. The whole game is only made by a couple.图5：《魔方世界》完全以程序随机生成内容，让玩家可以不断探索无限的世界。整个游戏仅由一对夫妻制作。

More detailed performance
The aforementioned game examples all use binary voxels, and their edges and corners are very prominent. Although it can be regarded as a style (such as the pixel style in the era of 8-bit game console), is there any way to improve it? One method, such as two-dimensional image, can improve the resolution of voxel data, for example, from one voxel per cubic meter to one voxel per centimeter, so as to enhance the degree of detail. However, volume data grows in cubic series, and the storage capacity is very high. For example, a large voxel space contains more than 16 million voxels (16m); It will grow to more than 1 billion voxels (1g). Even if each voxel occupies only 1 byte, a large amount of storage space is required. Of course, we can consider that in general applications, a large number of connected voxels are all hollow or solid, so we can use some data structures to compress these original voxel data, such as octree. NVIDIA published a study [8] in 2010 to show how to efficiently use GPU to ray trace scenes represented by sparse voxel octree (SVO). In this study, each voxel also stores the compressed data of color and normal. After compression, a cathedral model (Sibenik) stores 40963 data in 440mb, and the ray tracing ability when rendered reaches 100 million rays per second (Fig. 6). Gigavoxels [3] [4] is a similar technology. The atomontage engine also uses voxel data with color, but compresses it in an exclusive way, claiming that it can render large voxel scenes in real time at a very high frame rate (Figure 7).

However, the scheme of storing color / normal per voxel may not meet the needs of game development. The key point of this scheme is that each detail in the scene (such as an accuracy of 1cm) can be edited independently. This accuracy is necessary for voxel data obtained by scanning real scenes (such as terrain, architecture, biology, etc.) in scientific applications. However, games usually only need virtual scenes, and players don't care whether the concave convex of a wall in the cathedral is exactly the same as the reality. From the perspective of scene production, although the scene can be carved arbitrarily and is very free, this degree of freedom is difficult to manage and control. The situation is like a very huge map that can be drawn arbitrarily in a two-dimensional game. The debate on this issue is similar to the production and game capacity issues arising from the megatexture / virtual texturing technology [1] [6] of id software. The following will describe the use of isosurface extraction and data expansion to solve the problem of fineness and capacity.

更细致的表现

前述的游戏例子都是使用二元体素，其棱角非常突出，虽然可视为一种风格（如8位游戏机时代的象素风格），但是否有方法改善呢？其中一个方法，就如二维影像，我们可以提升体素数据的分辨率，例如从每立方米一个体素提升至每厘米一个体素，以增强细致程度。然而，体积数据是以立方级数增长的，所需的存储容量很高。例如一个   大小的体素空间含一千六百多万个体素（16M个）；而   就会增长至过10亿个体素（1G 个）。即使每个体素只占1字节，也需要大量储存空间。当然，我们可以考虑在一般的应用场合中，大量相连的体素是全部空心或实心的，那么我们可以使用一些数据结构去压缩这些原始体素数据，如八叉树。2010年 NVidia 就曾发表研究[8]，展示如何高效地使用 GPU 去光线追踪以稀疏体素八叉树（sparse voxel octree, SVO）表示的场景。在该研究中，每体素还存储了颜色及法綫的压缩数据。一个大教堂模型（Sibenik）压缩后以 440MB 存储 40963 的数据，被渲染时的光綫追踪能力达每秒1亿光綫（图6）。GigaVoxels[3][4]也是相似的技术。Atomontage 引擎也是使用含颜色的体素数据，但以独家的方式进行压缩，宣称可以极高帧率实时渲染大型体素场景（图7）。

然而，每体素储存颜色／法綫的方案，未必符合游戏开发所需。此方案的重点，是场景中每个细节（例如达 1cm 的精度）都可以独立编辑。对于在科学应用上通过扫瞄真实场景（例如地形、建筑、生物等）得到的体素数据，这种精确性是必须的。然而，游戏通常只需要虚拟的场景，玩家并不在乎大教堂中的某幅墙的凹凸是否和现实完全相同。从场景制作的角度看，虽然场景能任意雕刻，十分自由，但这种自由度反而难以管理及掌控。情况有如在二维游戏中，可任意绘画的非常巨大的地图。这个问题的争论点类似在id Software的MegaTexture／虚拟纹理（virtual texturing）技术[1][6]所产生的制作及游戏容量问题。以下将描述利用等值面提取及数据扩大解决细致程度及容量问题。

更多精彩图片 请登录

Figure 6: transform the Sibenik model voxels into 40963 sparse voxel octree (SVO). Each voxel contains color and normal, and is rendered by GPU ray tracing.
图6: 把 Sibenik 模型体素化为40963的稀疏体素八叉树（SVO），每个体素含颜色及法线，以GPU光线追踪渲染。

更多精彩图片 请登录

Figure 7: atomontage engine renders a large voxel scene in real time, and the scene can be destroyed dynamically and arbitrarily.图7: Atomontage 引擎实时渲染大型体素场景，场景可以被动态任意破坏。

Iso-surface Extraction

When rendering voxels with ray tracing, some interpolation methods and normal data can be added to make the effect smoother. Another rendering method is to store scalar data in voxels, then extract the isosurface of the scalar field, generate three-dimensional meshes, and then render in an ordinary rasterization way. If you compare the two-dimensional situation, it is like extracting the contour lines of the height field and rendering these contours. In the three-dimensional case, we can store the material density or signed distance of the scene as a scalar field.

Given a scalar field, we can use the classical marching cubes (MC) algorithm [10] to extract the isosurface. The MC algorithm is very simple, just scan the voxel data, if isovalue Between the values of two adjacent voxels, we use linear interpolation to find the middle isosurface vertices, and finally use look-up table to decide how to connect these vertices into isosurface triangular mesh. Because MC can only generate smooth isosurface, it can not represent sharp vertices and edges, and then dual contour (DC) [7] You can solve this problem, but you need to add normal data to voxels. The effect is shown in Figure 9.

等值面提取
对于上述谈到的棱角问题，以光綫追踪渲染体素时，可以加入一些插值方式及法綫数据令效果更为平滑。另一个渲染方法，是在体素中储存标量数据，然后提取该标量场的等值面（isosurface），生成三维网格，再以普通的光栅化方式渲染。如果类比二维的情况，就如同提取高度场的等高綫（contour line），再把这些等高綫渲染。在三维的情况，我们可以存储场景的物质密度，或是有符号距离（signed distance)，作为标量场。
给定一个标量场，我们可以使用经典的移动立方体（Marching Cubes, MC）算法[10]去提取等值面。MC 算法十分简单，只需扫瞄体素数据，若等值（isovalue）介乎两个相邻体素的值之间，便使用綫性插值求出中间的等值面顶点，最后使用查表去决定如何把这些顶点连接成等值面三角网格。由于 MC 只能生成圆滑的等值面，不能表示锐利的顶点及棱，后来的对偶轮廓（dual contouring, DC）[7]可以解决此问题，但就需要在体素中加入法綫数据，效果如图9所示。

更多精彩图片 请登录

Figure 8: 15 cube configurations in the marching cubes (MC) algorithm. After comparing the values at both ends of each edge with the equivalent, if one is greater than the equivalent and the other is less than the equivalent, the vertex is generated by linear interpolation on the edge, and then the triangular patch is generated according to these configurations. (Wikipedia pictures)
图8: 移动立方体（Marching Cubes, MC）算法中的15个立方体组态。每条棱两端的值与等值比较后，若一个大于等值，一个小于等值，就在该棱上线性插值生成顶点，然后按这些组态生成三角面片。（维基百科图片）

更多精彩图片 请登录

Figure 9: dual contour (DC) algorithm can maintain sharp vertices and edges at the same time图9: 对偶轮廓（dual contouring, DC）算法可以同时保持锐利的顶点及棱

The voxel construction scene function supported by cryengine 3 and C4 engine uses this kind of isosurface extraction method. Both engines solve the shortcomings of height field terrain (such as unable to represent caves) by voxels. The next generation of endless tasks includes two works EverQuest next and EverQuest next landmark, which integrate the voxel farm engine, fully use the voxels of isosurface extraction to construct a large-scale game world, including terrain, caves, buildings, etc. (FIG. 10), and also add the skill design of destroying / changing the game environment.
CryEngine 3和C4 Engine所支持的体素建构场景功能，都使用了这类等值面提取方式。这两个引擎都是以体素方式解决高度场地形的缺点（如无法表示山洞）。下一代的《无尽的任务》包括两个作品《EverQuest Next》及《EverQuest Next Landmark》整合了Voxel Farm Engine，全面使用了等值面提取方式的体素去建构大型的游戏世界，包括地形、洞穴、建筑物等（圖10），而且还加入破坏／改变游戏环境的技能设计。

更多精彩图片 请登录

更多精彩图片 请登录

Figure 10: screenshot of EverQuest next. Terrain and buildings are modeled with voxels to generate smooth or sharp edge meshes, and then texture mapping is used to enhance details and create a unique artistic style of the game. Voxel editing demo video.
图10: 《EverQuest Next》的场景截屏，地形和建筑物都是用体素建模，生成圆滑或尖锐边缘的网格，再使用紋理映射加強细节及营造游戏独特的美术风格。体素编辑演示视频。

Data expansion
After using the isosurface extraction method, there is no need for high-resolution voxels to produce a smooth surface, which can be said to solve the problem of edges and corners on the one hand. On the other hand, how can we improve the level of detail without significantly increasing the amount of data? One of the common technologies is data amplification - generating large amounts of data from small amounts of data. The general height map terrain simply adopts the texture of multi-layer repeated tiling, which can also be regarded as a simple data expansion. This method can also be applied to isosurface extraction, but it requires more complex texture mapping methods. For example, C4 engine can mix three plane projections to mix texture sampling [9]. To avoid visual repetition, we can also consider Wang tile [10] or other texture generation techniques, which may involve how to parameterize the isosurface. See Figure 11 for an example of EverQuest next.

数据扩大

使用等值面提取方式后，不需要高分辨率的体素来产生圆滑的表面，可以说一方面解决了棱角的问题。但另一方面，我们如何在不大幅增加数据量的情况下，提升细致程度？其中一个通用技术就是数据扩大（data amplification）──用小量数据生成大量数据。一般高度图地形简单地采用多层重复密铺（tiling）的纹理，也可算是一种简单的数据扩大。这种方法也可以应用到等值面提取上，不过它需要更复杂的纹理映射方式，例如 C4 Engine 可混合三个平面投影去混合纹理采样（tri-planar mapping）[9]。要避免视觉上的重复问题，还可以考虑 Wang Tile [10] 或者其他纹理生成技术，这可能涉及如何参数化（parameterize）等值面的问题。可以参看图11《EverQuest Next》的例子。

更多精彩图片 请登录

Figure 11: EverQuest next blends two projection textures to map to the generated mesh of any topology.图11：《EverQuest Next》混合两个投影纹理，以映射至任何拓扑结构的生成网格。
In addition to the texture of the surface, it can also enhance the geometric complexity. For example, we can use displacement mapping to add more details to the surface.
除了表面的纹理外，还可以加强几何方面的复杂度，例如我们可以使用位移贴图技術（displacement mapping）去为表面加上更多细节。

Digital engraving and other modeling methods
Before we talked about the representation of many voxels, we will talk about how to establish and edit these data. The predicate of graphics is modeling. Voxels are very suitable for digital engraving, that is, voxels are used as clay to provide tools such as pasting, pushing, pulling, grinding and fabricating to make models. Mudbox (Fig. 12) and ZBrush are ready-made digital engraving tools, but these tools are usually based on modifying the surface mesh geometry without changing the topology of the model. This topology problem will not occur with voxels, but its editing tools are relatively immature.

数字雕刻与其他建模方式
之前谈及许多体素的表示方式，以下再談可如何建立、编辑这些数据，用图形学的述语，就是建模（modeling）。体素非常适合数字雕刻（digital scupting），即是把体素当作粘土，提供贴土、推入、拉出、磨平、捏造等工具去制作模型。Mudbox（图12）和 ZBrush 是现成的数字雕刻工具，但这类工具通常是基于对表面网格几何作出修改，而不能改变模型的拓扑结构。采用体素就不会出现这种拓扑问题，但相对地其编辑工具还未成熟。

更多精彩图片 请登录

Figure 12: Digital engraving on model grid using Mudbox. At present, this kind of technology is usually used for character modeling and texture, and the details are added through normal / displacement mapping. Basic engraving tutorial.
图12：使用 Mudbox 在模型网格上进行数字雕刻。现时这类技术通常用于角色建模及纹理，通过法线／位移贴图去增加细节。基本㓮刻教程。

One of the characteristics of voxels is that it can simply realize the construction of solid geometry (CSG). In order to make modeling easier, CSG can be used to model buildings and other works, which can be voxeled at run time. Compared with direct engraving, this method saves time, is easy to modify, can save capacity, and is more suitable for some automatic generation algorithms. In two-dimensional analogy, just like using vector shape editing in Photoshop, it is only deleted into pixels when necessary. In addition, for ordinary 3D meshes, voxelization can also be carried out, but it is not easy to save the original texture mapping.

体素的一个特点，是可以简单地实现构造实体几何（CSG）。为了更容易建模，可以使用CSG去为建筑等人工物建模，在运行时才体素化。这样比直接雕刻省时，容易修改，而且更能节省容量，并更适合一些自动生成算法。以二维来类比，就像在Photoshop中使用矢量形状编辑，需要时才光删化成像素。另外，对于普通的三维网格，也可以进行体素化，但并不容易保存原来的纹理映射。

Advanced rendering technology
In addition to isosurface extraction and texture mapping, there are many techniques that can be developed in voxel rendering. Because voxels are suitable for ray tracing, some studies have used voxel based real-time global illumination in recent years, such as voxel cone tracing [5]. If the game world itself is already composed of voxels, the voxelization step is omitted. In addition to the common secondary reflection of diffuse surface, this global illumination can also achieve the effects of area light source and glossy reflection / refraction material, as shown in Figure 13.

高级渲染技术

除了等值面提取及纹理贴图等技术外，体素在渲染上还有很多可发展的技术。由于体素适合光线追踪，近年有一些研究使用了体素为基础的实时全局光照，例如体素圆锥追综（voxel cone tracing）[5]。如果游戏世界本身已经是由体素组成，就省却体素化（voxelization）的步骤。而这种全局光照，除了常见的漫反射表面（diffuse surface）的二次反射，还可以实现面积光源、光泽反射／折射（glossy reflection/refraction）材质等效果，如图13。

更多精彩图片 请登录

Figure 13: global illumination using voxel cone tracking. The light source is reflected from top to bottom to the arch ceiling on the ground, and the red cloth also has color bleeding to the ceiling. In addition, note that the ground material contains glossy reflection. (the scene itself is rendered with a triangular mesh.) demonstration video.
图13：利用体素圆锥追综制造全局光照。光源从上而下，在地面反射至拱门天花，红布也有渗色（color bleeding）至天花。另外留意地面材质含有光泽反射。（此场景本身是以三角形网格渲染。）示范视频。

Game technology
Of course, the game is not just a real-time renderer. The focus of the game is gameplay. Many binary voxel games have shown some different game elements, which will not be analyzed in detail here. However, at the technical level, we still need to solve some problems of dynamic voxel world, mainly in physics and artificial intelligence. In terms of physics, the most basic thing is to consider the collision detection and support analysis of isosurface and rigid body collision (the suspended part may fall after cutting, or even break due to structural problems). In addition, relevant fluid simulation and combustion simulation can also be studied. In artificial intelligence, the most basic is line of sight detection and path search. Voxels can also facilitate geographical reasoning and analysis.

游戏性技术
当然，游戏并不仅是一个实时渲染器，游戏的重点是游戏性（gameplay）。许多二元体素游戏已经展示出一些与别不同的游戏性元素，在此不作详细分析。但在技术层次上，我们还需要解决一些动态体素世界的问题，主要有物理和人工智能方面。在物理方面，最基本的要考虑等值面与刚体形撞的碰撞检测、支撑分析（切割后悬空的部分可能需要掉落，甚至因结构问题而断裂），此外也可研究相关的流体模拟、燃烧模拟。人工智能方面，最基本是视线查测及路径搜寻。体素也可利于进行地理上的推理分析

epilogue
The traditional game world has certain restrictions on gameplay and production. Voxel based production can bring various innovations, improve game quality and control production costs. However, subverting the tradition requires the cooperation of all aspects. New thinking should be injected into game design, level design, art production and game programming, which must also be supplemented by solid tools and production processes. In terms of engine technology, we need to solve the needs of multi-resolution modeling of large-scale world, resource streaming according to LOD, real-time rendering, physical simulation, artificial intelligence and so on.
Perhaps this is also an opportunity to explore another game technology path and make innovative games with technical barriers in the future.

结语

传统的游戏世界在游戏性、制作上都有一定限制，基于体素的制作方式可带来各种创新，提高游戏品质并控制制作成本。然而，颠覆传统需要各方面的配合，游戏设计、关卡设计、美术制作、游戏性编程都要注入新的思维，也必须辅以扎实的工具及制作流程。在引擎技术上，需要解决大规模世界的多分辨率建模、依 LOD 作资源串流、实时渲染、物理模拟、人工智能等各个方面的需求。
或许这也是一个机遇，可以开拓另一条游戏技术道路，制作未来具技术壁垒的创新游戏。

谢谢楼主分享

感谢分享！！！！