基于GPU的2D线段相交算法

Question

基于GPU的2D线段相交算法

algorithmcudaopenclcomputational-geometrygpgpu

5

我正在寻找一种算法，以GPU友好的方式测试2条线段是否相交。这些线段在2D空间中。虽然网络上讨论了很多完成此操作的算法，但我看到的所有算法都使用了大量的分支指令。在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));
}

- Jonathan DeCarlo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- njuffa · Accepted Answer

这超出了我的专业范围，但是NVIDIA CUDA论坛上的以下帖子讨论了这个话题，并包含一些代码，可能会提供一个有用的起点：

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

请注意，代码不必完全无分支才能在NVIDIA GPU上高效运行。该架构支持预测以及“select”类型指令（类似于C / C ++中的三元运算符），编译器很擅长将局部分支映射到这些无分支结构中。我建议使用cuobjdump检查生成的机器代码，这样您就会知道实际使用了多少分支。