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.