Edges on polygon outlines not always correct
Requires Eigen as written, but the core operations should map easily to whatever vector class you're using.
// 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 = 4;
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);
}
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();
}
EDIT: Screenshots:
What about:
- Draw each line up to the inside of the corner
- Draw an extra line at each corner perpendicular to the angle of the corner
Like this:
alt text http://www.geekops.co.uk/photos/0000-00-02%20%28Forum%20images%29/CorrectAngleDrawing.png
Blue / red represent the two lines you're trying to connect. Dotted green is the extra one you add to smooth the corner. The image above shows the content would be clipped very slightly for sharp corners. If that's a problem, you could extend the two connecting lines further outwards and draw the extra line further out.
[Edit] I've spotted a flaw in my suggestion. You have some concave sections in there which won't work at all well. For those occasions you'll want to do something like drawing a chamfered edge instead:
alt text http://www.geekops.co.uk/photos/0000-00-02%20%28Forum%20images%29/CorrectAngleDrawing2.png
[Edit2] I've done a little debugging on the code I posted previously. The following should be of more use:
// PolygonOutlineGen.cpp : A small program to calculate 4-point polygons
// to surround an input polygon.
#include <vector>
#include <math.h>
#include <iostream>
#include <iomanip>
using namespace std;
// Describe some structures etc. so the code will compile without
// requiring the GL libraries.
typedef double GLdouble;
typedef float GLfloat;
typedef struct POINTFLOAT
{
float x;
float y;
} POINTFLOAT;
// A function to generate two coordinates representing the start and end
// of a line perpendicular to start/end, offset by 'width' units.
void GenerateOffsetLineCoords(
POINTFLOAT start,
POINTFLOAT end,
int width,
POINTFLOAT& perpStart,
POINTFLOAT& perpEnd)
{
float dirlen;
POINTFLOAT dir;
POINTFLOAT ndir;
POINTFLOAT nperp;
POINTFLOAT perpoffset;
// Work out the offset for a parallel line which is space outwards by 'width' units
dir.x = end.x - start.x;
dir.y = end.y - start.y;
dirlen = sqrt((dir.x * dir.x) + (dir.y * dir.y));
ndir.x = static_cast<float>(dir.x * 1.0 / dirlen);
ndir.y = static_cast<float>(dir.y * 1.0 / dirlen);
nperp.x = -ndir.y;
nperp.y = ndir.x;
perpoffset.x = static_cast<float>(nperp.x * width);
perpoffset.y = static_cast<float>(nperp.y * width);
// Calculate the offset coordinates for the new line
perpStart.x = start.x + perpoffset.x;
perpStart.y = start.y + perpoffset.y;
perpEnd.x = end.x + perpoffset.x;
perpEnd.y = end.y + perpoffset.y;
}
// Function to generate quads of coordinate pairs to surround the 'input'
// polygon.
void GenerateLinePoly(const std::vector<std::vector<GLdouble>> &input,
std::vector<GLfloat> &output, int width)
{
// Make sure we have something to produce an outline for and that it's not contaminated with previous results
output.clear();
if(input.size() < 2)
{
return;
}
// Storage for the pairs of lines which form sections of the outline
POINTFLOAT line1_start;
POINTFLOAT line1_end;
POINTFLOAT line2_start;
POINTFLOAT line2_end;
// Storage for the outer edges of the quads we'll be generating
POINTFLOAT line1offset_start;
POINTFLOAT line1offset_end;
POINTFLOAT line2offset_start;
POINTFLOAT line2offset_end;
// Storage for the line we'll use to make smooth joints between polygon sections.
POINTFLOAT joininglineoffset_start;
POINTFLOAT joininglineoffset_end;
for(unsigned int i = 0; i < input.size() - 2; ++i)
{
// Grab the raw line input for the first line or if we've already done one, just re-use the last results
if( i == 0 )
{
line1_start.x = static_cast<float>(input[i][0]);
line1_start.y = static_cast<float>(input[i][1]);
line1_end.x = static_cast<float>(input[i + 1][0]);
line1_end.y = static_cast<float>(input[i + 1][1]);
GenerateOffsetLineCoords(line1_start, line1_end, width, line1offset_start, line1offset_end);
}
else
{
line1_start = line2_start;
line1offset_start = line2offset_start;
line1_end = line2_end;
line1offset_end = line2offset_end;
}
// Grab the second line and work out the coords of it's offset
line2_start.x = static_cast<float>(input[i+1][0]);
line2_start.y = static_cast<float>(input[i+1][1]);
line2_end.x = static_cast<float>(input[i+2][0]);
line2_end.y = static_cast<float>(input[i+2][1]);
GenerateOffsetLineCoords(line2_start, line2_end, width, line2offset_start, line2offset_end);
// Grab the offset for the line which joins the open end
GenerateOffsetLineCoords(line2offset_start, line1offset_end, width, joininglineoffset_start, joininglineoffset_end);
// Push line 1 onto the output
output.push_back(line1_start.x);
output.push_back(line1_start.y);
output.push_back(line1_end.x);
output.push_back(line1_end.y);
output.push_back(line1offset_end.x);
output.push_back(line1offset_end.y);
output.push_back(line1offset_start.x);
output.push_back(line1offset_start.y);
// Push the new section onto the output
output.push_back(line1offset_end.x);
output.push_back(line1offset_end.y);
output.push_back(line2offset_start.x);
output.push_back(line2offset_start.y);
output.push_back(joininglineoffset_start.x);
output.push_back(joininglineoffset_start.y);
output.push_back(joininglineoffset_end.x);
output.push_back(joininglineoffset_end.y);
}
// TODO: Push the remaining line 2 on.
// TODO: Add one last joining piece between the end and the beginning.
}
int main(int argc, char* argv[])
{
// Describe some input data
std::vector<std::vector<GLdouble>> input;
std::vector<GLdouble> val1; val1.push_back(010.0); val1.push_back(010.0); input.push_back(val1);
std::vector<GLdouble> val2; val2.push_back(050.0); val2.push_back(100.0); input.push_back(val2);
std::vector<GLdouble> val3; val3.push_back(100.0); val3.push_back(100.0); input.push_back(val3);
std::vector<GLdouble> val4; val4.push_back(010.0); val4.push_back(010.0); input.push_back(val4);
// Generate the quads required to outline the shape
std::vector<GLfloat> output;
GenerateLinePoly(input, output, 5);
// Dump the output as pairs of coordinates, grouped into the quads they describe
cout << setiosflags(ios::fixed) << setprecision(1);
for(unsigned int i=0; i < output.size(); i++)
{
if( (i > 0) && ((i)%2==0) ) { cout << endl; }
if( (i > 0) && ((i)%8==0) ) { cout << endl; }
cout << setw(7) << output[i];
}
cout << endl;
return 0;
}
..which looks like it works for convex polygons as far as I can see :-)