What is an inner miter calculation?

Question

I found the following algorithm to generate polygon outlines:

void CGlShape::GenerateLinePoly(std::vector<DOUBLEPOINT> &input, int width)
{
 OutlineVec.clear();
 if(input.size() < 2)
 {
  return;
 }


 if(connected)
 {
  input.push_back(input[0]);
  input.push_back(input[1]);
 }


 float w = width / 2.0f;

 //glBegin(GL_TRIANGLES);
 for( size_t i = 0; i < input.size()-1; ++i )
 {
  POINTFLOAT cur;
  cur.x = input[i].point[0];
  cur.y = input[i].point[1];


  POINTFLOAT nxt;


  nxt.x = input[i+1].point[0];
  nxt.y = input[i+1].point[1];

  POINTFLOAT b;
  b.x = nxt.x - cur.x;
  b.y = nxt.y - cur.y;

  b = normalize(b);



  POINTFLOAT b_perp;
  b_perp.x = -b.y;
  b_perp.y = b.x;


  POINTFLOAT p0;
  POINTFLOAT p1;
  POINTFLOAT p2;
  POINTFLOAT p3;

  p0.x = cur.x + b_perp.x * w;
  p0.y = cur.y + b_perp.y * w;

  p1.x = cur.x - b_perp.x * w;
  p1.y = cur.y - b_perp.y * w;

  p2.x = nxt.x + b_perp.x * w;
  p2.y = nxt.y + b_perp.y * w;

  p3.x = nxt.x - b_perp.x * w;
  p3.y = nxt.y - b_perp.y * w;

  OutlineVec.push_back(p0.x);
  OutlineVec.push_back(p0.y);
  OutlineVec.push_back(p1.x);
  OutlineVec.push_back(p1.y);
  OutlineVec.push_back(p2.x);
  OutlineVec.push_back(p2.y);

  OutlineVec.push_back(p2.x);
  OutlineVec.push_back(p2.y);
  OutlineVec.push_back(p1.x);
  OutlineVec.push_back(p1.y);
  OutlineVec.push_back(p3.x);
  OutlineVec.push_back(p3.y);



  // only do joins when we have a prv
  if( i == 0 ) continue;


  POINTFLOAT prv;
  prv.x = input[i-1].point[0];
  prv.y = input[i-1].point[1];

  POINTFLOAT a;
  a.x = prv.x - cur.x;
  a.y = prv.y - cur.y;

  a = normalize(a);

  POINTFLOAT a_perp;
  a_perp.x = a.y;
  a_perp.y = -a.x;

  float det = a.x * b.y  - b.x * a.y;
  if( det > 0 )
  {
   a_perp.x = -a_perp.x;
   a_perp.y = -a_perp.y;

   b_perp.x = -b_perp.x;
   b_perp.y = -b_perp.y;
  }

  // TODO: do inner miter calculation

  // flip around normals and calculate round join points
  a_perp.x = -a_perp.x;
  a_perp.y = -a_perp.y;

  b_perp.x = -b_perp.x;
  b_perp.y = -b_perp.y;

  size_t num_pts = 16;

  std::vector< POINTFLOAT> round( 1 + num_pts + 1 );
  POINTFLOAT nc;
  nc.x = cur.x + (a_perp.x * w);
  nc.y = cur.y + (a_perp.y * w);

  round.front() = nc;

  nc.x = cur.x + (b_perp.x * w);
  nc.y = cur.y + (b_perp.y * w);

  round.back() = nc;

  for( size_t j = 1; j < num_pts+1; ++j )
  {
   float t = (float)j/(float)(num_pts+1);
   if( det > 0 )
   {
    POINTFLOAT nin;
    nin = slerp2d( b_perp, a_perp, 1.0f-t );
    nin.x *= w;
    nin.y *= w;

    nin.x += cur.x;
    nin.y += cur.y;

    round[j] = nin;
   }
   else
   {
    POINTFLOAT nin;
    nin = slerp2d( a_perp, b_perp, t );
    nin.x *= w;
    nin.y *= w;

    nin.x += cur.x;
    nin.y += cur.y;

    round[j] = nin;
   }
  }

  for( size_t j = 0; j < round.size()-1; ++j )
  {

   OutlineVec.push_back(cur.x);
   OutlineVec.push_back(cur.y);


   if( det > 0 )
   {
    OutlineVec.push_back(round[j + 1].x);
    OutlineVec.push_back(round[j + 1].y);
    OutlineVec.push_back(round[j].x);
    OutlineVec.push_back(round[j].y);
   }
   else
   {

    OutlineVec.push_back(round[j].x);
    OutlineVec.push_back(round[j].y);

    OutlineVec.push_back(round[j + 1].x);
    OutlineVec.push_back(round[j + 1].y);
   }
  }
 }

}

    POINTFLOAT multiply(const POINTFLOAT &a, float b)
    {
     POINTFLOAT result;
     result.x = a.x * b;
     result.y = a.y * b;
     return result;
    }

    POINTFLOAT normalize(const POINTFLOAT &a)
    {
     return multiply(a, 1.0f/sqrt(a.x*a.x+a.y*a.y));
    }


    POINTFLOAT slerp2d( const POINTFLOAT &v0, 
           const POINTFLOAT &v1, float t )
    {
     float dot = (v0.x * v1.x + v0.y * v1.y);

     if( dot < -1.0f ) dot = -1.0f;
     if( dot > 1.0f ) dot = 1.0f;

     float theta_0 = acos( dot );
     float theta = theta_0 * t;

     POINTFLOAT v2;
     v2.x = -v0.y;
     v2.y = v0.x;

     POINTFLOAT result;
     result.x = v0.x * cos(theta) + v2.x * sin(theta);
     result.y = v0.y * cos(theta) + v2.y * sin(theta);

     return result;
    }

There is a comment saying that inner miter calculation should be performed but I'm not sure what this is or how it should be done. Right now this algorithm produces round edges but I'd like to modify it to make miter edges (square) instead, how could this be done? Does it involve inner miter calculation?

Thanks

Answer 1

The code puts rounded corners (mitres) on polygon outlines, but only on the outside edge.

If you can conceptualize the outline of a square as a big, black box with a smaller white box nestled inside it, this code will round the edges of the black box, but not the white one
_{(This is just a thought exercise, the code doesn't actually work like this)}

That's what all that slerp stuff is; it's interpolating between the directions perpendicular to the first edge and the second edge, and adding points along the arc.

The comment is suggesting that somebody should do the same to the interior corners.

Answer 2

Try this modification to my other answer:

// v0 and v1 are normalized
// t can vary between 0 and 1
// http://number-none.com/product/Understanding%20Slerp,%20Then%20Not%20Using%20It/
Vector2f slerp2d( const Vector2f& v0, const Vector2f& v1, float t )
{
    float dot = v0.dot(v1);
    if( dot < -1.0f ) dot = -1.0f;
    if( dot > 1.0f ) dot = 1.0f;

    float theta_0 = acos( dot );
    float theta = theta_0 * t;

    Vector2f v2( -v0.y(), v0.x() );

    return ( v0*cos(theta) + v2*sin(theta) );
}


void glPolyline( const vector<Vector2f>& polyline, float width )
{
    if( polyline.size() < 2 ) return;
    float w = width / 2.0f;

    glBegin(GL_TRIANGLES);
    for( size_t i = 0; i < polyline.size()-1; ++i )
    {
        const Vector2f& cur = polyline[ i ];
        const Vector2f& nxt = polyline[i+1];

        Vector2f b = (nxt - cur).normalized();
        Vector2f b_perp( -b.y(), b.x() );

        Vector2f p0( cur + b_perp*w );
        Vector2f p1( cur - b_perp*w );
        Vector2f p2( nxt + b_perp*w );
        Vector2f p3( nxt - b_perp*w );

        // first triangle
        glVertex2fv( p0.data() );
        glVertex2fv( p1.data() );
        glVertex2fv( p2.data() );
        // second triangle
        glVertex2fv( p2.data() );
        glVertex2fv( p1.data() );
        glVertex2fv( p3.data() );

        // only do joins when we have a prv
        if( i == 0 ) continue;

        const Vector2f& prv = polyline[i-1];
        Vector2f a = (prv - cur).normalized();
        Vector2f a_perp( a.y(), -a.x() );

        float det = a.x()*b.y() - b.x()*a.y();
        if( det > 0 )
        {
            a_perp = -a_perp;
            b_perp = -b_perp;
        }

        // TODO: do inner miter calculation

        // flip around normals and calculate round join points
        a_perp = -a_perp;
        b_perp = -b_perp;

        size_t num_pts = 1;
        vector< Vector2f > round( 1 + num_pts + 1 );
        for( size_t j = 0; j <= num_pts+1; ++j )
        {
            float t = (float)j/(float)(num_pts+1);
            if( det > 0 )
                round[j] = cur + (slerp2d( b_perp, a_perp, 1.0f-t ) * w);
            else
                round[j] = cur + (slerp2d( a_perp, b_perp, t ) * w);
        }

        ///////////////////////
        // new outer miter code
        float theta = acos( a.dot(b) ) / 2.0;
        float val = w / tan( theta );
        float miter_length = sqrt( w*w + val*val );
        Vector2f miter = ((a_perp+b_perp)*0.5).normalized() * miter_length;

        round[1] = cur + miter;
        // end new outer miter code
        ///////////////////////

        for( size_t j = 0; j < round.size()-1; ++j )
        {
            glVertex2fv( cur.data() );
            if( det > 0 )
            {
                glVertex2fv( round[j+1].data() );
                glVertex2fv( round[j+0].data() );
            }
            else
            {
                glVertex2fv( round[j+0].data() );
                glVertex2fv( round[j+1].data() );
            }
        }
    }
    glEnd();
}