What is the most efficient line algorithm using a shader program

Question

I'm new to shaders and I have been experimenting with them in shadertoy. I'm trying to get a deeper understanding of the graphics pipeline and I want to implement some features using shaders. I want to start off simple and draw a line on the screen using shaders. I wrote two-line algorithms from scratch

struct Vertex {
    vec2 p;
    vec4 c;
};

vec4 overlay(vec4 c1, vec4 c2) {
    return vec4((1.0 - c2.w) * c1.xyz + c2.w * c2.xyz, 1.0);
}

vec4 drawLineA(Vertex v1, Vertex v2, vec2 pos) {
    vec2 a = v1.p;
    vec2 b = v2.p;
    vec2 r = floor(pos);
    
    vec2 diff = b - a;
    
    
    if (abs(diff.y) < abs(diff.x)) {
        if (diff.x < 0.0) {
            Vertex temp1 = v1;
            Vertex temp2 = v2;
            
            v1 = temp2;
            v2 = temp1;
            
            a = v1.p;
            b = v2.p;
            diff = b - a;
        
        }
        
        float m = diff.y / diff.x;
        float q = r.x - a.x;
        
        if (floor(m * q + a.y) == r.y && a.x <= r.x && r.x <= b.x) {
            float h = q / diff.x;
            return vec4((1.0 - h) * v1.c + h * v2.c);
        }
        
        
    } else {
        if (diff.y < 0.0) {
            Vertex temp1 = v1;
            Vertex temp2 = v2;
            
            v1 = temp2;
            v2 = temp1;
            
            a = v1.p;
            b = v2.p;
            diff = b - a;
        
        }
    
        float m =  diff.x / diff.y;
        float q = r.y - a.y;
        
        if (floor(m * q + a.x) == r.x && a.y <= r.y && r.y <= b.y) {
            float h = q / diff.y;
            return vec4((1.0 - h) * v1.c + h * v2.c);
        }
    
    }
    
    return vec4(0,0,0,0);
}

vec4 drawLineB(Vertex v1, Vertex v2, vec2 pos) {
    vec2 a = v1.p;
    vec2 b = v2.p;
    
    vec2 l = b - a;
    vec2 r = pos - a;
    float h = dot(l,r) / dot (l,l);
    
    vec2 eC = a + h * l;
    
    if (floor(pos) == floor(eC) && 0.0 <= h && h <= 1.0 ) {
       return vec4((1.0 - h) * v1.c + h * v2.c); 
    }
    
    return vec4(0,0,0,0);
}



void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
    float t = iTime;
    float r = 300.0;
    Vertex v1 = Vertex(vec2(400,225), vec4(1,0,0,1));
    Vertex v2 = Vertex(vec2(400.0 + r*cos(t) ,225.0 + r*sin(t)), vec4(0,1,0,1));
    
    vec4 col = vec4(0,0,0,1);
    col = overlay(col,drawLineA(v1, v2, fragCoord));
    col = overlay(col,drawLineB(v1, v2, fragCoord));
    // Output to screen
    fragColor = col;
}

However, they are both quite slow, is there a more efficient line algorithm that I can use that outputs a color based on whether the pixel is in the line or not. I've heard that Bresenham's line algorithm is the fastest however I don't know how to use shaders to speed up the algorithm because it needs the previous y value to compute the next. Can line algorithms be sped up by shaders or is it already the fastest it can be on the CPU. If there is a optimised line drawing algorithm using the GPU (where the GPU would out-perform the cpu) how can I implement it into my code?

Thanks

Answer 1

Here is a (mostly) minimal version of an SDF for a line segment using a signed distance field as suggested in the comments. I take no credit for this code, it is your function pieced together with IQ's SDF function done in the style you listed above.

Be sure to go to IQ's website, it is one of the best learning resource out there for this material. Though it can be hard to digest till you get all the basics down. IQ's Index Page.

float udSegment( in vec2 p, in vec2 a, in vec2 b )
{
   vec2 ba = b-a;
   vec2 pa = p-a;
   float h =clamp( dot(pa,ba)/dot(ba,ba), 0.0, 1.0 );
   //return length(pa-h*ba); // use actual length

   // or use length squared
   vec2 sqrd = pa-h*ba;
   sqrd = sqrd * sqrd;
   return sqrd.x+sqrd.y;
}

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
   vec2 p = ((2.0*fragCoord-iResolution.xy)/iResolution.y)*1.4;

    // give it some spin
    vec2 v1 = iResolution.xy * vec2(cos(iTime),sin(iTime));

    vec2 v2 = vec2(0,0); // set the start point
    float th = 0.004; // Controls line thickness

    float d = udSegment( p, v1, v2 ) - th; // compute sdf

    vec3 col = vec3(1.0) - sign(d);
    fragColor = vec4(col,1.0);
}

If all this is doing is drawing a line, then there is no need to compute the actual length, so don't...just return lenght squared. I made an edit to the code above that skips the sqrt, but line thickness is now squared.

Bresenham's algorithm was intended to be used for drawing individual pixels and is often implemented directly in the hardware of GPU's. So it drives which pixels to draw in its own loop and tells the hardware which pixel to draw.

ShaderToy is drawing the entire screen, so every pixel is covered probably by drawing a fullscreen triangle, then calling the mainImage function in the fragement shader.

To implement Bresenham's algorithm in ShaderToy the code would need to determine if a particular fragment was actually on the line and in so doing we lose any advantage gained by this clever line drawing technique.

The most efficient way to draw a line on a GPU is not to use ShaderToy at all but write our own bit of code that tells the hardware to just draw a line, this is where graphics API's like OpenGL come into play. Which ultimately would call a fragment shader but unlike ShaderToy, the fragment shader would only be called for those fragments which are actually on the line and our fragment shader would then be reduced to something ultra simple like:

void main(){ return vec4(1,1,1,1); }

Which would result in a pure white line being drawn on screen.