Jump to content
  • Advertisement
Sign in to follow this  
Cornstalks

Polycolly's great and all...but I'm lost

This topic is 4463 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've searched the forums for SAT documents, and everyone recommends Polycolly (by olii...or however you spell it). Anyways, I downloaded it and I've looked through the code, the applications, and the documents. I'm disappointed though that the documents didn't really explain what was going on in the code. I understand the SAT, but its implementing the projection I'm having trouble with, and I'll explain why. Areas I don't get I'll mark with // NUMBER)*************************** (they are mainly in the second function) In Polycolly[Polygon.cpp]
bool PolyColl::Collide(const Vector* A, int Anum, 
					   const Vector* B, int Bnum, 
					   const Vector& xOffset)
{
	if (!A || !B) return false;
 
	// All the separation axes
	Vector xAxis[64]; // note : a maximum of 32 vertices per poly is supported
	int    iNumAxes=0;
 
	// test separation axes of A
	for(int j = Anum-1, i = 0; i < Anum; j = i, i ++)
	{
		Vector E0 = A[j];
		Vector E1 = A;
		Vector E  = E1 - E0;
		xAxis[iNumAxes] = Vector(-E.y, E.x);
 
		if (!IntervalIntersect(	A, Anum, 
								B, Bnum, 
								xAxis[iNumAxes], 
								xOffset))
		{
			return false;
		}

		iNumAxes++;
	}

	// test separation axes of B
	for(int j = Bnum-1, i = 0; i < Bnum; j = i, i ++)
	{
		Vector E0 = B[j];
		Vector E1 = B;
		Vector E  = E1 - E0;
		xAxis[iNumAxes] = Vector(-E.y, E.x);

		if (!IntervalIntersect(	A, Anum, 
								B, Bnum, 
								xAxis[iNumAxes], 
								xOffset))
		{
			return false;
		}

		iNumAxes++;
	}

	return true;
}
 
// calculate the projection range of a polygon along an axis
void GetInterval(const Vector *axVertices, int iNumVertices, const Vector& xAxis, float& min, float& max)
{
	min = max = (axVertices[0] * xAxis); // 1)***************************

	for(int i = 1; i < iNumVertices; i ++)
	{
		float d = (axVertices * xAxis); // 1)***************************
		if (d < min) min = d; else if (d > max) max = d;
	}
}
 
bool IntervalIntersect(const Vector* A, int Anum,
					   const Vector* B, int Bnum,
					   const Vector& xAxis, 
					   const Vector& xOffset)
{
	float min0, max0;
	float min1, max1;
	GetInterval(A, Anum, xAxis, min0, max0);
	GetInterval(B, Bnum, xAxis, min1, max1);

	float h = xOffset * xAxis; // 2)***************************
	min0 += h;
	max0 += h;

	float d0 = min0 - max1; 
	float d1 = min1 - max0; 

	if (d0 > 0.0f || d1 > 0.0f) 
	{
		return false;
	}
	else
	{
		return true;
	}
}

I understand most of it, except for the multiplication of the vertex and the axis. I know that you would use the dot product to project a vertex onto the axis, but in [Vector.h] it states this in the Vector class: inline float operator * (const Vector &V) const { return (x*V.x) + (y*V.y); } // dot product But every other place I go it shows the dot product to be |A||B|cos(theta) I don't understand how (A.x*B.x + A.y*B.y) is the same as |A||B|cos(theta), and if it is, then why do people write |A||B|cos(theta) and not (A.x*B.x + A.y*B.y). If you could please explain how and why this works, I would appreciate it a lot. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by MikeTacular
But every other place I go it shows the dot product to be |A||B|cos(theta) I don't understand how (A.x*B.x + A.y*B.y) is the same as |A||B|cos(theta), and if it is, then why do people write |A||B|cos(theta) and not (A.x*B.x + A.y*B.y). If you could please explain how and why this works, I would appreciate it a lot. Thanks.

The two statements are equivalent. They are both the dot product of two vectors A and B. The first is the way dot product (aka scalar product) is defined - you multiply the first component of both vectors, then the next, etc. and add all the products together. The second statement is just another interpretation of a dot product, namely the geometric interpretation. I think this article explains it very clearly.

As far as the rest of it goes, I'm not too sure because I haven't gotten to learning all about Polycolly yet, but I am certainly looking forward to it when the time allows. I've missed so much in the last few years. >.<

Share this post


Link to post
Share on other sites
Oh, thank you very much for that article. I finally understand it. I don't get exactly why people use the geometric interpretation, but I'm sure it has it's uses. Thank you.

Share this post


Link to post
Share on other sites
both interpretation are useful.

For example, if you want to know the angle between two segments, you can use ...

A . B = Ax * Bx + Ay * By = |A| * |B| * cos(angle(A, B))

=> cos(angle(A, B)) = (Ax * Bx + Ay * By) / (|A| * |B|)
=> (+/-) angle(A, B) = arccos((Ax * Bx + Ay * By) / (|A| * |B|))

the sign of the angle is undefined. Basically, arccos() is in the range (0, Pi).

similarly, to get the angle in range (0, 2*Pi), you can do

tan(angle(A, B)) = sin(angle(A, B)) / cos(angle(A, B))
sin(angle(A, B)) = A x B / (|A| * |B|) = (Ay * Bx - Ax * By) / (|A| * |B|)
cos(angle(A, B)) = (Ax * Bx + Ay * By) / (|A| * |B|)
=> tan(angle(A, B)) = (Ay * Bx - Ax * By) / (Ax * Bx + Ay * By)
=> angle(A, B) = atan2((Ay * Bx - Ax * By), (Ax * Bx + Ay * By))

atan2, this times, returns the angle in range (0, 2 * Pi), well, (-Pi, Pi) to be precise, but it's the same thing. It checks the signes of both parameters.

BTW, This is the standard SAT intersection test. For the continuous part, the code and algorithm is deprectated (meaning, there is something better).

I'm still suppose to write a final version, but I feel kinda lazy :/ I may have a go at the weekend. It will be probably in the form of a series of posts with attached code and pics in my a new thread, right here on Gamedev. It should take me 2, 3 hours, I just need to get started [grin].

Share this post


Link to post
Share on other sites
Quote:

I don't understand how (A.x*B.x + A.y*B.y) is the same as |A||B|cos(theta)


A proof:

http://mathworld.wolfram.com/DotProduct.html

The first part of any proof starts with a definition of what you want, because it's useful for something. In this case, the definition is this:

"It follows immediately that X.Y==0 if X is perpendicular to Y. The dot product therefore has the geometric interpretation as the length of the projection of X onto the unit vector Y^^ when the two vectors are placed so that their tails coincide."

Following from that, they get into how the dotproduct works.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!