algorithm - 从球体(二十面体)上的网格捕捉矢量到一个点

Question

这是一个会让你的大脑彻底崩溃的问题，我已经尝试处理它很长一段时间了。

假设您有一个位于 3d 空间原点的球体。球体被分割成等距点的网格。形成网格的过程并不是那么重要，但对我来说似乎很简单的是使用常规的 3d 计算机图形球体生成过程(形成球体的算法如下图所示)

现在，在我有了这样的球体(即某种程度的二十面体)之后，我需要一个计算简单的过程，该过程能够将随机单位向量捕捉(角度)到它最近的二十面体边缘点。如果矢量将捕捉到矢量相交的三角形的中心点也是可以接受的。

我想强调的是，该过程在计算上应该是微不足道的，这一点很重要。这意味着实际上在内存中创建一个球体然后在球体中的每个三角形之间进行搜索的过程不是一个好主意，因为这样的搜索将需要访问全局堆和 ram，这很慢，因为我需要执行这个过程数百万次在低端移动硬件上。

该过程应该通过一组仅基于两个值的数学方程式得出结果，即向量和二十面体(即球体)的度数

有什么想法吗？提前致谢!

============

编辑

事后想到，在第 3 步下方的图表中(即将每个新顶点投影到单位球体)似乎根本不重要，因为在平分之后，每个顶点到球体的投影将保留我们试图对齐的对分形状的所有角度特征。因此，任务简化为识别被矢量穿透的二等分子三角形坐标。

Answer 1

制作一个包含 20 个顶级二十面体面坐标条目的表格 - 例如，从 wiki coordinate set 构建它们)

The vertices of an icosahedron centered at the origin with an edge-length of 2 and a circumscribed sphere radius of 2 sin (2π/5) are described by circular permutations of:

 V[] = (0, ±1, ±ϕ)
 where ϕ = (1 + √5)/2
 is the golden ratio (also written τ).

并计算相应的中心向量C[](每个面的顶点的三个向量之和)。

使用向量 P 和所有 C[] 的最大点积 (DP) 找到最近的中心向量。或许，可以减少对 P 分量的检查次数(例如，如果 P 和某些 V[i] 的点积为负，则将人脸视为 V[i] 的邻居是没有意义的)。不确定这种消除比直接将 DP 与中心进行全面比较花费的时间更少。

确定大三角面后，project P onto the plane该面的坐标并获得 P' 在 u-v 中的坐标(将 AP' 分解为 AB 和 AC，其中 A、B、C 是面顶点)。

将 u,v 乘以 2^N(分割程度)。

 u' = u * 2^N
 v' = v * 2^N
 iu = Floor(u')
 iv = Floor(v')
 fu = Frac(u')
 fv = Frac(v')

u'的整数部分是小三角形的“行”，v'的整数部分是“列”。小数部分是小三角面内的三线坐标，所以我们可以选择fu, fv, 1-fu-fv中的最小值来得到最近的顶点。计算这个最近的顶点并在需要时归一化向量。