# What is the most efficient line algorithm using a shader program

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

• Use a signed distance field for a line. Here's an example: shadertoy.com/view/Wl23Dy (you can make it a segment with some further modifications). If you don't want it to pulsate, change: thickness = 0.01 + 0.04*abs(sin(2.0*iTime)); to thickness = 0.01;. Feb 20 at 22:50
• I put your code in a shaderToy, looks nice (very complicated for a line though). One quick tip is you can get the resolution from the variable "iResolution". Then use that to replace the radius, "r" so it isn't constant I used iResolution.y*0.5, then replace all the constant 400,225 values with iResolution*0.5. Then when someone does a fullscreen it will resize with the window. Feb 20 at 23:17
• I made a couple comments that were red herrings, ignore them please. Have you been to the website of the shaderToy creator? Here is a link to IQ's signed distance field functions iquilezles.org/www/articles/distfunctions2d/distfunctions2d.htm Also, IQ has tutorials that explain many of his techniques in great detail. They are well worth the time investment. Lines are referred to as segments on this page. These are all signed distance fields just like lightxbulb suggested. Feb 21 at 0:30

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.

• Thanks for the answer, wouldn't the length function be expensive as it uses a square root. I've heard that Bresenham's algorithm is the fastest but I have no idea how to implement it using shaders because it requires the previous y (or x) value to compute the next values. Is there any way that I can use the efficiency of the Bresenham's line algorithm but using compute shaders to speed up the for loop. Feb 21 at 3:27
• I added a fair bit of explanation above. Feb 21 at 13:29
• How would I create it with OpenGL? Would I need to create a functions library in C++ where I could compute the algorithm? How would I implement it? Sorry, if I'm asking a lot of questions. Thanks Feb 21 at 15:36
• If you want to recreate Bresenham's line algorithm the best way is to implement it on the CPU, that would be written in a language like C++. If your goal is to understand graphics programming in general then you may want to start learning how to draw lines from OpenGL a website like learnopengl.com is a good web resource to learn the programming side. But won't explain the math well. The math is better learned from books (there are many to choose from) also khanacademy.org/math is an excellent resource. Feb 21 at 16:17
• Is drawing lines faster on the cpu? Feb 21 at 21:44