Jump to content

  • Log In with Google      Sign In   
  • Create Account


Questions about Polygon Intersection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 L i n c k   Members   -  Reputation: 148

Like
0Likes
Like

Posted 29 April 2014 - 01:17 PM

Hi. I'm trying to implement polygon intersection using SAT (Separating Axis Algorithm). There is plenty of nice material on the internet, but there is one particular part of the algorithm that I couldn't understand.

 

Here are three of the articles I've been reading, just If you wanna take a glance to be sure what I'm talking about:

http://www.phailed.me/2011/02/polygonal-collision-detection/

http://www.codezealot.org/archives/55

http://www.sevenson.com.au/actionscript/sat/

 

The part I don't understand, is the projection part. You have a normal vector pointing outwards, perpendicular to each edge, and based on that normal, you have to project the shadow of the polygon. But when I read these articles, this shadow seems to be represented by only two values, a min and a max value. This is the part I don't understand.

 

To clarify. This is an Image of a projection from the third article:

 

step2.jpg

 

 

This magenta line is the line I understand is the projection, or the shadow. But how can It be represented by two values? the min an the max? This is a line, and a line as far as I know can only be represented by two points, that is, four values: x1, y1, x2, y2.

 

So my question is, how is this projection represented by two values and not two points?


Edited by L i n c k, 29 April 2014 - 01:17 PM.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 11972

Like
0Likes
Like

Posted 29 April 2014 - 01:54 PM

The two values don't represent the line: They represent the two pink dots in some coordinate system for points in the line. Since the line is a 1D object, you only need one number per dot.



#3 L i n c k   Members   -  Reputation: 148

Like
0Likes
Like

Posted 30 April 2014 - 07:18 AM

So these values represent like a magnitude of the axis vector? As if the the axis vector would be transformed in a vector that would go to the first pink dot, and than in another vector that would go to the second one, and the two numbers are the magnitude of both vectors?

 

I have already Implemented my SAT in my code and it's working, but I made It looking to the tutorial codes and not fully understanding. So in my code the values of min and max come as for instance "-338578" and "49700". Really high numbers, and I don't understand why. My shapes are no more than 700 pixels in size.


Edited by L i n c k, 30 April 2014 - 07:33 AM.


#4 Álvaro   Crossbones+   -  Reputation: 11972

Like
0Likes
Like

Posted 30 April 2014 - 07:58 AM

Those values are probably obtained by taking the dot product between a vector along the line you are projecting on and the vector from some reference point (the origin?) to a vertex. You probably started by computing the normal vector to an edge by reversing the coordinates of the edge and flipping one sign. If you normalize that vector (divide it by its length, so it has length 1), the resulting values from the dot product will be in pixels, and you won't get the large numbers you are seeing.



#5 L i n c k   Members   -  Reputation: 148

Like
0Likes
Like

Posted 30 April 2014 - 09:27 AM

The numbers are correct now. Thanks. Actually, I was thinking that I was already normalizing my axis vector, but then I looked again at this part, and I realized I was calling a method to normalize the vector, but the method was returning another vector, and not normalizing the vector that was calling. Just a simple mistake.

 

Thank you for your answers. I think I fully understand the concept and the code now.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS