道路千万条，思路第一条
意识不到位，开发两行泪
近期打算在项目中实现3D场景的自动寻路，从2D到3D，有很多思维定式需要打破，在学习的过程中我的三观也被不断刷新。
所以作为这个系列的第一篇，先讲一下重塑对3D空间的认知
1.2D到3D的思维转换
2D的时候可以用2维数组来描述地图网格(grid mesh)，1表示无阻挡可行走，0表示有阻挡不可行走
2维数组描述地图的局限性在于，当地图非常大的时候，内存开销和阻挡描述的精确性就变成一对矛盾：
单位格子划分过细，那内存开销会非常巨大
单位格子划分过粗，那阻挡就会呈现明显的“锯齿状”，与实际的客户端模型表现有较大出入
另外这样的表示方式可能会造成一些思维误区：
误区一：游戏场景中假如有一块大的连续的不可行走区域（比如一座山或者一个湖）需要把这块区域都标记为不可行走
其实并不需要把所有区域都填满，只要将区域的外轮廓标记为不可行走就足够了（不考虑程序bug导致穿过阻挡的情况）
就像在2D平面中，我们画一个矩形的时候，画的是4条线段，而不需要真的把矩形完全填充
所以当地图很大时，就需要用“轮廓线”（多边形顶点集）的方式来描述一个阻挡
误区二：有阻挡则不可行走，无阻挡则可行走
这在2D不考虑玩家模型大小的时候是正确的
而如果考虑模型大小，那么无阻挡的区域也不一定是可行走的，需要空间尺寸足够容纳模型
而在3D空间中，玩家其实并非浮空的，而是站在阻挡上的（地面，山坡，屋顶），如果没有这些阻挡，玩家就会下坠
可以参考2D的横版超级玛丽，地面和“石头层”既是“阻挡”又是“行走区域”，如果没有地面，马里奥就会直接掉下去gameover
所以在3D空间内的可行走区域其实是阻挡的上表面
2.3D建模（体素化与可行走面）
改变对“体”与“面”的认知
如何表示一个“体”（比如一间房屋，一个山坡）
跟2D用线段来表示多边形一样，我们可以用多面体的所有表面来表示一个多面体
比如一间房屋（一个6面体）可以用6个矩形来描述
如何表示一个“面”
这里会引入“体素化”的概念：
想象有一个3维网格，一个平面会与其中的若干小立方体（即体素，可以对应二维图形的像素来理解）相交，把所有相交的小立方体取出来，就可以用这些体素的集合描述一个平面
这里需要注意的是体素化之后，“面”实际上已经转换成了一组“体”，数学意义上的“面”是没有厚度的，但是体素化之后的“面”是有厚度的，厚度就是体素的边长
因此3D场景的“地面”其实只要一个平面就可以表示了，而不需要一个大而薄的立方体
如何表示一个面是否可行走
考虑这几种“面”
地面
山坡坡面
房子的墙
对游戏来说，地图是可走的，墙是不能“爬着走”的，山坡坡度小的时候可以走，坡度高了就不能走
因此我们可以定义一个最大可行走角度
对于面的体素集，我们可以在体素化时记录面在这个体素上的法线角度，并与可行走角度做比较，由此得出这个体素的“上表面”是否可行走
对墙来说，由于所有体素的角度都大于可行走角度，所以走到墙边就会被挡住
而一个面的体素集中所有上表面可行走的部分就构成了一个“可行走面”
一些“反?！钡南窒?/h5>
当我们用多个面来表示一个不可穿行的实心多面体的时候（比如一块巨石），在计算机实现时，内部其实不是实心的，而是可行走的。只是玩家永远无法穿过表面进入内部而已
3.将可行走面从体素转换回3维空间顶点集合
体素集合可以用来判断空间内的点是否可行走，但是如果在体素集上寻路，效率会非常低（体素的粒度非常细，所以在体素上直接寻路，会生成过多的中间节点），所以我们希望将由体素表示的连续的可行走面合并，再转换回由顶点集合表示的空间平面，
同一平面内部的任意两点是直线可达的，不同平面上的点，需要根据联通关系通过其他的寻路算法（比如a*）来求出路径
可行走面实际上是空间内若干个在xz平面投影相邻的小方格平面组成的，我们将这些相邻的小方格平面合并，得出它们的边界顶点，然后将这些顶点进行过滤，只保留实际影响图形形状变化的部分。
而这些保留下来的点就是可行走面的3维空间顶点集合
看到这里你可能会问，那这跟输入的多边形顶点集合有什么差别呢？
实际上我们输入的数据是游戏场景中的几何体，我们并不知道那些面是可行走（比如屋顶），哪些是不可行走（比如墙壁或者陡坡）
而进过体素化之后，得到的多边形顶点集合，描述的都是可行走面，并且会通过一些条件合并可行走面（如楼梯会被合并成一个斜面）
