Sign in to follow this  

yet another seperating axis thread

This topic is 2851 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

to whomever read this, thank you for first taking your time to read this post even though there are plenty sources of information about this particular subject, i still have a hard time grasping the actual maths. The concept im fine with, it's the calculation's to actually implement it. so what going to happen is im going to give you my step by step account of how i understand your supposed to do it, and there are gaps in my knowledge and understanding and hopefully someone can help fill those voids. So..... Step One: determine the separating axis you wish to test along: from what i understand your supposed to take an edge of the shape find its difference hence giving you just the one vector turn it into a unit vector, then find the normal. that normal is the the separating axis. so for example I have two points A and B A( 5,10 ) & B( 8,6 ). so find the difference you get V( 3,-4 ). from my understanding that is basically like taking A and placing it at the origin 0,0 while keeping the original length exactly the same which then gives you ( 3,-4 ). then turn it into a unit vector, i should end up with U( 0.6, -0.8 ) and then find the normal, which i understand depends on whether your going clockwise or anti clockwise, but on further thought shouldent matter which direction you get the normal in as your testing along it. so this should then give me N( 0.8, 0.6 ), and that's all the information I've got so far on that. Step Two: project onto the axis and find the max and min value. this took me a while as i was looking at vector projection rather than scaler projection, and from there i found to do scaler projection the equation whittles down to A.Unitvector gives you the projection of A along that unit vector so from there you take every point of your two objects project onto this unit vector take the maximum and minimum values projected onto the axis from each object your testing on, so you should end up with minA, maxA, minB, maxB, then you find out between the point's, which is the lowest on the axis and which is the highest,which will give you their distance apart. Then you find the difference between the shapes distance apart and their combined length on that axis, if its negative. they are overlapping. okay now for some pseudo code of each step step one
bool findAxisToTestAlongAndTest( polygon *poly, polygon *otherPoly )
{
     for every point in the polygon
     {
       vector vec = poly[i+1] - poly[i];
       vector unitVec = sqrt(vec.x * vec.x + vec.y * vec.y);
       vector Normal;
       normal.x = unitVec.x * 0 + unitVec.y * -1;
       normal.y = unitVec.x * 1 + unitVec.y *  0;

       if(!projectPolygons( Normal, poly, otherPoly ))
       break;

       if(last point in polyogn test returns true)
        return true;       
     }

return false;
}


step two project polygons and find the minimums and the maximums
bool projectPolygons( Vector N, polygon *p, polygon *oP )
{
    float minP,maxP
    float minOP, maxOP
    float referenceValueP = dotProduct( N,p[0] )
    float referenceValueOP = dotProduct( N,oP[0] )
    minP = maxP = referenceValueP
    minOP = maxOP = referenceValueOP 

    for every point in p
    {
       referenceValueP = dotProduct( N,p[i] )

      if reference value is less than minP
      minP = reference value
      else
      if reference value is greater than maxP
      maxP = referenceValue
    }

    and the same for the other polygon. 

    return checkIntervals( min and max points )
}


find out if they are intersecting
bool checkIntervals(minP,maxP,minOP,maxOP)
{ 
   float a,b
   float sumLengths = (maxP - minP) + (maxOP - minOP)
   if minP < minOP
      a = minP
   else
      a = minOP

   if maxP > maxOP
      b = maxP
   else
      b = maxOP

   float distance = a + b; 

   if distance - sumLengths < 0
   return true;

return false
}


phew that took a while and im sorry if its a bit chunky and the code is a bit hacky, any optimizations and of course corrections are highley appreciated i just need to get it off my chest and hopefully ive got it down.

Share this post


Link to post
Share on other sites
oh my, i dont seem to have gotten many replies, i assume its cause the segment is a tad too chunky and crowded in some of the paragraph's. okay let me break it off into this question which is step one.

Calculating the separating axis, is that part at least correct? cause what is confusing me slightly is i get the unit vector normal of an edge which in my example is N( 0.8,0.6 ) which essentially give me a direction or an axis, and from there do you just dot product things against that to get its projection along it? I suppose whats confusing me is the unit vector normal itself, i know it's representative as a direction only but without an actual magnitude or length how do you project along it since it's so small? Do you extrapolate it? or when you dot product against it, do the points be scaled accordingly?

UPDATE:
Hello all, I just ran a quick and dirty simulation for an answer to my last question on finding the actual separating axis and thus far it seems to indicate that when you dot product against the unit vector normal it scales it accordingly, giving you the a value along that axis. awesome

[Edited by - homojedi on February 21, 2010 3:00:34 AM]

Share this post


Link to post
Share on other sites
so far so good, but I'm not sure what you are trying to achieve in your checkIntervals() function.

If you have two intervals [mina, maxa] and [minb, maxb], the intervals overlap is mina is < maxb and maxa > minb.

Or in other words, they do not overlap is maxa < minb or mina > maxb.

Quote:

bool checkIntervals(minP,maxP,minOP,maxOP)
{
return (minP < maxOP && maxP > minOP);
}


Also, normalising is not necessary. Not normalising means that the minP, maxP and minOP and maxOP are all scaled by the axis length, and that doesn't affect the checkIntervals() test (distributivity of a multiplication).

Your normal calculation is correct, normal(x, y) = vector(-y, x) or vector(y, -x) depending on your coordinate system. As you say, whichever vector you choose has no impact on the algorithm.

Share this post


Link to post
Share on other sites
Quote:
Original post by homojedi
Calculating the separating axis, is that part at least correct?


yes.

Quote:
cause what is confusing me slightly is i get the unit vector normal of an edge which in my example is N( 0.8,0.6 ) which essentially give me a direction or an axis, and from there do you just dot product things against that to get its projection along it?


yes. Doing the projection onto a normalised direction is similar to squashing your shape onto that direction. Shadows are just that, the projection of a shape in 3 dimensions onto a surface in 2 dimensions, so you loose some information about the depth information.

Quote:
I suppose whats confusing me is the unit vector normal itself, i know it's representative as a direction only but without an actual magnitude or length how do you project along it since it's so small?


small or big doesn't matter. Vectors can represent positions in space (or a plane in 2D), and directions. To differentiate between a position and direction vector in 2D, you need a 3D representation. [x y 1] would represent a position in the (X, Y) plane, [x y 0] would represent a direction vector in the (X, Y) plane.


Quote:
Do you extrapolate it? or when you dot product against it, do the points be scaled accordingly?


You just dot product. If you have direction vector 'm' and decompose it into a normal vector 'n' and a length 'd', where m = n * d.

You do the dot product of a vector 'v 'against 'm', and you will get (v . m) = (v . n) * d. So basically, the dot product with a non-normalised vector is the same as a dot-product with a normalised vector n, but your result will be scaled by the length of that vector.

Quote:
UPDATE:
Hello all, I just ran a quick and dirty simulation for an answer to my last question on finding the actual separating axis and thus far it seems to indicate that when you dot product against the unit vector normal it scales it accordingly, giving you the a value along that axis. awesome
.

yes :) If you want to find out the mtd vector (minimum translation distance), or basically the direction and distance of intersection between the two objects, you will need to calculate the amount of overlap between all your [minP, maxP]-[minOP, maxOP] intervals for every axis, and take the minimum of them all.

For that, if you do not normalise your projection axis, all your interval overlaps for each axis, will be scaled by their axis length. So either, you normalise your axis before projection (like you do), or you also cache the axis length along with each interval overlaps.

Share this post


Link to post
Share on other sites
Hey oliii,
yeah i figured out the proper way to do a check intervals function this morning before work somthing like


float checkIntervals( minP,maxP,minOP,maxOP)
{
if( minP > minOP )
{
return minP - maxOP
}
else
{
return minOP - maxP;
}
}




and then take the sum of the polygons's lengths and find the difference if its negative you have an intersection on that plane.

and i dont know how to do the funny quote box so when you say.
"Also, normalising is not necessary. Not normalising means that the minP, maxP and minOP and maxOP are all scaled by the axis length, and that doesn't affect the checkIntervals() test (distributivity of a multiplication)."
i assume by normalizing you mean turning it into a unit vector? so from V(3,-4) to U(0.6,-0.8)
and yes i can see that for the test its just a scale and will not adversely affect the outcome. its just that following the equations, that

A.B = |A||B|cos theta
cos theta = A.B/|A||B|
therefore
A.uB = |A|cos theta

and |A| cos theta being the projection on the plane of B.

so i was just following the maths really, which i had to do to understand all this. one last thing about what you said about the mtd. i take it for every axis you test along once your done checking and there is an intersection you check to see if the current intersection is less than the previous one and if so use that, and by the end you have your mtd which is the minimum amount to seperate the polygons?

cheers

Share this post


Link to post
Share on other sites
yup.

It's also explained and demonstrated here.


edit : for formatting tags, you can 'edit' a post of someone else, and see the tags used (like [ s o u r c e ], [ c o d e ] and [ q u o t e ]).

Share this post


Link to post
Share on other sites
awesome, cheers oliii, and i had seen that sight but the concept i understood its just the nuts and bolts of it that make it work that i had trouble getting my head around.

cheers

Share this post


Link to post
Share on other sites

This topic is 2851 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this