Unity Light Probe 自动均匀分布方法
在使用 Unity 的 Light Probe 进行光照烘焙存储时，常常需要手动添加大量的 Light Probe 点，这种手工操作既枯燥又繁琐。因此，我们需要一种能够根据选中的 Mesh 表面信息，自动生成一层均匀分布的 Light Probe 的方法。
现有方法及其局限性
网上有一种简单的方法，它基于选中 Mesh 的 AABB 三维包围盒，在 XY 平面根据包围盒大小均匀散布 Light Probe 点，然后沿 Z 方向位移一定距离后复制所有点，从而生成整个 Light Probes Group。生成的 Light Probe 点集分布如下所示：
这种生成方法的主要缺点是与物体本身的形状耦合度较低。如果场景中需要生成 Light Probe 点的区域不是规则平整的平面，要获得较密集且均匀的点集就非常困难。此时，需要手动选择平整的面，一个面一个面地生成，操作十分麻烦。特别是在赛车场景中，通常只需要在赛道上均匀分布 Probe 点，而其他部分不需要，这种情况下就不能对整个场景使用该算法。
基于 Triangle Mesh 的均匀随机采点算法
针对上述问题，我们小组查阅了相关资料，发现一种名为“扔飞镖” [1] 的基于 Triangle Mesh 的物体表面均匀随机采点算法，非常适合解决当前遇到的问题。
算法基本思路
该算法将每个三角形（Triangle）看作一个独立的整体，每个三角形获取样点的概率与其面积成正比。首先，将所有三角形面片收集到一个名为 Bin 的数据结构中，如下所示：
算法会维护这个 Bin 数据结构，将三角形按照面积所在的区间，分布在不同的三角形集合内。假设最大三角形面积为 $A{max}$，则 0 号集合的面积区间为 $[A{max}, A{max}/2]$，1 号集合的面积区间为 $[A{max}/2, A_{max}/4]$，依此类推。最后一个集合保留所有未归类到上述区间的三角形。实际应用中，可以根据三角形的数量来决定总共需要几个三角形集合，集合内的三角形是无序的（即不排序）。
采样过程
- 选择三角形：首先随机选择一个集合，然后从选定的集合中依次遍历所有三角形，采用拒绝采样的方法选择该轮选中采样的三角形。具体做法是随机生成一个 $[0, 1]$ 的数，如果该数小于 $A{cur}/B{max}$（其中 $A{cur}$ 为当前选中的三角形面积，$B{max}$ 为选中三角形所在集合的最大区间值），则选中该三角形进行随机采样。
- 三角形内部随机采样：当三角形获得一次采样机会后，使用三角形 UV 坐标系进行随机采样。三角形内部随机采样公式如下： [P = (1 - \sqrt{r_1}) \times A + (\sqrt{r_1} \times (1 - r_2)) \times B + (\sqrt{r_1} \times r_2) \times C] 其中，$r_1$ 和 $r_2$ 分别是两个 $[0, 1]$ 的均匀随机数，$A$、$B$、$C$ 分别为三角形三个顶点的坐标。详细的数学推导可参见参考文献 [2] 的 4.2 节。
- 三角形细分：假设采样的三角形为 $T$，给定一个样点距离 $l$。在 $T$ 中随机采样完成后，如果三角形的三个顶点到采样点的距离都小于 $l$，则该三角形被抛弃；否则，将三角形细分。具体做法是取 $T$ 每个边的中点，将三角形分为四个大小相等的三角形 $T_1'$、$T_2'$、$T_3'$、$T_4'$，如下图所示。然后对这四个三角形进行上述检测，通过检测后将它们加入到维护的 Bin 数据结构中。
注意事项
- 采样点距离检测：为了防止采样点距离过近，需要维护一个三维数据结构，如八叉树（OCTree）或 KD 树（KD-tree），用于检测当前计算好的采样点是否满足距离要求。如果不满足，则重新选取采样点。如果超过三次仍找不到满足要求的采样点，则将三角形直接分为四个小三角形并加入 Bin 结构中。
- 防止无限细分：为了避免三角形无限细分，可以设置一个阈值。如果三角形的面积小于该阈值，则直接取三角形的重心点作为采样点；当三角形过小时，则直接抛弃。
生成 LightProbes Group
最后，为了构成 LightProbes Group，在每个 Probe 所在的三角形法线方向进行一定位移，复制生成另外一个 Probe。效果图如下所示：
（左边为本算法生成分布图，右边为原算法生成分布图）
将该算法应用于赛车项目中，对跑道进行 LightProbes 均匀分布，取得了较好的效果，如下图所示：
参考文献
[1] Dart Throwing on Surfaces, D. Cline1, S. Jeschke1, K. White2, A. Razdan1 and P. Wonka1, Eurographics Symposium on Rendering 2009 [2] Shape Distributions, ROBERT OSADA, THOMAS FUNKHOUSER, BERNARD CHAZELLE, and DAVID DOBKIN, ACM Transactions on Graphics (TOG) 2002