Trouble with SAT style vector projection in C#/XNA

Question

Simply put I'm having a hard time working out how to work with XNA's Vector2 types while maintaining spatial considerations. I'm working with separating axis theorem and trying to project vectors onto an arbitrary axis to check if those projections overlap, but the severe lack of XNA-specific help online combined with pseudo code everywhere that omits key parts of the algorithm, googling has left me little help.

I'm aware of HOW to project a vector, but the way that I know of doing it involves the two vectors starting from the same point. Particularly here:

http://www.metanetsoftware.com/technique/tutorialA.html

So let's say I have a simple rectangle, and I store each of its corners in a list of Vector2s. How would I go about projecting that onto an arbitrary axis? The crux of my problem is that taking the dot product of say, a vector2 of (1, 0) and a vector2 of (50, 50) won't get me the dot product I'm looking for.. or will it? Because that (50, 50) won't be the vector of the polygon's vertex but from whatever XNA calculates. It's getting the calculation from the right starting point that's throwing me off.

I'm sorry if this is unclear, but my brain is fried from trying to think about this. I need a better understanding of how XNA calculates Vector2s as actual vectors and not just as random points.

Answer 1

Here is the theory you need:

A Vector2 is nothing but an X coordinate and a Y coordinate. It can represent either a position - OR - a direction and a magnitude (aka: a "length"). If the magnitude is 1, then you have a "normal" (a "normalized vector" or "unit vector" - which represents only a direction).

I think what is making you unstuck here is you might be trying to use only a single vector to represents concepts/data that require two vectors to express: A "line" is two positions. A "ray" is a starting position and a direction.

Finally, I'm pretty sure that the vector that you are projecting onto must be normalized (of unit length) for the algorithm to work.

So, using this information:

Take one of the edges of your polygon. It is made up of two position vectors in the form of a line. Call the vectors A and B.

If you take A as a starting point, then do Q = Vector2.Normalize(B - A), then A and Q together form a ray. If you take Q on its own, it represents the tangent of the polygon on that edge (a direction).

The algorithm requires you to take an axis that is perpendicular to that edge. So rotate your tangent 90 degrees (the vector (X, Y) rotated 90 degrees is (-Y, X) or (Y, -X), note that the magnitude does not change). The normalized direction vector that faces outwards from an edge is known as the "normal" of that edge.

(Note: the winding order of your polygon will determine which direction you need to rotate 90 degrees in (ie: left or right) in order to have a vector that faces outwards.)

Note that, even though the tangent and normal are associated with a given edge, they contain no positional data - they are only directions!

Just like (1, 0) represents the X axis, and (0, 1) represents the Y axis, the normal that you have now can be used to represent an axis (starting at the origin). You can project positions onto this axis by taking the dot product of any position with your normal.

From here, the tutorial explains how to project polygon vertices (positions) onto that axis to determine whether a polygon is separated from another polygon on that axis. It goes on to explain how to repeat this technique on multiple axes to determine if polygons are intersecting.

---

What I strongly recommend is finding some line-drawing library for XNA, and then using that to make interactive diagrams - similar to those in the tutorials. This will allow you to see what your algorithm is doing, so you can more easily see where anything might be going wrong.