AS3: Seperating Axis Theorem

[crucifix]

I have been reading through some tutorial and i dont know how to get my SAT test to work. I will post up a zip, can anyone help me?

[dandylion13]

Hi,

Which tutorial have you been reading?

[crucifix]

The N Tutorials, sorry i forgot to mention it.

[Favardin]

Haven't got the time to look into your code right now, but a common mistake is that people forget to project onto the perpendicular vector of a polygon's side (i.e. this side's normal vector). Also, if you are calculating a push vector, keep in mind that this normal vector must be normalized (have length 1), otherwise the distance will be skewed.

[dandylion13]

Hey Crucifix.. unfortunately those tutorials are very general (which can be a good thing sometimes!) but you're pretty much on your own figuring out how to transfer the concepts to code. Unless you've got the time to reverse engineer the source code (which is in AS1.0 and quite a mess!), some of the details regarding the vector math won't be that obvious. Sorry, I also haven't had time to check your source code. I don't know of any better tutorials at the moment unfotunately.. maybe someone else reading this can help out.

But, as a gerneral approach.. if you're able to figure out the the y and x overlap ("projection"), as well as the dx and dy, you can then use that information with a bit of vector math to create the physical reaction.

One VERY important thing... those tutorials are based on physics using Verlet integration. If you're using Euler integration (which most of us do for game design) you're going to have transfer some of the approaches so that they work. SAT works just fine with Euler but you'll have to do a bit of trial and error with the code. Let me know if you need more info on the Euler vs. Verlet systems

Also, SAT is really not that hard once you get around the basic concepts so I'm sure you'll figure it out! :) You seem like a pretty good coder and it's actually much easier than some of the other things I've seen you working on, and it's easier than the n tutorials and source code make it look. I wish I could post some more specifics but I'm a bit swamped at the moment :(

[crucifix]

Thanks guys. I have the basic understanding of this stuff and i have a fully working dot product generator. This is so i can find the distance between two 2d points in a 1d variable along an axis i define. As i gather it when you test the axis' of your polygon you do this and see if it is less the 0. What i need to know is what the delta x and delta y in my code is. I though it was the distance bettween the center of my two squares but it doesnt seem to work. So if anyone knows what these are, i would very much appreciate it.

[dandylion13]

Strange, it should work. What you're doing sounds right. Yes, that's how you calculate the dx and dy.

[crucifix]

well can you please look at my code to see what im doing wrong. I know this is a big ask but i have looked all over the net and this is the best i can do. Thanks very very much if you have the time :D

[dandylion13]

Hi :)

I don't understand this bit of code:

ActionScript Code:

asize = boxA.width / 2;;
bsize = ProjectBox(boxB, axis_x, axis_y);
dsize = Math.abs(deltax * axis_x + deltay * axis_y);

var penAx = (asize + bsize) - dsize;




The problem I have is with "bsize". Shouldn't it simply be:

ActionScript Code:

bsize = boxB.width / 2;



?

I don't understand why you're caclulating the projection before you've tested for the collision?

Don't worry though, I'm pretty slow with these things so I'm sure your code makes sense :) I've just never seen that before so I'm having trouble understanding it.

[crucifix]

I dont think this is the problem, please this would be much appriciated.

[crucifix]

Does anyone know what to do?

[crucifix]

Ill put up a less confusing example. I have done the aabb against aabb collsion already. Ill put this is the zip aswell.

[crucifix]

Well if noone knows. Can someone explain how to determine veroni Regions and how to determine them in AS3

[crucifix]

Anyone?

[crucifix]

**bump**

[crucifix]

Seriously. How do you determine the axis' and veroni regions dynamicly. Ie for rotating objects and rotate to surface type things.

[crucifix]

Ok so ive decided to store the vetices in an array. And then i think i will be able to do it form there but i need to know how to determine veroni regions and such? if anyone has any idea. that would be aweseom

[Favardin]

Ok so ive decided to store the vetices in an array. And then i think i will be able to do it form there but i need to know how to determine veroni regions and such? if anyone has any idea. that would be aweseom

You probably don't need Voronoi-regions. Determining the closest feature of a polgony to a point by brute-force will be fast enough in almost all cases. In any case: the Voronoi-region of a side can be drawn by adding to rays at the corners, shooting outwards perpendicular to it. If you do this for every side, the remaining regions all belong to the closest corner (try it with pen & paper, then formulate it in mathematical terms and you'll have it).

[crucifix]

Ok ill try that.

[crucifix]

Is there a fast way to determine these othere then testing every axis because i choose this technique for its speed?

[crucifix]

Here is a SWF if my veronoi region test. How would i go about determining which zone a point or axis was in or closest too.

[crucifix]

Now i know where the regions are how do i test to see if a point or axes is in them..?

[crucifix]

**BUMP**

[crucifix]

*bump* please i really need to know how to do this

[Favardin]

Would you please stop spamming?

First of all: yes, you have to go through all edges and test their axises. There are some possible ways to speed that up, but you should probably first get it right before you start thinking about speed issues -- you will probably not run into any.

Now, on to the Voronoi regions. First of all, I assume you know how to handle vector projections. Now, instead of determining the regions we will simply determine the closest feature of the polygon (I assume that is what you need). Given a point, it is pretty easy to calculate the distance to the vertices of the polygon, so the main difficulty should be determining the distance to the edges.

I will write vectors bold in the following, AB denotes the vector from point A to point B (that is: AB = B-A if we take the position vectors of A and B).
Let's say we have an edge [E,F] from vertice E to F (and thus the vector EF) and a point P. To calculate the distance, we first take the Vector EP and project it onto EF and call that projected vector EP'. Imagine the difference vector EP-EP': it points from the edge [E,F] perpendicularly to P -- thus we simply have to take the length of EP-EP' and we're done.

In short: d = | EP-(EP proj. on EF)|
(Might contains typos, so check it).

[crucifix]

Could you show me an example i am trying to hittest Polygon against Polygon.

[crucifix]

Like an Fla so i can fiddle around and learn it first hand

[crucifix]

*fla*

[dimumurray]

What format are your FLAs in? I can't seem to open them in Flash 9/CS3.

[crucifix]

cs4