程序化岩石包边
前言
哎，大过年的闲的没事，把这个史前大坑给凑合填了填。
一开始为啥做这个呢，主要是看到育碧那一套岩壁生成，以及网易的撒点包边技术分享，觉得道理都懂了，突然就充满了自信想着挑战一下这个难题，结果把自己坑进去坐牢。断断续续地研究了差不多三个月吧，走了非常多弯路，推倒重来了无数次，现在算是摸索出了一个能提供点生产力的方案，总结一下。
首先得说一下这个工具的一个技术目标，以及我期望他能达到的一个效果。
1. 为了更方便做性能优化以及美术修改，走的是撒点工作流。
2. 着重于对非重要小石头的合理分布使得场景丰满，对于场景观感影响较大的石头仍需要手动放置。
3. 需要尽量让非技术背景的用户理解参数意义，参数空间不能太大，降低学习成本。
4. 中间过程需要可视化，让有经验的用户更好的调节参数，所以选择用PDG来进行流程控制。
大概就是这些，目前由于还没有投入实际使用，第三点还难以评估，其他目标倒是都实现了。
先看一下引擎里头实际操作的效果：
地形大小为512*512，只用了一块石头prefab。多种尺寸的石头进行尺寸匹配的规则已有，只是懒得搞那么多石头……
视频里头看到五颜六色的玩意是中间切分产物，给了一个显示顶点色的材质进行可视化而已，下面会每一步单独说一下。
整体思路
接下来介绍一下主要思路：灵感说来也怪，来自于看GAMES202光追部分时对于场景物体的bbox抽象，以及生成多噪声结果再进行降噪的做法。我个人理解，包边问题其实就是一个地理特征识别的问题，而在不考虑神经网络前提下，这其实就转变为一个不规则几何表面的划分问题。一个地形高度图的属性无非就那几个，曲率，高度，密度等等。而所谓地理特征，比如怎么定义一个陡坡，怎么定义一个悬崖，如果用这几个仅有的属性，总会难免陷入阈值难以确定的死胡同。
我的做法就是摆烂，生成一堆噪声，然后合并。既然难以做到精确切割，那么就用保留大量噪声的切割加一次合并去逼近。并且，这个切割-合并组合是可以多次进行的，次数越多结果的可控程度也会越高。
第一轮切分
首先，用最糙的滤波方法（使用坡度作为阈值进行二值化）过滤掉比较显著的噪声，得到一个较大的可摆放石头的区域；
然后，对这个区域进行一个窄边切分（这是重点），尽量切多点区块出来（切的越碎越好，生成大量噪声）；
最后设置一个合并的目标（比如面积，宽高比），对零碎的区块进行邻接区块合并（降噪）。
上述最主要的三个中间步骤，而能供调节的参数并不多，但都能产生非常显著的变化。
第二轮切分
有了小区块之后，其实已经可以开始考虑计算石头的缩放和枢轴位置了。但是，经过我多次测试，到这一步其实切的还是太糙了。很多细长区块本来应该包上多个石头会比较好看，但是合并的时候把这部分信息筛掉了。所以，我又开始了新一轮的切割-合并。
这次和第一轮不太一样，因为我们这次主要是要处理细长区块，我们就该先把这些部分识别出来。我的识别标准是区块有且只有两个边缘与周围区块相连（如下图）。
然后把符合要求的片朝向信息和bbox信息记录到上边缘的线中，只保留上边缘线，得到这样的结果：
白色部分为参考，这部分的结果是彩色的线。
从面降维到线之后，我们的切分手段可就太多了。依然是切分-合并的原则，我对于所有连接一起的线进行等距细分之后（细分的时候线上的bbox和朝向信息取最近区块的值），设定合并的长宽目标（高度忽略不计，石头往下插地里看不出），高度差，角度差作为判断条件之后开始走feedback循环和领接线段合并，这部分ui如下：
而进不了精细切割的区块，只能走按照bbox来生成石头信息的方式了。这一个部分会产生大量的巨大石头（原因是前面窄边切割的时候对参数的设置不合理，同时也是目前窄边切割方法一个局限性，下文说）：
目前只是简单的给所有石头大小排了个序，然后可以选择去除最大的N个石头这样子。不过有的时候一些大石头摆起来也挺好看的，特别是石头种类多的时候，在大区块中匹配到更大的石山类型的组合石头。当然这是用资源丰富度去弥补算法不足了，再看吧。这部分可以控制的参数如下：
核心算法介绍
说了这么多，其实大部分工作都是纯苦力，没什么技术含量。我真正坐牢的是卡在了窄边切割算法上，这里要感谢houdini群里的大佬提供的思路，没有您就没有这一个玩意呐！感谢感谢！
一开始的时候，我考虑的是如何找到面片的“龙骨”，即如何得到面片的中心线。很明显应该用SDF，于是我试了，错就错在SDF是逐点的一个值，而且所谓“中心线”上的SDF值域是不可知的，也就是我确实可以进行中心线可视化，但是我不能把它给提取出来。这个牛角尖钻了好久，中途发现了一些诸如straight_skeleton_3d的神奇节点能找模型的龙骨（基于体素，计算实在是太慢了），以及随机切割然后找短边的方法等等，都不太给劲。
现在使用的方法非常巧妙，是基于地形生成的面片都是均匀像素化的这个前提。先放一下节点图：
熟悉groupexpand节点的朋友应该已经知道怎么做了。就是每一次循环走不同的step，不同的step可以产生不同的独立中心区域：
把区域同时往外flood（直到遇到另一个区域为止），可以在不同独立区域之间产生一条分界线，这样就把窄区域给切出来了：
这个方法固然是非常粗略的，但是足够用了，重点是非常快，比真的去算中心线快多了。
而这个方法弊端就是，对于各式各样的面片，有点难以判断step多少是比较合适的。我之前尝试过一种启发式的算法，让step从1开始到一个固定值进行循环，每一次记录一次独立中心岛屿的数量，然后取最大数量的那次step进行实际的计算。想法很美好，但实际上不太可行。这个step可以理解为用户想要切分的“窄边”的宽度一半，而所谓“窄”其实是相对面片实际面积的一个概念，而不是一个绝对的数值，所以其实是不存在一个“理想值”的。另一个方面，这个“理想值”可能需要非常大的样本量才能收敛到最优值，而这就给算法带来一个死循环的风险，这也是不可接受的。
正因如此，我把这个step的设置交给了用户，即上面第一轮切分的UI中“切分单位”那个奇怪的数组。这里数组有四个数字，代表这种切分会循环四次，并且分别会以6，4，2，1作为step来切割。
所以，切分结果如果出现了太大的片，可以把step给调大，增加循环，比如我这里设置了30，20，10，6，4，2，1，进行切分：
能看到大区块也被切的更小了。而目前设计比较好的一点是，step的数值的大小对于单次循环的运算时间影响是非常小的，所以多几次循环也还好。只是这个值的合理设置确实需要一些学习和使用经验，没什么办法。
差不多就是这样咯，这玩意现在也只是一个雏形，在这之上我个人还有挺多想法的，比如改一下HE的UI，整一个网易他们那样拼石头资产库的工具等等……以及看看Houdini 20版本sidefx能不能把他们画的神经网络识别地形的大饼给做出来，他们要整出来了我这套东西直接可以丢了咯~收工！
本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 (CC BY-NC-ND 4.0) 进行许可。