GPU 友好的 2D 线段相交算法

Question

我正在寻找一种算法来测试 2 条线段是否以 GPU 友好的方式相交。线段是二维的。虽然网络上讨论了许多用于执行此操作的算法，但我所见过的所有算法都使用了大量分支指令。在 CPU 上，这不是一个问题。但是，在 GPU 上，大量分支指令会降低性能。

有谁知道适合这种环境的好算法？任何示例伪代码、CUDA 代码、OpenCL 代码或 DirectCompute 计算将不胜感激。

---

跟进

如果有人感兴趣，这（基本上）就是我最终得到的。我把它删减了，所以它更像是伪代码而不是 OpenCL C，但希望它能理解要点。

__kernel void findCrossingLines(__global float2 p1, __global float2 p2, 
                                __global float2 p3, __global float2 p4, 
                                __global bool* output)
{
    int result = 0;
    float2 A = p2;
    float2 a = p2 - p1;
    float2 B = p4;
    float2 b = p4 - p3;
    float2 c = B - A;
    float2 b_perp = (float2)(-b.y, b.x);

    float numerator = dot(b_perp, c);
    float denominator = dot(b_perp, a);
    bool isParallel = (denominator == 0.0f);

    float quotient = numerator / denominator;
    float2 intersectionPoint = (float2)(quotient * a.x + A.x, quotient * a.y + A.y);

    *output = (!isParallel && 
                  intersectionPoint.x >= min(p1.x, p2.x) && 
                  intersectionPoint.x >= min(p3.x, p4.x) &&
                  intersectionPoint.x <= max(p1.x, p2.x) && 
                  intersectionPoint.x <= max(p3.x, p4.x) &&
                  intersectionPoint.y >= min(p1.y, p2.y) && 
                  intersectionPoint.y >= min(p3.y, p4.y) &&
                  intersectionPoint.y <= max(p1.y, p2.y) && 
                  intersectionPoint.y <= max(p3.y, p4.y));
}

Answer 1

这超出了我的专业领域，但 NVIDIA CUDA 论坛上的以下主题讨论了该主题，并包含一些可能提供有用起点的代码：

https://forums.developer.nvidia.com/t/intersecting-line-segments-on-gpu/18832

请注意，代码不必完全无分支才能在 NVIDIA GPU 上高效运行。该体系结构支持谓词以及“选择”类型指令（类似于 C/C++ 中的三元运算符），并且编译器非常擅长将本地分支映射到那些无分支结构。我建议使用 cuobjdump 检查生成的机器代码，这样您就可以准确地知道实际使用了多少个分支。