# yet another seperating axis thread

## Recommended Posts

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 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 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 on other sites
Quote:
 Original post by homojediCalculating 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 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 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 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

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627636
• Total Posts
2978331

• 10
• 12
• 22
• 13
• 33