Talk:Separating axis theorem

From Wikipedia, the free encyclopedia

[edit] 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.

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)

[edit] 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)