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

This code is quite poor to read, why are there no functions to provide such basic vector services like addition and negating? There is a nice `multiply` function that is not even used to multiply. Also it looks like we're missing some of the values as well; where does `w` come from in the first snippet? — Ron Warholic, Jul 22 '10 at 02:54
[Some styles](http://www.opengl.org/resources/code/samples/sig99/advanced99/notes/node281.html). Do you want an outer miter or an outer bevel? — genpfault, Jul 22 '10 at 03:14

score 3 · Accepted Answer · edited May 23 '17 at 11:57

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();
}

Watch out though, miters look weird for steep angles since they tend to shoot off into infinity. — genpfault, Jul 22 '10 at 03:38

kibibu · Answer 2 · 2010-07-22T03:06:34.737

0

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.

edited Jul 22 '10 at 03:06

answered Jul 22 '10 at 03:00

kibibu

6,115
1
35
41

okay, what should I do to make square corners instead of round ones? – jmasterx Jul 22 '10 at 03:04
Leaving the code as is, change `size_t num_pts = 16;` to `size_t num_pts = 0;`, or better yet change the method to accept a (possibly default) parameter. `num_pts` is the number of points in the rounded bit. – kibibu Jul 22 '10 at 03:12
No that creates beveled edges not squaare – jmasterx Jul 22 '10 at 03:12
That'll give you a [bevel](http://www.opengl.org/resources/code/samples/sig99/advanced99/notes/node281.html), not a miter. – genpfault Jul 22 '10 at 03:14
1

Apologies, got the terms confused. In high-level, calculate the point where the edges intersect (as a point) and insert that instead of the rounded points. If you are only using non-degenerate triangles they are guaranteed to intersect. – kibibu Jul 22 '10 at 03:31
Thanks, :) but genpfaults answer was more what I was looking for – jmasterx Jul 22 '10 at 03:35

What is an inner miter calculation?

2 Answers2