在并行计算中查找多个最近的光线-线段交点

Question

我知道如何找到以感兴趣的2D点（POI）为根的射线是否与给定的2D线段相交，以及如何针对给定的射线有效地找到与多个线段相交的最接近POI的点。

然而，我有几条（不太多）射线，每个射线都以许多（我是指非常多）POI为根，并且有许多（我再次强调非常多）线段，我需要找到与每个射线对应的POI最接近的线段相交点。

对于此问题，我的想法是将射线视为以相应POI为一侧、另一侧朝非常远的右方的线段，然后运行sweep line algorithm以查找所有交点，然后对于每条射线输出最接近POI的交点。这应该可以在O(N log N)时间内运行，因此足够好了。

然而，这部分恰好成为整个系统的瓶颈，我希望做得比“勉强够用”更好。特别是因为确实有很多对象需要排序，我想使这个算法并行化。不幸的是，扫描线算法似乎本质上是顺序的，如果接受这一点，将会影响我的整体性能，否则我的系统就会相当并行。

因此问题是：您对上述问题的有效并行化有何建议？

此外，是否有任何已知的高度并行的交点检测算法可以利用CUDA级别的并行性？

- Michael

---

到目前为止，我看到的唯一相关的并行扫描是Goodrich、Ghouse和Bright的这篇论文。我想找到一些高度并行化的东西，适用于CUDA多线程。 - Michael

我想将这个算法改为多线程。但是，多线程可能不是最适合你的选择。请问你的系统是否能够进行并行处理？ - ryyker

你是否查看了你提供的链接中的这份***手册***？它似乎阐述了如何将计算段轻松地分割成在不同核心或处理器上运行的离散进程。 - ryyker

@ryyker：根据您的建议，刚刚仔细研究了扫描线算法，但我并没有看到明显的方法可以将其并行化超过2核。在任何给定的垂直线上，平衡树状态都依赖于先前垂直线的状态。对于两个核心，可以从左到右同时进行扫描，并从右到左输出大约一半的交点。但是，如何将它并行化到1024个核心，这是CUDA上典型的并行化级别呢？ - Michael

本文介绍了2009年的技术现状：https://mediatech.aalto.fi/~samuli/publications/aila2009hpg_paper.pdf。所描述的方法解决了射线与三角形相交的三维情况，但所有的概念都适用于二维和线段。 - Jared Hoberock

Answer 1

你可以尝试基于四叉树或其他空间索引的2D数据结构来实现算法。

具体思路如下：

在四叉树的每个叶子节点中，存储与该正方形相交的任何线段的引用。初始状态下，分辨率为零，即所有线段都在未划分的边界框节点中。

对于每条射线，查看射线的起点并细分包含它的节点，直到节点仅与一个线段相交。如果细分后该节点不与任何线段相交，则通过沿着射线移动到下一个节点来继续搜索。如果节点内部相交了一条线段，则已经找到了第一个相交点，可以停止沿该射线的搜索。如果射线没有与节点内的线段相交，则可以从搜索中剪枝该线段，并移动到射线相交的下一个节点。

显然，这个算法可以并行运行，通过同时沿着每条射线进行搜索。虽然四叉树是共享的，但随着它的细分，线程很快就不会竞争访问。 运行时间： 运行时间有点难分析，因为它取决于线段和射线的二维结构。也许有人可以帮助更好地分析运行时间，但这是我最好的尝试：

如果存在一个小距离d，它比最接近的非相交线段的任何射线的距离小，并且比同一射线上任意两个交点之间的距离小，则我们可以得到一个上限。然后我们可以称r=D/d为问题的“分辨率”，其中D是包围框的维数。

运行时间将受到 N * r 的限制，但这是一个极其粗略的界限，因为它基本上假设每条射线必须在其整个长度上以分辨率d进行解决。

让我们试着改进这个界限。

对于任何一条射线，考虑它的起点和第一个交点之间的部分。对于该部分上的任何点，我们可以询问哪个非相交线段最接近该点。然后我们可以询问有多少个不同的非相交线段最接近这条射线部分上的某个点。换句话说，如果我们制作了非相交线段的 Voronoi 图，我们正在询问这条射线部分将与多少个单元相交。如果我们让p成为任何射线的此问题的最大答案，则我们可以得到更好的上限。

 N*p*log(r)

在沿着射线搜索时考虑最大所需分辨率。

因此，如果p和r是常数，我们有一个线性时间算法！

不幸的是，我非常确定p、N和r之间存在某种关系，阻止了p和r保持大致恒定。粗略猜测，我会说r ~ sqrt(N)，这意味着回到了N log N的运行时间。

并行化很有趣。如果我们假设有C个核心，那么搜索运行时间为N/C*p*log(r)，但仍然存在划分子树的瓶颈问题。有log(r)级别，每个段必须在至多N个位置上划分到这个级别，所以需要N/C*log(r)的时间，这意味着总运行时间将是

(N/C)*p*log(r)

这基本意味着假设 C < N，它是完全可并行化的。

结论 在单核算法方面，这可能不太好，但对于具有特殊结构和/或可并行化的问题，它可能效果很好。我不建议尝试实现此算法，除非您已经仔细考虑过，并且确定可以平滑处理粗糙的边缘，并且我在分析中没有犯错误。我还建议搜索基于类似概念的已发布算法。

- Jeremy Salwen

Answer 2

如果不需要进行数学精确计算，您可以基于近似射线的算法，这些射线具有相同的起点，但斜率已被捕捉到集合中最接近的离散值。

例如，考虑将射线的角度四舍五入到最接近的度数。 角度将有360个可能的值。 如果我们考虑180条不同的线，每条线旋转一度，则每个射线都将与至少一条线平行。 如果我们让我们的线集大小为l，则在近似射线角度方面，我们将具有分辨率pi /（2l）弧度。

我们注意到，如果射线轴对齐，则很容易找到射线的第一个交点。 因此，我们在l个不同的基础上执行计算。 每个射线将在其中一个基础上轴对齐，因此我们只需要找出找到一组x轴对齐射线的第一个交点的算法。

为此，我们为y轴构建一个线段树，然后在线段树中查找与x轴对齐的射线相交的线段集。但是，由于我们不关心整个相交线段集，而只关心沿着射线的第一个交点，因此我们在遍历树时不需要跟踪整个交点集，而只需跟踪到目前为止找到的最佳交点即可。这将运行时间降至log(n)+k，其中k是交点数。但是，k的因素可以并行化到log(n)。

因此，每个基础都需要进行线段树构造n*log(n)，每个射线都需要在线段树中查找(log(n)+k)。

因此，总运行时间为：

l*n*log(n)+n*(log(n)+k)

but it is all extremely parallelizable for c

(n/c)*(l*log(n)+k)

Which is pretty good, but k could potentially scale with n, meaning we still have linear running time even with ~n cores (and down to log(n) with more than n cores, because the factor of k is further parallelizable). Linear running time is better than line-sweep, but I still feel like we could do better, and I can't figure out how. Interestingly, our algorithm can find the set of segments that intersect with the line extending from the ray in (n*l/c)*(log(n)) time, but the part that is slow is to go through every intersecting segment and check whether it is on the right side of the origin point, and check whether it's the first. It seems like you couldn't get rid of this term even in a parallel version of the line sweep algorithm.

- Jeremy Salwen

Answer 3

你可以尝试使用并行版本的线性扫描算法，只需将空间分割并在每个部分上并行执行几次线性扫描即可。

如果将空间分成s个部分，并在每个部分上进行线性扫描，则可以获得一些加速。但是，它不是尴尬地并行，因为您需要为每个中间起始点多次执行初始化。

每个初始化都需要对每个跨越该线位置的段进行n*log(n)排序和n*log(n)事件队列的构建。 但是，两者都可以尴尬地并行处理n个核心。 然后，扫描提供了高达s的尴尬并行加速。

因此，使用c个核心查找交点的运行时间将为

(s*n/c)*log(n) +((n+k)/s)*log(n)

其中k是交叉点的总数。如果我们选择s=sqrt(c)，那么我们就得到了：

((n+k)/sqrt(c))*log(n)

换句话说，我们获得的加速比与核心数的平方根成比例。

但由于k是交点的总数，它可能会像n^2一样扩展，这将使事情变得糟糕。即使c=n，我们也可能有最坏情况下的运行时间。

n^1.5 * log(n)

此外，还有最优O(nlogn+k)算法可用于查找交点（其中k是交点的总数），它比扫描线算法更快，但更为复杂，因此我不知道它的工作原理或是否可以并行化。

- Jeremy Salwen