2d polygon collision detection, and reaction
Author
hmm. being fairly new to the more complex aspects of game programming, i was not able to think of any decent way of doing this. i have one idea, but. i would like to hear an experienced pov. about this.
what i thought, was to just keep a list of all the lines in every polygon, and constantly check if the movement line, interfere with the line of the polygon. hmm. but how to determin what side of the polygon you are in (to not end up inside it), i havnt manage to think of. atleest not any decent/safe way.
please give me some pointers, thanx.
JFK
H Fruz. Not quite sure what you mean here, but I can offer you this:
It is a peice of code that I origonaly picked up from somones post in the Maths and Pysics forum, the addapted for my own use. It returns whether or not the point passed into the function is inside the triangle, which is good when dealing with 2D polygons. Not quite sure if this is any help or not.
Completly off-topic, I was wondering how that line-of-sight thing with DDraw went?(a little while ago now)
struct vector{float x, y;};bool PointInTri( vector A, vector B, vector C, vector Point ){vector AB;// = B-A;vector BC;// = C-B;AB.x = B.x - A.x;AB.y = B.y - A.y;BC.x = C.x - B.x;BC.y = C.y - B.y;if( AB.x * BC.y - AB.y * BC.x < 0 ){if( AB.x * ( Point.y - A.y ) >= AB.y * ( Point.x - A.x ) ) return( 0 ); if( BC.x * ( Point.y - B.y ) >= BC.y * ( Point.x - B.x ) ) return( 0 ); if( ( A.x - C.x ) * ( Point.y - C.y ) >= ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 ); } else { if( AB.x * ( Point.y - A.y ) < AB.y * ( Point.x - A.x ) ) return( 0 ); if( BC.x * ( Point.y - B.y ) < BC.y * ( Point.x - B.x ) ) return( 0 ); if( ( A.x - C.x ) * ( Point.y - C.y ) < ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 ); } return( 1 );}It is a peice of code that I origonaly picked up from somones post in the Maths and Pysics forum, the addapted for my own use. It returns whether or not the point passed into the function is inside the triangle, which is good when dealing with 2D polygons. Not quite sure if this is any help or not.
Completly off-topic, I was wondering how that line-of-sight thing with DDraw went?(a little while ago now)
Author
thanx. although not exactly what i needed. but that''s ok, i think i have found a decent way that checks wheter or not i am inside a polygon, by using angles etc.
ah, yes, the los-thing. actually i have just experienced with it a little. not included it into the game. you could say it got put on hold (as projects often do), but i have picked it up recently and i''m working on it on a daily basis.
the question posted here is actually about the game. i decided to do a polygon based map system, instead of tiles. atleast experience with it and see how it looks. everything to get the best results
JFK
ah, yes, the los-thing. actually i have just experienced with it a little. not included it into the game. you could say it got put on hold (as projects often do), but i have picked it up recently and i''m working on it on a daily basis.
the question posted here is actually about the game. i decided to do a polygon based map system, instead of tiles. atleast experience with it and see how it looks. everything to get the best results
JFK
If you are doing polygons then I ceratinly hope you have switched to D3D for you game (you do intend to draw these polygons to the screen, as opposed to just using them for collision?).
Author
as for the moment, no. no d3d. the polygons are easily drawn with DD. the only problem(?) is that i cant find a decent way to fill them. the one way i know is by using windows built in functions, allthough what i would really want are textured poligons. so that would require the impletation of d3d.
this is what i did for Street Cars (see the thread about it):
(I only used recangles should work with any shape).
PointInPoly func: use the dotproduct of the normal of each side and a vector from the side to the point to determine if the point is inside the poly.
PolyToPoly collision: check each poly''s points against the other polys.
To resolve the collision: find the deepest penetrating point. Compute a resolve vector that will displace the polys to a non-penetrating distance. From this make 2 vectors, taking into account the objects'' masses, which will displace the polys. Add the two vectors to each poly''s Center of Mass.
I also used Chris Hecker''s paper for computing speeds after the collision.
Also you could use circles: fill the poly with circles (do this manually, or use an algorithm - very hard). The circle to circle collision test is quite simple and so is finding the resolve vectors.
[ My Site ]
''I wish life was not so short,'' he thought. ''Languages take such a time, and so do all the things one wants to know about.'' - J.R.R Tolkien
/*ilici*/
(I only used recangles should work with any shape).
PointInPoly func: use the dotproduct of the normal of each side and a vector from the side to the point to determine if the point is inside the poly.
PolyToPoly collision: check each poly''s points against the other polys.
To resolve the collision: find the deepest penetrating point. Compute a resolve vector that will displace the polys to a non-penetrating distance. From this make 2 vectors, taking into account the objects'' masses, which will displace the polys. Add the two vectors to each poly''s Center of Mass.
I also used Chris Hecker''s paper for computing speeds after the collision.
Also you could use circles: fill the poly with circles (do this manually, or use an algorithm - very hard). The circle to circle collision test is quite simple and so is finding the resolve vectors.
[ My Site ]
''I wish life was not so short,'' he thought. ''Languages take such a time, and so do all the things one wants to know about.'' - J.R.R Tolkien
/*ilici*/
quote:Original post by Ilici
PolyToPoly collision: check each poly''s points against the other polys.
I''m trying to do poly-poly collisions as well, so i''m interested in knowing how you did this. But if you''ve checking points of one against the poly of the other (and vice versa), what about this situation?:
+----+ | |+------------+| | | |+------------+ | | +----+
That will never happen given that the timestep does not exceed some limit. And if it does you can do multiple loops over the collision detection in one frame.
[ My Site ]
''I wish life was not so short,'' he thought. ''Languages take such a time, and so do all the things one wants to know about.'' - J.R.R Tolkien
/*ilici*/
[ My Site ]
''I wish life was not so short,'' he thought. ''Languages take such a time, and so do all the things one wants to know about.'' - J.R.R Tolkien
/*ilici*/
Yes, that was what someone else pointed out to me, assuming the timesteps are small enough you''ll detect the initial entry before this odd case.
However it raises the question - whats ''small enough''. If you get very thin rectangles, or very fast moving ones, you can still end up with this situation.
Just a trade off for speed over accuracy I guess. I''m going to try this method first and see if its good enough. If so then no need to spend time doing something more complex
However it raises the question - whats ''small enough''. If you get very thin rectangles, or very fast moving ones, you can still end up with this situation.
Just a trade off for speed over accuracy I guess. I''m going to try this method first and see if its good enough. If so then no need to spend time doing something more complex
Lemme ask a question: Are all of your bounding rectangles parallel to the x or y axis? If so, there is an easy 2D collision algo I''ve got for you
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
