May 17, 2011

Drawing nearly perfect 2D line segments in OpenGL

With premium quality anti- aliasing, color, thickness and minimum CPU overhead


Introduction

OpenGL is great, when it comes to line drawing most people would draw it by:
    glBegin(GL_LINES);
    glVertex3f( x1,y1,0);
    glVertex3f( x2,y2,0);
    glEnd();
It does give you a straight line, but a very ugly one. To improve, most people would enable gl line smoothing:
    glEnable(GL_LINE_SMOOTH);
    glHint(GL_LINE_SMOOTH_HINT, GL_NICEST);
    glEnable(GL_BLEND);
    glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
But this technique has a couple of drawbacks:
-hardware dependent. It does not necessarily look the same on different machines.
-average quality. It does not give perfect quality on most hardware. (surprisingly on my mobility Radeon HD 4200 it looks really good.)
-poor thickness control. Most drivers only support thickness of integer value. And the maximum thickness is 10.0px


Observation

You just need to know a little bit OpenGL. Look at the hello world OpenGL program. It merely draws a triangle with different colors on each vertex. What do you observe?


glLoadIdentity();
//window size is 300x300
glOrtho( 0,300,300,0,0.0f,100.0f);
glClearColor( 1,1,1,0.5f);
glClearDepth( 1.0f);
glClear(GL_COLOR_BUFFER_BIT |GL_DEPTH_BUFFER_BIT);

glBegin(GL_TRIANGLE_STRIP);
glColor3f( 1,0,0);
glVertex3f( 150,10,0);
glColor3f( 0,1,0);
glVertex3f( 280,250,0);
glColor3f( 0,0,1);
glVertex3f( 20,250,0);
glEnd();
Yes the edge is jaggy. Then?
Well the interpolation among colors looks perfect.
The above observation is sufficient to enable us to do what we want.

The fade polygon technique

Now lets draw a paralellogram which changes color from white to red.


glBegin(GL_TRIANGLE_STRIP);
glColor3f( 1,1,1);
glVertex3f( 50,270,0);
glVertex3f( 100,30,0);
glColor3f( 1,0,0);
glVertex3f( 58,270,0);
glVertex3f( 108,30,0);
glEnd();
The right side is still jaggy. The left side is,,, smooth. Can you now think of anything?
Now lets draw two paralellograms, which change color from white to red then to white again.


glBegin(GL_TRIANGLE_STRIP);
glColor3f( 1,1,1);
glVertex3f( 50,270,0);
glVertex3f( 100,30,0);
glColor3f( 1,0,0);
glVertex3f( 54,270,0);
glVertex3f( 104,30,0);
glColor3f( 1,1,1);
glVertex3f( 58,270,0);
glVertex3f( 108,30,0);
glEnd();
Let's call this 'the fade polygon technique': draw a thin quadrilateral to render the core(inner) part of a line, then draw two more beside the original one that fade in color to give effect of anti- aliasing.

Quality

This article focuses on 2D line drawing so the meaning of “perfect quality” is with respect to 2D graphics. In particular, Maxim Shemanarev (responsible for Anti-Grain Geometry) is the boss in fine grained 2D rendering.
Let see a picture from his article.

The above picture shows lines with thickness starting from 0.3 pixels and increasing by 0.3 pixel.
Using triangles to approximate line segments in the correct dimension is not easy. I do it by experiment and hand calibrated the drawing code,

then obtained:

Believe that it is rendered by the above technique in OpenGL. It is not perfect though, so I say “nearly perfect”.
(Update: I refined the rendering such that the end points of a line looks better)
I found fltk-cairo convinent to build so I actually took Cairo, the popular 2D rendering API on Linux, as a benchmark.

Flip between the two picture to compare.

It is seen that Cairo draws thin lines a little bit thicker than it should look. The circular fan on the right is drawn as 1px black lines by cairo_set_line_width (cr, 1.0) .

But you see the horizontal line is a 2px grey line. In my code I tried hard to give a 1px #000000 line when you request a 1px #000000 line on exact pixel coordinate, especially at horizontal/ vertical condition. But there is no guarantee in sub- pixel coordinate, other colors and orientations.
Ideal 1px black lines should look very close to aliased raw 1px lines, but just being smoother. Now take a closer look at the fan on the right and flip to compare:

Hope you agree with my judgment.

A final compare:

Functionality

This technique gives you:
-premium quality anti-aliased lines
-smaller CPU overhead than any other CPU rasterizing algorithms
-finer line thickness control
-line color control
-alpha blend (can choose to use alpha blend or not)


Most importantly, source code and usage

source code is at here.
void line(
    double x1, double y1, double x2, double y2, //coordinates of the line
    float w, //thickness of the line in pixel
    float Cr, float Cg, float Cb, //RGB color components
    float Br, float Bg, float Bb, //color of background, ignored if alphablend is true
    bool alphablend); //use alpha blend or not
void hair_line( double x1, double y1, double x2, double y2, bool alphablend=0);
The first function line() gives you all the functionality. You can choose not to use alpha blending by setting alphablend to false, in this case you will get color fading to the background. In no- alpha- blending mode you still get good result when the background is solid and lines are not dense. It is useful when doing overdraw. The below image should tell you what alphablend=false means.

The second function hair_line() draws near-perfectly a black "hair line" of thickness 1px with no color or thickness control. You can optionally use alpha blend otherwise it assumes the background is white. I provide this in case you do not need all the functionalities.
You only need to include the header vase_rend_draft_1.h and it should work. This code use only little features of OpenGL so should be easily incorporated into any existing program. Your base program can be a Nehe hello world sample, glut, SDL, fltk or whatever. If you copy only part of the code, make sure you copy also the function
static inline double GET_ABS(double x) {return x>0?x:-x;}

Make sure you render 2D in this way:
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
glMatrixMode(GL_PROJECTION);
glPushMatrix();
    glLoadIdentity();
    glOrtho( 0,context_width,context_height,0,0.0f,100.0f);
    line(10,10,100,80, 1.0, 1,0,0.5, 0,0,0, true);
    //other 2D drawings,,,
glPopMatrix();
glDisable(GL_BLEND); //and whatever to restore blending options

Performance

Today's graphics card can render millions of triangles per second. Although alphablend is not as fast, it is still faster than any other method.
Some how (by a breif benchmark) it is 100 times faster than OpenGL native line drawing with smoothing turned on (on my machine, maybe that's why it looks so good). And 40 times faster than Cairo when drawing 10000 5px thick lines. Later if I have time I can include a more formal benchmark.
If you want to boost things up further, this technique allows you to separate opaque drawing from semi- transparent drawing (identify it easily by glColor4f( C,C,C, 0);). You can draw the solid part of all lines first then the those which require alphablend. However this ends up an drawing engine which is not easy to incorperate into existing code.

Portability

I have not tested the code on many machines, so I cannot guarantee.
This technique depends on rasterizing. There is (always) a higher chance that a GL driver implements rasterization correctly than smooth- line drawing.
As far as I know most hardware support sub- pixel accuracy rasterization. I observe that rasterization in OpenGL ES on iPhone looks good. It would probably work.
In my testings, there are often rounding errors which cause tiny artifact. That is not perfect, but still good.
Again I cannot guarantee, the best way is to test it yourself.

Final words

I can provide the source I used to produce the above images. But I assume you know how to compile fltk 1.3 with cairo and gl enabled. If you find this useful I just hope you to cite this page. If you used it in a program make sure you email me to let me see how well it would work.
Do not miss the second episode Drawing polylines by tessellation.

By Chris Tsang  tyt2y3@gmail.com, 2011 May

5 comments:

  1. This is one of the most unreadable blogs I have encountered. For your own sake, change your fonts. There is such a thing as "too fancy".

    ReplyDelete
  2. Perhaps you simply need to check you eyes again, there's nothing wrong with this font in terms of readability. You simply don't like it.

    Thanks for the technique, I was using opengl's linesmoothing but this works out much better for me!

    ReplyDelete
  3. (Actually he might be correct. I changed the font of title and subtitle after his words. the previous font is kind of 'fancy'.)

    Oh, I am glad that someone really used my code, thanks for you trial. If you need to draw high quality polylines as well, check out my other blog post. cheers!

    ReplyDelete
  4. This is actually a very useful technique and is one I was trying to get right until I stumbled across this on CodeProject.

    I stripped out some stuff from your original v2 function (namely optional alpha blending) and converted everything over to floats (double precision is not necessary in these cases and helps to reduce possible cache misses), but overall it's intact and has found its use in one of my projects.

    Thanks for providing a very useful function!

    ReplyDelete
  5. Thank you for your kindly feedback. I am glad that you found it useful. There are other techniques involving shaders to draw anti-aliased line segments, but it is likely an overkill.
    By the way, I released a more powerful library to draw polylines and curves in opengl, you can have a look if you need these features. VASE renderer

    ReplyDelete