Physics, world representation

[Massimo Del Zotto]

Hello to all contributors.
I need some help in understanding how physics libraries are supposed to be
used. I am referring to Bullet in particular as it appears to have
everything I need with a liberal, cross-platform licensing.
So far I have been experimenting with physics for a few months with mixed
results at best. As I write this, I have just resolved an issue with
player-controlled objects which has been keeping me awake at night for
quite a while so I'm thinking at the next problem I see on the horizon.

Now, in Bullet there are three kinds of objects:

1. STAtic
2. DYNamic
3. KINematic

I think I have finally got a kinematic behaviour that works right for my
game.
The point of this email is the interaction of dynamic objects and a world
built from static objects.
I started modelling my world by procedurally generating a set of hulls, in
most cases, those were boxes. I don't remember the exact numbers but I'd
say my current data set for the world is about 96% boxes (mostly
axis-aligned) and 4% hulls.
The *main problem* I've observed is that *DYN objects won't interact
properly with static collision geometry at bounduaries*. I am not well
aware if this happens as I allow the static geometry to overlap or not.
That is, I don't know if adjusting the collision geometry by a margin would
fix that.

The current line of thinking in Bullet forums appears to be using generic
trimeshes and GIMPACT collision. Trimeshes allow to mark internal edges and
thus provide proper information to dynamic bodies to interact properly.

Now, let's leave out the fact that Bullet's demo about internal edges does
not seem to work as intended on my system.
Let's leave out the problem that I would need to write some code in the
filter to brute-force internal edge detection.
Let's start by considering that in general, I don't really feel ok with
feeding collision systems with graphics-oriented meshes. It *might* work
for now, but I'm afraid someone should be producing a reduced polycount
mesh.

But my main problem is that I feel like I'm seriously missing
something. For example, Bullet has a BSP demo from which they build
collision geometry. Now, BSPs are strictly related to convex hulls so it
appears to me that worlds are meant to be built as an assembly of multiple
rigid bodies rather than a single big trimesh. BSP demo *appears *to work
ok with dynamic rigid bodies to me.

So in short, *I am asking for a direction is choosing a world
representation for my collisions*. *Maybe collision shapes are only meant
to be used for dynamics, with trimeshes being the only way to represent a
world?*

I cannot quite see a big picture with those things, so I start thinking
perhaps I've misunderstood everything since day 0.

Elaborations are welcome.

Massimo

[Jon Watte]

I've been wanting to learn Bullet, but time is scarce... My physics
experience comes from a few other libraries, both Open Source and
commercial. The main ones are ODE, JigLib, PhysX, and some home-grown
systems. Here's my generalization of how they all work, more or less (with
slight variations in naming and API):

First, collision detection, done between shapes/hulls/boxes, is separate
from physical movement/rotation, done by bodies. You can have one without
the other.

In general, the "world" built from "static" geometries is fixed. It won't
move, take damage, or do anything other than provide impenetrable barriers.
Important to note is that the collision shapes in this world have no rigid
bodies at all in the simulation/solver. Resolving a collision between a
static geometry and a geometry tied to a dynamic body means moving only the
dynamic body. Another use for no-rigid-body colliders is volumes used for
triggers/detectors -- in that case, the "static" geometries don't even
provide any collision response forces.
Because static geometry doesn't move, static geometry won't typically be
tested against other static geometry, so most libraries actually work just
fine with intersecting static geometry. However, static geometry which has
surfaces that alias (coplanar, or close to it,) may generate bad contact
information for dynamic objects that contact.

"Dynamic" is used for anything that moves. "Dynamic" means that you can
receive forces, as well as apply them to others. "Dynamic" also means that
the solver will resolve geometry intersections by pushing both objects in
inverse proportion to their mass. (CCD such as used in Bullet may "resolve"
by simply moving the object a shorter amount of time through the time step
-- that's one of the things I've been wanting to learn about Bullet)

"Kinematic" is somewhat of a mix between the two. It's a body that can be
moved, but the body doesn't participate in incoming force resolution, only
in outgoing force generation. There is some variability here -- some
kinematic bodies tied to collision geometries will "stop" when running into
static geometries. Thus, a dynamic body that hits a kinematic body will be
resolved entirely by moving the dynamic body, not affecting the kinematic
body.

"Static" geometry, which really means geometry without a dynamic rigid
body, can generally be whatever you want -- trimeshes, convex hulls,
half-open planes, boxes, cylinders, spheres, ... Whatever fits your "game
level" and won't move around in the game design. Building a trimesh out of
a BSP tree and using that as static geometry for a level is a fine way to
go about things. Regarding your understanding of BSP geometry:
- BSP can describe convex geometry, because each plane only splits the
current half-space sub-cell, not the entire world.
- Worlds don't typically use bodies at all, especially in BSP based games
like Quake or whatnot. Some physics APIs may still want you to talk about
"static bodies," but these don't partake in the linear constraint solver
used for force/body/collision interaction.

"Dynamic" geometry, which really means geometry with a dynamic rigid body,
generally has some constraints, especially with respect to concave bits.
Typically, it's very hard to generate a sane representation of how you're
supposed to "resolve" contact, or penetration, between two concave
geometries. Thus, trimeshes used for dynamic movement are often not as
robust or well-performing as convex geometries of various sorts. For a CCD
system, you may be able to calculate time-of-first-contact between two
moving convex geometries, but that's likely to use a lot of CPU. Might
still be worth it for cases where there's really only a few things moving
-- like a space ship docking with a space station.

Finally, I've found that, for me, it works better to avoid kinematic
bodies, and simply drive user agents (avatars, cars, tanks, whatever) using
somewhat large forces and a PID controller. I know where I want the avatar
to be next frame; I know where it is and what its current velocity and spin
is; I can apply appropriate forces/torques (controlled by a PID controller)
to "trend towards" that goal. This ends up having pretty good interaction
with various obstacles, piles of rigid body debris, stacks of crates, etc.
For higher-fidelity simulations, you can do the same thing for an animated
avatar; play back the animation as a force generator (based on a PID
controller per joint, with the animation as target.)


Sincerely,

Jon Watte


--
"I pledge allegiance to the flag of the United States of America, and to
the republic for which it stands, one nation indivisible, with liberty and
justice for all."
~ Adopted by U.S. Congress, June 22, 1942

Post by Massimo Del Zotto
Hello to all contributors.
I need some help in understanding how physics libraries are supposed to be
used. I am referring to Bullet in particular as it appears to have
everything I need with a liberal, cross-platform licensing.
So far I have been experimenting with physics for a few months with mixed
results at best. As I write this, I have just resolved an issue with
player-controlled objects which has been keeping me awake at night for
quite a while so I'm thinking at the next problem I see on the horizon.
1. STAtic
2. DYNamic
3. KINematic
I think I have finally got a kinematic behaviour that works right for my
game.
The point of this email is the interaction of dynamic objects and a world
built from static objects.
I started modelling my world by procedurally generating a set of hulls, in
most cases, those were boxes. I don't remember the exact numbers but I'd
say my current data set for the world is about 96% boxes (mostly
axis-aligned) and 4% hulls.
The *main problem* I've observed is that *DYN objects won't interact
properly with static collision geometry at bounduaries*. I am not well
aware if this happens as I allow the static geometry to overlap or not.
That is, I don't know if adjusting the collision geometry by a margin would
fix that.
The current line of thinking in Bullet forums appears to be using generic
trimeshes and GIMPACT collision. Trimeshes allow to mark internal edges and
thus provide proper information to dynamic bodies to interact properly.
Now, let's leave out the fact that Bullet's demo about internal edges does
not seem to work as intended on my system.
Let's leave out the problem that I would need to write some code in the
filter to brute-force internal edge detection.
Let's start by considering that in general, I don't really feel ok with
feeding collision systems with graphics-oriented meshes. It *might* work
for now, but I'm afraid someone should be producing a reduced polycount
mesh.
But my main problem is that I feel like I'm seriously missing
something. For example, Bullet has a BSP demo from which they build
collision geometry. Now, BSPs are strictly related to convex hulls so it
appears to me that worlds are meant to be built as an assembly of multiple
rigid bodies rather than a single big trimesh. BSP demo *appears *to work
ok with dynamic rigid bodies to me.
So in short, *I am asking for a direction is choosing a world
representation for my collisions*. *Maybe collision shapes are only meant
to be used for dynamics, with trimeshes being the only way to represent a
world?*
I cannot quite see a big picture with those things, so I start thinking
perhaps I've misunderstood everything since day 0.
Elaborations are welcome.
Massimo
_______________________________________________
Sweng-Gamedev mailing list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

[pontus birgersson]

Finally, I've found that, for me, it works better to avoid kinematic bodies, and simply drive user agents (avatars, cars, tanks, whatever) using somewhat large forces and a PID controller. I know where I want the avatar to be next frame; I know where it is and what its current velocity and spin is; I can apply appropriate forces/torques (controlled by a PID controller) to "trend towards" that goal. This ends up having pretty good interaction with various obstacles, piles of rigid body debris, stacks of crates, etc. For higher-fidelity simulations, you can do the same thing for an animated avatar; play back the animation as a force generator (based on a PID controller per joint, with the animation as target.)
I tried something like this for animation once and I found it to be very prone to oscillations due to forces compensating one another between frames. Did you do something special in order to cope with this? BTW what is a PID controller?

Regards
Pontus

From: Jon Watte
Sent: Monday, June 11, 2012 8:12 PM
To: sweng-***@midnightryder.com
Subject: Re: [Sweng-Gamedev] Physics, world representation

I've been wanting to learn Bullet, but time is scarce... My physics experience comes from a few other libraries, both Open Source and commercial. The main ones are ODE, JigLib, PhysX, and some home-grown systems. Here's my generalization of how they all work, more or less (with slight variations in naming and API):

First, collision detection, done between shapes/hulls/boxes, is separate from physical movement/rotation, done by bodies. You can have one without the other.

In general, the "world" built from "static" geometries is fixed. It won't move, take damage, or do anything other than provide impenetrable barriers. Important to note is that the collision shapes in this world have no rigid bodies at all in the simulation/solver. Resolving a collision between a static geometry and a geometry tied to a dynamic body means moving only the dynamic body. Another use for no-rigid-body colliders is volumes used for triggers/detectors -- in that case, the "static" geometries don't even provide any collision response forces.
Because static geometry doesn't move, static geometry won't typically be tested against other static geometry, so most libraries actually work just fine with intersecting static geometry. However, static geometry which has surfaces that alias (coplanar, or close to it,) may generate bad contact information for dynamic objects that contact.

"Dynamic" is used for anything that moves. "Dynamic" means that you can receive forces, as well as apply them to others. "Dynamic" also means that the solver will resolve geometry intersections by pushing both objects in inverse proportion to their mass. (CCD such as used in Bullet may "resolve" by simply moving the object a shorter amount of time through the time step -- that's one of the things I've been wanting to learn about Bullet)

"Kinematic" is somewhat of a mix between the two. It's a body that can be moved, but the body doesn't participate in incoming force resolution, only in outgoing force generation. There is some variability here -- some kinematic bodies tied to collision geometries will "stop" when running into static geometries. Thus, a dynamic body that hits a kinematic body will be resolved entirely by moving the dynamic body, not affecting the kinematic body.

"Static" geometry, which really means geometry without a dynamic rigid body, can generally be whatever you want -- trimeshes, convex hulls, half-open planes, boxes, cylinders, spheres, ... Whatever fits your "game level" and won't move around in the game design. Building a trimesh out of a BSP tree and using that as static geometry for a level is a fine way to go about things. Regarding your understanding of BSP geometry:
- BSP can describe convex geometry, because each plane only splits the current half-space sub-cell, not the entire world.
- Worlds don't typically use bodies at all, especially in BSP based games like Quake or whatnot. Some physics APIs may still want you to talk about "static bodies," but these don't partake in the linear constraint solver used for force/body/collision interaction.

"Dynamic" geometry, which really means geometry with a dynamic rigid body, generally has some constraints, especially with respect to concave bits. Typically, it's very hard to generate a sane representation of how you're supposed to "resolve" contact, or penetration, between two concave geometries. Thus, trimeshes used for dynamic movement are often not as robust or well-performing as convex geometries of various sorts. For a CCD system, you may be able to calculate time-of-first-contact between two moving convex geometries, but that's likely to use a lot of CPU. Might still be worth it for cases where there's really only a few things moving -- like a space ship docking with a space station.

Finally, I've found that, for me, it works better to avoid kinematic bodies, and simply drive user agents (avatars, cars, tanks, whatever) using somewhat large forces and a PID controller. I know where I want the avatar to be next frame; I know where it is and what its current velocity and spin is; I can apply appropriate forces/torques (controlled by a PID controller) to "trend towards" that goal. This ends up having pretty good interaction with various obstacles, piles of rigid body debris, stacks of crates, etc. For higher-fidelity simulations, you can do the same thing for an animated avatar; play back the animation as a force generator (based on a PID controller per joint, with the animation as target.)


Sincerely,

Jon Watte


--
"I pledge allegiance to the flag of the United States of America, and to the republic for which it stands, one nation indivisible, with liberty and justice for all."
~ Adopted by U.S. Congress, June 22, 1942




On Mon, Jun 11, 2012 at 12:54 AM, Massimo Del Zotto <***@gmail.com> wrote:

Hello to all contributors.
I need some help in understanding how physics libraries are supposed to be used. I am referring to Bullet in particular as it appears to have everything I need with a liberal, cross-platform licensing.
So far I have been experimenting with physics for a few months with mixed results at best. As I write this, I have just resolved an issue with player-controlled objects which has been keeping me awake at night for quite a while so I'm thinking at the next problem I see on the horizon.

Now, in Bullet there are three kinds of objects:
1.. STAtic
2.. DYNamic
3.. KINematic
I think I have finally got a kinematic behaviour that works right for my game.
The point of this email is the interaction of dynamic objects and a world built from static objects.
I started modelling my world by procedurally generating a set of hulls, in most cases, those were boxes. I don't remember the exact numbers but I'd say my current data set for the world is about 96% boxes (mostly axis-aligned) and 4% hulls.
The main problem I've observed is that DYN objects won't interact properly with static collision geometry at bounduaries. I am not well aware if this happens as I allow the static geometry to overlap or not. That is, I don't know if adjusting the collision geometry by a margin would fix that.

The current line of thinking in Bullet forums appears to be using generic trimeshes and GIMPACT collision. Trimeshes allow to mark internal edges and thus provide proper information to dynamic bodies to interact properly.

Now, let's leave out the fact that Bullet's demo about internal edges does not seem to work as intended on my system.
Let's leave out the problem that I would need to write some code in the filter to brute-force internal edge detection.
Let's start by considering that in general, I don't really feel ok with feeding collision systems with graphics-oriented meshes. It might work for now, but I'm afraid someone should be producing a reduced polycount mesh.

But my main problem is that I feel like I'm seriously missing something. For example, Bullet has a BSP demo from which they build collision geometry. Now, BSPs are strictly related to convex hulls so it appears to me that worlds are meant to be built as an assembly of multiple rigid bodies rather than a single big trimesh. BSP demo appears to work ok with dynamic rigid bodies to me.

So in short, I am asking for a direction is choosing a world representation for my collisions. Maybe collision shapes are only meant to be used for dynamics, with trimeshes being the only way to represent a world?

I cannot quite see a big picture with those things, so I start thinking perhaps I've misunderstood everything since day 0.

Elaborations are welcome.

Massimo

_______________________________________________
Sweng-Gamedev mailing list
Sweng-***@lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com





--------------------------------------------------------------------------------

[Richard]

[...] BTW what is a PID controller?

<http://en.wikipedia.org/wiki/PID_controller>

[Massimo Del Zotto]

Thank you Jon for your elaborated answer.
It appears I have not pointed out my concerns clearly enough.

I also notice I have not made out clear what is the relationship between
the BSP and the physics.
The idea is this: we need to make dynamics collide with the world. So,
BSP-based engines typically pull out hulls from BSPs (because BSPs,
regardless of the geometry, will describe hulls as well). Either the game
provides the physics API with this information or the world will be
non-solid. That's it. For what it counts, my understanding of BSP appears
to agree with yours.
As a final note about that, let me state that clear: *I do not use BSP and
I don't plan to*.
My current system has a fully decoupled representation for physics.

*My mail is all about what you refer to "coplanar or close to it" geometry.*
When two static rigidbodies are placed near each other the contact
information is indeed garbled. And this is the problem because, as you
notice, it gives issues in resolving the dynamics.
So for example, say we have two boxes with half extents being (.5, .5, .5),
centered at O1=(.5, .0, .0) and O2=(1.5, 0, 0). They'll both generate a
face whose "collision vertices" will be at x=1 yz plane.
This prevents correct behavior of dynamic objects. At the very best, they
will get stuck at the edge. If the forces involved are big
in magnitude then they will (very likely) cause the dynamic object to jump
over the shared plane. This approach also appears to interact poorly with
encroaching resolution.
Not to mention it does not support warping natively. And I cannot figure
out how to walk upstairs without causing hiccups. It also has some
nontrivial implication WRT scripting design.
No, I don't think I will ever go back to dynamic bodies for modelling
player or logic controlled entities.

While we're at it, I would be interested in knowing for what kind of
geometry this system actually works, because I see no way for which it
would work for me. In general, it appears to me modelling "self-moving"
entities by dynamic object is a bit of an overcomplication compared to just
move a kinematic body.
But again,* the problem is not player controlled stuff, the problem is
purely dynamic objects.*

Problem is, if I don't solve the multiple contact issue above, then I won't
be able to use *dynamic objects reliably* at all.

Now, there's a thing I'm thinking about. Considering the two boxes above,
they are not actually (.5, .5, .5) in half length. For some reason I don't
quite understand, they have an *external *margin (other shapes typically
have an *internal *margin). Including the margin, the real half-extents
would be (.54, .54, .54). So the boxes actually overlap a bit. Maybe the
problem would go away if I subtract .04. Can anyone confirm that?

To quote the original message:

main problem I've observed is that DYN[amic] objects won't interact
properly with static collision geometry at [shared] bounduaries.


It would also be interesting to know if and how other libraries deal with
this issue (of collision geometry near each other). In general, the
question remains the same: how should I set up my world to allow dynamic
objects to work as intended?

Thank you,
Massimo

Post by Jon Watte
Because static geometry doesn't move, static geometry won't typically be
tested against other static geometry, so most libraries actually work just
fine with intersecting static geometry. However, static geometry which has
surfaces that alias (coplanar, or close to it,) may generate bad contact
information for dynamic objects that contact.

[Jon Watte]

Post by Massimo Del Zotto
*My mail is all about what you refer to "coplanar or close to it" geometry.*

In systems that generate contact joints (step-based systems,) you can do
post-processing on all the contacts you detect, and merge coincident or
near contacts to try to patch over the problem. In CCD systems, I don't
know exactly what to do. Perhaps there's some location within the
detection/reaction loop which lets you do the same.


So for example, say we have two boxes with half extents being (.5, .5, .5),

Post by Massimo Del Zotto
centered at O1=(.5, .0, .0) and O2=(1.5, 0, 0). They'll both generate a
face whose "collision vertices" will be at x=1 yz plane.
This prevents correct behavior of dynamic objects. At the very best, they
will get stuck at the edge. If the forces involved are

I'm assuming you mean that objects come from outside and collide with both
the objects at x=1.
What you're describing must be a behavior specific to Bullet. In the
systems I have used, the out-facing faces would actually be deemed the
deepest penetrations, and would generate contacts that push the object out.
In general, coincident faces are mostly a problem where they both face the
actual dynamic geometry, in a situation similar to how rendering would
generate Z fighting surfaces.

Post by Massimo Del Zotto
No, I don't think I will ever go back to dynamic bodies for modelling
player or logic controlled entities.

Use what works for you in your game! I'm just reporting what works for me.
(And if you go down that route, you end up with something like Endorphin,
which IMO is super cool ;-)

Post by Massimo Del Zotto
Problem is, if I don't solve the multiple contact issue above, then I
won't be able to use *dynamic objects reliably* at all.

In general, any system will require that some amount of contact
merging/filtering/conditioning is done. For example, you can prefer contact
normals that point towards the center of the collider over contacts that
point away; you can prefer contacts that are deeper to contacts that are
shallower; you can prefer contacts that point opposite to the object
velocity to contacts that point perpendicular or in the same direction as
movement. Some systems have a level of contact filtering built in; others
leave it entirely to the user.

Post by Massimo Del Zotto
Now, there's a thing I'm thinking about. Considering the two boxes above,
they are not actually (.5, .5, .5) in half length. For some reason I don't
quite understand, they have an *external *margin (other shapes typically
have an *internal *margin). Including the margin, the real half-extents
would be (.54, .54, .54). So the boxes actually overlap a bit. Maybe the
problem would go away if I subtract .04. Can anyone confirm that?

That has to be specific to Bullet, and I have no experience to help out
there.


Sincerely,

jw