I am going to develop a library for prediction of linear collision detection.
[Version 1]
What will be the library do?
★ Given a list of objects with velocities, the library will compute each object’s first collision, the object it collides with and the time to collision will be computed. It will also fire a listener when the objects actually collide.
★ One can change the velocities of any object at any time, the affecting object’s predicted collision will be recomputed
★ Bounding Volumes: Sphere Bound for moving objects, any for static
What will be the library good for?
★ Since the collision is predicted, high speed and low speed objects are treated alike, thus, there is no ‘passing-through-object’ without collision
★ It will be good for objects that move at linear speeds and it will use little resources for objects that do not change their velocity too often(like every few ms).
★ computations are done when: adding a new objects, removing an object that had a collision predicted, changing velocity of an object, and on collision of objects
Dev. plan:
[v1] Linear Velocity
[v2] Velocity and Acceleration
[v3] Linear Angular Velocity
Chapter 1: Collision Prediction between objects moving at linear speed
Version 1: Assuming objects have sphere bounding volumes Proof of concept:
Given two spheres s1,s2 moving at velocities v1 and v2.
By subtracting velocity v2 from both spheres, we will get sphere s1 moving relatively to s2 with speed of (v1-v2), and a static non moving sphere s2. Since v2-v2 = 0
If we move a sphere in the direction of its velocity, the shape that contains the sphere at any point in time is a capsule. Thus if the capsule for s1 intersects s2, a collision will/had occurred. The time till impact is calculated by dividing the distance of s1 and point on line s1+v1*x closest to s2 by the relative speed of s1. [Conveniently, this distance is already calculated when checking the intersection of the capsule with sphere].
Chapter 2: Collision prediction between objects rotating at linear angular velocity around two points that are moving at linear velocity
Things get a bit tricky now. ~If one were able to express the movement of these spheres by a function~
Due to optimization purposes the problem can be split to collision checks between: 1. Rotating and Not rotating spheres
Considering velocity relative to the rotating projects, the path that the rotating object follows can be described by circle! The path of not rotating object is Line or a Point. 2. Two Rotating spheres
Again, the velocity of one sphere can be subtracted from another, to get one stationary but rotating about a point sphere. This one can be represented once again by a Circle.
However, this leaves us with Circle and “some function” for the other spheres. To make matters simple, lets create a function that will represent the relative movement of sphere A to sphere B, thus we will have only one function and one stationary point.
Lets say that we have managed to make this function, then using distance formula, and plugging in our function and the stationary point B. We can solve this equation by setting the distance to the sum of radius of A and B.
Chapter 3: Collision prediction between objects moving with velocity and acceleration
It turns out that one needs to solve only a quartic equation to solve this problem.
Below is a demo:
-the box once again is not part of the system
-spheres that goes outside the box have their velocity modified, subsequently new collision prediction are calculated
I have been thinking of implementing a reduced-and-simplified version of this for my game, which is a space theme. Real space objects can be traveling at many thousands of meters per second.
Do you see this library being able to cater to those kinds of speeds when calculating impacts between objects?
Yes, absolutely. In fact, this is one of its advantages that object’s high or low velocity and acceleration are treated the same. Thus there will be no ‘passing-through’ situations.
I guess that when you treat one object as stationary and the other as moving using vector mathe-magics (mathematics), I guess it’s becomes quite do-able.
I’m looking forward to seeing this lib mature. I can see it being quite popular too.
Question: Would the collision prediction be for the next frame? Or for a certain number of frames in the future? How would timing work?
So far I have thought of two events that will be provided from the library - “soonest” CollisionPredicted, “onCollision”.
Let’s say you add several objects along with their speed/acceleration. The collisionpredicted will be immediately fired(using the same thread that added the object) if given your objects a collision in the future was predicted. You will be provided with the first collision that will take place, the two colliding objects, and the time in seconds till collision.
To receive the onCollision event, one would call update(float tpf) method, that would simply just count how much time has passed. When the accumulated time will be greater than the predicted collision time, onCollision event will be called, after which the next predicted collision will be provided.