I had an idea for a simple way to do a swept collision test between polyhedra. It's not accurate, it's probably not even fast, but it's easy. Basicly, I'd like some feedback, any blatent errors etc. We have a moving object and a static object. We want to find when the moving one hits the static one. 1. Transform all the vertices of the moving object according to it's movement for the frame, and create line segments between the start and end positions. 2. Test all these line segments against all the polygons of the static object. If there is an intersection, find out how much by, and you can work out the time of collision (near enough). But you need to keep going, as there might be smaller times. 3. Test all the vertices of the static object against the moving in a similar manner, but transformed the opposite way. 4. Test the edges of the first object against the edges of the second. This is where it gets interesting. A swept line segment test seems too hard, so just find the start and end points of the moving edge vertices, construct 2 triangles out of the 4 points (though this does not accurately represent the path of the edge due to rotation, but hey, we used straight lines earlier) and test the other edge against those triangles. You can interpolate the time of collision across the triangles. The advantages I see are: It's easy. It only uses triangle - line segment tests. It works for arbitrary models, not just convex ones or anything. The disadvantages are: No early outs, so it's not that fast. But it shouldn't be to bad compared to other swept tests. It's really really inaccurate. But it should beat non-swept tests. It doesn't even notice if the objects already intersect. I don't know how much of a problem this is, I'd have to try it. You'd probably have to take the collision times with a grain of salt anyway. So yea, has it been done? Is it useless? Does it even work? Let me know!

Considering how easy the separating theorem is, your idea is probably not as easy as you think. At least, it is much more involved and probably a great order of magnitude slower too... But if it works, it works ;).

For a complete test as you describe, I seem to remember reading that you need to test the face barycentre aswell but I don't remember the details sorry...

Quote:Original post by b34r
Considering how easy the separating theorem is, your idea is probably not as easy as you think.

I have read about the seperating axis theorem, but I didn't think it could be used for swept arbitrary objects... can it? You're right though, three two deep loops isn't what you call brilliant.

Quote:Original post by b34r
For a complete test as you describe, I seem to remember reading that you need to test the face barycentre aswell but I don't remember the details sorry...

I don't know, but I can't think of any a way two objects can intersect without any vertices moving through faces or any edges through edges.

[Edited by - RAZORUNREAL on August 2, 2005 6:34:38 AM]

you can call the SAT on a pre triangle-triangle basis, but obviously, it's expensive. SAT is OK for small convex polygonal shapes. Anything else isn't.

as for swept edge-edge, there is a simpler method.

point-triangle, that's simple enough. You'll aso have to check for edge-triangle intersection.

What you'll end up with, is a load of messy intersection results, that you'll need to turn into something intelligible for the physics system, so it can process contacts and overlaps.

Another way is the binary time search. Go back and forth in time until you found the first intersection time (using some tolerance).

Just throwing random ideas...

Hmm, I do so like to make a fool of myself. After thinking a little more I realised you can map the swept triangle onto the plane of the static one, and work in 2d from there. But theres probably a million other things I havn't thought of, so, less thinking more reading.

Thanks guys.