How do I get the axis from a face of a 2D rectangle?
Pseudo code is more than fine.
I've never heard of an SAT collision test, but there's an algorithm that I know of which will probably do the same thing. It works equally well in 2D and 3D, so I'll try to describe it in dimension-independent terms.
Whenever you have a collision between convex objects, one of the vertexes of one object will be inside the other. In order for a point to be "inside" of the convex shape, it needs to be behind [I]every[/I] face or hyperplane. Point/hyperplane tests are very quick and easy and form the basis for much of the technology you see in video games (BSP or binary space partition maps, etc).
A hyperplane is a plane that divides space into two sub-spaces. In 3D, it is a plane, in 2D, it's a line. A hyperplane can be described in terms of a normal vector, [I]n[/I], and a "distance" from the origin, [I]d[/I].
To find the "normal" vector in 3D space, you can use the cross product on two vectors generated from the coords of vertexes in the face (I won't go into detail because you're working in 2D). To find the "normal" of an edge in 2D, you subtract the first coordinate from the second, swap the [I]x-[/I] and [I]y-[/I] components of the vector, and switch the sign of one of them (which sign gets reversed depends on whether the vector is clockwise or counter-clockwise around the edge of the object):
[I]n = <y1 - y2, x2 - x1>[/I] or [I]n = <y2 - y1, x1 - x2>[/I], depending on direction
The distance is the dot product of the normal vector and the coordinates of a point on the hyperplane (either one of the two edge vertexes will do):
[i]d = n·a[/i], where [I]a[/I] is a point on the line.
You can test any point against the hyperplane by taking the dot product of the hyperplane's normal and the point you want to test, and comparing the result against the hyperplane's distance from the origin. If [I]b[/I] is the point you wish to test, then:
[I]n·b > d[/I] point is in front of the hyperplane.
[I]n·b = d[/I] point is on the hyperplane.
[I]n·b < d[/I] point is behind the hyperplane.
So what you do is construct a set of every point in object [I]A[/I] (or the whole scene, if you want to do lots of collision tests in one pass), then loop through every hyperplane in object [I]B[/I] and test the points. If a point is in front of the hyperplane, discard it, it isn't colliding. If any remain after every test, you've got a collision. If you didn't find a collision, repeat the process in reverse (B tested against A).
[code]
for (vertex in A) {
for (hyperplane in B) {
if (dotProduct(hyperplane.normal, vertex) > hyperplane.distance) {
break;
}
/* collision found, return colliding vertex */
return vertex;
}
}
return NULL; /* no collisions */
[/code]
Depending on the complexity of your geometry, you might want to do some quick preliminary tests, such as an axis-aligned bounding box test or quad/octrees to speed things up.
[editline]05:02AM[/editline]
Wow, that is a solid wall of text. Sorry if I went off on a bit of a tangent there.
Ok awesome, I'll try that. Seems a little easier than seperating axis theorem.
[quote]Whenever you have a collision between convex objects, one of the vertexes of one object will be inside the other.[/quote]
Uh, no. Two rectangles could intersect while not having any vertices within each other. Point in polygon would be enough for most collision detection though.
I used [url=http://rocketmandevelopment.com/2010/05/19/separation-of-axis-theorem-for-collision-detection/]this[/url] when I was making my own 2D collision detection. I have a working C# sample if you're interested in seeing it.
[QUOTE=noctune9;24064618]Uh, no. Two rectangles could intersect while not having any vertices within each other.[/QUOTE]
Right. I totally forgot about the special cases.
It will fail for collisions like this:
[code]
+----+
| |
+---------+
| | | |
+--|----|-+
+----+
[/code]
But it is a decent approximation. Collision detection is a trade-off between speed and exactness. If your objects are sufficiently thick and the difference in position/orientation of each object is sufficiently small, it should work out well enough. You have to work out some method of preventing objects from moving large distances between collision tests. Either by doing multiple tests in a game frame, or by limiting velocity + game frame duration.
[QUOTE=ROBO_DONUT;24052513]A hyperplane is a plane that divides space into two sub-spaces. In 3D, it is a plane, in 2D, it's a line.[/QUOTE]
What makes hyperplanes incredibly awesome is that the hyperplane in four dimensions is a cube.
[QUOTE=ROBO_DONUT;24064800]Right. I totally forgot about the special cases.
It will fail for collisions like this:
[code]
+----+
| |
+---------+
| | | |
+--|----|-+
+----+
[/code]But it is a decent approximation. Collision detection is a trade-off between speed and exactness. If your objects are sufficiently thick and the difference in position/orientation of each object is sufficiently small, it should work out well enough. You have to work out some method of preventing objects from moving large distances between collision tests. Either by doing multiple tests in a game frame, or by limiting velocity + game frame duration.[/QUOTE]
And your method would work perfectly for say a platformer or top down shooter, where each character is like to be a small rectangle or square of about the same size, you'd barely EVER get those edge cases.
OK, so I am implementing a vector class for the required vectory stuff in the algorithm. I don't get something, though: vectors have a start and endpoint, but none of the tutorials I've read show any kind of endpoint member, just a startpoint and how to get the length/magnitude and normalize it. Is there something I am missing?
Well, you can imagine every vector starting at 0,0 and ending at the point it contains.
I don't think vectors have 2 points... they only define angle and length.
A vector in 3d graphics has an assumed origin, which is relative. It's assumed to be starting at 0,0 when dealing with force and movement usually. 0,0 is actually the origin of the entity.
[editline]12:10PM[/editline]
i'm pretty sure in a lot of applications you still need a startpoint AND an endpoint though, but especially with movement the location of the moving object is usually assumed.
[QUOTE=MrBob1337;24085087]I don't get something, though: vectors have a start and endpoint[/QUOTE]
They have neither a start nor endpoint. They only express a direction and a magnitude.
[QUOTE=esalaka;24067857]What makes hyperplanes incredibly awesome is that the hyperplane in four dimensions is a cube.[/QUOTE]
In five dimensions it is a hypercube.
[editline]07:59PM[/editline]
[QUOTE=ROBO_DONUT;24085522]They have neither a start nor endpoint. They only express a direction and a magnitude.[/QUOTE]
And the direction is implicit.
[QUOTE=nos217;24139185]In five dimensions it is a hypercube.[/QUOTE]
Technically true, but more specifically it's a tesseract. Any hyperplane in over four dimensions is a hypercube:
[quote=Tesseract - Wikipedia]A generalization of the cube to dimensions greater than three is called a "hypercube", "n-cube" or "measure polytope". The tesseract is the four-dimensional hypercube, or 4-cube.[/quote]
Sorry, you need to Log In to post a reply to this thread.
