4
\$\begingroup\$

I am having trouble understanding why, in a game collision detection, separating axis determination requires checking for the cross product of edges of the two polytopes as additional potential separating axes. In 2D the process is much more intuitive, in that it only checks the edges normals as potential separating axes.

I have been thinking about this very hard but I cannot visualize this at all, nor can I find a good motivating example or explanation.

\$\endgroup\$
  • \$\begingroup\$ you are going to have to specify what 3D Engine, Language, and IDE you are using. normally you are giving the collision detection the size of the object in 3 dimensions, the location, the velocity, then the same stuff for the other object. it has been a while since I did anything with collision Detection or 3D. the cross product probably gives the Distance between the two objects \$\endgroup\$ – Malachi Aug 7 '13 at 15:39
  • \$\begingroup\$ as the objects move through space, the Angle at which they will eventually collide may change based on Several Parameters. the Cross Product will determine the Vectors of the collision and the Vectors of the objects following the collision. i wanted to post this as an answer but I am not sure I have given the answer sufficiently \$\endgroup\$ – Malachi Aug 7 '13 at 15:43
2
\$\begingroup\$

The cross product of two vectors is a vector perpendicular to both, and normal to the plane that they span. If the two vectors are two adjacent edges of a face, their cross product is a vector normal to that face.

Because of this, taking the cross product of two edges of a face of a polygon in 3D is analogous to taking the normal to an edge of a polygon in 2D.

Also, in case it helps you to visualise:

  • In 2D, you check a series of axes to find one where the projections of the two polygons are disjoint. This means that there was a line, normal to the axis, separating the two polygons.

  • In 3D, you do the same, checking axes until the projections of the polyhedra onto an axis are disjoint. This time, this means that there is a plane in space, normal to the line, separating the two polyhedra.

In both cases, the projections of the polytopes end up as line segments (intervals), and you just check if they overlap.

N.B.: None of this works for concave polyhedra - think of a ball resting in a cup, not intersecting with it. No matter what axis you project along, the projections of the two shapes intersect, even though the objects are disjoint. This is because there is no plane separating the ball and the cup. Using separating axis tests on non-convex polytopes will give false intersections.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.