那是什麼的排序算法（它運行在GPU如何有效）

我已經實現了一個着色器進行排序像素：那是什麼的排序算法（它運行在GPU如何有效）

void main() 
{ 
    vec4 renderedImagePixel = texture2D(CalculatedImage,v_texcoord); 

    if(int(numRenderPass) == int(v_texcoord.y*float(height)) && fbo){ 

     vec2 coordTHIS = vec2(v_texcoord.x,v_texcoord.y-1.0/float(height)); 
     float THIS = unpack(texture2D(CalculatedImage,coordTHIS)); 
     renderedImagePixel = texture2D(CalculatedImage,coordTHIS); 

     if(sieveCycle == true){ //even Cycle 

      //Even cell 
      if(mod(int(v_texcoord.x*float(width)),2) == 1){ 
       //CHANGES IN CODE HERE 
       vec2 coordTHAT = vec2(v_texcoord.x+1.0/float(width),v_texcoord.y-1.0/float(height)); 
       float THAT = unpack(texture2D(CalculatedImage,coordTHAT)); 

       //CHANGES IN CODE HERE 
       if(THIS > THAT){ 
        renderedImagePixel = texture2D(CalculatedImage,coordTHAT); 
       } 
      }else{ 
      //Odd cell 
       //CHANGES IN CODE HERE 
       vec2 coordTHAT = vec2(v_texcoord.x-1.0/float(width),v_texcoord.y-1.0/float(height)); 
       float THAT = unpack(texture2D(CalculatedImage,coordTHAT)); 

       //CHANGES IN CODE HERE 
       if(THAT > THIS){ 
        renderedImagePixel = texture2D(CalculatedImage,coordTHAT); 
       } 
      } 

     }else{ //odd cycle 

      //Even cell 
      if(mod(int(v_texcoord.x*float(width)),2) == 0){ 
       //CHANGES IN CODE HERE 
       vec2 coordTHAT = vec2(v_texcoord.x+1.0/float(width),v_texcoord.y-1.0/float(height)); 
       float THAT = unpack(texture2D(CalculatedImage,coordTHAT)); 

       //CHANGES IN CODE HERE 
       if(THIS > THAT){ 
        renderedImagePixel = texture2D(CalculatedImage,coordTHAT); 
       } 
      }else{ 
      //Odd cell 
       //CHANGES IN CODE HERE 
       vec2 coordTHAT = vec2(v_texcoord.x-1.0/float(width),v_texcoord.y-1.0/float(height)); 
       float THAT = unpack(texture2D(CalculatedImage,coordTHAT)); 

       //CHANGES IN CODE HERE 
       if(THAT > THIS){ 
        renderedImagePixel = texture2D(CalculatedImage,coordTHAT); 
       } 
      } 

     } 
    } 

    gl_FragColor = renderedImagePixel; 

}

現在我想知道它是多麼有效？

我的想法是，如果在一個循環中計算每個像素，算法在最壞的情況下應該是O（n）。這是正確的嗎。如果它只是Bubble Sort的衍生產品。

這裏有一個排序示例的圖片：

EXAMPLE of "sieve-sort" algorithm

來源

2015-01-05 schwenk

你可能希望看看排序網絡，這是有點你試圖實現https://en.wikipedia.org/wiki/Sorting_network –

老兄，它很漂亮。 –

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html – Luca

要實現一個sorting network並使用奇偶排序算法。

這需要在輸出完全排序之前進行O（n）迭代。

但是更高效的算法存在，如bitonic sort。這隻需要O(log² n)迭代。着色器將變得更加複雜，因爲other值將根據迭代次數而變化。

您可以通過使用其他索引將被編碼以及是否取最小值或最大值的另一個紋理來簡化它。

來源

2015-01-05 13:29:10

我在哪裏可以找到用於生成相對索引掩碼的實現？ – schwenk

那是什麼的排序算法（它運行在GPU如何有效）

回答

相關問題