Rounding the start and end of an outline

I use the following algorithm to generate polygon outlines:

void OGLSHAPE::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 = 4;

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

   开发者_C百科     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;
}

I noticed that vector drawing applications allow the ability to round the beginning and the end of a segment. How could I modify my line generation algorithm to round the beginning and the end of an unconnected segment?

See below for example of what I mean:

alt text http://img39.imageshack.us/img39/6029/capss.png

Thanks

Took me a while to understand how slerp2d() worked and I still might have it wrong but it strikes me that you could use the unit vector and it's perpendicular to round the ends, using them to draw the 2 halves of the hemispheres.

As long as the ends don't meet, use slerp2d(-b, b_perp, t); and slerp2d(-b, -b_perp, t); for the start (order of terms may need swapping) with slerp2d(b, b_perp, t); and slerp2d(b, -b_perp, t); for the end.

You could avoid calculating round.back() again, because this is still P0 (or P1 depending on determinate) and round.front() is the previous P2 or P3 which you have tucked away in OutlineVec. Calculating the inner mitre point might help with this because it'll remove the other points.

Edit
On second thought beziers won't be so useful because they will require you to add extra points, and then you need to differentiate which paths should be draw as a straight line and which should be draw as a curve.

In essence you need a function that has the following prototype:

void DrawRoundedRectangle(Rectangle rect, Angle angle);

My main point remains that the code that renders the coordinates for the rectangle does not need modification and that it's up to the rendering code to add any roundings.

I believe GDI+ is capable of doing this.

What platform are you developing for, and what library are you using, if I may ask? :)

Original post

The algorithm for generating the lines can stay mostly the same. It's the rendering code that needs to connect the dots as bezier curves instead of straight lines.

So you basically need a bezier rendering library. I've used GDI+ for this on Windows.

If you are using X/Motif, there's a field for this in the Graphics Context; I forget what it is, though, as it was a long time ago when I last used it.

I can't find anything worthwhile on the web, either. Sorry. The O'Reilly books have an excellent discussion of the point.