[toc]

# 引用 (放在最上面咯)

[1] dividePoly
[2] 从零开始学导航网格
[3] recastnavigation
[4] critterai

# 引言

Unity 中 navmesh 网格的生成就是通过 recast navigation 进行的。recastNavigation 构建的第一步就是对被烘焙对象的网格进行体素化。
而这个体素化就是本篇文章索要探讨的内容。

# 1. 高度场

什么是高度场？如下图所示是一个空间
图一。完整空间 将这个空间按照指定的 块大小 和 块高 进行分割，可以得到如下的区域划分：
图二。高度场
我们称这个空间划分的方式叫 高度场

# 概念一 - AABB 包围盒

用最简单的语言来讲，三角形的 AABB 包围盒就是一个可以包裹住一个三角形的最小的矩形。这个矩形平行于 xz 轴和平面。 图二。高度场 如上图所示，一个完整的模型的 AABB 包围盒就是可以完整包围住这个模型的最小矩形。

AABB 包围盒的计算方法

遍历模型的每一个顶点，找到所有顶点中最小的 <x,y,z> 和最大的 < x,y,z>, 记前者为 bmax , 后者为 bmin , 由这两个顶点组成的就是该模型的包围盒。

# 凸多边形沿轴切分

# 想要解决的问题

在进入正题之前，需要先阐述清楚为什么 导航网格 的生成前要进行体素化。

导航网格主要需要以下几个信息：
- 1. 模型的表面 - 2. 模型的表面是否可以通行 - 3. 希望网格数据尽可能的少 图三。高度场内的体素化 上图所示是 recastNavigation Demo 的体素化结果，这个体素化的结果是在图二所示的高度场空间内完成的。由上图可知，如果想要知道一个表面是否可以穿行，就必须得到表面到 天花板 的距离。而这个距离借助 图二 的高度场可以很轻松的得到 (比如计算当前所在体素格子到上方第一个体素格子间的空白格子数)。
所以，体素化实际上是将模型转换到高度场空间，且体素化有助于更轻松的计算模型的表面和其他信息。

# 体素化

在渲染引擎中，模型是由无数小的 三角形 构成的，实际的体素化过程也是对这些三角形进行体素化。 在图形学领域有一个概念叫做光栅化，即计算三角形需要绘制到屏幕上的哪些像素。这个概念在体素化中也有用到。 首先，三角形在高度场的 XZ平面 上进行 光栅化 。在 Recast Navigation 中的光栅化算法使用的是 逐行扫描 的算法。