Discussion:
[CsMain] Physics worlds
(too old to reply)
Michael Ewert
2000-02-25 00:22:36 UTC
Permalink
Warning: semi-long rambling post :)

One problem that has been gnawing on the back of my
mind for a while has been one of seperation of the
equations governing physical entities who are
independent of each other.

i.e. During collisions the "best" ( not best
performance but garuanteed not to mess up the
simulation ) handling of collisions is to rewind the
entire simulation back to the point just before the
collision, deal with the collision and then continue.

A huge drawback to this is that if one entity
collides, then you need to redo _all_ the computations
for every entity in the world.

Another thing that is desireable is to detect entities
whose state is not changing ( rest on ground not
moving ) and then not compute those guys until
something happens to them.

The best optimization of the physics lib is obviously
to minimize the number of computations every frame.

Another constraint I have is that I don't want the
physics lib to duplicate all the 3d data in the world.

I came to the conclusion that the "cleanest" way to
seperate entities is to have non-interacting entities
exist in their own worlds ( class ctWorld ). This
sort of dumps the responsibility for this sort of
thing on the application. csphyziks would supply some
interface to support this kind of thing, i.e. like
callbacks when an object is at rest or start moving
from rest.

So it would be the responsibility of the app to move
entities between worlds.

I think this allows for a lot of flexibilty. The app
could have one world per sector for a CS app. For a
FPS you could have one world for objects at rest, one
for objects that never rest and are still computed
when out of sight, and one for each player ( which
contains all entities close to that player ). For a
networked game you could have clients compute their
own worlds and send the results back to the server.
It would really be different for different
applications.

One disadvantage of this approach is the extra
overhead required by lots of worlds ( also some world
management code is needed ). But I think the
advantages far outwiegh these small disadvantage.

A layer could be put on top of csphyziks and collision
detection that would handle all this and try to
generalize things, but I don't know how effective this
would be.

Just thinking out loud :)

- Michael Alexander Ewert
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
Noah Gibbs
2000-02-25 00:38:21 UTC
Permalink
One necessary problem here is that it'd be tough to
have things in different worlds collide/interact. Not
impossible, but very awkward.
However, if that caveat is made clear, I like it.
Besides, if people want everything in the world to
interact, they can put it all in one big ctWorld, and
then the burden of fast and efficient collision,
derivatives and whatnot is on their shoulders.
Post by Michael Ewert
Warning: semi-long rambling post :)
One problem that has been gnawing on the back of my
mind for a while has been one of seperation of the
equations governing physical entities who are
independent of each other.
i.e. During collisions the "best" ( not best
performance but garuanteed not to mess up the
simulation ) handling of collisions is to rewind the
entire simulation back to the point just before the
collision, deal with the collision and then
continue.
A huge drawback to this is that if one entity
collides, then you need to redo _all_ the
computations
for every entity in the world.
Another thing that is desireable is to detect
entities
whose state is not changing ( rest on ground not
moving ) and then not compute those guys until
something happens to them.
The best optimization of the physics lib is
obviously
to minimize the number of computations every frame.
Another constraint I have is that I don't want the
physics lib to duplicate all the 3d data in the
world.
I came to the conclusion that the "cleanest" way to
seperate entities is to have non-interacting
entities
exist in their own worlds ( class ctWorld ). This
sort of dumps the responsibility for this sort of
thing on the application. csphyziks would supply
some
interface to support this kind of thing, i.e. like
callbacks when an object is at rest or start moving
from rest.
So it would be the responsibility of the app to move
entities between worlds.
I think this allows for a lot of flexibilty. The
app
could have one world per sector for a CS app. For a
FPS you could have one world for objects at rest,
one
for objects that never rest and are still computed
when out of sight, and one for each player ( which
contains all entities close to that player ). For a
networked game you could have clients compute their
own worlds and send the results back to the server.
It would really be different for different
applications.
One disadvantage of this approach is the extra
overhead required by lots of worlds ( also some
world
management code is needed ). But I think the
advantages far outwiegh these small disadvantage.
A layer could be put on top of csphyziks and
collision
detection that would handle all this and try to
generalize things, but I don't know how effective
this
would be.
Just thinking out loud :)
- Michael Alexander Ewert
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
_______________________________________________
Crystal-main mailing list
http://lists.sourceforge.net/mailman/listinfo/crystal-main
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
dyad
2000-02-25 00:42:21 UTC
Permalink
Good thinking is best out loud! I like yer ideas.
Post by Michael Ewert
Just thinking out loud :)
- Michael Alexander Ewert
Michael Ewert
2000-02-25 00:55:15 UTC
Permalink
Post by Noah Gibbs
One necessary problem here is that it'd be tough
to
have things in different worlds collide/interact.
Not
impossible, but very awkward.
Right. Although possible to do in two worlds ( no
physically correctness garaunteed ), the app should
move things so both entities are in one world once it
knows that they are interacting. Otherwise wierd
things could happen, like the law of conservation of
energy being violated.

I should probably put a reference to which ctWorld a
entity belongs to into ctEntity. That also would
allow the phyziks lib to optionally detect when two
objects not of the same world interact. This does get
a bit messy because collision detection has to factor
in there as well. Probably still best left to the app
to figure it out.
Post by Noah Gibbs
However, if that caveat is made clear, I like it.
Besides, if people want everything in the world to
interact, they can put it all in one big ctWorld,
and
then the burden of fast and efficient collision,
derivatives and whatnot is on their shoulders.
Post by Michael Ewert
Warning: semi-long rambling post :)
One problem that has been gnawing on the back of
my
Post by Michael Ewert
mind for a while has been one of seperation of the
equations governing physical entities who are
independent of each other.
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
Aaron Drew
2000-02-25 02:23:30 UTC
Permalink
Why not just flag an object as being static? It would save the complications
with handling inter-world collisions. Also, what happens if say, a player
bumps a table (which is generally still) and it moves? If using flags, a
statement such as:

while(objects available)
{
if(object->static || <object velocity vector nill)
continue;
// Process object
}

could be used without much hassle to process objects that are 'active' and
might be a bit neater..

I'm not sure. Still havn't had a chance to look through the code in depth..


-----Original Message-----
From: Michael Ewert <***@yahoo.com>
To: crystal-***@lists.sourceforge.net <crystal-***@lists.sourceforge.net>
Date: Friday, 25 February 2000 10:44
Subject: Re: [CsMain] Physics worlds
Post by Michael Ewert
Post by Noah Gibbs
One necessary problem here is that it'd be tough
to
have things in different worlds collide/interact.
Not
impossible, but very awkward.
Right. Although possible to do in two worlds ( no
physically correctness garaunteed ), the app should
move things so both entities are in one world once it
knows that they are interacting. Otherwise wierd
things could happen, like the law of conservation of
energy being violated.
I should probably put a reference to which ctWorld a
entity belongs to into ctEntity. That also would
allow the phyziks lib to optionally detect when two
objects not of the same world interact. This does get
a bit messy because collision detection has to factor
in there as well. Probably still best left to the app
to figure it out.
Post by Noah Gibbs
However, if that caveat is made clear, I like it.
Besides, if people want everything in the world to
interact, they can put it all in one big ctWorld,
and
then the burden of fast and efficient collision,
derivatives and whatnot is on their shoulders.
Post by Michael Ewert
Warning: semi-long rambling post :)
One problem that has been gnawing on the back of
my
Post by Michael Ewert
mind for a while has been one of seperation of the
equations governing physical entities who are
independent of each other.
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
_______________________________________________
Crystal-main mailing list
http://lists.sourceforge.net/mailman/listinfo/crystal-main
Jorrit Tyberghein
2000-02-25 07:15:38 UTC
Permalink
Post by Aaron Drew
Why not just flag an object as being static?
Actually that flag already exists for things. Things are marked movable
if they can move.

Greetings,


--
==============================================================================
***@uz.kuleuven.ac.be, University Hospitals KU Leuven BELGIUM

Wobbler thought that California was where good people went when they died.
-- (Terry Pratchett, Only You Can Save Mankind)
==============================================================================
Ben Sego
2000-02-25 14:18:49 UTC
Permalink
Post by Jorrit Tyberghein
Post by Aaron Drew
Why not just flag an object as being static?
Actually that flag already exists for things. Things are marked movable
if they can move.
I think that's different. They were talking about things that _could_ move, but
that currently have no velocity. Since, in a newtonian world, those things won't
move until a velocity is imparted to them (by a collison or by self-motivation)
not including them in the physics computation loop might provide a bit
optimizaton.
Michael Ewert
2000-02-25 19:58:00 UTC
Permalink
Yes, that is an option. I am not sure which way is
better yet. There is still a small performance hit by
keeping sleeping objects in the world due to the way
the physics core views things. I was thinking that
having the external handler deal with sleeping objects
would be good because it would centralize entity-world
management. Determining which objects interact with
each other can not currently be done effectively
within the physics lib because it lacks the 3d world
data needed for that and also app specific data.
Post by Aaron Drew
Why not just flag an object as being static? It
would save the complications
with handling inter-world collisions. Also, what
happens if say, a player
bumps a table (which is generally still) and it
moves? If using flags, a
while(objects available)
{
if(object->static || <object velocity vector
nill)
continue;
// Process object
}
could be used without much hassle to process objects
that are 'active' and
might be a bit neater..
I'm not sure. Still havn't had a chance to look
through the code in depth..
-----Original Message-----
Date: Friday, 25 February 2000 10:44
Subject: Re: [CsMain] Physics worlds
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
Aaron Drew
2000-02-26 01:47:47 UTC
Permalink
I see your point and agree that it could cut back on processing overhead for
stationary entities but does the added complication to the engine warrent
the seemingly marginal speed gains? Couldn't a similar thing be achieved via
a simple test before executing any physics code to see what the object is
doing? Also, how will this work in a scenario such that:

Object A is on top of object B. Both are stationary.
Object B is taken out from under object A.

If the physics code is skipped for stationary objects then something like
this may not work the way it should.
I don't know for sure. You all seem to have a much better feel for the
engine than I do. I'm just throwing thoughts around the place...

-----Original Message-----
From: crystal-main-***@lists.sourceforge.net
[mailto:crystal-main-***@lists.sourceforge.net]On Behalf Of Michael
Ewert
Sent: Saturday, February 26, 2000 6:58 AM
To: crystal-***@lists.sourceforge.net
Subject: Re: [CsMain] Physics worlds





Yes, that is an option. I am not sure which way is
better yet. There is still a small performance hit by
keeping sleeping objects in the world due to the way
the physics core views things. I was thinking that
having the external handler deal with sleeping objects
would be good because it would centralize entity-world
management. Determining which objects interact with
each other can not currently be done effectively
within the physics lib because it lacks the 3d world
data needed for that and also app specific data.
Post by Aaron Drew
Why not just flag an object as being static? It
would save the complications
with handling inter-world collisions. Also, what
happens if say, a player
bumps a table (which is generally still) and it
moves? If using flags, a
while(objects available)
{
if(object->static || <object velocity vector
nill)
continue;
// Process object
}
could be used without much hassle to process objects
that are 'active' and
might be a bit neater..
I'm not sure. Still havn't had a chance to look
through the code in depth..
-----Original Message-----
Date: Friday, 25 February 2000 10:44
Subject: Re: [CsMain] Physics worlds
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
Michael Ewert
2000-02-26 21:44:23 UTC
Permalink
Post by Aaron Drew
I see your point and agree that it could cut back on
processing overhead for
stationary entities but does the added complication
to the engine warrent
I shouldn't have mentioned speed. It is pretty
irrelevant here.

It's not extra code in the engine. It's extra code in
the app or game api. Maybe in csclear and/or csgame.
Post by Aaron Drew
the seemingly marginal speed gains? Couldn't a
similar thing be achieved via
a simple test before executing any physics code to
see what the object is
doing? Also, how will this work in a scenario such
Thats the whole problem. "Seeing what the object is
doing" is something that can't be accomplished by the
physics lib alone. At it's core the physics lib knows
nothing about 3d geometry. Perhaps it could with some
clever callbacks, but I think that is the wrong
approach to take.

The physics lib is a general computational physics
engine, I think that compliments crystal space well,
which is a general rendering engine. The physics lib
at its core just solves a bunch of equations, it
doesn't even know what those equations are for. It is
fed the current state, and a function that resolves
the derivitive vector of that state and it will return
the new state. Right now the only "meat" on those
bones is a rigid body dynamics layer. Noah Gibbs has
some plans for the physics lib that have _nothing_ to
do with rigid-body dynamics.
Post by Aaron Drew
Object A is on top of object B. Both are stationary.
Object B is taken out from under object A.
If the physics code is skipped for stationary
objects then something like
this may not work the way it should.
We can generalize this to: object A depends on object
B for calculating it's state.

Three issues here. Knowing how and if A depends on B.
Knowing that A and B can be put to sleep. Knowing
when to wake either of them up.

The first issue is the one I am trying to address
using seperate worlds to seperate entities that don't
depend on each other. This will minimize wasteful
re-computation.

Different ways A can depend on B.
- Force dependancy: i.e. a spring attaches A to B
* belongs in physics

- Spatial dependancy: A and B are close enough and
moving with enough speed that they may collide soon.
* belongs in collision detection

- Structural dependancy: A is part of B
* maybe physics, maybe application level

- Contact dependancy: A is temporarily part of B ( in
resting contact or something ).
* maybe physics maybe collision detection maybe
application

- Logical dependancy: A is B's pet and B can tell A to
go fetch things ( game logic ). Or when A enters a
certain area B accelerates towards it.
* application

- Maybe others I haven't thought of.

What I am saying is that the physics lib will have a
really tough, messy time figuring out what depends on
what. And when it does the logic needed to handle
weeding out dependancies within a single world are
brutal and maybe impossible to get robust and
error-free. Moving the responsiblity of deciding what
depends on what up to the app layer makes things much
cleaner ( hopefully :).

The sleeping objects thing is a bit different, but
still related. I haven't given it a whole lot of
thought yet.

Ok so here is an example of how your example could be
handled.

The two objects somehow come to rest on each other (
or are initialized that way ). This is done when the
collision detection lib passes the seperation distance
of the closest features to the physics lib. The
physics lib does the collision response, which results
in an response impulse of effectivly 0. That
indicates the objects are in resting contact. Since
the objects are now in resting contact they are added
to the resting contact solver. Then they are put to
sleep once they stop moving/accelerating.... Ok, yeah
it would be much better for the physics to decide that
the stack of objects has gone to sleep.

Right, so physics entities will have a flag that says
if they are asleep or not. Which can be set
internally or externally. That sleep flag will
indicate if an entities derivitive should be just set
to 0 or calculated.

So to continue your example. Something would change
the state of B or the calculation of the derivitive of
B. If this was done by a call to ctEntity::set_v() or
ctEntity::add_force() then the sleep bit would be
turned off by those methods. If B was in a collision
then the sleep bit would be turned off by the
collision response code within physics.... So really
waking up is completely contained within the physics
lib as well as long as there is no way for external
factors to directly change the state or calculation of
state without going through some physics lib method.
Post by Aaron Drew
I don't know for sure. You all seem to have a much
better feel for the
engine than I do. I'm just throwing thoughts around
the place...
Throwing thoughts around tends to stir up more
thoughts, which is a good thing :)
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com
Daníel Guðbjartsson
2000-02-27 11:29:06 UTC
Permalink
Warning: I refuse to appologise for rambling :)

The current physics simulations are based on a structure that updates the
state of all components at once. If S(t) is the combined physical state
(location, orientation, velocity and angular velocity) of all components,
then roughly speaking the simulations approximate S(t + Dt) given S(t) and
the forces that affect the components (force infers first derivative of
velocity). The simulation is not exact in the sence that they do not
produce the same results as continuous time caclulations, but it has the
nice property that the as the time increments approach 0, the simulation
approaches the continuous time result (given some continuity conditions).

Another alternative is turn based simulation. Assume that there are n
components with state functions S_1(t), ..., S_n(t), (S(t) = {S_1(t), ...,
S_n(t)} ) then update the states in the following manner:

For i = 1, ..., n calculate S_i(t + Dt) given S_1(t + Dt), ..., S_(i-1)(t +
Dt),
S_i(t), ..., S_n(t) and the forces affecting the i-th component.

This procedure does not have the nice property that the limiting case
apporaches the continuous time case in general. In the special case where
the components are independant of each other, the property is fulfilled
though.

The turn based simulation can be extended by first grouping components
"that are linked" at time t, and then performing turnbased simulation on
the groups. It is not quite easy to say what linked means, but at least two
components are linked if a force is excerted on one because of the other,
two components are linked if they are at a 0 distance from one another
(potentially at collision) and two components are linked if one can excert
a force on the other (e.g. two bodies of an N-body or two bodies connected
by a spring). In our case two components should also be linked if the user
says they are. The physics engine should be the one to determine which
bodies are linked. I should be safe to assume that if two components are
not linked at t then there exsists a Dt > 0 s.t. they are not linked at t +
Dt (this is just continuity). If this assumption is met then the good
property above is fulfilled.

The main disadvantage of this extendend turn based simulation I can think
of is that if component i has been handled and then j affectes i, e.g. by
colliding with it, would require special attention. The simplest thing to
do store the force applied on i by j and let them take effect in the next
time interval. Another potential remedy for this is to do the following: If
group j affects group i, and the state of i has allready been updated,
rewind the state of i, join groups i and j and update their state. This
approach would have rather bad worst case behaviour but proably good
behaviour in practise.

The benefit of the turn based simulation should be obvious, when a
component collides only its group has to be rewound. I feel this approach
would automatically take care of seperating the calculations into
independant parts.

The turn based approach is similar to Ewert's suggestion of splitting the
world into subworlds, but has the advantage of natural interaction between
worlds. By allowing the user to tell the physics engine which components
should be linked, the user should have sufficient control over the simulation.

Daniel
CrystalSpace Developer
0100-02-28 19:52:31 UTC
Permalink
Post by Michael Ewert
Another thing that is desireable is to detect entities
whose state is not changing ( rest on ground not
moving ) and then not compute those guys until
something happens to them.
This is fairly easy to do:
- Give the object a boolean property.
- Initialize it to true when it's loaded / created.
- When CD goes through the list, skip objects with it set to false.
- For CD, first set it to false, then process.
- When anything moves, rotates, or otherwise changes in any way
that would affect CD, set that bit to true.
Post by Michael Ewert
... For a
FPS you could have one world for objects at rest, one
for objects that never rest and are still computed
when out of sight, and one for each player ( which
contains all entities close to that player ).
Then how would you collide between objects in different worlds?
I think splitting it up like that is over-complicating things.
Just use the boolean check I gave above, or something equally
straight-forward.

Also, I think there is a need for an "object" grouping of
geometric structure at the low level that simply collects
different objects. That way, you could have a bounding
box for _any_ group of structure, no matter what it was,
and if the structure was complex enough, you could have
sub-"objects" that each had their own. Hmm... I may
code this up...


Jesse
Michael Ewert
2000-02-28 17:59:47 UTC
Permalink
Post by Daníel Guðbjartsson
Another alternative is turn based simulation. Assume
that there are n
components with state functions S_1(t), ..., S_n(t),
(S(t) = {S_1(t), ...,
S_n(t)} ) then update the states in the following
For i = 1, ..., n calculate S_i(t + Dt) given S_1(t
+ Dt), ..., S_(i-1)(t +
Dt),
S_i(t), ..., S_n(t) and the forces affecting the
i-th component.
This procedure does not have the nice property that
the limiting case
apporaches the continuous time case in general. In
the special case where
the components are independant of each other, the
property is fulfilled
though.
Very cool. I like it.
Post by Daníel Guðbjartsson
The turn based simulation can be extended by first
grouping components
"that are linked" at time t, and then performing
turnbased simulation on
the groups.
You update the individual groups using simultaneous
simulation right? So you could probably use adaptive
step-sizing quite effectively. Or even use different
ODE solvers for the different groups.
Post by Daníel Guðbjartsson
The main disadvantage of this extendend turn based
simulation I can think
of is that if component i has been handled and then
j affectes i, e.g. by
colliding with it, would require special attention.
The simplest thing to
do store the force applied on i by j and let them
take effect in the next
time interval. Another potential remedy for this is
to do the following: If
group j affects group i, and the state of i has
allready been updated,
rewind the state of i, join groups i and j and
update their state. This
approach would have rather bad worst case behaviour
but proably good
behaviour in practise.
This is still much better than the one big world
approach where everything is rewound.

Still there could be an ugly chaining problem.
Something in group A collides with something in group
B. Then something in group C collides with something
in group AB. and so on and so on until there is only
one big group. But I guess that is what needs to be
done.

The trick will be setting the threshold for how
"close" objects have to be to be in the same group.
Too much and things degenerate into one big group.

Might be some other collision detection implications
with this scheme.
Post by Daníel Guðbjartsson
The benefit of the turn based simulation should be
obvious, when a
component collides only its group has to be rewound.
I feel this approach
would automatically take care of seperating the
calculations into
independant parts.
The turn based approach is similar to Ewert's
suggestion of splitting the
world into subworlds, but has the advantage of
natural interaction between
worlds. By allowing the user to tell the physics
engine which components
should be linked, the user should have sufficient
control over the simulation.
Overall I think this is quite good. And it seems like
it should work.
Post by Daníel Guðbjartsson
Daniel
_______________________________________________
Crystal-main mailing list
http://lists.sourceforge.net/mailman/listinfo/crystal-main
__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com

Continue reading on narkive:
Loading...