next »

[Freezy]

Greetings!
First of all, I'm really new to all this Graphics stuff and i never was a pro in mathemathics, but i consider myself as 'came rally far'
Currently i try to implement a little 2D engine using SDL and C++ and it works pretty well. I'm able to draw, rotate and scale a texture (yeeeah i know, awesome but it also has a StateManager and FPSControll  ). So I'm familiar to mess around with my ProjectionMatrix and tought of implementing a simple Bounding Box collision detection. This is where the fun starts. My basic understanding is, that i can transform my sprites and the mouse coordinates back to the 'standart' matrix to determine the collision without the scaling and rotaion stuff:



Picure 1 represents my scaled, rotated sprite in the center of the screen and the Mousepointer right over it. The sprite is rendered in the transformed matrix and the Mousepointer in the 'standart/resett/loadIdentity' one. Now i transform the sprite back to it's origins (upper-left corner, unscaled, unrotated), copy the Mouse to the transformet matrix (red pointer) and also transform the mouse back to the sprites origins. Hypothetical this should work, but i have no idea how to 1:1 'copy' the Mouse from the 'standart' matrix to the projected place in the transformed matrix. Or is there a better approach to solve this?

This is my draw routine (as stated... c++ newbie). Translatef to set the 'hotspot' of the texture to the center.

Code:

glLoadIdentity();

	glColor4f( 1, 1, 1, 1 );
	glBindTexture( GL_TEXTURE_2D, mTexture.id );
	rScreenPosition = rScreenPosition - Vector2D( (float)mTexture.width /2, (float)mTexture.height /2 );

	glTranslatef( (mTexture.width  /2) + rScreenPosition.X,
				  (mTexture.height /2) + rScreenPosition.Y, 0);

	glScalef( rScale.X, rScale.Y, 0 );
	glRotatef( rSpin, 0, 0, 1 );
	glTranslatef( -( (mTexture.width  /2) + rScreenPosition.X),
				  -( (mTexture.height /2) + rScreenPosition.Y), 0);

	glBegin( GL_QUADS );
           ...
        glEnd();

Sorry if this is a standart noob question 

[Mikademus]

If you're after the simplest solution you could go with AABBs (axis-aligned bounding boxes), which are rectangles enclosing the current object.

You of course need to update all AABBs to their shape's extremes every frame.

[David Pittman]

Start by thinking of it like this: the mouse pointer position is not in a different space than the rotated object; they're both in screen space in Picture 1. The cursor should be transformed from screen space into object space ("sprite space?") just the same as the sprite rectangle, and then you can do a simple (left <= x <= right && top <= y <= bottom) kind of check (which is the whole point of transforming it, to simplify this test).

But that's not actually how you're applying the matrices--you're transforming the sprite to make it be rotated instead of to get back to its normal position. So, transform the mouse pointer by the inverse of that matrix and you should get the cursor position relative to the sprite.

[Freezy]

Thanks. Both solutions make perfect sense to me, but i got a technical problem. For both, I have no idea how to get to the actuall coordinates for the points as there are drawn. I always have the screen coordinates. I try'd to get the modelview matrix an multiplying my mousepinter with it.

Code:

GLdouble modelMatrix[16];
glGetDoublev( GL_MODELVIEW_MATRIX, modelMatrix );

Looks something like this:


Now how can I recalc the x,y of the mouse or the aktually points of the Sprite to be in the same space? Is there a method i missed (like glApplyMatrix(&x, &y, &z, modelMatrix))? I'm to dump to multiply the matrix manually

[E D I T]
Nevermind. Found a solution. I transform the cursorposition back with the same way I re-transformed the Sprite. Then i can call gluProject on the transformed Cursor to get it's real coordinates. The real coordinates are mirrowed but it works for the Collision Detection. What a brainfuck

[Shuger]

I don't think that you should mess collision detection code with graphics rendering code. Anyway 4x4 matrices are for 3d transformations, in 2d you can go without even knowing that things like matrices exist. Simple trigonometry is you friend

[Bad Sector]

I think you're complicating this stuff, all you need to do is to check if any of the box vertices are inside the other box (think of them as arbitrary convex polygons - in fact you can use arbitrary convex polygons to make the bounding volume for your sprites) and check this for both boxes. This is something like (pythonish code):

Code:

def poly_in_poly(poly1,poly2):
    for vertex in poly1.vertices:
        if point_in_poly(vertex, poly2):
            return True
    for vertex in poly2.vertices:
        if point_in_poly(vertex, poly1):
            return True
    return False

The point_in_poly function can be made using a bunch of methods, discussed here, here, here and other places basically. Using a bounding sphere that covers the exterior of the polygon is recommended since its very fast and you can first check for sphere-to-sphere collision and then poly-to-poly collision which usually is slower. Of course if you only have a few sprites visible this won't matter :-).

[BorisTheBrave]

Um, no, BadSector. Your code would fail for two thin rectangles making a Greek cross.

Also matrices are definitely better than trigonometry, once you get used to them. Even for 2d. They are faster to write code for, and run faster. Though it sounds like good advice not to mix collision detection and display code.

I think you've got it figured out, but I'll spell out here what you are doing.
You have a box with vertices (0,0), (w,0), (0,h) and (w,h) in local co-ordinates.
The openGL transform matrix, M, can transform these into screen co-ordinates. M is a 3x3 matrix, which represents arbitrary linear transforms in 2d space.
We'd write M * v for taking v from local to screen co-ords.
Now we have a point, p, in screen co-ordinates that is the mouse position. We can go back to screen co-ordinates using the matrix M^-1, the inverse matrix of M. (matrix libraries will calculate this for you). As it's easier to work in local co-ordinates because we have an AABB there, our point in box procedure would be:

Code:

v =  M.inverse() * p
if v.x<0 or v.x>w or v.y<0 or v.y>h
  return p not in box
return p in box

Assuming you have set up your matrices correctly in the first place, there should be no hacks or corrections to points. Multiplying by a matrix or it's inverse merely transforms points from one co-ordinate system to another, and back again.

This doesn't help for checking if two boxes overlap though, as we can transform into either boxes local co-ordinates, but the other one will still not be oriented correctly. You'd need to use a test like SAT, though by this point you should really be looking for a pre-written one.

[Bad Sector]

Um, no, BadSector. Your code would fail for two thin rectangles making a Greek cross.

Gah, when i tried to do something like this at the past (that was 4 years ago) i remember that for *some reason* i also had to test for the polygon's edges too. However i couldn't remember why so i assumed there isn't need for that 

[Shuger]

Also matrices are definitely better than trigonometry, once you get used to them. Even for 2d. They are faster to write code for, and run faster. Though it sounds like good advice not to mix collision detection and display code.

The point is they do the same thing. However, they surely are not faster, you still need to calculate all those sine and cosine stuff to put it in matrix. Matrix multpilication is surely slower then rotating vectors using simple trigonometry, and that's all he needs: adding vectors and rotating vectors. It's also easier to write actualy.
Say, you want to rotate vector by angle alfa. Would you prefer to do this:

Code:

newx = x*cos(alfa) - y*sin(alfa);
newy = y*cos(alfa) + x*sin(alfa);

or create 3x3 matrix and then get the vector multiplied by it?

All you need to store is angle and position vector.
As for SAT, here's good tutorial

[BorisTheBrave]

Yes, I'd rather create the matrix. In C++ with a suitable library:

vec2 rotate(float angle, vec2 b){
return Matrix23(angle) * b;
}

Even with no library at all, I would just write the exact same code you did, because that is just an inlined matrix multiplication as they are equivalent, after all. "using" trig really means working with angles all the time, such as in your example. "using" matrices means working with vectors and avoiding sin and cos wherever possible. You wouldn't have to start from an angle all that often.

Further, trigonometry will go crazy once you start translating as well as rotating. Suppose I want the transform from local to screen coords, having only the affine transformations (represented how you like) for local to world and world to screen. I'd like to see you trot that off with trig.

[Shuger]

Further, trigonometry will go crazy once you start translating as well as rotating. Suppose I want the transform from local to screen coords, having only the affine transformations (represented how you like) for local to world and world to screen. I'd like to see you trot that off with trig.

Well... if you have locals and want to transform to screen.. That's not a problem at all. You always start with local coordinates of object and transform them to screen. Like, every time you calculate physics, visuals, whatever? Well since you wanted too tell me i'm wrong i think you meant transforming from screen space to object local space, did you?

[BorisTheBrave]

No, I meant compositions of transforms, not inverses, was just putting it in more concrete terms.
Yes, it's easy to take a single point through two different transforms. But I was asking you form the transform which does this. So if I have a lot of points in local space I wish to draw, I wouldn't have to double my work.

As in, if local to world rotates by a and translates by (x,y), and world to screen rotates by a' and translates by (x', y'), what would the transform from local to screen be, a'', (x'', y''). (answer: it's not too complicated, but no one is going to memorise it; and I didn't include scaling in there).

[Shuger]

No, I meant compositions of transforms, not inverses, was just putting it in more concrete terms.
Yes, it's easy to take a single point through two different transforms. But I was asking you form the transform which does this. So if I have a lot of points in local space I wish to draw, I wouldn't have to double my work.

Oh, come on, the topic is about collidin 2d boxes. Even if you do double work, so what? Seriously, to expierience performance issues in 2d box colliding code you need to try really hard.

As in, if local to world rotates by a and translates by (x,y), and world to screen rotates by a' and translates by (x', y'), what would the transform from local to screen be, a'', (x'', y''). (answer: it's not too complicated, but no one is going to memorise it; and I didn't include scaling in there).

So you ask, what if transformation stack, right? They don't. Read the question. Or even topic title witch has "simple" word in it.

[BorisTheBrave]

I merely was trying to indicate that vector maths is superior in general. As the approaches are of roughly equivalent ease at low levels (though I would still argue there is no point at which trig is easier), it seems important to give advice that won't lead to frustration later on. Particularly, as the OP is already making use of openGL which features matrices heavily, and already has all the transformations in terms of matrices. It would be foolish to ignore this.

[Freezy]

Nice to see that this Thread has developed it's own dynamic. I hope it will help lost souls in search for the answer. As for me it is too late :D. I deleted all the Debug-Grown code in an attack of nerd rage after i thought i did it. It worked really well as i stated above with scale, translation and rotation but as soon i added zoom it all messed up again. Seems like I'm not skilled enough in the aspect of mathematics and how openGl handles all this stuff. I't just blows my mind. I'm using Indielib now to get myself more into C++ and graphics programming in general. 

[Mikademus]

Nice to see that this Thread has developed it's own dynamic.

You do know that replies like that from the OP spells instant doom for any thread, right?

[handCraftedRadio]

I only skimmed through the thread, so sorry if this isn't what you are looking for, but there's an article on gamedev.net that i think might help.