• Advertisement
Sign in to follow this  

Please comment on my collision system design

This topic is 4401 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am currently designing and refining a collision system, and I would enjoy some comments on it.

Philosophy

Perfect collision detection is impossible in real-time (and is very hard to attain because of numeric approximation errors). Any collision detection system makes approximations. The usual method in a posteriori collision detectors is to perform detections at intervals, checking for overlapping objects and moving them back to non-overlapping positions. Such systems cannot handle many situations, such as detecting the collision of a bullet and a piece of paper, without introducing code to handle 'special cases'. My approach falls within the bounds of a priori collision prediction. It predicts the time at which the collision between two objects will occur, thus ensuring that no collisions are ever overlooked. The prediction of the time of first contact also allows more precise collision detection, because it does not depend on an heuristic to reverse overlaps. However, the usual methods of a priori collision prediction are not easily applied to real-time simulations. In order to increase performance, all movements are considered to be linear: all objects are moving along segments at constant speeds. While this might appear as an over-restrictive approximation, all movements in n dimensions can be approximated as closely as necessary by a sequence of linear movements through (n+1)-dimensional tesellation of the path. Besides, movements are often the results of discrete integration, which is already in many cases such an approximation.

System foundation

The system is based on a clock engine which allows me to call functions or methods in three different ways: now, before, and at. now-calling is the usual calling method: the function is called immediately, and is allowed to return a value. at-calling will call the function after a specified delay has elapsed: neither before nor after that duration, but exactly when it ends. No return values are allowed, but side-effects are allowed. before-calling ensures that the function will be called before the end of a specified duration. No return values or side-effects are allowed, except for before-calling or at-calling other methods at some point in the future that does not depend on the instant when the call was actually resolved. before-calling will usually be resolved by the clock engine when it is idle. If a call is made in the future on objects that do not exist anymore (they disappeared in the mean time), the call does not occur at all.

User interface

It is assumed that the user wants to detect the collision between two groups of objects A and B (the case of collisions within the same group is a simple consequence of this). For this, he adds to both groups associations composed of the following: - a hull, which is spherical or polygonal, and includes a bounding sphere. - a trajectory, which describes a single segment of the object's movement (velocity, start position and time, end time). When the end time is reached, the association is removed, as it is not longer necessary. - a piece of data, which is used to respond to collisions. A collision function (provided by the user) is called whenever a collision occurs. It receives as argument the data associated to the two colliding objects (as well as general information, such as the current time). Since a trajectory is not mutable, the user would describe a full movement by adding several such associations, with their corresponding start and end points. Since this is seldom practical, a position object represents the movement as a sequence of trajectories. Whenever a trajectory ends, a new one is added to the collision system, associated with the same hull and data as the previous one. The position object is mutable, and when it is changed it removes the previous trajectory and adds the new one.

System design

The addition of a new trajectory triggers the now-call of the Add method of the group. Functions marked with an '*' are subsystem-specific functions (that depend on the implementation of the partitioning system, or are straightforward mathematical computations).
Add( object )

  // do not add past trajectories
  if end(object) < NOW then return
  
  // insert into partitioning system
  now-call InsertPartitioning( object )

  // predict collisions
  now-call PredictCollisions( object )

InsertPartitioning( object )

  // perform partitioning system magic based on the object's
  // current position
  partition(object) = now-call GetObjectPartition*(object)

  // get the time at which the object leaves its current partition
  // if the trajectory ends before the object leaves, leavetime
  // is equal to the end time of the trajectory.
  leavetime(object) = now-call WhenLeave*(object)

  // when the object leaves its partition, reinsert it
  at-call [leavetime(object)] Add( object )
  
PredictCollisions( object ) 

  // Find all objects in the object's partition, with which
  // the object can collide and iterate
  foreach( other = samepartition(object) ) 

    // Determine the earliest time when objects might collide,
    // using their bounding spheres
    earliest = now-call EarliestSphereContact*(object,other)

    // Ignore if it cannot occur
    if earliest = infinity 
    || earliest > leavetime(object) 
    || earliest > leavetime(other) then continue

    // Refine the computation before the spheres make contact
    before-call [earliest] RefinePrediction(object,other)
       
RefinePrediction( object, other )

  // Compute the actual time of collision
  time = now-call CollisionTime*(object,other)

  // Schedule the collision
  at-call [time] Collide(object,other)

Collide( object, other )
 
  // Call the user function on the data of the objects
  now-call UserFunction*(data(object),data(other))
Lazy evaluation is done through prediction refinement: if the system is too busy, the before-call will wait until the last moment to be resolved. On the other hand, if the system has a lot of idle time, the before-call will be resolved quickly to make more time for computations later. Movement changes (such as collision response) are handled by the removal of the object (so any at-called or before-called functions involving it will not be run) and the addition of a new one. If the system was under heavy load, most before-call functions will probably not have been called, thus saving precious computation time. Note that RefinePrediction is only called if a collision is bound to occur (outside of external events such as trajectory changes), its only purpose is to delay the computation of a precise collision time until it can be done (on idle systems) or must be done (busy systems). This is because collision time prediction requires square root computations for sphere, while computing 'earliest collision time' only requires a handful of adds and multiplies. In particular, the EarliestSphereContact function will always return infinity if two objects cannot collide (this involves a simple discriminant evaluation).

Conclusion

This system performs perfect collision detection for trajectories approximated by sequences of segments. Through lazy evaluation, it can dynamically adapt the amount of computations to the load of CPU. To the user, it only keeps the essential: adding objects to collision groups, modifying their movements, and having an event be triggered (that is, a function is called) every time a collision occurs, to allow collision response.

Share this post


Link to post
Share on other sites
Advertisement
I would say that the problem of a posteriori collision isn't the detection of fast moving objects against small extent objects (I interpret the bullet/paper example this way). To detect such a collision you "only" need to sweep the shape of the moving objects. I think you have to do something like sweeping also with your a priori system.

However, the advantage of your system seems me the avoidance of the need to belatedly guess how the objects would have behaved if the collision was detected in time instead of afterwards. This is of interest for correctness of collision behaviour of more than one moving object. Say, due to lining up possible collisions in order of estimated occurance, you know the current states of all objects at that moment. That were not the case (at least so easily) for a posteriori systems. Have I understood it right?

Well, it sounds very interesting, and I'm curious about the real-time behaviour of your system. Besides the effort for accuracy, it seems me that your system may need relative low runtime, since you defer furthur collision computation to the next time you know that something happens?!

Share this post


Link to post
Share on other sites
Quote:
Original post by haegarr
I would say that the problem of a posteriori collision isn't the detection of fast moving objects against small extent objects (I interpret the bullet/paper example this way). To detect such a collision you "only" need to sweep the shape of the moving objects. I think you have to do something like sweeping also with your a priori system.


Swept volume/area is a natural consequence a priori system, since the equations for finding the time of collision involve solving for a collision between two swept volumes/areas.

Quote:
However, the advantage of your system seems me the avoidance of the need to belatedly guess how the objects would have behaved if the collision was detected in time instead of afterwards. This is of interest for correctness of collision behaviour of more than one moving object. Say, due to lining up possible collisions in order of estimated occurance, you know the current states of all objects at that moment. That were not the case (at least so easily) for a posteriori systems. Have I understood it right?


Yes. There is no backtracking in this system at all, movements are always interrupted at the time of first contact, and penetration only occurs when the collision response does not prevent it.

Quote:
Well, it sounds very interesting, and I'm curious about the real-time behaviour of your system. Besides the effort for accuracy, it seems me that your system may need relative low runtime, since you defer furthur collision computation to the next time you know that something happens?!


The need for this system arised from my use of a game system that already relies on at-calling and before-calling instead of regular update steps to save processing time. The result is that such systems do indeed save time. While I have not implemented the collision system yet, I believe that, at least for sphere-sphere collisions, on a heavily loaded system, the amount of operations per second are:

(for N spheres, k detection steps per second, x collisions per second on average, no space partitioning)

N2 (k + x) for a traditional system
N x for the predictive system

Although such factors as at-calling implementation or sort-sweep algorithms may turn the N and N2 both into N log N.

EDIT: I'm currently trying to implement this system. I'll update the thread once I am done.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement