line-line or rectangle-rectangle collisions?

[SticksStones]

Hi all,

I'm really bored with bouncing balls and so I've been trying to figure out how to make bouncing lines. I didn't think it'd be too difficult but I just can't get my head wrapped around it!

There's lots of info on collision detection, but I can't seem to find anything much about collision reaction with anything other than circles.

Does anybody know anything about collision reaction with line-line or rectangle-rectangle collisions?

Thanks

[TOdorus]

It's really about the point of impact and the velocities of both bodies on that point.

Imagine you pushing a small box, like a matchbox. When you push directly towards the center of mass, the box won't turn, but only move. If you push in the same direction as you did first, but not towards the center mass, the box will move and turn (well it will always move, but you get my drift). If you push at the outside of the box it will only turn. The ratio rotational/linear acceleration is dependent on how far from the center mass you're pushing. You can find this by drawing a line through the centre mass which is orthagonal to the force acting on the box.

http://home.planet.nl/%7Ebogaa096/AngularLiniear.jpg

Chris Hecker has got a series of articles (http://chrishecker.com/Rigid_Body_Dynamics) dealing with the physics of rigid bodies which you can start to study. I also got a good article on the physics of pool which you will probably als be able to use, but I need to look that one up.

[SticksStones]

Thanks TOdorus!

Article 3 Page 13 onwards look like exactly what I've been trying to do!
Rigid bodies seems to be the search term...I've found a few related things now....thanks again!

[Gathan]

I would also suggest also trying out a separating axis test, you can get a testbed up and running with it fairly quick,
http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf describes the basic method, it can easily find the overlap of boxs and other convex objects, the method can also be extended to find time of impacts if given linear velocity to, so you can use it to solve the tunneling of objects if their displacement is too great problem, which is useful for fast paced games.
But I wouldn't worry too much about continuous collision detection, at least not at first, just concentrate on getting a stable collision detection and response system going.

[SticksStones]

I've covered separation of axis theorem and projection...Still thanks for the link, I'll give it a good read.

Everything I can find on rigid bodies isn't the approach I'd been attempting before I knew what rigid bodies were called...everybody is using particles! - I know from logically looking at the problem, particles (aka vertices) are unnecessary.

Say, I want to bounce a shape off a wall....
I should just be able to draw any shape...a square, triangle or blob. Line up it's centre of mass with the origin of the object then it's shape shouldn't matter, so long as the object never changes shape.
- the only things that should really matter is the distance from the point of impact to the centre of mass, the mass, the velocity and angle of impact (which can be greatly simplified).

In otherwords....somewhere our there, there is a fairly simple formula which can provide reasonable results for impacts between any shape....but I've not figured it out yet and it seems nobody else is doing it that way.

....if anybody knows what I'm going on about please let me know!

[Gathan]

I've covered separation of axis theorem and projection...Still thanks for the link, I'll give it a good read.

Everything I can find on rigid bodies isn't the approach I'd been attempting before I knew what rigid bodies were called...everybody is using particles! - I know from logically looking at the problem, particles (aka vertices) are unnecessary.

Say, I want to bounce a shape off a wall....
I should just be able to draw any shape...a square, triangle or blob. Line up it's centre of mass with the origin of the object then it's shape shouldn't matter, so long as the object never changes shape.
- the only things that should really matter is the distance from the point of impact to the centre of mass, the mass, the velocity and angle of impact (which can be greatly simplified).

In otherwords....somewhere our there, there is a fairly simple formula which can provide reasonable results for impacts between any shape....but I've not figured it out yet and it seems nobody else is doing it that way.

....if anybody knows what I'm going on about please let me know!
If you wish to know the exact points of impact mathematically you still need someway to define the dimensions for your object, yes it is true that most engines use vertices to define their objects, its logical, can be used to describe a wide range of virtually any convex shape.
Even engines such as box2d which uses conservative advancement to solve for estimated time of impacts defines its core shapes in such way, expect for circles of course.
It seems your expecting to be able to draw your shapes and the engine somehow just works out what the shape is and solves for it.
The best your going to be able to do without some sort of prefinition of what the shapes dimensions are is pixel detection, and well I have seen engines that make perfect use of that method, and its surely a easy way to do it.
But it can't be used with fast moving objects-tunneling out of the world is a awkful scenerio, but with small enough velocity and big enough environment- cause anything small can easily be missed with that primitive method.

[SticksStones]

I'm interested in collision reaction, not detection.

I know where my point of impact is but am unsure as to how my object should react to the collision.

A point of impact is just that...a point...it has no shape. Therefore if you can detect the collision, you know the point of impact and center of mass for you shape. You can forget about the shape of your shape.

Concave/convex shapes will work fine but the center of mass will have to be within the shape or it will be possible for a collision to happen on the "wrong" side of the shape.

I know it's is possible.


Are you sure box2D does not project circles?! Tony Pa describes how to project with circles on his "vectors for flash" mini site. Even using the method I'm attempting, it's still possible to avoid tunnelling, I'm still using vectors.

I've yet to find any pixel detection method that can cope with the rotation of 2 objects. Both the Grant Skinner method and the Corey O'Neil CDK fail in this respect. O'Neil claims he has it working with rotation, but he doesn't.
- this is one example of where the method I'm attempting will really come into it's own! It's the best solution when you don't know where the vertices are.

If...when...I figure it out I'll post it up here.

[Gathan]

I'm interested in collision reaction, not detection.

I know where my point of impact is but am unsure as to how my object should react to the collision.

For the point of impact information you would want to know several pieces of information, the point of impact of course, the normal for the collision so you can uses math to either make one object slide up and down the other, or bounce off if you want, could even do some slide, bounce and rotate to while its at it.



Are you sure box2D does not project circles?! Tony Pa describes how to project with circles on his "vectors for flash" mini site. Even using the method I'm attempting, it's still possible to avoid tunnelling, I'm still using vectors.

Ya I'm sure it uses ca to give estimated time of impacts, if your interested in a little reading about that method I would suggest https://wwwx.cs.unc.edu/~geom/papers/documents/articles/2009/tang09.pdf



I've yet to find any pixel detection method that can cope with the rotation of 2 objects. Both the Grant Skinner method and the Corey O'Neil CDK fail in this respect. O'Neil claims he has it working with rotation, but he doesn't.
- this is one example of where the method I'm attempting will really come into it's own! It's the best solution when you don't know where the vertices are.

That would be because coping with rotation of objects is a hard problem even when the dimensions of the objects are knowing, throw that information out and try to solve for something in which you know nothing about the shapes and the problem becomes virtually impossible to solve.
You can always sweep the arbitrary shape as it rotates and get a pixel object that can be used to at least tell you if a collision might have happened, but that well tell you nothing about the point of impact, let alone let you solve for it in any realistic fashion.

[a tadster]

I had this problem, the thing is, how do you want to respond?

It boils down to knowing rate of speed, direction of movement, and the needed response.

If all you want is for your object to always not intersect/and or land on some other object,
it can be simple:



public function reactionOfObject(e:HitEvent):void {

var mainChar:BasicGameObject = e.target as BasicGameObject;
if (mainChar.directionY == -1 ) { mainChar.y += mainChar.velocityY; //+or- gravity if gravity }
else if (mainChar.directionY == 1 ) { mainChar.y -= mainChar.velocityY; }

if (mainChar.directionX == -1) { mainChar.x += mainChar.velocityX; }
else if (mainChar.directionX == 1) { mainChar.x -= mainChar.velocityX; }

}


And... all the Vector physics stuff is really not needed, AS3 already has the Point Class that can be used just like a Vector.

[SticksStones]

...you got my hopes up then tadster, but I'm trying to figure out the velocity and angular velocity after a collision with irregular shapes.
I think I need to stop waiting for someone to tell me how to do it and just get my head down and get it sussed...or give up and use box2d.

[a tadster]

That would work on irregular shapes, so long as you test from the middles of said shapes, so the middleX and Y of each shape must be calculated.

What i'm suggesting is doing away with the typical Velocity/angular velocity notion (simple trig/geom vs physics).
In that example velocityX and Y are just rate of speed in those directions.

[TOdorus]

So what is it you're not getting than SticksStones? Basicly a rigid body is a collection of particles, or molecules if you will. A collision affects one particle. Since the particle is set in a rigid shape of other particles these will be affected by the collission as well.

Say a rigid body is turning round it's axis. This means that the rigid body has rotational velocity. The particles however, don't. Each particle has it's own linear velocity. The particles at the center will have lower velocities than the particles in the periphery. By using the distance to the center of mass you can calculate the rotational velocity.

Now the further from the center you push at a rigid body, the more it will start to rotate. This makes sense, as converting a velocity of a particle at the core will result in a lot less rotational velocity than a particle in the periphery.

From what I understand, the center of mass is at the location where there are the same amount of particles (or mass really) in every direction. So when a particle on one side starts to move, there is a countermovement on the other side of the center of mass. Think of it this way. When a circle rotates around it's center, a particle on one side of the circle will have exactly the opposite direction as the particle on the opposite side of the center of mass.

This brings me to the following conclusion how a force affects a rigidbody:


A force will directly influence the linear acceleration of the rigidbody.
A force will influence the torque by converting the linear velocity of a particle to angular velocity

The main idea is, that angular velocity doesn't really exist. It's a term devised by us humans to describe a certain type of motion. In reality it's just a bunch of particles having linear velocities and pulling/pushing at each other through Van der Waals force.

EDIT:
Or the short version:
Rigid bodies are rigid. If one particle moves, all other particles have to move in relation to that particle, to maintain the shape (or else the body would break or deform). So if one particle moves, all other particles move in relation to that particle. The point of impact, is the particle that you influence.

[oldmanwinter]

...you got my hopes up then tadster, but I'm trying to figure out the velocity and angular velocity after a collision with irregular shapes.
I think I need to stop waiting for someone to tell me how to do it and just get my head down and get it sussed...or give up and use box2d.

Just to clarify- you want the velocity and angular velocity of two objects after they've collided, and you already know the point of impact relative to the center of mass of each object? Is this collision elastic?

I'm too lazy to figure out the energy exchanged between two such objects in an elastic collision, but if you can get that far and know the energy transferred to each, here's how that impact would affect an object-


given:
E- energy transferred to object
m- mass of object
i- moment of inertia of object (using lower case i because I is impulse)
r- distance from center of mass to point of impact (assuming line from CoM to PoI is perpendicular to direction of impact)

first, you need to figure out what the impulse (I) would be

E = ▲E (kinetic energy) + ▲Er (rotational kinetic energy)
▲E = 1/2 m (I/m)^2 -> ▲E = 1/2 I^2 / m
▲Er = 1/2 i (I*r/i)^2 -> ▲Er = 1/2 I^2 * r^2 / i
E = 1/2 * I^2 * (1/m + r^2 / i)
I = sqrt( 2 * E / (1/m + r^2 / i) )
(double check that if you use it, to make sure i didn't screw it up)

and then you plug I into your ▲v and ▲w:
▲v = I/m ▲w = I*r/i

[SticksStones]

TOdorus yeah you're completely right, but I think there's a method which doesn't require the use of particles, but rather you can just apply the forces to the object directly. This should be faster and be easier to apply.

I've been doing loads of reading on this, but I must admit I'm feeling really dumb, I'm sure it's not that hard and I should have sussed it by now. I'm still really struggling with the greek. I can read most of it now, but I'm not past the point where it scares me and makes my mind go blank.

What I think what I'm talking about is something called "parallel axis theorem". Which (if I understand it correctly and I'm really not sure that I do) is when the "center of mass" lines up with "the moment of inertia". This being the case, you don't have to calculate the moment of inertia. Whist this may be widely inaccurate in some cases, I think it'll work perfectly well. What I've noticed about collision reaction is that, if things bounce off in generally the right direction and spin generally in the right direction, at more or less the right speed, the eye really can't tell.

Tbh....I probably just need to take Box2D apart and cut the correct code out.
...or oldmanwinter has just written the answer and I'm a bit too dumb to realise it!

[oldmanwinter]

well for physically accurate collisions and reactions, the only way to get away with not taking the moment of inertia into account would be by having circles/spheres collide with each other (the center of mass will rarely be in-line with the impact vector if the objects aren't round and the collisions are random).

if you're not comfortable with physics, it's gonna be a nightmare to figure this out! if i were in your shoes, i'd just wing it and add a random bit of spin to the object upon impact, like you said. you're not planning on having a bunch of these objects in a confined space, constantly colliding with each other, right? if you do, things could get a little wacky (like they'll speed up until they're going insanely fast), but if it's the the occasional collision and you tweek it so it looks ok to the human eye, that'd probably be fine

[TOdorus]

TOdorus yeah you're completely right, but I think there's a method which doesn't require the use of particles, but rather you can just apply the forces to the object directly. This should be faster and be easier to apply.

Well duh! That was my entire point :D
Particles just make it easier to visualize how the force influences the body as a whole. As I said in my previous post, you can deduct the movement of the body from a particle (although that is not entirely true, it is in the case of impuls).

If an object has a rotational velocity of x radians per second, how fast is the particle at radius r from the centre moving? Now reverse that. If a particle is moving at velocity x at radius r from the centre, how high is the rotational velocity? Again rephrasing that: what is the effect of a force acting at point (x,y) from the centre on the rotational velocity of the body? You really should catch on about now ;)

So after collision you basicly:
Set the linear velocity of the body to the velocity of the particle.
Set the rotational velocity of the body relative to the velocity of the particle.

[SticksStones]

tbh...I've got distracted have been working on something else, but I'm still interested in getting this figured out.

I have the objects spinning away from a collision almost correctly, in that they spin in the correct direction, but I've yet to convert the liner velocity to angular velocity...which is V * R..?

In order to use the conversion I'm going to need to know how much velocity would be converted in any given situation...which I've not quite sussed yet. Also I need take account of any pre-existing spin on the object..and um..not quite got there either.

But the main thing is that I really can't figure out the linear part. If a drop a pencil at 45 degrees which direction will it bounce? - the force seems to act upon the length of the pencil, so it would bounce off in a 45 degree direction...but then what happens if I tilt the table to one side, say 45 degrees in the other direction. My head seems to think the pencil will still bounce off at 45 degrees...but it can't be both...?