btGjkEpaSolver thread safe?

[RobW]

Hi,

I have been working on an alternate threading implementation specific for the xbox 360. Unlike the SPU version, there is no memory limitations and no manual cache coherency to maintain, which means I have been able to use most of Bullet's single threaded architecture, pluging in new versions of the collision dispatcher and dynamics world to do parallel processing. A few of the things I have needed to include, allocating a stack allocater per thread, and not use a single global penetration depth solver or simplex solver.

Initially, I didn't allocate a stack allocator per thread, and used the Minkowski penetration depth solver as I could see that btGjkEpaSolver was the only bit of code I was trying to parallelize that used a stack allocator. However, I would like to get btGjkEpaSolver working too. Although I now have a stack allocator per thread, I'm getting almost instantaneous crashes once btGjkEpaSolver is being used by multiple threads at once, usually in the Detach() function, sometimes elsewhere. I've been looking at it for several hours and cannot see anything that is not thread safe, so I was just wondering if anyone had any similar experience...

I notice the the SPU version only uses the Minkowski solver, perhaps the author had the same problem as me?

Besides this problem everything works great!

[Erwin Coumans]

btGjkEpaSolver is not threadsafe currently. We used an alternative PD solver for SPU, because it fits better in 256kb local store memory (code-size, data usage).

You might want to check out this recent patch from the author of btGjkEPA, Presson Nathanael:

http://code.google.com/p/bullet/issues/detail?id=28

It is more compact and readable code. Once we got time, we will evaluate it and integrate it into Bullet. If you can give us your experiences, please let us know,
Erwin

[RobW]

Thanks Erwin!

The new version certainly looks more readable! I'll have it integrated by the weekend and let you know my experiences.

I would be interested to know why the old one isn't thread safe, I couldn't seem to find the problem myself. I thought for a while it could be using too much stack but all our worker threads have the same stack size as the main thread and that worked fine.

[Nathanael]

Thanks Erwin!

The new version certainly looks more readable! I'll have it integrated by the weekend and let you know my experiences.

I would be interested to know why the old one isn't thread safe, I couldn't seem to find the problem myself. I thought for a while it could be using too much stack but all our worker threads have the same stack size as the main thread and that worked fine.

I did test the old version under multi stack / multi thread without crashes, but it was a long time ago, i am not sure the code was exactly the same, still, it could interesting to find why, just in the unlikely case the bug is not in the GjkEpa module. I may give it a shot this week end.

I'll be interested to know if the new version work well under x360, multi threading is the main reason for the rewriting.
Do not hesitate to ask any questions regarding the new implementation, I'll be happy to answer.

[RobW]

Many thanks Nathanael,

I patched in your new version, and it works absolutely fine. I'm guessing the problem was related to the use of btStackAlloc, although I'm still not clear why. I did notice, while investigating the problem, that btGjkEpa sometimes seemed to return without freeing all its memory from the stack allocator, but never did so single threaded. When it actually crashed it looked like a classic case of thread interference, a pointer was NULL when it had no right to be! Yet, none of the normal thread issues seemed to be at fault, e.g. function static variables, global variables, etc

I'll take another look at the use of btStackAlloc in the old version later, it would be nice to get to the bottom of the problem.

In general, I can't comment on exactly how well everything is working under threading on the xbox 360, because I haven't timed it carefully yet. I do know that the physics was denting our framerate, and now it isn't

[Nathanael]

I glad the that new version let you move forward. Performance wise, i may try implement an idea from Erwin that basically let EPA use the previous GJK simplex (in most cases, currently, we always rebuild it from scratch), that should improve penetration depth evaluation greatly. I know that the theory say that deep penetration is not called that often, but in real cases, players tend to blow stuff aways just at right velocity, before CCD (if any!) kicks in, so yes, fast deep penetration resolution matter.

[RobW]

I thought the problem with doing that was that the simplex from the first GJK step used margins, but the EPA GJK step doesn't. I thought perhaps the simplex from the first step could be deflated to remove the margins, but I haven't analysed that idea carefully to determine whether it is valid...

but for now, I'm happy

[Erwin Coumans]

To clear up some confusion:

Bullet doesn't use margins inside the first GJK (btGjkPairDetector uses getSupportingVertexWithoutMargin). However, EPA needs to use margins, so the starting simplex needs to be recalculated using a second GJK. That is the current situation, and that should be fine.
I think it is best to keep that behaviour: running a second GJK that includes the margins, to get a better starting simplex for EPA.

Main point is to get EPA on SPU and other multi-core, so cleaned up code and lower memory requirements are great.
Thanks,
Erwin