Talk:Hyperplane separation theorem

Explanation of my partial revert

I did a partial revert of the recently added text. That because I find the new language too complicated. The separating axis theorem says that two convex bodies can be separated by a line. Once you have the line, you can of course project the two bodies onto the line perpendicular to it. But there is no need to state the definition in terms of the projection, that is just too complicated and does not add much.

This image has glitches.

I'd also like to note that the modified image, with the projection, does not render well, I see black rectangles on the screen, as seen on the right. That would need fixing before it can be used. Oleg Alexandrov (talk) 06:50, 8 January 2008 (UTC)

I think you are confusing separating axis and separating line. In practice, the separating axis theorem says that if two convex objects are not penetrating, there exists an axis for which the projection of the objects will not overlap. This is an important definition, because it suggests an algorithm for testing whether two convex solids intersect or not -- and, in fact, it's heavily used in computational geometry, including computer games. It is also an important definition, because no matter what the dimensionality, the separating axis is always an axis. For example, in 3D, there is still a separating axis. That axis is the dual of a separating plane.

When someone comes across the term "separating axis theorem," chances are pretty high that they did it because of some computational geometry need, the most common of which in practice is physical simulation such as found in games programming, and thus describing the actual separating axis and the property of the projection is necessary on the page. 75.144.241.102 (talk) 19:42, 8 January 2008 (UTC)

Btw: I generated the updated image in Inkscape. How can I make it not generate those artifacts for the labeling text?

The two formulations are trivially equivalent (if you are already familiar with it). And, "separating axis" does suggest more that the axis separates things, rather than the dual of the axis. In short, you do have a point, but I'd stick with the simpler formulation. Oleg Alexandrov (talk) 06:43, 10 January 2008 (UTC)

Well, I disagree -- a separating line is something that separates two objects, but a separating axis is the axis along which objects can be separated. I come to this from practical computational geometry, where those two definitions are the most natural. Also, presumably people using Wikipedia (instead of Mathworld or just a textbook) are not computational geometry mathematicians, and the duality between axis and hyperplane might not be immediately obvious. In fact, the reason I fixed the article was I sent someone here, and they didn't "get it." I updated the text to hopefully serve both purposes. I still need to know how to fix the illustration, though -- why are the Inkscape labels black? 66.253.99.66 (talk) 22:56, 10 January 2008 (UTC)

Wrong

I am sorry, but I belief this article is just plain wrong and did a good job in confusing me.

1.) The figure is wrong. The line show is not a separating axis. A separating axis is an axis on which the projections of the objects A and B do not overlap. If an axis with this property can be found the objects A and B are said to be non colliding if such an axis could not be found A and B are said to be colliding. There is an infinity of lines to check for collisions this way. The Separating Axis Theorem states that when such an axis exists, there also exist some with a specific property: the axis is orthogonal to either a face or edge of one of the objects. So the search space may be reduced to all orthogonal lines of all faces and edges in the scene.

The exact formulation is: "For a pair of non intersecting polytopes, there exists a separating axis that is orthognal to a facet of either polytope, or orthogonal to an edge from each polytope" cited from Gino van Bergens "Collision Detection in Interactive 3D Environments"

I am sorry that is all I can do for now. I hope some knowledgeable person will rewrite this article. I haven't the time and expertise to do that right now. In the meanwhile this article should be completely removed. False information is actually much worse than no information. For me that was an excellent lesson what is the difference between wikipedia and a proper book... sorry no offense but this article was part of lasting misunderstandig of what SAT means on my side. Sorry for posting anonymously, but I have never commited to wikipedia before.

Fair enough. As a mathematican, to me it makes more sense to talk about the line separating the two, not the axis on which to project, but I see your point. I replaced the picture. Oleg Alexandrov (talk) 05:05, 21 April 2008 (UTC)

The first statement of the theorem makes no sense to me: "given two convex shapes, there exists a line onto which their projections will be separate if and only if they are not intersecting." But if we are given the two shapes, they either are or are not intersecting, so if and only if can't come into it.

The second statement of the theorem, however, it perfectly clear. Could we just get rid of the first statement? Maproom (talk) 20:06, 4 December 2011 (UTC)

Re-reading the first statement of the theorem with a fresh clear mind, I figured out what it was struggling to say. I rewrote it to say that more clearly. Maproom (talk) 14:13, 8 December 2011 (UTC)

More Examples needed

I understand the separating axis theorem and the article didn't confuse me (although a link to some other article explaining the line/plane duality may be useful). But the line "If the cross products were not used, certain edge-on-edge non-colliding cases would be treated as colliding" seems quite ambiguous to me: do we need the cross products of all pairs of face normals (which would be quite a lot) or only some of them? and second: if we need edge normals as stated above in the discussion, which edge normals (in dimensions >2, each edge has infinitely many of them)? I ask because i can think of dozens of examples which are resolved by face normals, but none which need other axes (as long as the shapes don't have curved surfaces). So, whoever mentioned "certain edge-on-edge non-colliding cases", could you please give an example or a link?--Catskineater (talk) 09:26, 21 September 2008 (UTC)

Which cross products ?

For 3D, you talk about cross products for separating axis ... but which ones ? —Preceding unsigned comment added by Vanderfula (talk • contribs) 16:46, 26 January 2010 (UTC)

The cross products required are the face normals of one polyhedron crossed with each of the face normals of the other. For example, with 2 colliding 3D boxes, there are 3 axes each, and 9 pairs of cross products between the two of them, making 3+3+9=15 axes you must test before you can guarantee no collision. This is to ensure that no edge-edge collision occurs. If you feel it is necessary i can write that in the article with source later. --OrangeKyo (talk) 17:43, 2 February 2011 (UTC)