Vertex intersection

It isn''t clear what you are trying to do. A vertex is basically a point that is part of a shape or in other words your corners. Two shapes can intersect, i.e. have areas in common, but generally collision detections goal is to prevent overlap. So you find the time they just touch one another.

A vertex has some function of time that defines it''s position. That can be quite complex over a long time interval, but over a small period such as one frame of an animation it is roughly a straight line. You can define an edge by two vertices, i.e. (v2-v1)*s+v1 where s varies from 0 to 1. Since the vertices are moving this gives (v2(t)-v1(t))*s+v1(t). When the shapes collide some vertex in the other shape, call it v, will be in the same place as an edge. So v(t)=(v2(t)-v1(t))*s+v1(t). You then solve that equation to find the time of collision. Those are vector equations so in 2D you have two equations and two unknowns. If there is a unique solution that is the time of collision. That may be before, after or during your time interval. If there is a range of solutions then the vertex is moving with/along the edge and you want the earliest solution within your time interval.

Now that is just one edge of one shape versus one vertex of the other. You have to do all vertices of one shape against all vertices of the other for both shapes. That can get time consuming with a lot of complex shapes. So you put a circle or rectangle around a shape and check if it is possible for them to collide during the time frame. If it isn''t possible then you don''t do all the individual edge/vertex checks. That is not your collision detection, but rather just part of it. It seems that is a point you are missing with your comment about what you don''t want. Under some circumstances it is good enough. You don''t have to stop there.

If you are doing collision detection and response then you should never have an overlap of shapes at the end of a frame. The collision altered the path so that they didn''t overlap. A simplier way of doing collision detection though is to split your frame into subintervals. Maybe the frame is .02 seconds. If there is an overlap at the end of the frame then you check at half way through the frame, i.e. .01 seconds. If there is still an overlap then you check .005 seconds. If there is no longer an overlap you check .0075 seconds. You continue that until you get down to a time interval you feel is sufficently small, i.e. 1/4, 1/8, 1/16, etc of a frame. You can short circuit your intersection test since you just need either yes they intersect or no they don''t.

quote:

---

Original post by LilBudyWizer
It isn''t clear what you are trying to do. A vertex is basically a point that is part of a shape or in other words your corners. Two shapes can intersect, i.e. have areas in common, but generally collision detections goal is to prevent overlap. So you find the time they just touch one another.

A vertex has some function of time that defines it''s position. That can be quite complex over a long time interval, but over a small period such as one frame of an animation it is roughly a straight line. You can define an edge by two vertices, i.e. (v2-v1)*s+v1 where s varies from 0 to 1. Since the vertices are moving this gives (v2(t)-v1(t))*s+v1(t). When the shapes collide some vertex in the other shape, call it v, will be in the same place as an edge. So v(t)=(v2(t)-v1(t))*s+v1(t). You then solve that equation to find the time of collision. Those are vector equations so in 2D you have two equations and two unknowns. If there is a unique solution that is the time of collision. That may be before, after or during your time interval. If there is a range of solutions then the vertex is moving with/along the edge and you want the earliest solution within your time interval.

Now that is just one edge of one shape versus one vertex of the other. You have to do all vertices of one shape against all vertices of the other for both shapes. That can get time consuming with a lot of complex shapes. So you put a circle or rectangle around a shape and check if it is possible for them to collide during the time frame. If it isn''t possible then you don''t do all the individual edge/vertex checks. That is not your collision detection, but rather just part of it. It seems that is a point you are missing with your comment about what you don''t want. Under some circumstances it is good enough. You don''t have to stop there.

If you are doing collision detection and response then you should never have an overlap of shapes at the end of a frame. The collision altered the path so that they didn''t overlap. A simplier way of doing collision detection though is to split your frame into subintervals. Maybe the frame is .02 seconds. If there is an overlap at the end of the frame then you check at half way through the frame, i.e. .01 seconds. If there is still an overlap then you check .005 seconds. If there is no longer an overlap you check .0075 seconds. You continue that until you get down to a time interval you feel is sufficently small, i.e. 1/4, 1/8, 1/16, etc of a frame. You can short circuit your intersection test since you just need either yes they intersect or no they don''t.

---

Thanks for the reply, and that what you sayd about overlapping, yes that is exactly what im trying to do, prevent it. Im sorry that I dont know the right word but I think the word is polygon. But is PLANE same thing than polygon?

To make my self clear, consider five lines for example, and all thoes lines are connected so its a shape (now what ever its called). And I need to prevent these shapes from overlapping. Plus make collision response.

it''s polygon

i''ll use a triangle for the plane. point you thumb in one direction, your index finger in another, and middle in another (you dont have to make yourself look awkward doing this btw). Well done, you now have your triangle. now place your other hand flat on the tips of those points. well done, you flat hand is the plane. it has no perimeter or volume, just direction.

the reason i used the triangle as an example is because it''s the only polygon that''s garenteed to be co-planar (all of it''s points are on the same plane). if you used 4 fingers and bent some of them, in some cases it would be impossible to create a plane without bending the flat hand.

as to the collision detection - do a search for intersecting lines and point-in-polygon algorims (flipcode.com has a good article outlining this - it''s in their development tutorials section).

it all depends on if your shape is concave or convex. look, 2 new words for you to look up on google

good luck

quote:

---

Original post by MENTAL
it''s polygon

i''ll use a triangle for the plane. point you thumb in one direction, your index finger in another, and middle in another (you dont have to make yourself look awkward doing this btw). Well done, you now have your triangle. now place your other hand flat on the tips of those points. well done, you flat hand is the plane. it has no perimeter or volume, just direction.

the reason i used the triangle as an example is because it''s the only polygon that''s garenteed to be co-planar (all of it''s points are on the same plane). if you used 4 fingers and bent some of them, in some cases it would be impossible to create a plane without bending the flat hand.

as to the collision detection - do a search for intersecting lines and point-in-polygon algorims (flipcode.com has a good article outlining this - it''s in their development tutorials section).

it all depends on if your shape is concave or convex. look, 2 new words for you to look up on google

good luck

---

Ok thanks Il have to think this over again.