【从Houdini到UE4】基于体素的模型乐高化算法

山水之间大有人

本文将讲述体素在虚幻引擎中的部分运用以及模型乐高化的特效的制作方法。



题图，出处https://www.iamag.co/object-to-lego-in-houdini/，本文的实现可以100%复刻甚至可以做到其做不到的复杂Pattern（当然，物理需要读者自己去实现了）

通常该算法都使用Houdini实现，但是读者可以跟随本文，不需要Houdini，从0开始在虚幻引擎内构造一个乐高化的算法。本文的笔法将会比其他杂谈简练，尽量不说废话（没错，就是尽量不打括号）。
本文实际上是三年前【从Houdini到UE4】基于点云与Dijkstra的血管生长特效蓝图底层算法实现 - 知乎 (zhihu.com)这篇文章的延续，目标是把Houdini里的一些基础算法复现一次，以加深认识。
先贴几张效果图：



左一：原模型；左二：体素模型；右一：俄罗斯方块；右二：乐高模型



左一：原模型；左二：体素模型；右一：俄罗斯方块；右二：乐高模型



左一：原模型；左二：体素模型；右一：俄罗斯方块；右二：乐高模型



左一：原模型；左二：体素模型；右一：俄罗斯方块；右二：乐高模型

以及一个生成的全过程视频：

乐高化模型全过程演示
https://www.zhihu.com/video/1615036231515119617
本文使用的工具只有蓝图，将会从0开始对模型乐高化算法进行解析。如果读者需要复现这个项目的话，可以到虚幻商城搜索Fantastic Toy Bricks Generator或者点击下面的链接支持作者。
目前全部收入都会用作作者平时的生活费（以及未来可能的学费），最近已经没钱支撑生活开销了，作者在屏幕外面给大家磕头了。

目录

零、动机
一、表面体素生成
        1.体素化是什么/为什么
        2.体素化算法分析
        3.本文的算法
二、体素着色
三、内部体素生成
        1.Greedy Meshing
        2.厚度体素
        3.内部着色
四、应用乐高化
        1.Pattern Matching
        2.应用Style
        3.乐高Style
4.俄罗斯方块Style
五、问题与改进
六、总结
零、动机

动机就是没钱了，做点插件赚点钱。顺便整理一下体素化的算法（虽然笔者之前的文章也整理了许多次）。
一、表面体素生成

1.体素化是什么/为什么




https://www.sciencedirect.com/science/article/pii/S0264127519308470

体素化的定义，根据imagej[1]的介绍
Voxelization is the process of converting a data structures that store geometric information in a continuous domain (such as a 3D triangular mesh) into a rasterized image (a discrete grid).
翻译过来介绍把其他储存几何信息的数据结构转为体素的结构。体素的性质对比多边形有许多优点，因此在一些任务经常会使用体素（具体的优劣，本文不进行赘述）。
根据我们之前流程，我们需要搞清楚乐高化这个任务的输入输出是什么。对于游戏资产来说，我们常用三角形作为数据储存方式。因此输入的是三角形的模型，而输出则是乐高化后的（三角形的）模型。而体素化只是中间一个步骤。示意图如下：


2.体素化算法分析

体素化的算法有很多，这里列举几种常用的表面体素化算法。
A. 三角形-体素求交法[2]。该算法输入三角形和Box（也就是更泛化的体素，由Center和Extent构成，也叫做AABB），输出bool判断是否有交点。
利用这个算法，我们有两种做法，一是For Each Grid，利用BVH Query这个Grid可能覆盖的三角形，求交，填入结果；二是For Each Triangle，求出其Bounding Box包裹的体素，然后对于每个体素进行这个算法进行求交。这两个方法各有优劣，本文不过多分析复杂度。前者可以无锁进行多线程加速，后者可以通过原子操作也进行多线程加速。（个人偏好后者）
B.光栅化。该算法最初是在SVOGI（或者VXGI）里经常用到的。原理也很简单，通过正交视图的光栅化获得当前像素的深度来还原表面体素的位置。该算法可以通过关闭深度剔除来多次写入体素（没实现过，这里可能有误，但是意思大概是这样）来实现被自身遮挡的部分的体素化。



vxgi的配图

C.多次光栅化。该算法是B的简化版。我们知道，体素可以看作是一堆相同维度的图像的堆叠，换句话说沿着轴，每个Slice都是一张图像。我们可以通过让正交相机在体素BoundingBox范围内For Each Slice进行捕获，慢慢堆叠出来一个完整的体素模型。这个功能笔者也曾经在UE中复现过，具体可以参考，比较Tricky这里不在赘述。
D.LevelSet。其实就是把Mesh转为有向距离场，然后在水平集=0的地方（也就是和三角形距离为0的地方）填入体素。该步骤可以直接简化为，对于每个体素的Grid，找到最近三角形的距离，如果小于某个阈值则写入体素。

E.PointCloud。想象这样一个场景，在模型上撒了无数均匀的点。每个点都会对应唯一一个体素，把每个体素包含的点积分一次就可以获得模型的体素信息。这个算法在笔者之前的知乎上有介绍过【从Houdini到UE4】基于点云与Dijkstra的血管生长特效蓝图底层算法实现 - 知乎 (zhihu.com)，里面也包含了一个简单的项目，感兴趣的读者可以去看看（给俺点个赞咧谢谢大家）。


这个算法的优点是，他几乎就是GroundTruth（通过核函数对点云进行Filter着色体素，十分地完美），在点接近无穷的情况下。但是我们在一般的项目里没有那么多的算力，在点较少的情况下很难做到完全体素化，会有洞洞。避免的方法也有很多，下面笔者将会介绍一种。

3.本文的算法（Ray Trace）

本文的项目使用的是不一样的算法，比之前介绍的算法要更加Tricky，但是实现十分简单。我们知道，在表面上的点集可以转为体素，但是这样做很可能会出现孔洞，那么有没有一种办法能基于表面点集又能避免孔洞呢。答案是Ray Trace。
拿2D来举例，



左边理想情况，右边虽然不是理想情况但是也能兜住

如果随机从一个格点发射一条射线，他有可能会和物体相交，而交点就是上面提到的点云的子集（里的一个点）。他也有可能不和物体相交。但是如果对于每个格点来说，我们都做若干次随机的射线，那么错过这个格点附近的交点的概率则几乎很小（本文不会用严格的数学来证明）。
因此本文采用的算法是
Foreach Grid:
    Loop N Times:
        Raytrace(GridCenter, RandomDirection)如果有交点，就将该交点信息 R_{i,j} （比如颜色，法线）储存到（交点）最近的体素格子 i 中。
这样我们就得到了一个十分简单的体素化算法。
二、体素着色

前面提到，我们把交点信息储存到了最近的体素格子里，本文仅使用了颜色信息。
简单地把当前体素格子里储存的颜色信息做一个平均即可： C_{i} = \frac{1}{\left| R_{i} \right|}\sum_{j}{R_{i,j}}
如果需要更加物理，更加看上去厉害的结果，我们可以用一些衰减（或者说核函数）来控制权重。
这里假设交点信息包含了该交点到最近体素中心的距离 D_{i,j} ，我们加权平均一下就好了：
C_{i} = \frac{1}{\sum_{j}{f(D_{i,j})}}\sum_{j}f(D_{i,j}){R_{i,j}}
三、内部体素生成

通过前文的步骤，我们应该能生成一个体素模型，但是他没有内部结构。


为了方便后续模型乐高化，我们需要一个有若干厚度的体素模型。为此我们需要对目前的体素模型建立一个可以支持射线求交的Query系统（也就是能让他用UE4的方法进行Trace）。首先，需要建立一个ProxyMesh。
1.Greedy Meshing

相信对于熟悉Minecraft的玩家来说不陌生。Greedy Meshing是一种古老的常用的体素模型优化算法。
具体的效果是，输入体素信息，输出优化过的模型表达形式（不是最优）。



https://bbtarzan12.github.io/Marching-Squares-Part-3/

具体的感觉可以参考上面的文章，总的来说就是减少了三角形的数量（以及减少了Box的数量）。这对于脆弱的蓝图系统来说很重要，因为太多的Box很可能会导致引擎无响应很长一段时间。



Greedy Meshing的中间过程

2.厚度体素/3.内部着色

有了ProxyMesh之后，我们能接着生成带厚度的体素。具体做法和表面体素生成算法类似，都是从体素中心发射射线出发。
首先我们需要判断体素的内部。只有发射出去的全部射线都Hit了才算内部（这是一个Relax的条件，如果射线数量过少，会有误判，既不是内部，但是被误判为内部的情况发生）。
其次我们需要计算射线的最短距离。当这个最短距离 小于 某个阈值，即可判断为内部厚度体素。其余的情况，虽然是内部体素，但是并非我们需要的，均可以舍弃。
最后是对于内部体素的着色，方法也有很多，可以简单地选取最近的交点的颜色作为体素颜色，也可以通过射线加权的结果作为最终的体素颜色。
四、应用乐高化

回顾之前的步骤，我们现在应该得到了一个带有若干厚度的体素数据，这个体素数据我们可以假设包含
1.占/空状态
2.颜色信息
通过这些数据，我们接下来可以应用乐高化。当然，乐高化只是一个特例，实际上本文的项目的系统可以实现其他更多种的配对方式，因此我们将会从最通用的方法开始介绍。
1.Pattern Matching

对于一个“乐高砖块”，我们可以视作一个小的体素信息。比如我们可以通过两种方式来表达以下的两种砖块。这里我们采用长宽高的顺序进行表达。


A.方法一
红色砖块是1x2x1的，但是由于高度未满1，因此红色砖块有一个附加的生成规则：只能用于最顶端。
黄色方块则是1x1x1的最简单的形式。
B.方法二
红色砖块是2x4x1的。
黄色方块则是2x2x2的形式。
为了能让表达形式更加自由，可以将这两个方法进一步抽象出来，通过预设的匹配规则来定义一个乐高块，目前本文的项目的匹配规则有以下几种：
有五个字符代表了体素的不同组合规则：
0代表该位置必须为空，但不会被写入；
1代表该位置必须为空，将被写入并标记为非空；
?代表该位置可以是任何状态，但不会被写入；
#代表该位置必须非空，但不会被写入；
X代表该位置必须为空，将被写入并标记为特殊。这也许和图灵机有点像，具体的原理目前笔者没有水平解析，但是通过这些Pattern的组合可以完成一些复杂的过程化生成。



斜边，梯度匹配



斜边，梯度匹配

比如斜边，可以通过判定周围体素的斜率（也是通过这个提前定义的Pattern进行的）来进行生成。



一个Pattern的示例

2.应用Style

对于一个 X\times Y\times Z 大小的Pattern，我们可以对体素中每个 X\times Y\times Z 大小的子体积进行一次Match的判断，判断是否符合该Pattern的规则。同时，我们可以通过设置检测时的Stride来加速这个过程。
因为对于一个 W\times H\times D 的体积来说，判断一个Pattern需要的复杂度是 O(W\times H\times D \times X\times Y\times Z) 十分缓慢。加入Stride之后可以获得 O(W\times H\times D \times X\times Y\times Z)/(Stride^3) 的复杂度，稍微减缓了该算法的压力。
3.乐高Style



本文的乐高风格基本砖块由该五种模型构成。



正视图



顶视图

因为有斜边的存在，让模型更具有细节，以及更加可信。
4.俄罗斯方块Style

本文的俄罗斯方块Style比较复杂，因此只贴出效果图



正视图



顶视图

五、问题与改进

本文的算法有几个主要的问题

• 无法做到实时生成，受限于蓝图系统和Pattern Matching的判断复杂度过高，导致算法运行太过缓慢。
  
• Pattern的设计依旧过于抽象，用户可能比较难拓展。
  

对于这两个问题，目前还没有更好的解决办法。希望之后能解决然后继续更新该项目。

六、总结

本文介绍了一个可在UE4的蓝图系统中实现的模型乐高化算法。其中穿插了若干与体素相关的算法分析。
和三年前的文章一样，本文章不是教程，我的所有文章都是在分享自己的思想，每一步怎么想的都完整呈现了出来，希望能够帮到初学者，也希望有大神可以指出不足，这也是我写这一类文章的目的。比起分享知识，分享思路举一反三可能会更好，本人是如此觉得的。
因为受到某个不存在的病的影响，作者的家庭在收入方面受到了一点冲击，如果读者想支持我的学业（或者生活）的话，可以到下面链接购买本项目。目前作者在屏幕外面疯狂地磕头，在这里感谢大家的支持了。
接下来的文章，可能和流体模拟相关。希望能在这个假期抽空写完。
感谢阅读。

流体模拟，但是没有模拟
https://www.zhihu.com/video/1615030982334939136
写完之后感觉这篇文章好水QAQ
参考

• ^体素化定义 https://imagej.net/imaging/voxelization#:~:text=Voxelization%20is%20the%20process%20of,image%20(a%20discrete%20grid)
  
• ^三角形-体素求交（这里引用可能有误 https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tribox_tam.pdf
  

廖先振

[棒]

台敬协

tql[大哭][大哭]

君凡

厉害！[赞][赞]