Help with Separating Axis Theorem
Posted: Thu Mar 04, 2010 9:56 pm
So, like many others, I've recently become interested in the separating axis theorem and have decided to attempt to implement it. I've caught somewhat of a snag and need some algorithm assistance. I'll try to provide all of the necessary information.
Screenshot of current version in action:
The yellow lines are the projections, they are constantly changing size while the polygon rotates, but completely incorrectly. Notice they are all the same size for some reason.
vertices contains the vertex information for the polygon in coordinates relative to the origin (when rendering the viewport is translated and rotated to display the polygon correctly, but the vertices' values always remain the same).
axes[] and proj[] are both arrays of 5 vector pointers (the test polygon has 5 sides).
the last two lines of code [hopefully] populate the projection (proj) vector with the min and max values of the projection of the polygon onto the corresponding potential axis of separation, in effect using the vector as a point.
This is the draw code for the projections.
The drawn lines of projection do not correctly correspond to the correct projection of the polygon onto each axis, and seem to act somewhat sporadically. If anyone sees anything drastically wrong with how I'm finding the min and max values of the final projection I'd appreciate you letting me know.
If you need any more information to help me out, please let me know.
Screenshot of current version in action:
The yellow lines are the projections, they are constantly changing size while the polygon rotates, but completely incorrectly. Notice they are all the same size for some reason.
Code: Select all
int verticesSize = pos->bbox->vertices.size();
//Angle of rotation in radians
float theta = (rot->zRot) * PI / 180.0f;
//Angle + 90 degrees (right-hand perproduct)
float rperp = theta + (PI / 2.0f);
Vector2 side;
Vector2 perp;
for( int i = 0; i < verticesSize; i++ ){
//Get side vector
if( i == verticesSize - 1 ){
side.x = pos->bbox->vertices[0]->x - pos->bbox->vertices[i]->x;
side.y = pos->bbox->vertices[0]->y - pos->bbox->vertices[i]->y;
}else{
side.x = pos->bbox->vertices[i+1]->x - pos->bbox->vertices[i]->x;
side.y = pos->bbox->vertices[i+1]->y - pos->bbox->vertices[i]->y;
}
//Calculate right-hand perproduct (with rotation)
perp.x = cos(rperp) * (side.x) - sin(rperp) * (side.y);
perp.y = sin(rperp) * (side.x) + cos(rperp) * (side.y);
//Normalize vector
perp.Normalize();
//Store axis
*axes[i] = perp;
//Dot product
float dp;
//Endpoints of projection
Vector2 min;
Vector2 max;
Vector2 temp;
for( int j = 0; j < verticesSize; j++ ){
//Calculate dot product
dp = (pos->bbox->vertices[j]->x * axes[j]->x + pos->bbox->vertices[j]->y * axes[j]->y);
//Populate min / max on first iteration
if( j == 0 ){
min.x = dp * axes[j]->x;
min.y = dp * axes[j]->y;
max = min;
}else{
temp.x = dp / axes[j]->x;
temp.y = dp / axes[j]->y;
if( temp.x < min.x ){
min = temp;
}else if( temp.x > max.x ){
max = temp;
}
}
}
//Get projection vector from min / max
proj[i]->x = max.x - min.x;
proj[i]->y = max.y - min.y;
}
axes[] and proj[] are both arrays of 5 vector pointers (the test polygon has 5 sides).
the last two lines of code [hopefully] populate the projection (proj) vector with the min and max values of the projection of the polygon onto the corresponding potential axis of separation, in effect using the vector as a point.
Code: Select all
glBegin(GL_LINES);
glVertex3f( col->proj[i]->x, 0, 0);
glVertex3f( col->proj[i]->y, 0, 0 );
glEnd();
The drawn lines of projection do not correctly correspond to the correct projection of the polygon onto each axis, and seem to act somewhat sporadically. If anyone sees anything drastically wrong with how I'm finding the min and max values of the final projection I'd appreciate you letting me know.
If you need any more information to help me out, please let me know.
