高速SSEレイ - 4三角交差

Question

私は現在Path Tracerで作業しています。私は、光線 - 三角形の交差を最適化する方法を探しています。 （誰かが私に教えて、それを最適化する方法を参照した場合）

bool Ray::intersectTriangle(const Triangle tri, float& result) const 
{ 
    __m128 q = _mm_cross_ps(m_directionM128, tri.e2); 

    float a = _mm_dp_ps(tri.e1, q, dotProductMask).m128_f32[0]; 

    if (a > negativeEpsilon && a < positiveEpsilon) 
     return false; 

    float f = 1.0f/a; 

    __m128 s = _mm_sub_ps(m_originM128, tri.v0); 
    float u = f * _mm_dp_ps(s, q, dotProductMask).m128_f32[0]; 

    if (u < 0.0f) 
     return false; 

    __m128 r = _mm_cross_ps(s, tri.e1); 
    float v = f * _mm_dp_ps(m_directionM128, r, dotProductMask).m128_f32[0]; 

    if (v < 0.0f || (u + v > 1.0f)) 
     return false; 

    float t = f * _mm_dp_ps(tri.e2, r, dotProductMask).m128_f32[0]; 
    if (t < 0.0f || t > m_length) 
     return false; 

    result = t; 

    return true; 
} 

：私は現在、モラー・Trumboreアルゴリズムの次SSE4実装を使用します。 次に、SIMD命令を使用して4つの三角形に対して同時に交差テストを実行できることを読んだことがあります。しかし、それを行う方法？私はそれが私の逐次的な方法よりも効率的な方法でそれを実現することができる方法を見ていない。

Here私のレンダラーに関係する小さなコード。

Answer 1

AVX512では最大16個、AVX2では8個、SSEでは最大4個の三角形を使用できます。しかし、トリックは、データがSOA形式であることを確認することです。もう1つのトリックは、いずれのポイントでも「偽り」ないことです（結果を最後にフィルタリングするだけです）。だから三角形入力は、次のようになります。

struct Tri { 
    __m256 e1[3]; 
    __m256 e2[3]; 
    __m256 v0[3]; 
    }; 

そして、あなたの線は、次のようになります。注意してください（_mm_dp_psをはるかに見やすくするために開始し、その後数学コードを

struct Ray { 
    __m256 dir[3]; 
    __m256 pos[3]; 
    }; 

史上最速の関数ではありません__m128/__m256/__ m512タイプの内部実装へのアクセスは移植性がないことに注意してください）。

#define or8f _mm256_or_ps 
    #define mul _mm256_mul_ps 
    #define fmsub _mm256_fmsub_ps 
    #define fmadd _mm256_fmadd_ps 

    void cross(__m256 result[3], const __m256 a[3], const __m256 b[3]) 
    { 
    result[0] = fmsub(a[1], b[2], mul(b[1], a[2])); 
    result[1] = fmsub(a[2], b[0], mul(b[2], a[0])); 
    result[2] = fmsub(a[0], b[1], mul(b[0], a[1])); 
    } 
    __m256 dot(const __m256 a[3], const __m256 b[3]) 
    { 
    return fmadd(a[2], b[2], fmadd(a[1], b[1], mul(a[0], b[0]))); 
    } 

あなたは基本的にこの方法では4つの条件があります。これらの条件のいずれかに該当する場合には、何の交差点がない

if (a > negativeEpsilon && a < positiveEpsilon) 

if (u < 0.0f) 

if (v < 0.0f || (u + v > 1.0f)) 

if (t < 0.0f || t > m_length) 

を。それは基本的に少しのリファクタリング（擬似コードで）を必要とします。最終的に交差が発生した場合、結果はtになります。交差点がが発生しなかった場合、我々は最終的なコードなくなり何か間違ったこと（負の数は、この場合には、おそらく良い選択です！）

// if(failed) return -1; 
// else return t; 
return _mm256_blendv_ps(t, _mm256_set1_ps(-1.0f), failed); 

に結果を設定する必要があり、少し厄介に見えるかもしれあなたのアプローチよりも大幅に速くなります。

このアプローチの大きな問題の1つは、1つの線を8つの三角形に対してテストするか、8つの線を1つの三角形に対してテストするかの選択肢があることです。主にレイの場合、これは大きな問題ではないでしょう。異なる方向に散乱する習慣を有する二次光線については、物事は少し迷惑になることがあります。テストパターン - >並べ替え - >バッチ - >テスト - >並べ替え - >バッチのようなレイトレースコードのほとんどが終了する可能性があります。

このパターンに従わないと、ベクトルユニットを最大限に活用することはほとんどありません。 （ありがたいことに、AVX512の圧縮/伸長の手順はこれをかなり助けます！）

Answer 2

私は

struct PackedTriangles 
{ 
    __m256 e1[3]; 
    __m256 e2[3]; 
    __m256 v0[3]; 
    __m256 inactiveMask; // Required. We cant always have 8 triangles per packet. 
}; 

struct PackedIntersectionResult 
{ 
    float t = Math::infinity<float>(); 
    int idx; 
}; 

struct PackedRay 
{ 
    __m256 m_origin[3]; 
    __m256 m_direction[3]; 
    __m256 m_length; 

    bool intersect(const PackedTriangles& packedTris, PackedIntersectionResult& result) const; 
}; 

#define or8f _mm256_or_ps 
#define mul _mm256_mul_ps 
#define fmsub _mm256_fmsub_ps 
#define fmadd _mm256_fmadd_ps 
#define cmp _mm256_cmp_ps 
#define div _mm256_div_ps 

void avx_multi_cross(__m256 result[3], const __m256 a[3], const __m256 b[3]) 
{ 
    result[0] = fmsub(a[1], b[2], mul(b[1], a[2])); 
    result[1] = fmsub(a[2], b[0], mul(b[2], a[0])); 
    result[2] = fmsub(a[0], b[1], mul(b[0], a[1])); 
} 

__m256 avx_multi_dot(const __m256 a[3], const __m256 b[3]) 
{ 
    return fmadd(a[2], b[2], fmadd(a[1], b[1], mul(a[0], b[0]))); 
} 

void avx_multi_sub(__m256 result[3], const __m256 a[3], const __m256 b[3]) 
{ 
    result[0] = _mm256_sub_ps(a[0], b[0]); 
    result[1] = _mm256_sub_ps(a[1], b[1]); 
    result[2] = _mm256_sub_ps(a[2], b[2]); 
} 

const __m256 oneM256 = _mm256_set1_ps(1.0f); 
const __m256 minusOneM256 = _mm256_set1_ps(-1.0f); 
const __m256 positiveEpsilonM256 = _mm256_set1_ps(1e-6f); 
const __m256 negativeEpsilonM256 = _mm256_set1_ps(-1e-6f); 
const __m256 zeroM256 = _mm256_set1_ps(0.0f); 

bool PackedRay::intersect(const PackedTriangles& packedTris, PackedIntersectionResult& result) const 
{ 
    __m256 q[3]; 
    avx_multi_cross(q, m_direction, packedTris.e2); 

    __m256 a = avx_multi_dot(packedTris.e1, q); 

    __m256 f = div(oneM256, a); 

    __m256 s[3]; 
    avx_multi_sub(s, m_origin, packedTris.v0); 

    __m256 u = mul(f, avx_multi_dot(s, q)); 

    __m256 r[3]; 
    avx_multi_cross(r, s, packedTris.e1); 

    __m256 v = mul(f, avx_multi_dot(m_direction, r)); 

    __m256 t = mul(f, avx_multi_dot(packedTris.e2, r)); 

    // Failure conditions 
    __m256 failed = _mm256_and_ps(
     cmp(a, negativeEpsilonM256, _CMP_GT_OQ), 
     cmp(a, positiveEpsilonM256, _CMP_LT_OQ) 
    ); 

    failed = or8f(failed, cmp(u, zeroM256, _CMP_LT_OQ)); 
    failed = or8f(failed, cmp(v, zeroM256, _CMP_LT_OQ)); 
    failed = or8f(failed, cmp(_mm256_add_ps(u, v), oneM256, _CMP_GT_OQ)); 
    failed = or8f(failed, cmp(t, zeroM256, _CMP_LT_OQ)); 
    failed = or8f(failed, cmp(t, m_length, _CMP_GT_OQ)); 
    failed = or8f(failed, packedTris.inactiveMask); 

    __m256 tResults = _mm256_blendv_ps(t, minusOneM256, failed); 

    int mask = _mm256_movemask_ps(tResults); 
    if (mask != 0xFF) 
    { 
     // There is at least one intersection 
     result.idx = -1; 

     float* ptr = (float*)&tResults; 
     for (int i = 0; i < 8; ++i) 
     { 
      if (ptr[i] >= 0.0f && ptr[i] < result.t) 
      { 
       result.t = ptr[i]; 
       result.idx = i; 
      } 
     } 

     return result.idx != -1; 
    } 

    return false; 
} 

結果

結果は素晴らしいです、次の作業のコードで終了しました。 100kトライアングルシーンの場合、私は84％のスピードアップ !!を持っています！非常に小さいシーン（20の三角形）の場合、パフォーマンスの損失は13％です。しかし、これは普通ではないので大丈夫です。