Draw Quadratic Curve on GPU

Question

My task is to render quadratic Bezier curve (path) via Stage3d (Adobe Flash) technology, which have no any extensions for that drawing out-of-the box (while OpenGl have it, as I know). Yea, there is a Starling-Extension-Graphics, but it uses simple method to divide a curve segment to many straight lines, that generates very many triangles for my long curve path.

So.. There is a perfect way for rendering resolution independed shapes for Loop and Blinn. I've read GPUGems3 article (gpugems3_ch25.html) and ported that fragment shader to AGAL2:

Quadratic Curve Pixel Shader

float4 QuadraticPS(float2 p : TEXCOORD0,  
  float4 color : COLOR0) : COLOR  
{  
  // Gradients  
   float2 px = ddx(p);  
   float2 py = ddy(p);  
  // Chain rule  
   float fx = (2*p.x)*px.x - px.y;  
   float fy = (2*p.x)*py.x - py.y;  
  // Signed distance  
   float sd = (p.x*p.x - p.y)/sqrt(fx*fx + fy*fy);  
  // Linear alpha  
   float alpha = thickness - abs(sd);  
  if (alpha > 1)       // Inside  
    color.a = 1;  
  else if (alpha < 0)  // Outside  
    clip(-1);  
  else                   
  // Near boundary  
    color.a = alpha;  
    return color;  
}  

It works. But there are two fundamental problems:

1. I don't understand that algorithm :(. I read about signed distance field, derivates and other... I thought a lot of hours and read again - but no result! My question is: Does anyone help me and explain what happens in that shader (line by line (!), if it possible)?

2. The second problem is that the curve is clipped at the corner of triangle and has a variable thickness. Please look at the picture: https://monosnap.com/file/84EBOuQ1czNM5lprQ5VlnRUKP2mKmW So if I draw a path it looks like this: https://monosnap.com/file/54Zs5Xui6s3BL6lNdZRCx9ibcV2bCF

I like that method by using one triangle per curve segment, because no any geometry needed. And I don't need to have very thick curves (1-2 px is excellent), but a variable thickness is a problem. Can anybody help me?

(Sorry for my English. It is not my native language.)

[edit1 by Spektre] just moved from comment and invalid answer

I plan to use one triangle per one curve segment, something like on the picture

• the path consists from many triangles
• one per one path segment (quadratic curve)
• How to handle issue with this approach if all control points are collinear (lie on the same straight) or nearly collinear?

Durkheim

add details like which quadratic curve are you using (equations) how many contorl points per curve patch etc,... this looks like you are using triangle primitive (the reason for thickness artifacts) may be QUAD_STRIP would be better (where control points are inside the quad patch in defined manner like quad is constant enlargement of control points quadrilateral or what ever but that is tricky for generic curves) or provide control points separately as another attribute layout – Monosome

Thank you, Spektre! I want to draw any quadratic Bezier curves, that described by 3 controls points. Now I think the best way to do that is: 1. Use a constant enlargement quad (by 2 triangles) as the "canvas" where I can draw anything procedurally 2. Find the concrete quadratic qurve equation (math.stackexchange.com/questions/1360891/…) and pass it to the fragment shader instead of Loop/Blinn default equation (u^2 - v = 0). 3. Draw that new equation by Loop/Blinn algorithm. – Durkheim

take a look at this Is it possible to express “t” variable from Cubic Bezier Curve equation? you can easily change the code to meet your lower degree BEZIER ... – Monosome

Answer 1

For 3 control point Bezier curves I would:

1. use triangles as primitives
2. enlarge control points to include area around curve to avoid artifacts

This way is fast and there is no problem to compute A',B',C' from A,B,C and vice versa. If the scale is constant (for example scale=1.25) then the max usable curve thickness<=2.0*min(|control_point-M|)*(scale-1.0).

For safer enlargement you can compute exact scale needed (for example in geometry shader) and pass it to vertex and fragment ... All of above can be done by Geometry shader. You should use transparency to correctly join the curves together. The average middle point should stay the same M=A+B+C=A'+B'+C'

if transparency is not an option

Then you need to change the approach so pass control points and position inside textures.

1. create one 2D float texture with control points

• something like float pnt[9][N]
• pnt[0,1,2][] is control point A(x,y,z)
• pnt[3,4,5][] is control point B(x,y,z)
• pnt[6,7,8][] is control point C(x,y,z)

2. also create 1D color texture

• something like rgba col[N]
• The x axis resolution of both textures = N is the number of Bezier curves

3. now draw single Quad covering entire screen

And inside fragment shader check if pixel is inside any of the curve. If yes output its color ...

This can get very slow for high Bezier curve count N

[edit1] almost collinear control points

for those I would use Quads

• D,E are mirrored points A,B around C
• D=C+C-A
• E=C+C-B
• C is the middle point M = (A+B+D+E)/4 = C = (A'+B'+C'+D')/4
• and A',B',C',D' are enlarged A,B,D,E control points
• A'=C+(A -C)*scale
• B'=C+(B -C)*scale
• A =C+(A'-C)/scale
• B =C+(B'-C)/scale

This can be used for any Bezier not just almost colinear but it uses larger polygons so it will be slower on performance (more fragments then really needed)

Here more advanced/optimized GLSL approach with complete implementation of cubic BEZIER curves:

• rendering 2D cubic BEZIER with GLSL

Monosome

Thank you very much, Spektre! It's fantastic!!! That's what I thought, but I could not write! It will probably work very fast! – Durkheim

Hm... I don't undestand why I need to use transparency... What do you mean? The second approach is not entirely clear right now, too... ( – Durkheim

@Durkheim if you got just single color bezier curves then you do not need transparency but you need to throw away fragments not used by curve. Otherwise the empty area of triangle (overlapped/enlarged area included) will clear the already drawed bezier curves ... – Monosome

second approach is that for each pixel/fragment you loop through all of the control points of All Bezier curves and if inside triangle compute if it belongs to that Bezier curve and set the color or not ... – Monosome

yes I want to throw away fragments not used by curve as you said. And I plan use one triangle per one curve segment, something like on the picture below. One issue with this approach is what if all control points are collinear (lie on the same straight) or nearly collinear? – Durkheim

@Durkheim for those will this not work properly. You can handle those with different shader/primitive or use second approach for such cases – Monosome

The question is which shader/primitive? ;) Any nearly collinear bezier control points curve is Bezier curve yet. – Durkheim

@Durkheim added edit1 with different primitive (QUAD) example – Monosome

thank you very much! Now I think about another aproach to that problem, because as you said it will be slower on performance, unfortunately and don't give me easy way to draw straight lines too. – Durkheim

@Monosome Sorry for bringing up such an old question, but what is the scaling applied to? – Cohort

@Cohort to vertexes ... if you send original vertexes to GPU then they must be enlarged by scaling so the primitive area covers the whole curve this might be done in Geometry shader along with computation of the curve polynomial coefficients. You can do this also the other way around and apply the enlargment on CPU side ... then you scale down in geometry shader ... – Monosome

Thanks! I was trying to do a WebGL implementation (which doesn't have the geometry shader), so I got a bit confused on how to reverse the scaling in the fragment shader. I ended up doing the UV scaling in the fragmentshader, which worked with the help of your post. – Cohort