High Level simulator pseudo code

[John McCutchan]

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

[John McCutchan]

What happened to the reply that I saw earlier?

[Erwin Coumans]

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: Select all

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

or 2:

Code: Select all

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

Doom 3 approach is similar to your mainloop 1:

Code: Select all

loop
- (continuous) collision detection for all bodies, to gather contact points
- resolve constraints using LCP for ragdoll

- foreach body i
- foreach body j
apply impulse on contact
calculate 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).

[steveh]

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.