Looking for research topics in areas of realtime physics

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
mobeen
Posts: 122
Joined: Thu May 05, 2011 11:47 am

Looking for research topics in areas of realtime physics

Post by mobeen »

Hi all,
I would like to seek expert opinion on some of the open research topics (which are still unaddressed by the research community in general) especially from the point of view of real-time physics simulation. One of the topic that I know is soft body simulation with collision and self-collision handling. All of the research demos that I have seen show simple meshes but when you have a detailed soft body (a million or so polygons) the process goes to a halt as you add in more soft bodies. And once you add cutting simulation into the scene, the system goes to a halt. I have used Bullet, PhysX, VegasFEM, FastLSM and every other opensource code available. They all basically cant handle it or may be I have missed out some if so please let me know if there is anything.
I have also seen an explosion of CUDA/OpenCL/GPU implementations in recent years which are basically implementing TLED or a variant of it and then use a myriad of parameters which are difficult to fine tune and use.

But are there any other more important topics that are still unaddressed? This is for possible research topics for undergrad, graduate and post graduate students.

Thanks,
Mobeen
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Looking for research topics in areas of realtime physics

Post by Dirk Gregorius »

CCD and Continuous Physics.
Numsgil
Posts: 38
Joined: Wed May 14, 2008 5:58 am

Re: Looking for research topics in areas of realtime physics

Post by Numsgil »

A good way of handling collision response between bodies with vastly different mass ratios would be a reasonable project. It's not that it's an open problem so much as it's an unexplored problem. The onus is usually on the users to make the system less extreme by tweaking the masses. See, eg, this paper/presentation from Oliver Strunk from last GDC: Stop my Constraints from Blowing Up.

Like, someone could take Box2d and start exploring modifications to the solver code to make it more robust to extreme mass ratios. Boom: project.
mobeen
Posts: 122
Joined: Thu May 05, 2011 11:47 am

Re: Looking for research topics in areas of realtime physics

Post by mobeen »

Thanks for the inputs highly appreciated.

OK in the area of CCD, the most recent promising approach that I have seen is this http://www.cs.ubc.ca/labs/imager/tr/201 ... B2012.html

The papers only show basic geometries like a bunch of cloth piece etc. but has anyone used this in a real game/simulation system? If so could you share your experience. If you know of any new method, do let me know.

Thanks,
Mobeen
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Looking for research topics in areas of realtime physics

Post by bone »

Numsgil wrote:A good way of handling collision response between bodies with vastly different mass ratios would be a reasonable project. It's not that it's an open problem so much as it's an unexplored problem. The onus is usually on the users to make the system less extreme by tweaking the masses. See, eg, this paper/presentation from Oliver Strunk from last GDC: Stop my Constraints from Blowing Up.

Like, someone could take Box2d and start exploring modifications to the solver code to make it more robust to extreme mass ratios. Boom: project.
I think this could be addressed if somebody came up with a sparse matrix MLCP solver. And I mean one that could quickly handle changes in sparsity from frame-to-frame. But that may be more of a math problem, I don't know.
Numsgil
Posts: 38
Joined: Wed May 14, 2008 5:58 am

Re: Looking for research topics in areas of realtime physics

Post by Numsgil »

That wouldn't help actually. The core of the problem is that the mass matrix's condition number (basically your largest mass divided by your smallest mass) gets propagated to the larger equation. You need to find the inverse of that matrix, and inverting a matrix with a large condition number is ill conditioned. Doesn't matter if you solve it iteratively, densely, sparsely or magically, the math is ill conditioned. Which basically means you don't have enough digits in your floating point to handle the calculation properly.

As a motivating example, imagine a mass of 1e5 kg resting on top of a mass of 1e-5 kg resting on top of the floor. What's the force that the smaller body has to deliver to the larger body to keep it from falling down? Basically gravity * 1e5. And then, by Newton's third law, what's the force that the larger body is applying to the smaller body? gravity * 1e5. Then we'll just divide by the smaller body's mass and get its acceleration as... gravity * 1e10. Oops, we've overflowed our floating point numbers. Large forces + small masses = large accelerations. Ugh.

Personally I think you'd need to explore the dual of the system. That is, solve for accelerations instead of restorative forces. (The dual is basically the sparse form that Baraff constructs in Linear-Time Dynamics using Lagrange Multipliers). Plus some sort of balancing technique. Maybe you can take the sqrt of the mass matrix, do the calculation, and then "undo" that balancing at the end to get the real changes/forces. But I'm a linear algebra guy so I think in those terms. There might be another way to approach the problem. There are as many ways of dealing with bad condition numbers as there are people who've looked at the problem, so I don't think there's a "right" way. Hence, a good research project :)
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Looking for research topics in areas of realtime physics

Post by Erwin Coumans »

Numsgil wrote: A good way of handling collision response between bodies with vastly different mass ratios would be a reasonable project.
Yes, I agree that dealing with convergence issues, in particular handling large mass ratios deserves more research. I have been experimenting with Featherstone and large-matrix direct MLCP solvers and those solvers can deal with large mass ratios much better than typical iterative solvers such as PGS, but those have often performance issues. I am working on a GDC presentation on this topic.
bone wrote: I think this could be addressed if somebody came up with a sparse matrix MLCP solver. And I mean one that could quickly handle changes in sparsity from frame-to-frame. But that may be more of a math problem, I don't know.
Ideas to improve performance of large matrix direct MLCP solvers would help. Perhaps reducing the matrix size, exploiting the matrix properties and structure etc. I think that a hybrid of direct MLCP block solver and iterative PGS solver can help, dynamically moving constraint rows that don't converge into a large MLCP and trying to move rows back to PGS. Using the idea of constraint anticipation for a group of rows that don't converge might also help dealing with mass ratios. It would be nice not having to rely on hacks that change the masses/inertias.

Also, as Dirk mentions, continuous collision detection and continuous physics needs more research.

Another good topic one is convex decomposition and dealing with concave collision detection: local penetration depth is sometimes not good enough.
mobeen
Posts: 122
Joined: Thu May 05, 2011 11:47 am

Re: Looking for research topics in areas of realtime physics

Post by mobeen »

Thanks Erwin for your feedback. I thought HACD (and the different variants by Julio and John Ratcliffe) are already doing a pretty good job with convex decomposition. What is left now with convex decomposition it seems pretty good to me. Usually concave decomposition solutions split each concave object into a convex object and then treats it as a convex decomposition problem.

Original HACD code by Khalid Mammou http://sourceforge.net/projects/hacd/

Modifications to HACD code of Julio Jerez and Khalid's code by John Ratcliffe (http://codesuppository.blogspot.com/sea ... omposition)
http://code.google.com/p/juliohull/
http://code.google.com/p/hacd/

PS: I just saw Khalid's blog, he has modified HACD to V-HACD Volumetric Hierarchical Approximate Convex Decomposition
http://code.google.com/p/v-hacd/
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Looking for research topics in areas of realtime physics

Post by bone »

Numsgil wrote: As a motivating example, imagine a mass of 1e5 kg resting on top of a mass of 1e-5 kg resting on top of the floor. What's the force that the smaller body has to deliver to the larger body to keep it from falling down? Basically gravity * 1e5. And then, by Newton's third law, what's the force that the larger body is applying to the smaller body? gravity * 1e5. Then we'll just divide by the smaller body's mass and get its acceleration as... gravity * 1e10. Oops, we've overflowed our floating point numbers.
Not in double precision, you haven't.
Numsgil
Posts: 38
Joined: Wed May 14, 2008 5:58 am

Re: Looking for research topics in areas of realtime physics

Post by Numsgil »

bone wrote:
Numsgil wrote: As a motivating example, imagine a mass of 1e5 kg resting on top of a mass of 1e-5 kg resting on top of the floor. What's the force that the smaller body has to deliver to the larger body to keep it from falling down? Basically gravity * 1e5. And then, by Newton's third law, what's the force that the larger body is applying to the smaller body? gravity * 1e5. Then we'll just divide by the smaller body's mass and get its acceleration as... gravity * 1e10. Oops, we've overflowed our floating point numbers.
Not in double precision, you haven't.
Actually you're still in bad trouble. Overflow aside, you're talking about adding 1e11 and -1e11 and getting 0. That's a perfect recipe for cancellation error. Plus, anything much beyond 1e10 is getting in to trouble with numeric precision with doubles. One rule of thumb is to take epsilon to be the sqrt of machine epsilon (see "Real Time Collision Detection", 11.3 "Robust Floating-point Usage, pg 443). For doubles: sqrt(2^53) ~= 1e+/-8. You can probably squeeze to 1e10 if you're careful numerically, but 1e11 would make me uncomfortable. Certainly in a physics engine where we're talking about physics systems that have to handle jitter. 1e16 is actual machine epsilon, and you're not going to get better than that, so that's a hard upper bound. You don't have to tweak the above numbers much to hit an acceleration of 1e16.

Plus, double precision is kind of a non-entity in the game space. In practice everyone's using 32 bit floating point. Then you're talking about a 23 bit mantissa.
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Looking for research topics in areas of realtime physics

Post by bone »

My work is more engineering-related, where double-precision is more common. Thanks for the additional info and pointers about this issue, though.

Your example mass ratio is much more extreme than anything I use in practice. Originally I thought you were just complaining about the limit of most game physics engines, which is something like 10:1 before things start getting questionable. Your ratio of 10^10:1 is quite the leap, whereas I'm typically only worried about 1000:1 or so.
Post Reply