Best way to rotate a polygon used for collision test?

[Axeman]

I´ve just gotten starten on a simple Asteroid-type game, just to get the hang of game programming. I´m using lwjgl in 2d-mode and so far I´ve only got a Pong clone under my belt. To keep it simple I´m using only polygons for the ship and asteroids for the time being, since I´m mostly interested in trying to implement some more “advanced” game physics.

Anyway, last night i realized a a problem I´d never thought of before: That is the fact that a glRotate() only affects what I´m rendering to screen but not the vertices I´m using to calculate collision. What´s the best way to solve this problem? I did a little research that told me it´s possible to get the transformation made by glRotate and copy the matrix using a FrameBuffer… Is this the way to go or should I calculate the rotation myself and just render the new values with a simple glBegin?

[Tim_Spekler]

Hi !
I would recommend you for rendering to keep your glBegin…glEnd as it is and to use glRotate() for the rotation (as you just did).
For collision, you should create a Bounding Box associated to all objects that are concerned by collision.
What you should do is trying to find a separating axis between 2 bounding boxes (the one from your chip and the one for an asteroid I presume). If you find one, that means there is a collision, if there is not, then there is a collision.
You can find a lot of documentation on the internet about that. Just search for Oriented Bounding Box (OBB).
Hope this helps ;D

[namrog84]

In addition to what Tim said, I’d like you to a thing I made here

Simplified Advanced Collision Detection (SAT)(v2.1) (updated 8/4/2011)

There are both simple and advanced examples there and all the source code is provided to use freely without question or footnotes.

If not that, I’d also look into AABB or Axis Aligned Bounding Boxes

Its quite a bit more complicated problem then simply rotating an image, as you most certainly have done.

Alternatively, you could use a combination of regular boxes and distance checks(circular distance) and not deal with the shapes themselves.

[Axeman]

Hi guys! Thanks for your replies. I’m sorry if i wasn’t clear, but the collision isn’t a problem. I’ve made a SAT collision for that. My problem is how to handle the rotation of the polygon I use to test with SAT. If I glRotate I’m not actually changing the polygon, just how it’s displayed on screen. And therefor I’m thinking of the best way to deal with this problem.

[Tim_Spekler]

Well, the more obvious way to deal with it is to calculate on each rotation all corner positions of your bounding element, so you can use your SAT on its new position. That’s how I did for my projects.
But maybe you can use circular bounding area as namrog84 said (for asteroids for instance): this enables you to avoid calculating corners position, only center position is useful.

[davedes]

So I’m guessing you already have some sort of Polygon object, which contains an array of points?

You can either rotate each point, or apply a rotation matrix to all the points.

Some code:
Look at the source of Slick’s Transform class for an idea of matrix transformation.

Or check out Slick’s drawEmbedded which simply rotates each point before sending it to glVertex (no matrix).

Some reading:
http://www.gamedev.net/topic/286454-simple-2d-point-rotation/
http://www.ia.hiof.no/~borres/cgraph/math/twod/p-twod.html
http://wally.cs.iupui.edu/n351/3D/matrix.html

From there you will have to determine how best to check for collision; i.e. determine whether the point is within the polygon, or determine whether it’s within a bounding box/circle representing the ship, etc.

And since your points will already be rotated, you will no longer need glRotate when passing vertex data.

[Axeman]

Thanks a bunch, all of you! I think I got a pretty good idea how to handle this now. Now I just have to put it down into code and move on to the next unanticipated problem. And thank you, Davedes for those links. They are great stuff!

[Axeman]

I´ve got a spinning rect working now and I thought I should contribute to the forum with a code snippet, in case someone should be interested in the the same problem.

The method takes an “angle” in degrees. “AngleRad” gets the angle i radians. “numPoint” is number of vertices on the rectangle. As you can see the for loop iterates through the points of the rectangle and calculates the rotation for each vertex. Dx and dy only copies the coordinates from the rect[point] to make it a bit easier to read.

It should also be noted that I keep an “origin” variable outside of the method so I can translate the object to where I want it to rotate.

Disclaimer: I´m not saying it´s the best way or the most accurate way to rotate a polygon (a rectangle in this case). But it is a working spinning rectangle method and a code snippet might get someone on the right track.

public void rotate(float angle) {
		
		double tempX;
		double tempY;
		
		float dx;
		float dy;
		
		for(int point = 0; point < numPoint; point++)
		{	
			
			double angleRad = Math.toRadians(angle);
			
			dx = rect[point].getX();
			dy = rect[point].getY();
			
			tempX = (dx * Math.cos(angleRad)) - (dy * Math.sin(angleRad));
			tempY = (dx * Math.sin(angleRad)) + (dy * Math.cos(angleRad));
			
		
			rect[point].setPoint((float)tempX, (float)tempY) ;
			
			
		}
	}

I hope it makes somebody happy.

[davedes]

Since cos/sin are somewhat heavy calculations (compared to simple addition/multiplication at least) you shouldn’t be performing them more than necessary. Definitely not in each iteration of the loop!

Also look into a “FastMath” type alternative to Java’s Math class (which can be a little slow). There are some utilities in the forums here for faster math as well as a FastMath class in Slick.

[Roquen]

Also: complex numbers are your friend.

[Axeman]

Davedes: My first priority is just to get things working and understand the concept of why it´s working, that´s why I´m using Math.sin/Math.cos: It´s just easy. But I´d be happy to learn more about how to exchange those into something else. One thought I had is to simply make a array for sin[360] and cos[360], and just use integer angles. Any ideas…?

Roquen: I´ve noticed that you seem to like to use complex numbers. I promise that I´ll look into it when I feel ready. I´m just not there yet…

[Roquen]

2D or 3D, regardless of what techniques you use, you’re going to want to have the current orientation (rotation) of an entity stored in some manner. You should never be recreating information (when it’s hard) that you should just know. Within the context of space transforms (translations, rotation, etc.) you also want to be always working from “raw” untransformed data.

[Axeman]

Roquen: I´m not sure I understand…? In my case I use a rectangle, I rotate the rectangle and then I overwrite the old position with the new, rotated, position. Is that what you mean when you say “store”?

And could you elaborate on what you mean by “raw untransformed data”?

[Roquen]

If you rectangle is store as four vertices and you transform and overwrite them each time, after awhile your rectangle will not longer be a rectangle. Specifically after every transform the lengths of the edges and angles between them will change as floating point computations introduce error. So you need to store “raw” untransformed info about the rectangle so that it doesn’t change and use that to get the current information.

Personally I’d use storing the center (its translation), the positive distance to the upper right corner when unrotated and some rotational information (angle or complex number pair).

[Axeman]

Ah, I see! Thanks, that´s fantastic advice. I will rewrite my code now…

Ooh, just one more thing before I get started… How much is “Some rotational information”? Is it just a few key angles or the full 360?

[Roquen]

By “some” I simply meant: by “some” means…an angle, a complex number…whatever. If using an angle IHMO it’s worth getting used to using radians instead of degrees for runtime data. Think about angles however you want.