July 26, 2011

Poor Man's Graphics

This is Poor Man's Graphics( or ProgramMers' Graphics). As I observe, some programmers are reluctant to use any graphics program. Whenever they want to explain some vector or geometric stuffs, they would rather do it in ASCII in source code comment.

If you are one of them, I tell you what, Inkscape or Google Draw is not that hard to use. I know I can't convince you, so instead I bring you the concept and the proof of concept of an Ascii to image/ graphics converter - Poor Man's Graphics(PMG).

The best part of it? It is interactive so type in the text boxes below now! And all source code is embedded in this HTML file. Tada- happy coding and happy commenting! remember to toogle 'insert' when necessary.

PMG can only parse the 2 specific types of graphics below. It took me longer than expected, 1 week, to complete the following demo. It is indeed a very good programming exercise. If you have already programmed many apps, games and get bored with programming, then you should try to implement an Ascii art parser like me. It integrates basic concepts of computational pattern matching, geometry and graphics.

Most importantly, there are so many styles you can try!

small challenge

BIG challenge

July 15, 2011

Drawing polylines by tessellation


with joints, caps, feathering and varying color

Introduction

You can consider this as the second episode to the first article Drawing nearly perfect 2D line segments in OpenGL. In a 2D graphics application, drawing only line segments is not enough. We need polylines.

Analysis

Why don't we draw a polyline by a set of line segments?
If we do so, there would be a gap and overdraw at the join between segments. The image on the right are 2 grey segments with 50% transparency. There is a big gap and the darkened part is drawn 2 times. Any polyline thicker than 1.5px will not look good.
To avoid gaps and overdraw(pretend this word as a noun), proper joint treatment is needed. The 3 common joint types as seen in Cairo and most graphics libraries are:
  • miter
    Get the 'outer' border of each line segment and find the intersection point. Use the intersection point as the sharp end. However when the angle between lines is really small, intersection point would be at infinity. As a fall back when the included angle is smaller than a critical value, switch to type bevel.
    This not a perfect solution, as, if the polyline is animatable, it would change abruptly from sharp to beveled.
  • bevel
    Take the 'outer' corner of the two lines and connect them to form a bevel.
  • round
    Draw a circle centered at the common vertex with radius half the line width. Sounds easy but if not drawn carefully, there would be serious overdraw.
and common cap types:
  • butt
    The red line is the skeleton of the segment and a butt end always stays inside it.
  • round
    Draw a semi- circle, with radius half the line width, at the end points of a segment.
  • square
    Visually it is the same as a butt end. A segment is extended at a 'square cap', where the extension is equal to half the line width.

Our approach


Any polyline can be broken down into a set of 3-points-polyline ('^' or 'v'), and we call them anchors. In other words, base on an anchor drawing routine, we can build a polyline drawing routine easily.
Note: the approach attempted in this article is not general polygon outward offseting (as in computational geometry) or line buffering (as in GIS). Readers should seek other resources for those approaches.
The work flow to draw a polyline by tessellation:
  1. we receive a series of points which make up a polyline, together with color, thickness and additional styles like joint type and cap type
  2. break down the polyline into a set of anchors and issue anchor() calls
  3. calculate the geometry(outline) of the anchors according to the thickness
  4. break down the geometry into triangles with no overlap
  5. according to the outline, give each vertex of the triangles a color with alpha
  6. output the list of triangles and send them off the rendering pipeline, to be rasterized ultimately.
We will go through these steps one by one now, except 6, to keep this article less OpenGL specific.

Input

Assume we receives an array of points and color by:
struct Point
{
    double x,y;
    //constructors and operator overloadings...
};
struct Color
{
    float r,g,b,a;
};
void polyline( const Point* P, const Color* C, int size_of_P,
         double weight, char joint_type, char cap_type);
And the Point class has many methods and overloaded operators, allowing we do something like Point mid_point = (P[0]+P[1])*0.5;
We will discover why we are receiving an array of color soon.

Breaking down a polyline into anchors

There are many possible ways to break, and the simpliest is to break at the mid point of each segment:

  1. find the mid point of each segment of the polyline. The mid point between P[0] and P[1] is referred as mid[0]
  2. replace mid[0] with P[0] and mid[size_of_P-2] with P[size_of_P-1]
  3. for i=1 to size_of_P-2,
    create anchor with points[mid[i-1],P[i],mid[i]]
The first cap of the first anchor and the last cap of the last anchor must be drawn. No cap for rest of the anchors. That means the anchor() function must allow us to choose which cap to draw.
The declaration of anchor() should then be like:
void anchor( const Point* P, const Color* C,
         double weight, char joint_type, char cap_type,
         bool cap_first, bool cap_last);

Anchor metrics


P[0],P[1],P[2]the 3 points which make up an anchor
T[0]the perpendicular vector of the line[P[0],P[1]], pointing from P[0] to the outer border of an anchor
T[2]the perpendicular vector of the line[P[1],P[2]], pointing from P[2] to the outer border of an anchor
aT[1]same as T[0] but placed on P[1]
bT[1]same as T[2] but placed on P[1]
vP[1]a vector pointing from P[1] to the intersection of
line [T'[0],aT'[1]] and [T'[2],bT'[1]],
with the 4 vectors placed on their respective points, e.g. T'[0]=T[0]+P[0]

To get the outward vector, rotate the vector T[0]=P[1]-P[0] anti- clockwise 90 degrees. If the points P[0],P[1],P[2] are in clockwise order, do nothing. Otherwise, put the vector T[0] in the opposite direction. Then normalize T[0] and scale to the required thinkness.

Note: all code here uses upper left as origin. Clockwise/ anti- clockwise depends on your chosen coordinate system.
In pseudo- C++ code,
Point T[3];
T[0] = P[1]-P[0];          T[2] = P[2]-P[1];
T[0] = perpen(T[0]);       T[2] = perpen(T[2]);
if ( signed_area(P[0],P[1],P[2]) > 0)
{
    T[0] = -T[0];      T[2] = -T[2];
}
T[0] = normalize(T[0]);    T[2] = normalize(T[2]);
T[0] *= weight;            T[2] *= weight;

Point perpen(Point P) //perpendicular: anti-clockwise 90 degrees
{
    return Point(-P.y,P.x);
}
double signed_area(Point P1, Point P2, Point P3)
{
    return (P2.x-P1.x)*(P3.y-P1.y) - (P3.x-P1.x)*(P2.y-P1.y);
}
To calculate the intersection point between 2 lines, the method is explained here. Say we have an implementation like this:

int intersect( Point P1, Point P2, //line 1
               Point P3, Point P4, //line 2
               Point& Pout);       //output point
Then find vP by:
Point interP, vP;
intersect( T[0]+P[0],T[0]+P[1], T[2]+P[2],T[2]+P[1], interP);
vP = interP - P[1];
Having all these metrics, we can triangulate anchors for mitered joint and bevelled joint without difficulty, but not a round joint.

Inner arc

As mentioned before, to avoid overdraw, we cannot simply draw a circle over a round joint. We should only fill the gap by creating an inner arc from aT to bT. An inner arc is the shorter one of the 2 possible arcs between 2 specified angles.
First, lets look at the code for a basic arc:
void basic_arc( Point P, //origin
         float r,      //radius
         float dangle, //angle for each step
         float angle1, float angle2)
{
    bool incremental=true;
    if ( angle1>angle2) {
        incremental = false; //means decremental
    }
 
    if ( incremental) {
        for ( float a=angle1; a < angle2; a+=dangle)
        {
            float x=cos(a);    float y=sin(a);
            Point q( P.x+x*r,P.y-y*r); //the current point on the arc
        }
    } else {
        for ( float a=angle1; a > angle2; a-=dangle)
        {
            float x=cos(a);    float y=sin(a);
            Point q( P.x+x*r,P.y-y*r);
        }
    }
}
The first trial to fill an arc between 2 vectors:
void basic_vectors_arc( Point P, //origin
         Point A, Point B, 
         float r) //radius
{
 A = normalize(A);          B = normalize(B);
 float angle1=acos(A.x);    float angle2=acos(B.x); //A dot x-axis = A.x

 basic_arc( P,r,PI/18, angle1,angle2);
}

It only gives correct result when both A and B are upward. When any one of them is downward, it is wrong, see the interactive demo. One reason is arc cosine returns only from 0 to PI i.e. 0 to 180 degrees. To extend the range to 0 to 2*PI, do this after getting the value of acos():
if ( A.y>0){ angle1=2*PI-angle1;}
if ( B.y>0){ angle2=2*PI-angle2;}

An inner arc is always shorter than or equal to a half- circumference. If angle2-angle1 is greater than PI, minus angle2 by 2*PI.
Consider the image on the left. Say angle1=120° and angle2=330°. If the arc is calculated incrementally from angle1 to angle2, it would be an outer arc. Since angle2-angle1=210° > 180°, minus angle2 by 360° and becomes -30°. As defined by basic_arc, the arc is now calculated incrementally from angle2 to angle1, which is an inner arc. Handle similarly when angle1>angle2.
Sample code is at the same place.

Then, we can generate a triangle fan between aT and bT for round joint and round cap. The triangulation on the left chose -vP as the apparent center of the fan. Anyway, if the color is all the same over an anchor, the form of triangulation does not matter. Otherwise, triangulation does affect color interpolation.
Tips: use arc length = radius * angle to control dangle, so that the joint would remain smooth under any thickness, as the number of triangles is made proportional to radius.

Applying colors

We are receiving an array of color because we want to do per- vertex coloring. There are many profiles of coloring, as much as a child can produce by coloring a car with crayons. Here we just give each vertex the color of its nearest input vertex.

Suggested further work in coloring profile.

Facing the failed case


The above mentioned tessellation method can draw an anchor correctly at most cases. But not when the two segments are making a very small angle, overlapping and start to degenerate into one line segment. At degenerated case, the intersection point vP would be at infinity. We now have a slightly differed set of metrics.

To identify a degeneration, intersect the green line segment [T[2]+P[2], -T[2]+P[2]] with the red one [-T[0]+P[1], -T[0]+P[0]]. If the intersection point TP lies inside both segments, degeneration occurs.
Consider again when the order of points is reversed.
Luckily, the joint is unaffected.

Fade polygon


To achieve anti- aliasing using the 'fade polygon technique' mentioned in the first article, or just to make it more complicated, we can also render the fade polygon of an anchor. The math is the same, so I will not cover it here.

An addon is we can arbitrary scale the thickness of the fade polygon to achieve feathering. The effect? Very cool!
image on the right: an implementation of anchor() with round joint, round caps and feathering in OpenGL.

Introducing Vase Renderer

The implementation of all the above mentioned ideas to render polylines is put into a library called Vase Renderer. It is open sourced. It is still young so the only function it has is polyline().
Vase Renderer is the attempt to create high quality 2D graphics in OpenGL with a different fundament. Instead of thinking about pixels, we think about triangles. It is the attempt to break historical limitations of 2D graphics libraries. For example, Cairo, SVG has no per vertex color. They do not allow variable color along a polyline. It is not they cannot think of this feature (I believe), just it takes so much consideration to support varying color that they would better redesign the library from scratch. 2D computer graphics still needs evolution.

The benefit of tessellating each triangle by hand is you can control the color of each vertex, form of each triangle and overall topology. We can then create gracefull color blending. Moreover, although the implementation process is tough, once it is finished, the result is nice and fast.

Using the code

For usage and issues about Vase Renderer, visit the current documentation page.

Limitations

Each anchor is processed separately and is independent of each other. At degeneration overdraw would occur. If the polyline is colored, the artifact is especially obvious.

June 28, 2011

vase_renderer_draft1_2

A newer version of VASE renderer is released.

Vase Renderer

first draft, version 0.25 (VaseR draft1_2)

About

Vase renderer(VaseR) is a 2D graphics renderer built on top of OpenGL. Unlike most graphics libraries which are based on SetPixel(), VaseR is based on glDrawArrays(). That means, VaseR takes the advantage of GPU rasterization. Another unique feature of VaseR is rendering with premium quality anti- aliasing using 'fade polygons', as mentioned in this article.

Getting started

To properly use VaseR, you need to understand what role does VaseR play in the rendering pipeline. Suppose your application has a 2D rendering pipeline like:
model transformation
clippings
view transformation
primitives generation
i.e. glDrawArrays();
and/or glBegin(); glEnd();
OpenGL pipeline...
VaseR is a renderer and merely takes care the primitives generation part (highlighted in red). You should set the gl states to meet VaseR's requirements before calling any VaseR function:
blending
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
vertex array
client states
glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_COLOR_ARRAY);

glDisableClientState(GL_EDGE_FLAG_ARRAY);
glDisableClientState(GL_FOG_COORD_ARRAY);
glDisableClientState(GL_INDEX_ARRAY);
glDisableClientState(GL_NORMAL_ARRAY);
glDisableClientState(GL_SECONDARY_COLOR_ARRAY);
glDisableClientState(GL_TEXTURE_COORD_ARRAY);
othergl's default
important: no back face culling

Beginners' tips: hide
How to correctly set gl states for VaseR..
Suppose you have a helloworld application that only renders a line segment in draw():
void draw()
{
 glMatrixMode(GL_PROJECTION);
 glPushMatrix();
  glLoadIdentity();
  glOrtho( 0,context_width,context_height,0,0.0f,100.0f);
  glLineWidth(2.0);
  glBegin(GL_LINES);
   glColor4f(1,0,0.5, 1);
   glVertex2f(10,100);
   glColor4f(0.5,0,1, 1);
   glVertex2f(100,300);
  glEnd();
  //other drawings
 glMatrixMode(GL_PROJECTION);
 glPopMatrix();
}
extend it into:
void draw()
{
 glMatrixMode(GL_PROJECTION);
 glPushMatrix();
 
  glEnable(GL_BLEND);
  glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
   glLoadIdentity();
   glOrtho( 0,context_width,context_height,0,0.0f,100.0f);

   glEnableClientState(GL_VERTEX_ARRAY);
   glEnableClientState(GL_COLOR_ARRAY);
    { Vec2  P1 = {10,100};
     Vec2  P2 = {100,300};
     Color C1 = {1,0,0.5, 1};
     Color C2 = {0.5,0,1, 1};
     double W1= 2.0;
     double W2= W1;
     
     segment(P1,P2, C1,C2, W1,W2, 0);
    }
    //other VaseR calls
   glDisableClientState(GL_VERTEX_ARRAY);
   glDisableClientState(GL_COLOR_ARRAY);

   //other drawings with blending
  glDisable(GL_BLEND); //restore blending options
  
  //other drawings without blending
 glMatrixMode(GL_PROJECTION);
 glPopMatrix();
}

Usage

Provide these structs to VaseR before any vase_renderer_* include by:

struct Vec2 { double x,y;};
struct Color { float r,g,b,a;};
or
typedef your_vec2 Vec2;
typedef your_color Color;

#include "../include/vase_renderer_draft1_2.cpp"

The recommended way is to include "vase_renderer_draft1_2.cpp" .
You should not include "vector_operations.h" or "vertex_array_holder.h" directly. It may break things. They are included by "vase_renderer_draft1_2.cpp".
To compile "vase_renderer_draft1_2.cpp" separately, create an empty cpp file to provide the structs:
//file vase_renderer.cpp
 struct Vec2 { double x,y;};
 struct Color { float r,g,b,a;};
 #include "vase_renderer_draft1_2.cpp"
//end of file

Documentation

API design

VaseR has no states, only a set of functions. Thus you need to pass many parameters to a VaseR function on each call. And these parameters are stored in structures like WinAPI does. Normally if you do not know what options to set, just put 0 at the parameter polyline_opt*. VaseR ensures empty parameter polyline_opt* options=0 and empty structure polyline_opt opt={0}; are default options and would not cause any error.

polyline()

For technical details about polyline() look at here.
void polyline(
 Vec2* P,       //array of point of a polyline
 Color* C,      //array of color
 double* weight,//array of weight
 int size_of_P, //size of the buffers
 polyline_opt* options); //extra options
All arrays must be of the same size otherwise memory error will occur.

options

struct polyline_opt
{ //set the whole structure to 0 will give default options
 char joint;
  #define LJ_miter 0
  #define LJ_bevel 1
  #define LJ_round 2
 char cap;
  #define LC_butt   0
  #define LC_round  1
  #define LC_square 2
  #define LC_rect   3 //unique to vase renderer
 bool feather;
  double feathering;
  bool no_feather_at_cap;
  bool no_feather_at_core;
};
polyline_opt opt={0}; //consider this structure:

opt.joint
LJ_miter LJ_bevel LJ_round

opt.cap
LC_butt LC_round LC_square
LC_rect
LC_rect is related to feathering. Unlike the above 3 common cap types, LC_rect is unique to VaseR. LC_rect puts the fade polygon out of the end points of a polyline.
When feather=false, LC_rect looks very close to LC_butt. The difference is only obvious at high value of feathering.
LC_rect (with high value of feathering) LC_butt (with high value of feathering)

opt.feather, opt.feathering, opt.no_feather_at_cap, opt.no_feather_at_core
feathering is a multiplier to the magnitude of the fade polygon. do not set it to lower than 1.0 .
feathering is unique to VaseR. A feathered polyline with round cap and round joint can mimic the feel of an air brush stroke.
opt.feather = false;
opt.feather = true;
opt.feathering = 8.0;
opt.feather = true;
opt.feathering = 8.0;
opt.no_feather_at_cap = true;
opt.no_feather_at_core = false;
opt.feather = true;
opt.feathering = 8.0;
opt.no_feather_at_cap = false;
opt.no_feather_at_core = true;
remarks: no_feather_at_cap only affects cap type LC_butt, LC_square and LC_rect .


Usage


void sample_polyline()
{
 int size_of_AP=4;
 Vec2 AP[size_of_AP];
  AP[0].x=200; AP[0].y=50;
  AP[1].x=100; AP[1].y=150;
  AP[2].x=300; AP[2].y=150;
  AP[3].x=200; AP[3].y=250;
 Color AC[size_of_AP];
  { Color col={1 , 0, 0, 1}; cc[0]=col;}
  { Color col={.8,.8, 0, 1}; cc[1]=col;}
  { Color col={ 0, 0, 1, 1}; cc[2]=col;}
  { Color col={1 , 0, 0, 1}; cc[3]=col;}
 double Aw[size_of_AP];
  Aw[0] = 8.0;
  Aw[1] = 8.0;
  Aw[2] = 8.0;
  Aw[3] = 8.0;
 
 polyline_opt opt={0};
 polyline( AP, AC, Aw, size_of_AP, &opt);
}
example program is at samples/polyline under VaseR package.

Notes

Varying color is stable but will cause overdraw at degenerated cases.
Varying weight is unstable.
polyline() will "go wild" when a segment is shorter than its own width.

Further work

After solving the above 3 mentioned problems,
can provide the choice between color blending profiles, possibly 'hard' and 'soft'.

segment()

void segment(  const Vec2& P1, const Vec2& P2, //coordinates
        const Color& C1, const Color& C2,      //colors
        double W1, double W2,                  //weights
        const polyline_opt* options)           //extra options
{
 Vec2   AP[2];
 Color  AC[2];
 double AW[2];
  AP[0] = P1; AC[0] = C1; AW[0] = W1;
  AP[1] = P2; AC[1] = C2; AW[1] = W2;
 polyline( AP, AC, AW, 2, options);
}
segment() is merely a wrapper over polyline() , thus all options of segment() is the same as polyline().

Usage

void sample_spectrum()
{
 for ( int i=0; i < 20; i++)
 {
  Vec2  P1 = { 5+29.7*i, 187};
  Vec2  P2 = { 35+29.7*i, 8};
  Color C1 = { 1.0,0.0,0.5, 1.0};
  Color C2 = { 0.5,0.0,1.0, 1.0};
  double W1= 0.3*(i+1);
  double W2= W1;
  
  segment(P1,P2, C1,C2, W1,W2, 0);
 }
}

void sample_radial_spectrum()
{
 for ( double ag=0, i=0; ag < 2*vaserend_pi-0.1; ag+=vaserend_pi/12, i+=1)
 {
  double r1 = 30.0;
  double r2 = 90.0;
  
  double tx2=r2*cos(ag);
  double ty2=r2*sin(ag);
  double tx1=r1*cos(ag);
  double ty1=r1*sin(ag);
  double Ox = 120;
  double Oy = 194+97;
  
  Vec2  P1 = { Ox+tx1,Oy-ty1};
  Vec2  P2 = { Ox+tx2,Oy-ty2};
  Color C1 = { 1.0,0.0,0.5, 1.0};
  Color C2 = { 0.5,0.0,1.0, 1.0};
  double W1= 0.3*(i+1);
  double W2= W1;
  
  segment(P1,P2, C1,C2, W1,W2, 0);
 }
}
example program is at samples/segment under VaseR package. In the below spectrums, each segment is 0.3 pixel thicker/ heavier than the previous segment, demonstrating sub- pixel accuracy of VaseR.

Source code

Development package with documentation, source code, sample images and sample programs is at sourceforge: current stable release or git source tree.

Credit and license

This library is no longer maintained, though I wish I could come back to 2d computer graphics some day.
The license terms at this version "Vase Renderer first draft, version 0.25 (draft1_2)" are:
The MIT License (MIT)
Copyright (c) 2011 Chris Tsang (tyt2y3@gmail.com)

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

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