Some questions on simple particle game physics
Author
Hi,
I very recently decided to start taking the physics seriously and I've started with basic accelerated motion and collision detection for a particle. Now I have a few questions:
1. What I have now is that when the particle's distance from a plane is some amount (equal to or slightly greater than the radius of my "particle"), the velocity vector of the particle is reflected about the plane, and multiplied by some factor less than unity (coefficient of restitution).
When the ball has lost all it's energy and stopped after hitting the floor, the acceleration is still acting, and it's like the ball is hitting the floor and rebounding continuously too small to be noticed by the eye. But, since the coeff of restitution is < 1, it slowly starts going through the floor. What is usually done to prevent this?
2. A similar problem: let's say the radius of my "ball" is 0.2 units. Sometimes I see the ball "sticking" to the wall and sliding down. I reasoned that this is happening because 2 physics cycles are occuring while the ball is within the 0.2 units tolerance range and it's reflected away from the wall once, and again towards the wall so that it's trapped in the 0.2 unit zone. How can I prevent this?
3. I have tried 3 integrators, the NSV, a slightly modified Euler (x += v*dt + 0.5*a*dt*dt; v += a*dt; ) and Verlet. The Euler, like I've read around here, seems to add energy to a spring simulation (which is clearly unacceptable) but my Verlet and NSV both seem to damp oscillations to a small degree. Is that normal?
4. Since in my simulation the velocity of the ball is required (to reflect the ball off walls), how is this obtained if I want to use Verlet?
5. How is the x - x0 calculated when starting the Verlet? x = v*dt (ie Euler) for the first step?
Thanks for reading this, I especially want to be able to solve problems 1 and 2.
Hi deavik. I don't have *that* much experience with these myself, but at least I can suggest a couple of things...
The problem you describe in (2) also affects your first problem.
You describe both the jittering of objects that should rest flat on a floor, and the fact that an object may become entangled in a continuous collision response, causing it to ultimately pass through the unyielding object.
As for the continuous bouncing of objects that should -otherwise- rest on the floor, I understand that it's usually treated with a method that involves flagging objects as temporarily inactive in the simulation, to prevent applying forces that don't actually cause it to move. E.g. the ball bouncing on a floor. After some time it's kinetic energy should become small enough for it not to bounce back, but rather rest on the floor. In this case you keep track of its kinetic energy (or how much it moves each timestep) and when it becomes small enough, you explicitly position the ball on the floor, and flag it as inactive. From then on, you don't actually apply the change in position, until a big enough force is applied, that can make the object "active" again and change its kinetic state. Unfortunately I can't point you to any resources on that, but it's pretty much how this is treated.
As for the ball going through the floor, I think it's caused by the same reason that causes problem 2. It's quite often that people actually implement collision response, but neglect to also "correct" the position of the colliding object so that a collision response will not be triggered in the nect timestep.
E.g. you have a .2 units wide zone above the floor, and within that zone a collision response is triggered. Obviously when this happens you reflect the velocity vector and scale it by the coeff. of restitution. If the ball's speed is high enough, it will probably escape the "collision zone" within the next timestep, and luckily you won't trigger a collision response.
However, if the speed is not high enough, the ball will not be able to escape that region in a single timestep, the collision detection will be invoked flagging a collision response, the velocity will be negated ... and so on which will result in the ball being trapped in the collision region.
To conclude, once you've found a collision, don't just reflect the speed; use the previous velocity to move the ball back in time at the exact moment before the collision happens, reflect the velocity, and then move it along its new velocity for the rest of the timestep.
5) I think people use simple Euler in order to start Verlet, but if you want as much accuracy as possible, there is a potential for introduction of error into the simulation here. It should be fine for simple purposes though.
The problem you describe in (2) also affects your first problem.
You describe both the jittering of objects that should rest flat on a floor, and the fact that an object may become entangled in a continuous collision response, causing it to ultimately pass through the unyielding object.
As for the continuous bouncing of objects that should -otherwise- rest on the floor, I understand that it's usually treated with a method that involves flagging objects as temporarily inactive in the simulation, to prevent applying forces that don't actually cause it to move. E.g. the ball bouncing on a floor. After some time it's kinetic energy should become small enough for it not to bounce back, but rather rest on the floor. In this case you keep track of its kinetic energy (or how much it moves each timestep) and when it becomes small enough, you explicitly position the ball on the floor, and flag it as inactive. From then on, you don't actually apply the change in position, until a big enough force is applied, that can make the object "active" again and change its kinetic state. Unfortunately I can't point you to any resources on that, but it's pretty much how this is treated.
As for the ball going through the floor, I think it's caused by the same reason that causes problem 2. It's quite often that people actually implement collision response, but neglect to also "correct" the position of the colliding object so that a collision response will not be triggered in the nect timestep.
E.g. you have a .2 units wide zone above the floor, and within that zone a collision response is triggered. Obviously when this happens you reflect the velocity vector and scale it by the coeff. of restitution. If the ball's speed is high enough, it will probably escape the "collision zone" within the next timestep, and luckily you won't trigger a collision response.
However, if the speed is not high enough, the ball will not be able to escape that region in a single timestep, the collision detection will be invoked flagging a collision response, the velocity will be negated ... and so on which will result in the ball being trapped in the collision region.
To conclude, once you've found a collision, don't just reflect the speed; use the previous velocity to move the ball back in time at the exact moment before the collision happens, reflect the velocity, and then move it along its new velocity for the rest of the timestep.
5) I think people use simple Euler in order to start Verlet, but if you want as much accuracy as possible, there is a potential for introduction of error into the simulation here. It should be fine for simple purposes though.
Welcome to world of finite precision math.
1) Due to accuracy errors, you'll never get objects to match up perfectly. You will need to figure out when two objects are in contact, and/or at rest, then (as noted above) flag them and stop applying forces to them. It's also easier said than done.
2) Force the object to not penetrate. Whenever it happens, use the collision point and surface normal (for example, there's other methods as well) to push it back to the right side. As before, if you detect such a situation, you could adjust the forces, so that the component that forces the object through the wall is not applied. For example, if a ball is rolling on the floor, as long as you consider it being on the ground, you set the z component of force to 0.
3) Yes. Depending on oscillation and integrator properties, you will usually experience errors. These can be mathematically classified by evaluating the integrators themself. You could (for some cases) workout "safe" time steps, or at least the areas where these integrators have the danger of "exploding"
4) Not really sure what you mean.
5) v*dt - x0 perhaps?
1) Due to accuracy errors, you'll never get objects to match up perfectly. You will need to figure out when two objects are in contact, and/or at rest, then (as noted above) flag them and stop applying forces to them. It's also easier said than done.
2) Force the object to not penetrate. Whenever it happens, use the collision point and surface normal (for example, there's other methods as well) to push it back to the right side. As before, if you detect such a situation, you could adjust the forces, so that the component that forces the object through the wall is not applied. For example, if a ball is rolling on the floor, as long as you consider it being on the ground, you set the z component of force to 0.
3) Yes. Depending on oscillation and integrator properties, you will usually experience errors. These can be mathematically classified by evaluating the integrators themself. You could (for some cases) workout "safe" time steps, or at least the areas where these integrators have the danger of "exploding"
4) Not really sure what you mean.
5) v*dt - x0 perhaps?
I've had excellent results in my own physics simulator by seperating the velocity from the position for most forces.
Object to Object collisions, for instance, have two results in my engine: they change velocities and they change positions (stop colliding the objects). I calculate all the velocity changes for objects first, then integrate and move all the objects.
Then I go back through and provide some hard constraints (physically move objects out of walls, stop colliding with other objects, etc.) You generally have to run a few iterations of this if you have alot of interacting objects.
For instance, a bunch of objects stacking on the ground will, at present, slow my simulation to a crawl as all the objects are pushed away from each other, pushed back in bounds, pushed away from each other, etc.
But still a step up from earlier methods I used where I combined the two effects.
edit: oh, and to integrators. I personally prefer Velocity Verlet (near bottom of page).
It trades positional accuracy (which is t^4 in regular verlet) for some additional velocity accuracy (regular verlet is t^2 accurate with velocity I believe), in addition to giving you an explicit velocity term (which was important for my uses).
Not terribly important unless you have forces dependant on velocity. Turbulant drag relies on the square of velocity, so you can see where velocity accuracy might be as important as positional
Object to Object collisions, for instance, have two results in my engine: they change velocities and they change positions (stop colliding the objects). I calculate all the velocity changes for objects first, then integrate and move all the objects.
Then I go back through and provide some hard constraints (physically move objects out of walls, stop colliding with other objects, etc.) You generally have to run a few iterations of this if you have alot of interacting objects.
For instance, a bunch of objects stacking on the ground will, at present, slow my simulation to a crawl as all the objects are pushed away from each other, pushed back in bounds, pushed away from each other, etc.
But still a step up from earlier methods I used where I combined the two effects.
edit: oh, and to integrators. I personally prefer Velocity Verlet (near bottom of page).
It trades positional accuracy (which is t^4 in regular verlet) for some additional velocity accuracy (regular verlet is t^2 accurate with velocity I believe), in addition to giving you an explicit velocity term (which was important for my uses).
Not terribly important unless you have forces dependant on velocity. Turbulant drag relies on the square of velocity, so you can see where velocity accuracy might be as important as positional
You should follow what others have said, but I have a quick suggestion:
A quick fix for your problem 2) would be to only reflect the velocity, if it is pointing towards the surface from which it is supposed to be reflecting off of (but you shouldn't take too big time-steps in your simulation, because then fast objects might "teleport" through thin walls..)
my 2c
A quick fix for your problem 2) would be to only reflect the velocity, if it is pointing towards the surface from which it is supposed to be reflecting off of (but you shouldn't take too big time-steps in your simulation, because then fast objects might "teleport" through thin walls..)
my 2c
Author
Thanks for the input, everyone!
As of now, I corrected (1) by checking if the dot product of the ball velocity and wall normal is < 1, if > 1 don't reflect the velocity even if it is in the "collision zone".
I also corrected (2) by checking if the sq norm of the velocity is less than a factor such as 0.01, then don't integrate it's position. This is what someusername was saying, I think, but it seems to me an "extra" calculation I am doing each frame - is there any shortcut to achieving this goal?
I have another question:
6. Now I have just 1 ball and 6 walls. I was thinking about extending this to η balls (before I start with rigid bodies). For the collision detection, I will then have to check collision for:
a) with each of the η balls and the 6 walls, so 6η calculations for this
b) with each pair of balls, which will be ηC2 checks on paper, but in my program I will probably have to do η2 checks
With both of those it will become very expensive very fast. Are there any shortcuts when dealing with situations like these?
As of now, I corrected (1) by checking if the dot product of the ball velocity and wall normal is < 1, if > 1 don't reflect the velocity even if it is in the "collision zone".
I also corrected (2) by checking if the sq norm of the velocity is less than a factor such as 0.01, then don't integrate it's position. This is what someusername was saying, I think, but it seems to me an "extra" calculation I am doing each frame - is there any shortcut to achieving this goal?
I have another question:
6. Now I have just 1 ball and 6 walls. I was thinking about extending this to η balls (before I start with rigid bodies). For the collision detection, I will then have to check collision for:
a) with each of the η balls and the 6 walls, so 6η calculations for this
b) with each pair of balls, which will be ηC2 checks on paper, but in my program I will probably have to do η2 checks
With both of those it will become very expensive very fast. Are there any shortcuts when dealing with situations like these?
You'll need some sort of spatial partitioning, which is what I'm working on with my engine right now.
If your objects are basically the same size, and your game universe isn't too tremendously large and sparse, your best bet is using a uniform grid where each grid is the same size as your objects. Everytime an object moves, check to see if it's moved grids.
If it has, remove it from its old grid and place it in the new grid.
This link was immensely helpful for me in figuring out the best way to handle it for part of my code.
If your objects aren't the same size, this becomes trickier. I'm not 100% sure, (and would like to know the answer personally) but I believe octrees/quadtrees are the best way to organize the data. Though I'm not certain what kind of octree/quadtree to use depending on your situation.
Does anyone know any resource which describes what the pros/cons are of the different quadtree types, or even other spatial partitioning methods?
Anyway, once you've organized your data, you're approaching constant time to find all the objects that can potentially collide with any single object. You just need to check the surrounding grids/find the neighboring quads/octs.
That means your overall algorithm moves from O(n^2) to O(n) in complexity.
If your objects are basically the same size, and your game universe isn't too tremendously large and sparse, your best bet is using a uniform grid where each grid is the same size as your objects. Everytime an object moves, check to see if it's moved grids.
If it has, remove it from its old grid and place it in the new grid.
This link was immensely helpful for me in figuring out the best way to handle it for part of my code.
If your objects aren't the same size, this becomes trickier. I'm not 100% sure, (and would like to know the answer personally) but I believe octrees/quadtrees are the best way to organize the data. Though I'm not certain what kind of octree/quadtree to use depending on your situation.
Does anyone know any resource which describes what the pros/cons are of the different quadtree types, or even other spatial partitioning methods?
Anyway, once you've organized your data, you're approaching constant time to find all the objects that can potentially collide with any single object. You just need to check the surrounding grids/find the neighboring quads/octs.
That means your overall algorithm moves from O(n^2) to O(n) in complexity.
Author
OK, thanks for the reply Numsgil. I'm trying a lot of things right now, so I haven't got to anything decisive on this. But anyway, I think I should start with trying to get rigid bodies to work. That will a huge topic I am sure - let's see how far I can go!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
