Polygon collision detection

Performance Tuning
#1

I’m writing an asteroids remake with convex polygons used to represent the bounds of ships, asteroids, and bullets for use with collision detection. Each of these objects also has a bounding rectangle that must intersect another object’s bounding rectangle before polygon collision detection is done. The asteroids and ship must rotate and so must their bounding polygons/rectangles. I used a bit of trig to rotate the polygons, but I don’t believe I will be able to use rotated Rectangle object as I don’t have direct access to its x and y points so I can rotate them. To get around this I was thinking of using another Polygon to represent the bounding rectangle instead of a Rectangle object, but from what I hear Polygon collision detection isnt very efficient and I was wondering if using a 4 sided Polygon would be less efficient than a Rectangle for checking intersection. Obviously a rectangle is a polygon in math terms, but I’m not sure the differences between the objects. Also, Rectangle has a method for checking whether it intersects another Rectangle, but I lose this with Polygon and I can only check if one contains any of the points from another. so my questions are:

will using a 4 sided Polgyon object be slower for checking intersectio than a Rectangle object?

how can I use a Polygon for accurate collision detection, the only way I currently see is to go through and check if one Polygon contains any of the points from another polygon, this obviously isn’t completely accurate.

what is the best way to get around this issue with the rotating Rectangle bounds, do I need to create the four sided Polygon, or is there some other way this is done?

I’m doubting this, but maybe it would be better to just do pixel detection (check if two opaque pixels overlap from the two objects being checked) after bounding box detection, not sure how I would do this with with jogl…

thanks for any help.

#2

Don’t bother.
Use java.awt.Area shapes , transform them using AffineTransforms. It’s fast and easy to use. Moreover, you will not need anything else stored to make collisions.
Area to Area collision is fast (i did point in area test, which is enough for your game also, imho).

#3

That’s not true - lots of Area stuff is extremely slow (so slow it’ll make you weep).

The trick is to discover which bits are “as fast as anything you could hand-code” and which bits aren’t.

But certainly do NOT blindly assume all operations will be fast. In general, point - in - Area tests are fast so long as the area is very simple. Note that if you use CSG to make a complex area then the point tests can get slow.

In fact, if you do more than one or two unions/intersections/etc of areas, then everything gets slow (IIRC this is because Sun’s implementation stores it’s data in a VERY inefficient (for algorithms) way, that I suspect they will eventually change, because it’s just not possible to achieve high performance that way).

#4

You are right, and i think i am also.

Under the conditions i wrote, everything is fast.
Now, would CSG be fast enough or not for collision is something i FEEL like it would not be appropriate. i don’t see it as the right method for that purpose but YMMV…

#5

Yeah, sorry, I was trying to say that whilst the conditions you outlined would usually be OK, the rest of Area etc is a dangerous area for performance.

AFAICS CSG ought to be very fast, but I think it isn’t because Sun discards the information they could have used to do faster checks (which would have made their algorithms more complex but faster). Can’t be sure though - it’s a long time since I checked the speed of their algos.

#6

I think the CSG stuff splits objects up into scanlines and then does the CSG on each line. While that probably makes for a simple general case algorithm its bloody inefficiant and tends to give those annoying 1 pixel errors. >:(

#7

couple more questions. What is CSG?
My polygons are no more than six sided, would it be worth it to give them rectangle shaped Areas and check for a collision with these before checking Area intersection with the Areas shaped like my sprites?

#8

What is CSG?

Constructive Solid Geometry. That is… constructing rather complex shapes by combining shapes with logical operators like add, sub, xor…

Here is an (non java) example:

My polygons are no more than six sided[…]

Well, you can use faster algos if the polys are always convex. And if they are rather round you could use bouding circles instead.

edit: sp++

#9

they are convex, but bounding circles won’t work in this case since collision detection should be near perfect in an asteroids game. At least this is what I think since close encounters with asteroids/ships/bullets etc. are part of the game :wink: do you mean the algorithms will work more efficiently or that I can choose a different algorithm that will be more efficient?

#10

here is a link, just got it working on webstart:
http://www.cyntaks.com/projects/asteroids/webstart/asteroids.php the green lines show the bounds that are used for collision detection, a collision is found whenever two of the outer bounding boxes intersect because for some reason polygon.contains(x, y) is always returning true… I’m working on switching over to using Areas now though

#11

I’m not even using collision detection yet, but just to rotate the Areas that I will use for collision detection its using an extra 10% cpu according to task manager. Not only that but it seems like I’m having to create a objects every time through my gameloop. Here is the code I am using to rotate/translate my Areas:

Rotating/translating my ship:


public void updateBounds()
  {
    boundsTransform.setToRotation(Math.toRadians(-rotation), width/2, height);
    bounds = originalBounds.createTransformedArea(boundsTransform);
    boundsTransform.setToTranslation(x, y);
    bounds = bounds.createTransformedArea(boundsTransform);
  }

rotating/translating my asteroids:


public void updateBounds()
  {
    boundsTransform.setToRotation(Math.toRadians(rotation), width/2, height/2);
    bounds = originalBounds.createTransformedArea(boundsTransform);
    boundsTransform.setToTranslation(x, y);
    bounds = bounds.createTransformedArea(boundsTransform);
  }

I just want to make sure I’m not doing anything horribly wrong since it seems to be taking the majority of the processing time in my game.

#12 
trans.setTransform(1, 0, 0, 1, x - width/2, y - height/2);
trans.rotate(theta, width/2, height/2);

Area a = new Area(rectangleBounds);
a.transform(trans);

That’s all I’d do. Any comments on my way?

#13

is this meant to be something that could replace the body of my updateBounds() method? if so I don’t see how you could use your Area a since it is created within the method body. Other than that I’m not sure if it would work correctly or not since I can’t use half of it (creating Area a within the method body based on rectangleBounds).

Some good news, collision detection is working perfect and it didn’t require any extra noticeable amount of cpu, its just rotating and translating my Areas…

#14

i don’t understand why you need to recreate your bounds each frame.

also, your jnlp does not work.
JNLPException[category: Erreur de téléchargement : Exception: java.io.FileNotFoundException: http://cyntaks.com/projects/asteroids/webstart/externalresources.php : LaunchDesc: null ]

#15

you must have an old jnlp cached or something cause my current jnlp has no reference to externalresources.php (that file doesn’t even exist anymore). I was having troubles with webstart but they were fixed earlier today (guess thats yesterday now…) and I’ve been testing on a few different peoples computers with no troubles.

#16

I am recreating the bounds cause what I need each frame is a translated and rotated version of the original area I created. I don’t know of another way to do this so its not applying the rotation/translation to the already rotated/translated Area. Heres an example of my problem: The ship needs to be rotated at 45 degrees, and I have this value stored in a variable, but I can’t just tell it to rotate 45 degrees each frame or it will just spin. I am probably going about this wrong. maybe instead of changing the value of some theta variable, I could actualy rotate the ship on keypress… I was just trying to use it in the same way I do with a Graphics context in Java2D, g.rotate(theta, width/2, height/2) each time the screen is rendered.

#17

You are going about it the correct way - I am doing something similar in my 4KRacer game.

The smallest (in terms of code size) way of doing it is to create an Area that represents the original untransformed geometry, and, each frame create a new Area that is transformed to the objects location.


//init - done just once.
Area baseArea = new Area(new Rectangle(1, 0, CAR_WIDTH-2,CAR_HEIGHT));

...

while(running) //game loop
{

...

// in the game loop, iterate over all cars 
for(int i = 0;i< NUM_PLAYERS;i++)
{

...

//create a transform to represent the cars position for this frame
transforms[i] = new AffineTransform(carCos,carSin, -carSin,carCos, x-CAR_WIDTH/2*carCos+CAR_HEIGHT/2*carSin,y-CAR_WIDTH/2*carSin-CAR_HEIGHT/2*carCos);

//transform the base geometry to the cars position
Area carArea = baseArea.createTransformedArea(transforms[i]);

// iterate over all the cars, checking for collision
for(int n = 0;n< NUM_PLAYERS;n++)
{
   //oldTransforms will be null in the 1st game frame, so null check is needed
   if(n==i || oldTransforms[n]==null) continue; 

   //oldTransforms are the transforms from the previous game frame(or from this game frame if n < i)
   Area intersection = baseArea.createTransformedArea(oldTransforms[n]);

   //calculate the intersection between the 2 objects bounding Areas
   intersection.intersect(carArea);
    
   //if the intersection is not empty, a collision has occured.
   if(!intersection.isEmpty())
   {
      //collision has occured
      ...
   }
}
}
#18

Yep, thats what I’m doing for Gravity Battle also. Seems to work out quite nicely.

Kev

#19

Ok, stuff seems to be working pretty well now so thanks for all the help guys.

#20

For anyone who is curios I did come up with a way to improve performance (a lot). Its actualy quite simple, I just don’t call my updateBounds() method every frame now. I keep a loop counter and only call the method when loopCounter%5 == 0, this has had an unbelievable effect on performance. Before I did this I tried 50 rotating asteroids on screen at a time and it was very slow. I just tried 100 on screen rotating with no slowdown at all. Rotating my collision bounds doesnt even take a noticeable amount of cpu when I have a sane number of asteroids on screen now. It would probably be better to call updateBounds() after a certain period of time instead of every 5 times through the loop, I may switch to this. I should also say that I’ve switched between both modes (calling updateBounds() every frame and every fifth frame), and there is absolutely no visual difference.

edit: typos