Help with Separating Axis Theorem

[dandymcgee]

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.

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;

		}

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.

Code: Select all

glBegin(GL_LINES);
	glVertex3f( col->proj[i]->x, 0, 0);
	glVertex3f( col->proj[i]->y, 0, 0 );
glEnd();

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.

[Falco Girgis]

Just wanted to let you know that I'm busy as all fuck now, but this issue has been added to my priority queue of things to address.

[dandymcgee]

Just wanted to let you know that I'm busy as all fuck now, but this issue has been added to my priority queue of things to address.

Sweet, appreciate it. I've been playing for hours with all kinds of different, yet still completely wrong, results.

[RyanPridgeon]

-snip-

[dandymcgee]

-snip-

??

[RyanPridgeon]

I said something but I realised I was wrong, so I -snip-'d it