设计地图数据结构

[Alexbeast-CN]

参考以上格式实现地图的数据结构。此外，地图还包括以下功能：

• [ ] io (地图的保存与读取）
• [ ] 数据结构的文本编码
• [ ] 数据结构的二进制编码

[Alexbeast-CN]

数据可视化以及添加 cell 都不困难，比较难的是如何构建 cell 之间的 connection。

以下是使用 Matplotlib 绘制的 surface，随着 cell 数量的增加，可视化也越来越卡。

[Alexbeast-CN]

Connection 的定义：

Cell 之间存在 Connection 意味着 2 个 cell 存在 2 个共同的顶点（4邻域），或一个以上的共同顶点（8 邻域）。

先需要根据 connection 的定义实现已知一系列无序 cells，为每个 cell 计算 Connection

[Alexbeast-CN]

仅靠中心点和法向量无法定义唯一的正方形。只能定义一个平面。

但如果知道正方形的四个顶点，则可以找到唯一中心点和法向量。

因此存储数据的时候，使用 4 个顶点来表示一个 cell，而在 query 的时候则可以通过中心点的位置，或者 cell 正方形内部任意一点的位置，从 surface 的所有 cell 中找到所需的那个一个。

METHOD1: 新的 surface 存储时的数据结构应该为：

[Cells]
Cell1: {v1: (x1, y1, z1), v2: (x2, y2, z2), v3: (x3. y3. z3), v4: (x4, y4, z4)}
Cell2: {v1: (x1, y1, z1), v2: (x2, y2, z2), v3: (x3. y3. z3), v4: (x4, y4, z4)}
...

[Connections]
Cell1: [Cell2, Cell3, Cell4, Cell5]
Cell2: [Cell1, Cell6, Cell7, Cell8]
...

[Alexbeast-CN]

参考1：

在 voxel map 中，如果整个地图的所有 voxel 边长一致，则仅需要知道 voxel 的中心点位置就定义一个唯一的 voxel。这是因为 voxel map 禁止旋转，所有的 voxvel 必须延世界坐标系的 x, y, z 轴计算顶点。

仅靠中心点和法向量无法定义唯一的正方形。只能定义一个平面。

但如果依照上面的方法禁用旋转，得到的非世界坐标系 x, y ,z 方向的几何体会很抽象。比如下面的一个由边长为 1 的正方体组成的半径为 10 的球体：

[Alexbeast-CN]

在 3D 建模软件如 Blender 中有一个 uv map 技术，似乎非常符合我们的技术需求。以下是 blender 中人体建模的示意图：

[Alexbeast-CN]

[Research]

找到了一个名为 QuadRemesh 的技术，其功能是从现有的曲面、实体、网格或者细分物件快速重建四边面网格。很多三维建模软件都有提供。比如 Rhino RuadRemesh

[Alexbeast-CN]

[Research]

找到了一个开源仓库 QuadriFlow 可以实现如下效果：

其对应的论文为：QuadriFlow。使用Connected Paper 找到了领域的相关论文

[Alexbeast-CN]

[Resource]

MeshLab 是一个不错的开源库，可以先尝试一下其中 QuadRemesher 的效果，并与 State Of The Art 的开源方法，比如 quadwild 进行对比。之后选择最适合的，即能够在损失最小的几何形状的前提下，生成尽可能规则的四边形网格。

[Alexbeast-CN]

[测试]

MeshLab 的算法效果一般，里面的 QuadMesh 相关算法都已经很老了。不太好用。

仅能实现对简单的三角形配对成四边形，且四边形的质量不佳，大小不一。

[原因分析]

1. 我输入的模型，三角网格不均匀。
2. MeshLab 不对原始网格进行优化，直接匹配，因此效果奇差。

[优化]

最好先在模型表面采样，把让三角网格变得稠密。然后再转换为四边形网格。

[Alexbeast-CN]

[测试]

尝试了 instant-meshes 的代码，感觉效果还不错，这个仓库甚至自己实现了一个 GUI 以及固定光源下的实时渲染！

缺点： 依然存在一些非正则化的点。

Paper: instant-meshes ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2015)

[分析]

instant-meshes 利用了交叉场对表面重新网格化，这是我们非常需要的，因为我们的数据源中有一部分数据是 CAD 转出来的，这样的数据可视化效果与上图类似，问题是网格不均匀，虽然对 CAD 来说，这样的数据非常适合准确的描述几何特征，但不利于我们进行三角网格的匹配。而交叉场则可以完美的解决这类问题。

至于 instant-meshes 的缺点，在 15 年之后的论文都有在尝试改善，比如：QuadriFlow

[Alexbeast-CN]

[Problem]

Quad Mesh 导出的数据格式还是 .ply 或者 .obj 之类的网格。这类数据结构并不能够直接给规划来用，所以需要思考如何构建适合规划的数据结构，以及如果将 Quad Mesh 高效的转换为该种数据结构。

[Alexbeast-CN]

[测试]

• Instant Meshes

• QuadWild-Bi-MDF

• QuadriFlow

[分析]

Instant Meshes 生成的网格更加均匀，但会丢失一部分的模型准确度。

QuadWild 则会生成相当准确的模型，但是网格很不均匀，因此并不利于规划。

QuadriFlow 的模型形变的相当厉害，尤其最不希望发生形变的，一些 sharp 的边

[结论]

Instant Mesh 是最适合我们项目的方法。

[Alexbeast-CN]

换一种思路，如果我们在顶点上进行规划，就可以直接使用 QuadWild-Bi-MDF 的结果。在图搜的时候，直接沿着 edge 进行搜索，可以不用额外构建图。并且地图的保存，读取，和可视化也都可以使用 .obj 格式了，可以直接利用现成的库进行。

[Alexbeast-CN]

以下是 .obj 文件中常见的几种元素：

• 顶点 (Vertex): 用 v 开头的行表示顶点，后跟三个浮点数表示顶点的 x、y、z 坐标。例如：v 1.0 2.0 3.0

• 纹理坐标 (Texture Coordinates): 用 vt 开头的行表示纹理坐标，后跟两个浮点数表示纹理坐标的 u、v 值。例如：vt 0.1 0.2

• 法线 (Normal): 用 vn 开头的行表示法线，后跟三个浮点数表示法线的 x、y、z 分量。例如：vn 0.0 1.0 0.0

• 面 (Face): 用 f 开头的行表示面，后跟一系列顶点索引或者顶点索引/纹理坐标索引/法线索引的组合来定义一个面。例如：f 1/1/1 2/2/2 3/3/3 表示一个三角面或者 f 1/1/1 2/2/2 3/3/3 4/4/4 表示一个四边形面

[Alexbeast-CN]

在 .obj 文件中，是无法直接找到一个顶点的所有相邻顶点的。.obj 文件只包含了顶点、纹理坐标、法线和面等信息，而没有描述顶点之间的具体连接关系。要找到一个顶点的所有相邻顶点，可能需要在加载这些数据到内存后，根据面的定义来构建顶点之间的连接关系。这通常需要遍历所有的面，并根据面的顶点索引来确定顶点之间的连接关系。

[问题]

找到后是否需要边以另外一种形式存储？

• 好处：
  • 节省计算量，处理好之后就可以直接用来导航。
• 坏处：
  • 新的数据结构无法直接进行可视化，还是需要利用 .obj 来实现可视化。

[Alexbeast-CN]

以 Kd tree 的格式储存地图的节点，可以快速的找到地图上距离输入点最近的那个点。