CODEWITHSUNDEEP
c++qtsortingopenglglsl
schwenk
schwenk

Reputation: 360

What's that for a sorting algorithm (and how effective it runs on GPU)

I've Implemented a shader for sorting Pixels:

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;

}

Now I want to know how effective it is ?

My thought was that if in one Cycle every Pixel is computed the algorithm should have be O(n) in the worst case. Is this right. In case it's just a derivative of Bubble Sort.

Here's a Image of a sorting example:

EXAMPLE of "sieve-sort" algorithm

Upvotes: 2

Views: 245

Answers (1)

ratchet freak
ratchet freak

Reputation: 48216

You are implementing a sorting network and have used an odd-even sorting algorithm.

This needs O(n) iteration before the output is fully sorted.

However more efficient algorithms exist like the bitonic sort. This only need O(log² n) iterations. The shader will become more complicated as the other value will change depending on the iteration number.

You can simplify it by using another texture where the other index will be encoded and whether to take the minimum or the maximum.

Upvotes: 4

Related Questions