#6424 - sgeos - Sun May 25, 2003 6:05 am
What is the best general approach to collision between two sprites, or a bg and a sprite, where one or both is rotated. I do not think it should matter which sprite/bg, or if both are rotated. I think they will all boil down to variations of the same thing.
-Brendan
#6428 - Jason Wilkins - Sun May 25, 2003 10:08 am
Generally, I would probably approximate the shape of the sprites with sets of convex polygons and check for collisions between the polygons. Polygonal collision is fairly simple. Transform one polygon into the other polygon's space, and then check for line segment intersections.
To keep from having to test line segments, you could do a square-of-the-distance check to see if they are too far away (square of the distance, because you do not want to do a sqrt to find the actual distance).
I would have to experiment some to figure out the best way to do these sort of collision tests while avoiding doing too many divides.
I am sure there are quite a few optimizations if you force all your convex polygons to be rectangles, as I am sure things simplify somewhat if one of your line segments are always perpendicular.
This might be too high a level explanation if you are not familiar with transforming points into different spaces.
_________________
http://devkitadv.sourceforge.net
#6447 - sgeos - Sun May 25, 2003 10:43 pm
| Jason Wilkins wrote: |
| Transform one polygon into the other polygon's space, and then check for line segment intersections. |
What is the best way to test for a line segment intersection?
| Jason Wilkins wrote: |
| I am sure there are quite a few optimizations if you force all your convex polygons to be rectangles... |
Sounds like the way to go.
| Jason Wilkins wrote: |
| This might be too high a level explanation if you are not familiar with transforming points into different spaces. |
I'm not familiar with transforming points into different spaces. At least, I would not say I am. At any rate, it gave me some ideas. Thanks!
-Brendan
#6471 - Jason Wilkins - Mon May 26, 2003 9:00 pm
I realized that I said 'convex polygon' because I was originally thinking of doing a simple 'point in polygon' test, which is easiest if the polygon is convex. But, then I realized 'point in polygon' tests do not work generally to test if two polygons overlap. If you use line intersections, you can test if any type of polygons overlap. In that case, you do not need a set of polygons, because you do not have to simulate concave shapes with convex polygons.
I guess however, that if you wanted to simplify the tests by only using rectangles, then you may need to represent a shape with more than one if you have any odd shapes that cannot be approximated well using one rectangle.
Oh, and by rectangles, I mean axis-aligned rectangles, because it means that one of the lines in any line intersection test will be horizontal or vertical
I would have to put a considerable amount of thought into how to most efficiently represent the polygons, transform them, and how to do the intersection tests. I guess I could work it out and post again later.
_________________
http://devkitadv.sourceforge.net
#6504 - tepples - Tue May 27, 2003 10:35 pm
Or just use circles for intersection. A squared distance vs. squared sum of radii test is really cheap on a processor with fast multiplication such as the ARM7TDMI.
For testing against the background, translate the sprite's position into the world space (that's how you should be storing positions anyway), and use circle-square intersection testing (which is straightforward) for each sprite against each background tile that overlaps the sprite's bounding box.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#6509 - sgeos - Wed May 28, 2003 5:06 am
| Jason Wilkins wrote: |
| Oh, and by rectangles, I mean axis-aligned rectangles, because it means that one of the lines in any line intersection test will be horizontal or vertical. |
Could not the distance be taken, and the collision be checked relative to one of the rotated rectangles? Relative to one of them because then that one will be axis aligned. This would require adjusting the rotation of the other one, of course.
| tepples wrote: |
| Or just use circles for intersection. A squared distance vs. squared sum of radii test is really cheap on a processor with fast multiplication such as the ARM7TDMI. |
if ((x_dist * x_dist + y_dist * y_dist) < (rad0 + rad1) * (rad0 + rad1))
/* It's a hit? */
| tepples wrote: |
| For testing against the background, translate the sprite's position into the world space (that's how you should be storing positions anyway), and use circle-square intersection testing (which is straightforward) |
Never tried a circle-square intersection test, although I imagine a circle-anything intersection test must be pretty simple.
| tepples wrote: |
| for each sprite against each background tile that overlaps the sprite's bounding box. |
Do you mean bounding box before rotation, bounding box enlarged to take rotation into account, or bounding circle?
-Brendan
#6511 - tepples - Wed May 28, 2003 5:41 am
| sgeos wrote: |
| tepples wrote: | | Or just use circles for intersection. A squared distance vs. squared sum of radii test is really cheap on a processor with fast multiplication such as the ARM7TDMI. |
if ((x_dist * x_dist + y_dist * y_dist) < (rad0 + rad1) * (rad0 + rad1))
/* It's a hit? */
|
That's about right.
| Quote: |
| tepples wrote: | | For testing against the background, translate the sprite's position into the world space (that's how you should be storing positions anyway), and use circle-square intersection testing (which is straightforward) |
Never tried a circle-square intersection test, although I imagine a circle-anything intersection test must be pretty simple. |
Here's how to test intersection of a circle and rectangle. Given a circle of radius r centered at (x, y) and an axis-aligned rectangle with corners (0, 0) and (w, h):
If x > 0
If x < w then x = 0 else x -= w
If y > 0
If y < h then y = 0 else y -= h
If x^2 + y^2 < r^2 then collision
| Quote: |
| tepples wrote: | | for each sprite against each background tile that overlaps the sprite's bounding box. |
Do you mean bounding box before rotation, bounding box enlarged to take rotation into account, or bounding circle? |
Use the bounding box of the bounding circle for looping over the tiles, and use the bounding circle itself for the collision test. It's not too wasteful; about pi-fourths (78.6%) of the circle's bounding box is inside the circle.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#6528 - sgeos - Wed May 28, 2003 1:53 pm
| tepples wrote: |
Here's how to test intersection of a circle and rectangle. Given a circle of radius r centered at (x, y) and an axis-aligned rectangle with corners (0, 0) and (w, h):
If x > 0
If x < w then x = 0 else x -= w
If y > 0
If y < h then y = 0 else y -= h
If x^2 + y^2 < r^2 then collision |
It took e a second to figure out how that works.
| tepples wrote: |
| Use the bounding box of the bounding circle for looping over the tiles, and use the bounding circle itself for the collision test. It's not too wasteful; about pi-fourths (78.6%) of the circle's bounding box is inside the circle. |
I see how that works. How would I determine the side of the tile I hit (and perhaps the angle of the collision)? For the side of the tile I collide with, it looks to me like I'll need to figure out which quadrant the collision occured in.
-Bredan
#6534 - Jason Wilkins - Wed May 28, 2003 3:13 pm
I was under the impression that you wanted something that would handle oddshaped sprites under rotation without weird results. It didn't occur to me that you might not have a clue how to do collision detection at all, otherwise I would have just suggested squared distance bounding circles just like tepples.
If you needed more precise collision detection, you would use a method like what I suggested after you used the basic circle method to determine if the objects are close enough to touch.
_________________
http://devkitadv.sourceforge.net
#6537 - sgeos - Wed May 28, 2003 4:20 pm
| Jason Wilkins wrote: |
| I was under the impression that you wanted something that would handle oddshaped sprites under rotation without weird results. |
Thats the goal. Although oddshaped might be tall rectangles for now.
| Jason Wilkins wrote: |
| It didn't occur to me that you might not have a clue how to do collision detection at all, |
It's fairly easy to figure out sprites that don't rotate, but I did not how to start attacking rotating sprites.
| Jason Wilkins wrote: |
| otherwise I would have just suggested squared distance bounding circles just like tepples. |
I'm glad you suggested something different. Bounding circles will not give satisfactory results in all cases. The further the shape is from a circle, the less satisfactory the results. Restricted to rectangles, a square will give the best results. Still, this is much better than nothing.
| Jason Wilkins wrote: |
| If you needed more precise collision detection, you would use a method like what I suggested after you used the basic circle method to determine if the objects are close enough to touch. |
That comes out to three tests? Bounding box of bounding circle, bounding circle, and last line intersection test? Or should the bounding circle test be replaced by the line intersection test?
-Brendan
#6553 - Jason Wilkins - Wed May 28, 2003 8:41 pm
I do not think I would do both a bounding box and bounding circle test. The bounding circle test actually seems cheaper than the bounding box test, since the multiplication seems like it would be cheaper than all the branches required by bounding box test.
I feel the need to write a demo ^_^
_________________
http://devkitadv.sourceforge.net
#6577 - sgeos - Thu May 29, 2003 5:58 pm
| Jason Wilkins wrote: |
| I feel the need to write a demo ^_^ |
Excellent. Must see. =)
-Brendan
#6757 - Marcel24 - Mon Jun 02, 2003 3:59 pm
Hi..
This is my first Posting here ;)
I hope my ideas arent bad at all..
So i would do it like this...
1) Test where your sprite colides in the map array (positions)
2) Take theres tiles that may colide with your sprite
3) There rotate those in memory
4) pixel to pixel colision (only fore areas who are overlap,need some bounding box tests)
I hope you understand my strange ideas ;)
Or ist my idea slow an evil ?
Tnx..