algorithm - 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 来检查生成的机器代码，这样您就可以准确地知道实际使用了多少分支。