Алгоритм пересечения двухмерных отрезков с использованием графического процессора - PullRequest
Новая
       23

Алгоритм пересечения двухмерных отрезков с использованием графического процессора

4 голосов
/ 21 июля 2011

Я ищу алгоритм, который проверяет, пересекаются ли 2 отрезка линии для графического процессора.Сегменты линии в 2D.Хотя в Интернете обсуждается множество алгоритмов для этого, все те, что я видел, используют множество инструкций ветвления.На процессоре это не такая проблема.Однако на графическом процессоре множество инструкций ветвления снижают производительность.

Кто-нибудь знает хороший алгоритм для этой среды?Любой пример псевдокода, кода 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));
}

1 Ответ

4 голосов
/ 22 июля 2011

Это выходит за рамки моей компетенции, но следующая тема на форумах NVIDIA CUDA обсуждала эту тему и содержит некоторый код, который может послужить полезной отправной точкой:

http://forums.nvidia.com/index.php?showtopic=180839

Обратите внимание, что код не обязательно должен быть полностью разветвленным, чтобы быть эффективным на графических процессорах NVIDIA. Архитектура поддерживает предикаты, а также инструкции типа «выбор» (сродни тернарному оператору в C / C ++), и компилятор довольно хорошо отображает локальные ветвления в этих конструкциях без ветвей. Я бы порекомендовал использовать cuobjdump для проверки сгенерированного машинного кода, чтобы вы точно знали, сколько веток фактически используется.

...