9 replies to this topic

[jimbo]

Hi

Currently working on a 2d physics engine, but I'm not sure what is the correct term for what i'm doing, thus having a tough time looking up information about it.

some pseudo code:

loop while frameTime
check for collision
if collision found
update at time of earlyiest collision
resolve collided objects
remove the time of collision from frameTime
else exit

I know this method of checking for earliest collision then updating at that time and repeating untill all the time is used up isn't used by all engines. In my book it's called a "time-division engine", does this go by any other names?

Thanks,
Jim.

[fireside]

I think it's more on the collision end of it. ODE uses a separate collision system. It more decides what happens after collision. Depends what you mean by resolve collided objects, of course, because that's mostly what physics engines do. ODE puts things into sleep if they haven't moved for a certain length of time.

[jimbo]

By resolve collided objects I mean adjust their vectors.

so for each frame of the game, it is broken down into smaller slices depending on when collision occurs, kinda like if each frame has sub frames.

I calculate when a collision is going to happen within the frame, adjust the vectors of the collided objects and move all objects to that moment in time, I repeat this until no more collisions happen within the time of the frame.

I would like to know if there is a name for this algorithm/method, and would also like to discuss any issues with it (I have a few already :( ).

[Kenneth Gorking]

From the information you have provided, it sounds like you are doing narrow phase collision detection.

This is usually used in conjuction with broad phase CD, which simply checks to see if 2 objects might collide (often done with axis aligned bounding boxes). If the bounding boxes intersect, then the system proceeds to the narrow phase detection, to find the exact collision points (if any).

[SmokingRope]

I'm just following Ken and assuming you're talking about the collision detection part of this algorithm.

The book "real time collision detection" calls this (sampled motion) or (motion sampling). Just looking at the figure the main drawback is that you will potentially miss a collision between two objects if your sampling frequency is too low.

The only suggested alternative is swept-volumes, which is much like dragging your finger through the frosting on a cake. (And which is usually more difficult to do)

[jimbo]

Yes I think your are correct in what I'm talking about as being narrow phase collision detection.

But the actual algorithm of predicting when two objects will collide as done here
http://www.gamasutra...enhuevel_01.htm and then updating the position of all objects to that time (repeat until all time is used up), is what I'm mainly looking for. I believe that this is not the only algorithm used in narrow phase collision detection, i.e. some get all the collisions in the frameTime and resolve them all at once.

All help is very much appreciated as I'm going around in circles figuring this all out.

Jim.

[jimbo]

According to the wikipedia it would also be considered 'a priori algorithm' as it predicts the time two object collides.

But that does not necessarily describe the updating process i.e. 'resolving' (not sure if this is correct term for updating the trajectories of the collided objects)
each collision in time order rather than all at once.

Thanks
Jim.

[SmokingRope]

I have read about a collision response method that detects all of the collisions, calculates the displacement needed to correct inter penetration, and finally applying the new velocities at the beginning of the next frame.

Doing the collisions in time-order might lead to an infinite (seemingly infinite) loop if all of the objects are concentrated in one location. Maybe you should update the frame time a fixed amount for consecutive collisions between objects?

[jimbo]

Yes one of the issues that I'm encountering is collisions at time 0, which then leads to infinite loops.

Also I'm getting penetrations when in theory it should not be possible (supposedly due to floating point errors?). I've tried various 'hacks' of my own invention but with no joy. Is there a known method for handing these penetrations. I'm worried if i project the penetrating objects out of each other this will have knock on effects on other objects, i.e. move into collision/penetration with other objects.

Thanks again for any help.
Jim.

[SmokingRope]

My most recent attempt at handling a scene with a high-density of collisions used a fixed time step. An object would be moved the fixed timestep and any displacements and changes in velocity would be applied after the movement occurred. This would be repeated for each dynamic object. The issues i had with it were stability related, and yes when there were 24 spheres in a hole bouncing around one would pop through the floor every once in a while.

I also ported this scene to two physics engines on the market, i believe i used both tokamak and newton. They handled things mildly better, however performance was still unfriendly.

I would also appreciate an explanation from someone who has the theory and/or experience behind them. Pending that it might be worthwhile to dig through any of the open-source physics engines for inspiration.