Real-Time Physics Simulation Forum

High Level simulator pseudo code

2005-12-20T10:34:03+00:00

Hi all, this is my first post here, so please bare with me.

jmc : Thanks for the pseudo code, I've just started out on a simulator, and I'd have written exaclty the same pseudo code as you. It's nice to know you're thinking along the same lines...

You have:

build_collision_queue:
empty queue
foreach body i
foreach body j
calculate TOI between i & j
insert TOI,i,j into priority queue

Do you have a cunning way of elimating redundant checks between bodies you've already tested? For example you wouldn't want to test body 0 with body 2, then later in your loop test body 2 with body 0 would you? (as you would be calculating the forces twice).

I *think* if you insert the line:

build_collision_queue:
empty queue
foreach body i
foreach body j
if(j >= i){ // This line here.
calculate TOI between i & j
insert TOI,i,j into priority queue
}

This would stop any redundant checks. I realise I'm being pedantic, but I'm just starting my own simulator and I want to be aware of the pitfalls.

Also, as you are only interested in collisions that are earlier than your current earliest TOI, I assume you dont need to add them to the the list?

We might be able to refine the pseudo code to a slightly lower level, I think people new to this area would find very useful (myself included).

Thanks,

Steve.

Statistics: Posted by steveh — Tue Dec 20, 2005 10:34 am

Re: High Level simulator pseudo code

2005-08-03T09:47:36+00:00

I replied earlier, but changed my mind, deleted it and decided to reformulate it.

Hi, this is my first post. So let me introduce myself. I'm John McCutchan, I go to McMaster University in Hamilton, Ontario. I have been interested in 3D Physics engines for about a year now.

Last year I wrote a rigid body simulator based on the paper 'Non-convex rigid bodies with stacking'. I have since replaced the collision detection algorithm with GJK. Currently I am trying to implement ray casting and TOI GJK.

Can you share anything ? Do you have a demo ? Would be nice !

Lately I have been thinking about the high level simulator algorithm. I'm about half way through the timewarp paper by Mirtich. But, I'm starting to think that the timewarp algorithm is over kill. As far as I can see, there are two possible main loops.

1:
Code:
loop  foreach body i    foreach body j      calculate TOI between i & j      update i & j to TOI      respond to collisionend loop
or 2:
Code:
build_collision_queue:  empty queue  foreach body i    foreach body j      calculate TOI between i & j      insert TOI,i,j into priority queueloop  build_collision_queue  while (NOT_EMPTY collision_queue)    TOI = FRONT(collision_queue)    update simulation to TOI    respond to collisions    build_collision_queue ()end loop
From what I can tell, 2 should work perfectly. And 1 should work about as well as a discrete collision detection system.

I'm curious what other peoples main loops look like. Are people using the timewarp algorithm? What kind of overhead does the timewarp algorithm have?

-John

Doom 3 approach is similar to your mainloop 1:

Code:

loop- (continuous) collision detection for all bodies, to gather contact points- resolve constraints using LCP for ragdoll- foreach body i- foreach body japply impulse on contactcalculate toi, integrate to a safe (non-penetrating) position

Loop 2 is more global correct solution for time of impact. However every time of impact event will cause ALL objects to be integrated again etc.
This can be a big overhead. This is exactly what Time Warp solves:

Make an initial estimate of independent groups. Then simulate each group independently, with your loop 2. If the estimation fails, which leads to merging (fusion) or splitting (fision) groups, time warp messages are send, perhaps roll back (especially when you implement this in a parallel way, and do optimistic approach, assuming estimation was fine).

The cost of timewarp can be reduced in several ways. More conservative estimation will avoid fusion/fision. You can also ignore most fisions (splits).

Statistics: Posted by Erwin Coumans — Wed Aug 03, 2005 9:47 am

Missing reply?

2005-08-03T03:14:33+00:00

What happened to the reply that I saw earlier?

Statistics: Posted by John McCutchan — Wed Aug 03, 2005 3:14 am

High Level simulator pseudo code

2005-08-02T02:05:27+00:00

Hi, this is my first post. So let me introduce myself. I'm John McCutchan, I go to McMaster University in Hamilton, Ontario. I have been interested in 3D Physics engines for about a year now.

Last year I wrote a rigid body simulator based on the paper 'Non-convex rigid bodies with stacking'. I have since replaced the collision detection algorithm with GJK. Currently I am trying to implement ray casting and TOI GJK.

Lately I have been thinking about the high level simulator algorithm. I'm about half way through the timewarp paper by Mirtich. But, I'm starting to think that the timewarp algorithm is over kill. As far as I can see, there are two possible main loops.

1:

loop
foreach body i
foreach body j
calculate TOI between i & j
update i & j to TOI
respond to collision
end loop

or 2:

build_collision_queue:
empty queue
foreach body i
foreach body j
calculate TOI between i & j
insert TOI,i,j into priority queue

loop
build_collision_queue
while (NOT_EMPTY collision_queue)
TOI = FRONT(collision_queue)
update simulation to TOI
respond to collisions
build_collision_queue ()
end loop

From what I can tell, 2 should work perfectly. And 1 should work about as well as a discrete collision detection system.

I'm curious what other peoples main loops look like. Are people using the timewarp algorithm? What kind of overhead does the timewarp algorithm have?

-John

Statistics: Posted by John McCutchan — Tue Aug 02, 2005 2:05 am