我在高性能计算集群上从事理论化学研究，通常涉及分子动力学模拟。我的研究之一涉及到一个N维（通常N = 2-5）超球的静态场，测试粒子可能会与其碰撞。我希望优化（即彻底改进）用于表示球场的数据结构，以便进行快速的碰撞检测。目前，我使用一个简单的指向N成员结构体的指针数组（每个坐标的中心都是双精度），以及一个最近邻列表。我听说过八叉树和四叉树，但没有找到清晰的解释它们的工作原理、如何高效地实现它们以及如何使用它们进行快速的碰撞检测。考虑到我的模拟规模，内存几乎不是问题，但运算速度是关键。
5个回答
4
对于您的问题，如何最好地解决取决于您没有描述的几个因素：
- 是否将使用相同的超球排列进行多粒子碰撞计算？
- 超球是否具有统一的大小？
- 粒子的运动方式是什么（例如直线/曲线），并且这种运动是否受到球体的影响？
- 您是否认为粒子体积为零？
我假设粒子的运动不是简单的直线运动，因为这将是相对较快的计算，即查找线和点之间最近点的计算，这可能与查找线与哪些盒子相交（以确定在n-tree中要检查的位置）的速度大致相同。
如果您的超球位置对于许多粒子碰撞是固定的，则计算 Voronoi 分解/Dirichlet tessellation 将为您提供一种快速的方法，以便稍后在空间的任何给定点上找到最接近您的粒子的确切超球。
然而，回答你关于八叉树/四叉树/2^n树的原始问题，在n维空间中，你从一个包含你感兴趣的空间区域的（超）立方体开始。如果你认为内容过于复杂，它将被划分为2^n个超立方体。这种递归持续进行，直到只有简单元素（例如一个超球心）在叶节点中。 现在，构建好n树后，你可以通过将粒子路径与外部超立方体相交来使用它进行碰撞检测。交点位置将告诉你下一级树中要访问的哪个超立方体，并且你需要确定所有该级别的2^n个超立方体的交点位置，向下追踪直到达到叶节点。一旦到达叶节点，你就可以检查粒子路径和存储在该叶子上的超球之间的相互作用。如果发生碰撞，则已完成，否则你必须找到粒子路径从当前超立方体叶子退出的位置，并确定它移动到哪个超立方体。继续寻找碰撞或完全离开整个边界超立方体，直到结束。
高效地在退出一个超立方体时找到相邻的超立方体是这种方法中最具挑战性的部分之一。对于2^n树，可以采用Samet的方法{1,2}进行适应。对于kd-树（二叉树），建议在{3}第4.3.3节中提出一种方法。
高效的实现可以简单地存储每个超立方体到其子超立方体的8个指针列表，并以特殊方式标记超立方体如果它是叶子（例如，使所有指针为空）。
在Klinger和Dyer {4}中可以找到创建四叉树（您可以将其推广到n-tree）的空间划分描述。
正如其他人所提到的，与2^n-trees相比，kd-trees可能更适合作为任意维度扩展更直接，但它们会导致更深的树。使用kd-tree更容易使分割位置与您的超球几何匹配。上面关于2^n树的碰撞检测的描述同样适用于kd-树。
我假设粒子的运动不是简单的直线运动，因为这将是相对较快的计算，即查找线和点之间最近点的计算，这可能与查找线与哪些盒子相交（以确定在n-tree中要检查的位置）的速度大致相同。
如果您的超球位置对于许多粒子碰撞是固定的，则计算 Voronoi 分解/Dirichlet tessellation 将为您提供一种快速的方法，以便稍后在空间的任何给定点上找到最接近您的粒子的确切超球。
然而，回答你关于八叉树/四叉树/2^n树的原始问题，在n维空间中，你从一个包含你感兴趣的空间区域的（超）立方体开始。如果你认为内容过于复杂，它将被划分为2^n个超立方体。这种递归持续进行，直到只有简单元素（例如一个超球心）在叶节点中。 现在，构建好n树后，你可以通过将粒子路径与外部超立方体相交来使用它进行碰撞检测。交点位置将告诉你下一级树中要访问的哪个超立方体，并且你需要确定所有该级别的2^n个超立方体的交点位置，向下追踪直到达到叶节点。一旦到达叶节点，你就可以检查粒子路径和存储在该叶子上的超球之间的相互作用。如果发生碰撞，则已完成，否则你必须找到粒子路径从当前超立方体叶子退出的位置，并确定它移动到哪个超立方体。继续寻找碰撞或完全离开整个边界超立方体，直到结束。
高效地在退出一个超立方体时找到相邻的超立方体是这种方法中最具挑战性的部分之一。对于2^n树，可以采用Samet的方法{1,2}进行适应。对于kd-树（二叉树），建议在{3}第4.3.3节中提出一种方法。
高效的实现可以简单地存储每个超立方体到其子超立方体的8个指针列表，并以特殊方式标记超立方体如果它是叶子（例如，使所有指针为空）。
在Klinger和Dyer {4}中可以找到创建四叉树（您可以将其推广到n-tree）的空间划分描述。
正如其他人所提到的，与2^n-trees相比，kd-trees可能更适合作为任意维度扩展更直接，但它们会导致更深的树。使用kd-tree更容易使分割位置与您的超球几何匹配。上面关于2^n树的碰撞检测的描述同样适用于kd-树。
{1} 连通分量标记，Hanan Samet，使用四叉树，ACM期刊第28卷，第3期（1981年7月）
{2} 在八叉树表示的图像中查找邻居，Hanan Samet，计算机视觉、图形和图像处理，第46卷，第3期（1989年6月）
{3} 凸包生成、连通分量标记和集合定义模型的最小距离计算，Dan Pidcock，2000
{4} 在图片表示中使用常规分解的实验，Klinger，A.和Dyer，C.R.E，计算机图形学和图像处理5（1976），68-105。
- danio
1
因为你的领域是静态的（我假设你的意思是超球体不会移动），所以我知道最快的解决方案是使用Kdtree。
你可以自己制作，也可以使用其他人的，比如这个：
http://libkdtree.alioth.debian.org/
- user14273
0
一个八叉树可以工作，只要你能通过它们的中心指定球体 - 它将点分层地放入具有八个子节点的立方体区域中。在八叉树数据结构中找到邻居需要进行球与立方体的相交计算（在某种程度上比看起来容易），以确定八叉树中哪些立方体区域在球内。
查找最近邻居意味着向上遍历树，直到获得具有多个填充子节点和所有周围节点的节点（这确保查询获取所有侧面）。
从记忆中，这是球体-立方体相交的（有些天真）基本算法：
i. 中心是否在立方体内（这得到了同名情况）
ii. 立方体的任何角是否在距离中心为r的范围内（球内的角）
iii. 对于立方体的每个表面（您可以通过计算中心位于表面哪一侧来消除其中一些表面），计算（这都是第一年的向量算术）：
a. 表面的法线，指向球的中心
b. 从球的中心到法线与表面平面相交处的距离（弦与立方体表面平面相交）
查找最近邻居意味着向上遍历树，直到获得具有多个填充子节点和所有周围节点的节点（这确保查询获取所有侧面）。
从记忆中，这是球体-立方体相交的（有些天真）基本算法：
i. 中心是否在立方体内（这得到了同名情况）
ii. 立方体的任何角是否在距离中心为r的范围内（球内的角）
iii. 对于立方体的每个表面（您可以通过计算中心位于表面哪一侧来消除其中一些表面），计算（这都是第一年的向量算术）：
a. 表面的法线，指向球的中心
b. 从球的中心到法线与表面平面相交处的距离（弦与立方体表面平面相交）
c. 平面与立方体的边相交（弦与立方体相交的一个条件）
iv. 计算弦的大小（正常长度与球半径比值的余弦^-1的正弦）
v. 如果线上最近的点小于弦的距离，并且该点位于线的两端之间，则弦与立方体的一条边相交（弦在立方体表面沿着其中一条边相交）。
我有点模糊地记得这是我在使用八叉树数据结构处理球形区域的情况下做的事情（很多年前）。您可能还希望查看KD树，因为其他一些帖子建议的内容听起来与您最初的问题非常相似。
- Nigel Campbell
0
四叉树是一种二维树结构，每个节点都有四个子节点，并且每个子节点覆盖父节点的1/4面积。
八叉树是一种三维树结构，每个节点都有八个子节点，并且每个子节点包含父节点体积的1/8。这里有一张图片帮助你更好地理解：http://en.wikipedia.org/wiki/Octree
如果你正在进行N维交叉测试，可以将其推广为N叉树。
交叉算法通过从树的顶部开始递归遍历任何与被测试对象相交的子节点，最终到达包含实际对象的叶节点来处理交集。
- Don Neufeld
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接