Как быстро определить, перекрываются ли квадраты треугольника и круга

Question

Здесь я хочу определить, какой из треугольников в наборе двумерных треугольников перекрывается с прямоугольником круга.Треугольник, который не перекрывается, будет присвоен -1, в противном случае - его собственному индексу.

Вершины треугольников хранятся в thrust :: device_vector.d_pTriXys - это необработанный указатель на вектор.3 индекса каждого треугольника, указывающие на индекс массива вершин, хранятся в другом векторе устройства.d_pTriIndices - это необработанный указатель на этот вектор.triNum - это счетчик треугольника.

Код выполнен в Visual Studio C ++ и работает.Но производительность кажется проблемой.Для случая, когда проверяется 2225 кругов с 5,5 миллионами треугольников, 2,8 млн вершин, требуется около 3,5 секунд.Это не так быстро, как я хотел.У кого-нибудь есть идеи по улучшению алгоритма для повышения производительности?

Я пытался изменить счетчик регистров threadsPerBlock.сейчас настройки кажутся лучшими.

  // RangeAlgo.h

  struct tagXy_f
  {
     float x;
     float y;
  };


  CUDA_HOST_DEV __forceinline bool IsCircleAndTriangleBoxesSeparated(
     const tagXy_f triVertices[3], const tagXy_f &circleCen, float circleRad)
  {

     float t = min(triVertices[0].x, min(triVertices[1].x, triVertices[2].x));
     if (circleCen.x <= t - circleRad)
        return true;

     t = max(triVertices[0].x, max(triVertices[1].x, triVertices[2].x));
     if (circleCen.x >= t + circleRad)
        return true;

     t = min(triVertices[0].y, min(triVertices[1].y, triVertices[2].y));
     if (circleCen.y <= t - circleRad)
        return true;

     t = max(triVertices[0].y, max(triVertices[1].y, triVertices[2].y));
     return (circleCen.y >= t + circleRad);
  }


  // Main.cpp

  __global__ void MarkOutTrianglesKernel(const uint3 *d_pTriIndices, unsigned triNum,
     const float2 *d_pTriXys, const tagXy_f &d_circleCen, float circleRad,
     int *d_pValidTriIndices)
  {
     unsigned tid = blockIdx.x * blockDim.x + threadIdx.x;

     if (tid < triNum)
     {
        const uint3 &triInds = d_pTriIndices[tid];
        // to local variable/registers, make it faster
        const float2 triVertices[3] = { d_pTriXys[triInds.x],
        d_pTriXys[triInds.y], d_pTriXys[triInds.z] };

        bool b = IsCircleAndTriangleBoxesSeparated(reinterpret_cast<const tagXy_f *>(triVertices),
               d_circleCen, circleRad);

        d_pValidTriIndices[tid] = b ? -1 : (int)tid;
     }
  }


  void main()
  {
     // here is the sample code to check one circle with all triangles
     uint3 *d_pTriIndices;      // indices of all triangles
     unsigned triNum;           // count of triangles
     const float2 *d_pTriXys;   // all vertices of triangles
     tagXy_f d_circleCen;
     float circleRad;
     int *d_pValidTriIndices;

     ...

     int threadsPerBlock = 256;
     int blocksPerGrid = (int)((triNum + threadsPerBlock - 1) / threadsPerBlock);

     MarkOutTrianglesKernel<<<blocksPerGrid, threadsPerBlock>>>(d_pTriIndices, triNum,
        d_pTriXys, d_circleCen, circleRad, d_pValidTriIndices);

     ...
  }