Collisions between trampoline and animals

[jacobian56]

@cuneCSClub/collisions

You may need to wait a bit for the other teams to create the objects, but you can start by planning out the math and physics on paper. For now, we need the animals to bounce straight up when they collide with the trampoline. On each successive bounce, they should bounce lower in the air. Eventually (after three bounces?), the animals should bounce low enough that they can exit to the ground (just destroy the object at this point, cause we'll add the animation later). If you wish, you can start thinking about on the speed of the trampoline, or tilt of the trampoline, etc. Be sure to be in contact with the Animals team, so that you can work with the objects they create.

[Reepca]

I recommend that the trampoline and animal teams come up with a format for representing geometry. Doesn't matter much to me what it is, as long as it's consistent. They should provide a way for us to access the geometry (for collision purposes) of the objects - whatever that may be (outer vertices of vector-graphic objects would be ideal if we want the collisions to look sane).

I see a number of ways that we could implement collision-checking (in order of most-realistic to least-realistic):

1. Straight-up algebra. Each update, check for intersections between the motion vectors of the vertices of each object and each other object, identify those that are earliest in time for each object, process them (bounce? apply force?), re-check for intersections, and so on, until all objects are at the target time. To limit the time complexity of this, bounding-box checks can be done to prove that objects have NOT collided, but never that they have. If we want stuff to be able to bounce diagonally, especially against objects that can have many sides to be bounced off of, this will best accomplish that, since we know exactly which side an object collides with. This approach knows exactly when and where a collision happens. My understanding is that the term for this is "a priori", meaning basically: think about where stuff should go, then move it, then think about where stuff should go, then move it... repeat.
2. Teleporting. Move an object seconds forward in time (and therefore space), THEN check to see if it's sticking through anything. This is dangerous if objects can reach high speeds, since if updates are not fast enough and enough time passes between them an object can teleport straight through another one. This method does not know exactly when or where the collision happens, and can possibly completely miss collisions, but does know where the object was some arbitrary amount of time before it collided and some arbitrary amount of time after it (should have) collided. I think the correct term for this is "a posteriori", which can be summarized as "move everything first, ask questions later". Since it wouldn't know exactly where or when the collision happened anyway, there's much less reason not to use bounding boxes.

Those are the general approaches. The actual collision geometry we get (bounding boxes, not bounding boxes, etc) depends on what the trampoline and animal teams decide. Personally I'm partial to the former, but since the second one is probably a lot easier to implement we could use it now and then switch later after we see hideous edge cases (there's an entire science devoted to trying to handle the edge-cases from a posteriori collision detection).

@jacobian56 to clarify, @cuneCSClub/collisions is in charge of physics in addition to just detecting the collisions?

[blue42u]

The animal team does not need to have a format for geometry, as all the animals are falling straight down, in separate locations. All they need is an object to store all the properties of the animals. That said, the nice thing about Lua is that we can add extra data to the objects for our stuff, without messing up their stuff.

As for the geometry itself, the best options are bounding box (not realistic, but easy) and convex hull (very realistic, but not as easy). Both would support the extrapolation-intersection style of detecting collisions (i.e. the former).

It would be nice to implement the former (or at least try). We should have a week or two where the animal team is working on build the structure, and we can work on the math itself.

[Reepca]

My concern in having an agreed-upon way of accessing geometry is in being able to generate well-fitting collision geometry. Even if we have all objects be the same shape, it still doesn't make sense to have them all be the same size (elephants vs rabbits and such). I imagine it would be much easier (and more accurate) to generate bounding boxes and convex hulls based on the actual geometry of the object than to hard-code it. Even if that geometry is something as simple as width and height.

[jacobian56]

You're raising some good points, Reepca, and we'll have to hash these out. Unfortunately, my Trampoline meeting is tonight, so we're just going to run with whatever idea we think works best. We'll use a box defined by width and height for the trampoline, and probably use vectors to define movement. If the club decides there's a better way to simulate movement or organized object attributes, I'll be happy to change anything my team accomplishes tonight.

[Reepca]

After doing a lot of algebra, I've come up with an equation for finding the time at which a moving point and a moving line segment collide. For collision geometry that consists of straight lines, this is all that will be ever needed, since a collision between two objects will always occur at a point of one of the objects (unless they're parallel, in which case multiple points may collide at once and one would be arbitrarily selected when sorting collisions through time). Note that special cases will be necessary for when the velocity of both objects being tested is 0 (will this ever happen?) and for when the velocities are equal (both will result in division by 0). I'll try to come up with a reasonable explanation for how I came up with the equation later, but here it is:

(p3_0.x - p1_0.x) * (p2_0.y - p1_0.y) - (p3_0.y - p1_0.y) * (p2_0.x - p1_0.x) / ((V2.y - V.y) * (p2_0.x - p1_0.x) - (V2.x - V.x) * (p2_0.y - p1_0.y)) = t

EDIT-

(if it doesn't appear on one line here, copy+paste it into some other text editor. Or, better yet, mark it up in TeX so it's much more readable).

Where p1_0 is the initial position of one point on the moving line segment p2_0 is the initial position of another point on the moving line segment p3_0 is the initial position of the moving point V is the velocity of the moving line segment (assumed to be the velocity of both points on the line segment, though for cases such as rotation this is not true). V2 is the velocity of the moving point

Also, since it's hard to algebraically define a "line segment", it's necessary to check that the point of collision (easy to find, since it's where the moving point will be at the time provided by the equation) is inside of the box defined by the two points the line segments consist of at that time. If it isn't, then they never collide. If the time provided by the equation is greater than dt for that update, it means that the collision could happen, but in the future. If the time provided by the equation is negative, I guess that would mean that there could have been a collision at that time in the past, but it's irrelevant and should be ignored.

The general algorithm I have in mind so far is to, for 2 objects A and B that need collision-checking:

1. Sanity check - make sure they have non-identical velocities and they do not both have velocities of magnitude 0.
2. (Optional) optimization check to test whether they can collide in the given time, using something like bounding boxes
3. Test every point of object A against every line segment of object B. Find the soonest real collision.
4. Test every point of object B against every line segment of object A. Find the soonest real collision.
5. Pick the sooner of the two
6. Return the relevant information (where they collided, when they collided, which point collided with which line segment) for processing

There are some issues with this, most notably that it does not work in the case where more than two objects in the system can collide. This isn't an issue if we only care about animals colliding with the trampoline, but at the root of the problem is the lack of locality. If there is a collision between A and C, for example, that happens before any collision between A and B, it has to first be detected and handled before any others. And for any two objects, there isn't any way of knowing if another object could interfere with the check aside from checking all other collisions first, choosing the first collision that happens globally, handling it, and repeating. Which is really complicated and necessarily very inefficient, so if anyone can think of any ways of proving that a collision will not mangle an already-detected collision, I'd love to hear them.

Also, please check any test cases you can think of with that equation - I have a little test program, but manually thinking of and entering values is tedious, and checking correctness without just using the equation is also tedious (and requires the use of a whiteboard for maximum effectiveness).