Line cap calculation

To continue my previous post, I would like to explain a little more about how the line cap is calculated.

Here is the order at which the line is rendered:

1. Line Start Cap calculation
2. Join vertex calculation n1
3. ...
4. Join vertex calculation n1 + joinNum
5. Line End Cap calculation


As you can see the cap starts the line and ends it. Because I am using GL_QUAD_STRIP then it is important to properly connect all the vertices together, and espcially make their total number base power of 4, because each quad consists of 4 points.

There are usually 3 different cap styles:

1. None (the cap vertexes are created at origin of the start/end point) [2 vertexes]


2. Square (the cap vertexes are created at the same origin but with an offset equal the the line width)[2 vertexes]



3. Round (the cap vertexes form half-arc at the origin of the start/end point)[2 + 2*iterations vertexes]


So The first thing that is required - the general cap function:

//Calculates cap for the line
void CalculateCap(  LineVertex v0,
                                   LineVertex v1,
                                   bool start ) //decides is this cap starts the line = true or ends = false
{

     float len = CalculateDistance( v0 , v1 );

     float dx1 = (v1.posY - v0.posY) / len;
     float dy1 = (v1.posX - v0.posX) / len;
     float dx2 = 0;
     float dy2 = 0;

     dx1 *= _size;
     dy1 *= _size;

    if( _capStyle != CapStyle_Round)
   {
        if( _capStyle == CapStyle_Square)
       {
            dx2 = dy1 ;
            dy2 = dx1 ;
       }

       if( start )
      {
           AddVertex( v0.posX + dx1 - dx2, v0.posY - dy1 - dy2);
           AddVertex( v0.posX - dx1 - dx2, v0.posY + dy1 - dy2);
      }
      else
     {
          //end of path
         AddVertex( v0.posX - dx1 - dx2, v0.posY + dy1 - dy2);
         AddVertex( v0.posX + dx1 - dx2, v0.posY - dy1 - dy2);
     }
  }
  else
  {

      //Converts radian result of atan2 to Deg we need for comaring later
       float subAngle = -(TRIG_RAD2DEG( atan2( dx1 , dy1 ) ) - 180);

     //simple but does check the direction of the line edge
      if( (subAngle > 90 )&&( subAngle <= 270 ) )      
      {           
             if( start )          
            {               
                    CalculateRound(   v0 ,                                              
                                                   dx1, -dy1 ,                                             
                                                  -dx1, dy1 ,                                             
                                                   v0.posX + dx1 ,                                             
                                                   v0.posY - dy1 ,                                             
                                                   true );         
           }        
          else               
               {                      
                   CalculateRound(  v0 ,                                                   
                                                  dx1, -dy1 ,                                                 
                                                 -dx1, dy1 ,                                                  
                                                 v0.posX - dx1 ,                                                  
                                                 v0.posY + dy1 ,                                                 
                                                  true );               
               }    
      }   
     else        
          {          
                    if( start )          
                    {                  
                                 CalculateRound( v0 ,                                               
                                                             -dx1, dy1 ,                                                 
                                                              dx1, -dy1 ,                                               
                                                              v0.posX - dx1 ,                                                
                                                              v0.posY + dy1 ,                                                
                                                              false );         
                     }         
                     else              
                          {                           
                                  CalculateRound( v0 ,                                                       
                                                              -dx1, dy1 ,                                                        
                                                               dx1, -dy1 ,                                                         
                                                               v0.posX + dx1 ,                                                         
                                                              v0.posY - dy1 ,                                                         
                                                               false );             
                          }        
             }      
      }
}

This general function finds the result vertexes this way:

1. Finds relative position of the initial vertexes. Exactly the same way as it was made with "None" line join.

2.Now depending on the Cap style:     

  None     - Just use these calculated vertexes and add them to the render buffer.     
  Square  - Apply line width multiplier and add them to the render buffer.     
   Round  - This is more complicated:     

For round join the renderer needs to calculate arc:

void CalculateRound(    
                                         LineVertex v0,        //center of the line join                                        
                                         float dx1, float dy1, //the start point                                        
                                         float dx2, float dy2, //the end point                                       
                                         float middleX ,                                        
                                         float middleY ,   //The middle point for creating correct GL_QUAD vertex                             bool reverse) //use reverse incase of inner join

{            

          float a1 = TRIG_RAD2DEG( atan2( dy1 , dx1 ));            
          float a2 = TRIG_RAD2DEG( atan2( dy2 , dx2 ));            

          float angleStep = (a1 - a2) ;            //number of iterations            
          angleStep = angleStep / (iterations + 1) ;            //starting angle            
          float cangle = 0;          


           if( reverse )          
          {                
                     //INNER JOIN               
                     AddVertex( middleX , middleY );               
                     AddVertex( v0.posX - dx2 , v0.posY - dy2);              

                      a2 += 180;              
                      cangle = a2 ;             

                    for(int i = 0; i < iterations ; i++)            
                   {                    
                            cangle += angleStep;                   //Also put the middle point for the GL to correctly link other GL_QUAD later                   
                          AddVertex( middleX , middleY );                   //find the rotated point                           AddVertex(                                         
                                             _size * trig.Cos(cangle) + v0.posX ,                                         
                                             _size * trig.Sin(cangle) + v0.posY );            
                   }           

                         AddVertex( middleX , middleY );            
                         AddVertex( v0.posX - dx1, v0.posY - dy1);       
          }       
          else      
               {              
                       //OUTER JOIN              
                      AddVertex( v0.posX + dx1 , v0.posY + dy1);              
                      AddVertex( middleX , middleY );             //change the direction of angle iteration            
                      angleStep *= -1;            
                      cangle = a1 ;           

                      for(int i = 0; i < iterations ; i++)          
                     {                  
                            cangle += angleStep;                 //find the rotated point                

                            AddVertex(                                     
                                              _size * trig.Cos(cangle) + v0.posX ,                                     
                                             _size * trig.Sin(cangle) + v0.posY );               //Also put the middle point for the GL to correctly link other GL_QUAD later               

                           AddVertex( middleX , middleY );             
                   }            

                            AddVertex( v0.posX + dx2, v0.posY + dy2);           
                            AddVertex( middleX , middleY );        
           }
 }


The arc calculation is not that hard. For this we need to have the center point, the start and end point. The middleX and middleY are used as an additional point to connect quad with.

We also need to find the start angle from where to start iteration and the end angle when to end.

Each iterations adds additional 2 vertexes. If you look closely for the iteration code, you would see that it generates minimum 4 vertexes. The first 2 vertexes are actually at the same point, they start the cap, then there are iteration vertexes and at the end 2 more for opening the next 2 vertexes

The order of drawing for 3 iterations is shown next. This is for the start cap with values:

CalculateRound( v0 ,                              
                              dx1, -dy1 ,                              
                              -dx1, dy1 ,                              
                              v0.posX + dx1 ,                              
                              v0.posY - dy1 ,                              
                              true );

Initial state:


1. First 2 vertexes and iteration 0


2. Iteration 1


3. Iteration 2


4. And now the end 2 vertexes are calculated



This is probably all that is required for rendering line cap styles.

Line rendering Join calculation

For the past few weeks, I have been working on the new line join rendering system.

This was required for the GUI system, because right now it is using only the most basic method, with huge noticeable cracks between line. I was also always wondering how it would be possible to make this line rendering happen. I haven't found allot of sources. There is only one source I used mainly for this. It is AntiGrain project. This is really awesome rendering library that features vast number of different shapes. I used the join rendering system from there:

Math Stroke.H
VCGen stroke.cpp
VCgen stroke.H
Agg Math.h

It is GPL project so source code learning is a must.

I haven't figured out exactly how the rendering in the AGG works, but I managed to get a few pointers and a few handy functions, that I am using in my own implementation right now.

Ok, first let's take the simple path of lines that are connected with each other:



There are 9 lines each connected with different angle. Let's imagine the line size is increased. How the line would look like.

The current approach I am using right now, would produce something like that:



This is what I call "None" join style, because the vertices aren't connected to each other.

How it was calculated ?

Well it is done in specific order:

1. Line Start Cap calculation
2. Join vertex calculation n1
3. ...
4. Join vertex calculation n1 + joinNum
5. Line End Cap calculation

There is also different cap styles, for now I would only use the default none. Which creates 2 vertices for the start and end cap.

For this specific line example the vertices would be calculated in this order:
1. Cap (2) - none cap
2. A+B (4)
3. B+C (4)
4. C+D (4)
5. D+E (4)
6. E+F (4)
7. F+G (4)
8. G+H (4)
9. H+I (4)
10. Cap (2) - none cap

There is total of 36 vertices required.

Here is how the code would look for this:

//calculate the data
void Calculate()
{
     //fully clear the rendering array
     _renderVertex.Cleanup();
  
     //START THE CAP

    //atleast 2 points required
    if( _vertexes.GetLength() < 2 )
   {
       return;
    }

   //GENERATE START CAP
   CalculateCap( _vertexes[0] , _vertexes[1] , true );


   for(int i = 1; i < _vertexes.GetLength() - 1; i++)
  {
        //CALCULATE JOINS
        CalculateJoin( _vertexes[ i - 1] ,
                                  _vertexes[ i + 0] ,
                                  _vertexes[ i + 1] );
  }


//GENERATE END CAP
CalculateCap( _vertexes[ _vertexes.GetLength() - 1] , _vertexes[ _vertexes.GetLength() - 2] , false );


}

The Join calculation itself, only needs to do few things. Calculate the distance between points is the first thing to do:

float len1 = CalculateDistance( v0 , v1 );
float len2 = CalculateDistance( v1 , v2 );

Now if we have the distance we can calculate the rotated angle, like this:

float dx1 = _size * (v1.posY - v0.posY) / len1;
float dy1 = _size * (v1.posX - v0.posX) / len1;
float dx2 = _size * (v2.posY - v1.posY) / len2;
float dy2 = _size * (v2.posX - v1.posX) / len2;

Note the _size here is the width of the line.


After that we need to calculate only the line points relation. They are either inner or outer join:



This can be done by calculate something like cross product. I have taken this from AGG:

float cp = CrossProduct2D( v0.posX, v0.posY, v1.posX, v1.posY, v2.posX, v2.posY );

float CrossProduct2D(
                                       const float& ax, const float& ay, //1 LINE
                                       const float& bx, const float& by, //2 LINE
                                       const float& cx, const float& cy ) //3 LINE
{
return (cx - bx) * (by - ay) - (cy - by) * (bx - ax);
}


And now we can calculate the vertices itself, depending on the join style:

if(cp != 0 && (cp > 0) == (_size > 0))
{

     // INNER JOIN
     //just 2 vertices for end
     AddVertex( v1.posX + dx1, v1.posY - dy1); //1
     AddVertex( v1.posX - dx1, v1.posY + dy1); //2


     //and 2 vertices for start of another line
     AddVertex( v1.posX + dx2, v1.posY - dy2); //3
     AddVertex( v1.posX - dx2, v1.posY + dy2); //4
}
else
{
     // OUTER JOIN
     //just 2 vertices for the end of first line
     AddVertex( v1.posX + dx1, v1.posY - dy1); //1
     AddVertex( v1.posX - dx1, v1.posY + dy1); //2

     //and 2 vertices for start of another line
     AddVertex( v1.posX + dx2, v1.posY - dy2); //3
     AddVertex( v1.posX - dx2, v1.posY + dy2); //4
}

The first 2 vertices close to the previous quad and the next 2 opens the new one.




This would continue this way untill the end cap is reached, which closes the quad. It is important to properly close the quads. Atleast with my video drivers it caused some really dangerous issues, when the computer screen started to flicker or it crashed and restarted. So additional caution is required.

And here is how it looks when it is done:



So far for the most simple way :). I think I would also explain later how the more advanced ways of rendering line joins can be done.

Finally an update !

It has been a while since I have updated this blog. Well the primary reason is, that I was working on the new GUI system and at that time there wasn't anything that could be shown.

But it is progressing and I can show a few early screenshots.

The old GUI systems worked fairly well, but had a few flaws. I tried to avoid these problems and add more functionality this time.

One of the major problem in the old GUI was the rendering system. The GUI skin was one big file. It included description of how to render each widget and for each different state. There were generally 4 states: normal , disabled , hover , clicked. Each state is drawn by GL_POLYGON and all the points should be specified directly with (Color,Texture coordinate,position on the 2d screen and anchor).

The new GUI however tries to minimize the amount of data that needs to be written. This is achieved by creating one stroke object that would later be used to draw different parts of many widgets, but it only needs to be defined once.

The widget shape is created from the list of these strokes. The stroke itself is made from many 2d primitive shapes like: line , rectangle , round rectangle , circle , ellipse , arc and bezier. The amount of the data that needs to be written to define a stroke is minimum.

Here is an example of the stroke created from 2 bezier curves:



Each bezier curve is defined by 4 points. The GUI also allows to change the quality of shapes.

The previous shape was created from 16 iterations this is created from 8:


Each shape except line and rectangle can have different quality versions.

One of the most important additions to the GUI rendering system is the material system. The GUI uses the same material system that is used in any other engine part.
This makes it possible to create all sorts of animation effects. The texture coordinates , gradient and alpha values are generated automatically:



One of the most annoying issues when making GUI systems, especially with OpenGL is the lack of good line drawing functionality. The standard line drawing implementation is really limited. Not only it doesn't guarantee some line widths to be available, but the width itself is related directly to pixel width. Which makes it looks different on different resolutions. The other problem is antialiasing of the line. It is widely supported by most graphic cards this day, however their implementation depends on the graphic card manufacturer driver version, and can produce different results.

The line drawing system that I am using here is created by two 4 vertex quads. Original drawing with one 4 vertex quad produced really noticeable jagged lines. However by adding additional quad and using blending, made it look really well, without almost any performance impact. It would also work on any OpenGL implementation and on any resolution the same correct way:



I would probably make some more posts soon, if I manage to get something new working :)