body-body time of impact

[Dan Coming]

The main unknown of their approach is how they 'estimate' the first time of impact, rathern then what to do with this time.

Well that was my point really. The claim is that better results are provided than 4D (i.e., time-parameterized) intersection tests, to which I must raise an eyebrow. Perhaps the claim is for a closer estimate of the TOI...

I guess they either subdivide the timestep until there are no large 'gaps' in the motion or they use an iterative approach like the pure linear version of raycasting against the Minkowski sum (Gino van den Bergen) or the angular extension (described in my draft).

Given a scenario where a closed-form solution does exist (e.g., translation w/o rotation or rotation w/o translation) its doubtful that there exists a faster method that provides more accurate results than simply performing the calculations for the exact solution.

That said, I'm interested in what kind of motions objects can simultaneously undergo in the situations they do handle, and what makes their method so fast/accurate. I'm sure its very interesting, to all of us here. Given that it is stated to not handle extreme rotations, it sounds like the performance relies on some rather unsafe assumptions on the bounds of motion. Such assumptions as could be enforced perhaps by subdividing timesteps...? Just my thoughts, without specific knowledge of the intersection tests used.

Dan, what method do you use to estimate or calculate the first time of impact? And which shapes do you support?

My work focuses on the many-body problem mostly, though I've been looking into more object-pair intersection tests lately, to make a more complete system all my own. Initially I worked with spheres, but that lasted only until I came upon Dave Eberly's Wild Magic code. I've debugged, optimized, and extended some of the collision detection code. I've provided it all to Eberly and some has been added to the main code base. The portions I use handle triangle meshes as well as numerous bounding volumes of course. TOI is calculated by solving for closed form solutions to intersections between translating objects, using hierarchies for efficient traversal of the geometry. I'd like to look into point-set and other implicit surfaces though, if anyone can suggest good collision detection papers on them.[/url]

[Erwin Coumans]

Initially I worked with spheres, but that lasted only until I came upon Dave Eberly's Wild Magic code. I've debugged, optimized, and extended some of the collision detection code. I've provided it all to Eberly and some has been added to the main code base. The portions I use handle triangle meshes as well as numerous bounding volumes of course. TOI is calculated by solving for closed form solutions to intersections between translating objects, using hierarchies for efficient traversal of the geometry. I'd like to look into point-set and other implicit surfaces though, if anyone can suggest good collision detection papers on them

My work focuses on the many-body problem mostly, though I've been looking into more object-pair intersection.

I'm interested how your approach for the object-object case compares to Redon or my approach.

1) Are the closed-form calculations for your object-object time of impact documented? Do you have references to papers?

2) Do you have links to implementation in magic?

3) So after the many-object (broadphase + hierarchies) the problem reduces to either 1 static triangle versus dynamic bounding primitive or dynamic bounding versus dynamic bounding?

4) Do you restrict to pure linear motion, or do you include angular motion too? Do you have more details on the actual motion?

5) What bounding primitives do you support for the time of impact? Do you have closed solutions for all combinations?
Box, Sphere others ?

Box-Triangle, Sphere-Triangle, Box-Box, Sphere-Box, Sphere-Sphere?
(the triangle mesh assumed to be static?)

Thanks
Erwin

[dcoming]

I'm interested how your approach for the object-object case compares to Redon or my approach.

I think we've moved off-topic with the discussion of my work, so may want to bump to another thread. I don't want to hijack this one.

1) Are the closed-form calculations for your object-object time of impact documented? Do you have references to papers?

Eberly has many technical reports documenting his methods here:
http://geometrictools.com/Documentation.html

2) Do you have links to implementation in magic?

I linked it in "Wild Magic" before, but here's the plain url
http://geometrictools.com/SourceCode.html

3) So after the many-object (broadphase + hierarchies) the problem reduces to either 1 static triangle versus dynamic bounding primitive or dynamic bounding versus dynamic bounding?

Dynamic triangle-triangle is the final test.

4) Do you restrict to pure linear motion, or do you include angular motion too? Do you have more details on the actual motion?

Unfortunately Eberly's code doesn't do dynamic rotations, so the best I can do there is screw-motion (my own implementation, I don't have the original paper reference handy; it is not my own) or time subdivision with discrete rotations. Otherwise, pure linear motion works fine of course.

Like I said, I want to use better tri-tri intersection tests. To elaborate, I want to handle translation, rotation and orbits continuously, because my broad phase already supports these. Given dynamic tri-tri intersection tests that handle all 3 at once, I'd just plug them in, if such tests exist and are fast enough for real-time, and the code is available.

5) What bounding primitives do you support for the time of impact? Do you have closed solutions for all combinations?
Box, Sphere others ?

Box-Triangle, Sphere-Triangle, Box-Box, Sphere-Box, Sphere-Sphere?
(the triangle mesh assumed to be static?)

Just to be clear its Eberly's code, but it supports all of the above. Triangle meshes don't have to stay static but there's no support for continuous collision detection during continuous deformation. The boxes supported are oriented boxes as well as axis-aligned boxes. In addition, my own code supports k-DOPs (with good direction distributions up to k = 70000). Some of my other work that is currently under review makes efficient use of large k without as much overhead as would be expected.

[Erwin Coumans]

3) So after the many-object (broadphase + hierarchies) the problem reduces to either 1 static triangle versus dynamic bounding primitive or dynamic bounding versus dynamic bounding?

Dynamic triangle-triangle is the final test.

I'm surprised that dynamic triangle-triangle is the final test.
Real-time applications (especially games) usually use static triangle meshes and dynamic objects like spheres, boxes, cylinders, convex hulls, capsules and compounds of those. Moving concave triangle-meshes are typically avoided, and commercial game physics engines don't really support those. Novodex/Ageia has pmaps, but they recommend not to use them, and stay away from dynamic concave triangle meshes.

Like I said, I want to use better tri-tri intersection tests. To elaborate, I want to handle translation, rotation and orbits continuously, because my broad phase already supports these. Given dynamic tri-tri intersection tests that handle all 3 at once, I'd just plug them in, if such tests exist and are fast enough for real-time, and the code is available.

The Bullet source code has such time of impact available, for the general convex-convex. So it supports triangle-triangle continuously for translation and rotation. There is not support for orbits yet, but adding that won't be a bit thing. How do you describe orbits, does it involve gravity?

Can you make your dynamic broadphase and/or dynamic hierarchies available? I'm interested in trying out your dynamic broadphase/hierarchies and hooking it up to the object-object case too.

Thanks,
Erwin

[dcoming]

I'm surprised that dynamic triangle-triangle is the final test.
Real-time applications (especially games) usually use static triangle meshes and dynamic objects like spheres, boxes, cylinders, convex hulls, capsules and compounds of those. Moving concave triangle-meshes are typically avoided, and commercial game physics engines don't really support those.

Perhaps they should. Real-time is a self-imposed design requirement for our development, and we've seen success with hundreds to thousands of objects, depending on geometry. 3000+ triangle x-wings are more expensive to test than 240 triangle tori of course, though hierarchies aid performance. We do perform OBB-OBB dynamic tests to prune the majority of triangle-triangle tests necessary. Ultimately we're interested in the first TOI between actual geometry of objects, and that requires tri-tri testing.

How do you describe orbits, does it involve gravity?

An orbit would be an elliptical (or circular in the simple case) path of an object around an arbitrary centroid that doesn't need to be a part of the object. It would in effect involve gravity, but between a pair of objects, not just as an arbitrary "downward" acceleration.

Can you make your dynamic broad-phase and/or dynamic hierarchies available? I'm interested in trying out your dynamic broad-phase/hierarchies and hooking it up to the object-object case too.

At this time the dynamic broad-phase (kinetic sweep and prune) is unavailable for release as code and that status is up to the UC Davis Technology Transfer Department. I believe my paper, and more so the upcoming expanded journal version [currently in press], give sufficient detail for implementation. If you already have a sweep and prune implementation to work with, the conversion should be reasonable. If you have anything in particular you want me to test, I'll see what I can do.

I'll check with David Eberly to see how he would want to approach releasing my extensions alongside his own code. I'm happy to make these available.