Smooth, efficient, perfect curves

Hi,

there was a reply to one of my posts on the old forum and I’ve decided to reply on the new forums instead. It’s about rendering thick lines, a topic that sounds like “didn’t we solve this in the 60’s?” - but is surprisingly hard to pull off if you care about a) the looks and b) performance.

The old post described a way to draw long line strips without the little gaps between the individual segments. OpenGL by default doesn’t do a great job when rendering lines with a thickness > 1, so you have to come up with your own solution. I won’t repeat what I came up with, you can find a full discussion in the old post.

However, recently I was doing a project where I had to draw hundreds, maybe even thousands of quadratic curves per frame. The designers wanted thick (5 pixel) curves, anti-aliased of course, with a nice color gradient from start to end point and an adjustable curvature.

The solution I arrived at is based on this ShaderToy sample:
https://www.shadertoy.com/view/lts3Df

It calculates a distance to the curve for each pixel and renders a perfectly anti-aliased quadratic curve. It suffers from a few artifacts (e.g. it can’t handle straight lines) and can be optimized a bit more, but it was a good start. My first implementation used simple quads the size of the curve’s bounding box, but that was horribly slow. The calculations don’t come cheap, so you want to minimize the number of affected pixels as much as possible.

Next thing I did was calculating a simple mesh on the CPU for each curve, just so I could experiment with different options. I would then later translate this into a GPU-based solution. I found that it’s sufficient to subdivide the curve into roughly 40 segments (even for strongly bent curves) by calculating the position for:
t = 0.0, t = 0.025,t = 0.050t = 1.0
, then taking the normal of the tangent in that point and extending it outward. The wire frame then looks like this:

As you can see, this reduces the number of affected pixels drastically. It was already much faster to draw, but only if the total number of curves was low. Drawing lots of curves made me CPU bound and the frame rate dropped. So, GPU to the rescue.

I constructed a simple VboMesh, containing 80 vertices (39 segments in total). Their positions are completely irrelevant, for we will calculate them in the vertex shader. Instead, I stored the following information in the vertex:

 x = t0; // the "t" for this position
 y = t1; // the "t" for the next position on the curve (poor man's tangent)
 z = side; // either a 1 or a -1
 w = offset; // used to extend the mesh to accomodate for rounded end points 

To render all the curves, I use instanced rendering. The instance buffer contains the data for each curve:

 ci::vec2 p0;    // start point in window coordinates
 ci::vec2 p1;    // control point in window coordinates
 ci::vec2 p2;    // end point in window coordinates
 float    t_min; // range: we can animate the curve by 
 float    t_max; //        only drawing a portion of it
 ci::vec4 col0;  // start color
 ci::vec4 col1;  // end color

The vertex shader then simply calculates the position of each vertex based on this data.

    // Evaluate quadratic curve.
    vec2 a = evalQuadratic( p0, p1, p2, t0 );
    vec2 b = evalQuadratic( p0, p1, p2, ( t1 < 0.0 ) ? 1.0 - t1 : t1 );
    if( t1 < 0.0 )
        b = a + ( a - b );

    // Calculate normal.
    vec2 v = 2.0 * uThickness * normalize( b - a ) * sign( t1 );
    vec2 n = vec2( -v.y, v.x );

    vertPosition = side * n + offset * v + a;

The fragment shader is very similar to the ShaderToy sample, just a bit more optimized, cleaned up and with fewer artifacts (as in: none).

The end result looks like this:

We can endlessly zoom in on the curves and they remain perfect. Thickness can be adjusted as well, even to values like 30 pixels or more. Rendering 2048 long curves on a 10800x3840 screen takes less than 0.5ms in total, including uploading the instance data from the CPU.

Hopefully this answers your question, Caleb.

-Paul

15 Likes

Yes! Thank-you for such a detailed explanation. I think that is something I could really work with if not in my current application it is a beautiful solution for future ones.

Could you help me understand quadratic curves a bit more as I am not sure this implementation works in my scenario owing to the way my lines are formed.

To simplify my scenario lets say I wanted to draw a continuous but fading trail behind the users finger. The finger can move with any speed in any direction even doubling back on itself. To draw the line all I have is the current frame position of the finger, the position the finger was in during the last frame, and the position of the finger in the frame before that. As you can imagine this is a queue type scenario where next frame some data will be lost from a few frames ago and be replaced with the new position.

Can I still apply this solution since it involves quadratic curves? The line needs to match each point exactly.

Hi,

what you’re looking for is called a Ribbon or a Trail. Those can relatively easily be drawn using a triangle strip.

Create a vertex buffer std::deque<ci::vec2>>, which is empty at the start. In the first frame, you store the current position in a member variable. Every next frame, you check if the cursor has moved far enough from the initial position. If so, calculate a normal like so:

auto v = glm::normalize( current_position - previous_position );
auto n = vec2( -v.y, v.x );

, then add 2 vertices to your buffer:

vertices.push_back( current_position + thickness * n );
vertices.push_back( current_position - thickness * n );

, but before you do that you check if the buffer is full and remove the first two vertices if it is:

while( vertices.size() >= 100 ) {
    vertices.pop_front();
    vertices.pop_front();
}

Then set the initial position to the current position to get ready for the next frame. Finally, a quick and dirty way to render the ribbon is to use the built-in functions to render the triangle strip:

if( vertices.size() >= 4 ) {
    gl::begin( GL_TRIANGLE_STRIP );
    for( auto &vertex : vertices )
        gl::vertex( vertex );
    gl::end();
}

, but for better performance and more options I’d recommend creating a gl::Batch or gl::VboMesh with a fixed number of vertices, then update the vertex positions by mapping its vertex buffer in combination with a call to:

batch->draw( first, count ).

See this post for even more info.

Quadratic curves as described in this thread are just simple curves with 2 end points and a control point and are not suited to render wiggly lines.

-Paul

2 Likes

Hi,

thank you for the great post, it helped a lot. I wonder if you could send me your optimised fragment shader, because I was unable to fix some of the artefacts… :confused:

this post is exactly what I’m searching for. I need to draw curves without broken vertices, however, from the info, I still have doubt about how to implement it. Is there any cinder example where I can learn how to do it?

Hi David,

welcome back. What I did was the following:

  1. First construct a mesh that you can use for all the curves. It’s basically just a straight triangle strip with some extra information packed in the data that allows us to move the vertices in the vertex shader.
    constexpr int steps = 40;
    constexpr float increment = 1.0 / steps;

    std::vector<vec4> vertices;
    vertices.emplace_back( 0, increment, -1, -1 ); // Params: t0 [0...1], t1 [0...1] (if negative, subtract from 1.0), side (-1 or 1), offset (extend end points)
    vertices.emplace_back( 0, increment, +1, -1 );
    for( int i = 1; i < steps; ++i ) {
        vertices.emplace_back( i * increment, ( i + 1 ) * increment, -1, 0 );
        vertices.emplace_back( i * increment, ( i + 1 ) * increment, +1, 0 );
    }
    vertices.emplace_back( 1, -increment, -1, +1 );
    vertices.emplace_back( 1, -increment, +1, +1 );
  1. In your vertex shader, take this data:
    float t0 = ciPosition.x;
    float t1 = ciPosition.y;
    float s = ciPosition.z;
    float d = ciPosition.w;
  1. Also pass the curve points and desired thickness, either using uniforms or as instanced attributes:
uniform vec2 p0;
uniform vec2 p1;
uniform vec2 p2;
uniform float thickness;
  1. We’re going to output the vertex position:
out vec2 vertPosition;
  1. Evaluate the quadratic function to find the vertex positions:
vec2 evalQuadratic( in vec2 p0, in vec2 p1, in vec2 p2, in float t )
{
    float t1 = 1.0 - t;
    float b0 = t1 * t1;
    float b1 = 2.0 * t * t1;
    float b2 = t * t;

    return ( p0 * b0 + ( p1 * b1 + ( p2 * b2 ) ) );
}

void main(void)
{
    ...
    vec2 a = evalQuadratic( p0, p1, p2, t0 );
    vec2 b = evalQuadratic( p0, p1, p2, t1 );

    vec2 v = thickness * normalize( b - a ) * sign( t1 );
    vec2 n = vec2( -v.y, v.x );

    vertPosition = s * n + d * v + a;
    ...
}

This should give you a mesh that follows the curve closely and minimizes the number of pixels to evaluate in the fragment shader.

  1. Finally, use the code found in the ShaderToy sample to render the smooth curve.

~Paul

1 Like