Real-Time Physics Simulation Forum

Re: Looking for research topics in areas of realtime physics

2014-02-03T22:22:47+00:00

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.

Statistics: Posted by bone — Mon Feb 03, 2014 10:22 pm

Re: Looking for research topics in areas of realtime physics

2014-02-03T19:52:11+00:00

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.

Statistics: Posted by Numsgil — Mon Feb 03, 2014 7:52 pm

Re: Looking for research topics in areas of realtime physics

2014-02-03T18:46:13+00:00

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.

Statistics: Posted by bone — Mon Feb 03, 2014 6:46 pm

Re: Looking for research topics in areas of realtime physics

2014-02-03T07:37:27+00:00

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/

Statistics: Posted by mobeen — Mon Feb 03, 2014 7:37 am

Re: Looking for research topics in areas of realtime physics

2014-02-02T18:00:28+00:00

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.

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.

Statistics: Posted by Erwin Coumans — Sun Feb 02, 2014 6:00 pm

Re: Looking for research topics in areas of realtime physics

2014-01-31T17:40:01+00:00

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

Statistics: Posted by Numsgil — Fri Jan 31, 2014 5:40 pm

Re: Looking for research topics in areas of realtime physics

2014-01-31T15:49:19+00:00

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.

Statistics: Posted by bone — Fri Jan 31, 2014 3:49 pm

Re: Looking for research topics in areas of realtime physics

2014-01-31T03:53:10+00:00

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

Statistics: Posted by mobeen — Fri Jan 31, 2014 3:53 am

Re: Looking for research topics in areas of realtime physics

2014-01-31T01:08:57+00:00

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.

Statistics: Posted by Numsgil — Fri Jan 31, 2014 1:08 am

Re: Looking for research topics in areas of realtime physics

2014-01-30T17:44:02+00:00

CCD and Continuous Physics.

Statistics: Posted by Dirk Gregorius — Thu Jan 30, 2014 5:44 pm