Elysian Shadows

Posted: **Sun Mar 27, 2011 1:56 pm**

First of all I'd like it if we all prove eatcomics wrong:

Now I've been trying to calculate my own crap in EQ for matrix transformations and such. Now I've got translation and scaling however I'm having a slight problem calculating my rotation.

Here is my code for calculating the vertices

Code: Select all

if ( Pos.r != 0 ) {
		float sinn = sinf(Pos.r);
		float cosn = cosf(Pos.r);

		const float LEFT = Pos.x - (Pos.w / 2);
		const float RIGHT = Pos.x + (Pos.w / 2);
		const float TOP = Pos.y - (Pos.h / 2);
		const float BOTTOM = Pos.y + (Pos.h / 2);

		Verts[0].x = (LEFT  * cosn) - (TOP * sinn);
		Verts[0].y = (LEFT  * sinn) + (TOP * cosn);

		Verts[1].x = (RIGHT * cosn) - (TOP * sinn);
		Verts[1].y = (RIGHT * sinn) + (TOP * cosn);
		
		Verts[2].x = (RIGHT * cosn) - (BOTTOM * sinn);
		Verts[2].y = (RIGHT * sinn) + (BOTTOM * cosn);
		
		Verts[3].x = (LEFT  * cosn) - (BOTTOM * sinn);
		Verts[3].y = (LEFT  * sinn) + (BOTTOM * cosn);
	}
	else {
		Verts[0].x = ((-Pos.w / 2) + Pos.x);		Verts[0].y = ((-Pos.h / 2) + Pos.y);
		Verts[1].x = ((Pos.w / 2) + Pos.x);			Verts[1].y = ((-Pos.h / 2) + Pos.y);
		Verts[2].x = ((Pos.w / 2) + Pos.x);			Verts[2].y = ((Pos.h / 2) + Pos.y);
		Verts[3].x = ((-Pos.w / 2) + Pos.x);		Verts[3].y = ((Pos.h / 2) + Pos.y);
	}

Pos is a rectangle with 'r' being it's rotation.

Try drawing a quad like this:

Code: Select all

glTranslatef();
glRotatef();
//blah

However try drawing it like this:

Code: Select all

glRotatef();
glTranslatef();

It will change it's position as it rotates and that is what is happening.....So.....Am I missing something obvious?

Thanks.

P.S. Please don't send me to that topic in the education index because I've been to it

Posted: **Sun Mar 27, 2011 2:49 pm**

N64vSNES wrote: Try drawing a quad like this:
Code: Select all
glTranslatef();
glRotatef();
//blah
However try drawing it like this:
Code: Select all
glRotatef();
glTranslatef();
It will change it's position as it rotates and that is what is happening.....So.....Am I missing something obvious?

This is a very simple problem. When drawing in OpenGL using immediate mode or anything else for that matter, to perform rotation/scaling, you have to do it from the center point of the object. glTranslatef() moves you to the center of the whatever you're going to draw, and you do the rotation and scaling from after that translation. Without doing so, you end up scaling/rotating the entire scene from the last center given. If you just happen to be using Ortho, everything drawn will rotate off of 0.0f, 0.0f, unless set otherwise.

That may be your only problem, because your math for all of this seems like it would work fine

.

Posted: **Sun Mar 27, 2011 2:53 pm**

Yes, you are missing something. Matrix multiplication is not commutative.

For a matrix A and B. AB != BA

Furthermore, depending on the nature of the rotation desired, you may need to translate to the common or world origin to obtain your rotation. You must do this for rotations about the object's common origin. So if you have some model that you want to rotate around its own axis, you must first translate to the world origin, rotate, then translate back.

The final concatenation for rigid body transforms (eliminated shears to keep it simple) is:

X = T(t)T(c)RST(-c)

Here the matrix multiplication happens in reverse order. A Translation to the world origin is performed first ( T(-c) ), followed by a scale (S), then a Rotation (R), then a final desired translation (T(c) and/or T(t)).

Posted: **Sun Mar 27, 2011 3:14 pm**

N64vSNES, I'd like to point out a little something about what you're doing: it's terribly inefficient for most things. Although I know that you're probably not doing enough of it for a big performance hit, you're putting a lot of load on the CPU that the GPU can (and really, is designed to) take. Although I do understand that reinventing the wheel is a great way to understand the wheel, on a big project this can cause serious performance hits. GL provides its matrix transformation functions because it stores its own GPU-side matrix anyway, so why not let the GPU handle its transformations too? You probably won't have to worry about it with EQ, but keep it in mind for when you're working on more graphically complex projects.

Posted: **Sun Mar 27, 2011 3:26 pm**

I would like to note that the OpenGL driver will not perform matrix operations on the GPU. These (glMultMatrix, glTranslate, glRotate, etc...) are all implemented on the CPU because of the relative frivolousness of the calculation. The driver detects and is free to make use of SSE optimized routines where available but are still all taking place on the CPU.

To be clear, the vertex T&L (Vertex transform & lighting) is what occurs on the GPU. The state matrices are pushed as part of the current state in finality during draw calls and so the vertices are transformed by GPU hardware, not the matrices.

Posted: **Sun Mar 27, 2011 3:27 pm**

Ginto8 wrote:N64vSNES, I'd like to point out a little something about what you're doing: it's terribly inefficient for most things. Although I know that you're probably not doing enough of it for a big performance hit, you're putting a lot of load on the CPU that the GPU can (and really, is designed to) take. Although I do understand that reinventing the wheel is a great way to understand the wheel, on a big project this can cause serious performance hits. GL provides its matrix transformation functions because it stores its own GPU-side matrix anyway, so why not let the GPU handle its transformations too? You probably won't have to worry about it with EQ, but keep it in mind for when you're working on more graphically complex projects.

Sure I understand what you're saying.

But I need the vertices locations after rotation for collision between oriented bounding boxes (can't be bothered to spell it's name).

So I *could* just recalculate the vertices positions after I let OpenGL rotate them but I figure that would just put a equal amount of stress on the CPU right?

Oh and I actually boosted my frame rate by doing this with the transformations so....wtf?

edit:

WE'RE NOT GOING THERE!

Posted: **Sun Mar 27, 2011 3:30 pm**

7 pages

Edit: I pointed this out to him xD

Posted: **Mon Mar 28, 2011 9:13 pm**

Ginto8 wrote:N64vSNES, I'd like to point out a little something about what you're doing: it's terribly inefficient for most things. Although I know that you're probably not doing enough of it for a big performance hit, you're putting a lot of load on the CPU that the GPU can (and really, is designed to) take. Although I do understand that reinventing the wheel is a great way to understand the wheel, on a big project this can cause serious performance hits. GL provides its matrix transformation functions because it stores its own GPU-side matrix anyway, so why not let the GPU handle its transformations too? You probably won't have to worry about it with EQ, but keep it in mind for when you're working on more graphically complex projects.

qp and I actually had a gigantic conversation about this the other day. Very enlightening (for me, haha). Yeah, I also wanted to point out that this is incorrect (as qpHalcy0n already has).

Notice that you can save/retrive the modelview or projection matrices at any time? There is no way that you are literally grabbing shit off of the PCI-E bus at random like that.

As qp said, in a fixed function pipeline, that shit is happening on the CPU (with SSE hardware acceleration, when available).

And not only that, but you can do plenty of things BETTER than OpenGL even with a shitty matrix implementation. There are many special case affine matrix transforms such as the universal "instance" matrix (scale, rotate, translate) that are being calculated dynamically and inefficiently on the fly by OpenGL. When you do:

Code: Select all

glTranslatef();
glScalef();
glRotatef();

OpenGL is literally performing 3 matrix multiplications to give you a single matrix that you can easily instantiate all at once.

"Outperforming" is not just a matter of raw number crunching. It has to do with how general-purpose the OpenGL matrix stack is, and how it makes absolutely no assumptions about your transforms. YOU can make these assumptions, and save some 4x4 matrix multiplies.

Posted: **Tue Mar 29, 2011 6:03 pm**

Thanks guys I've got quite a education now and I've still achieved my mail goal...kinda

I decided to post here instead of make another thread (Seems silly since it's on the same topic really)

Going waaaaaay back I was trying to do this myself so I can get vertex locations and attempt *gulp* oriented rectangles collision detection.

Result:

I've not found much on the subject so I'm probably going at this at completely the wrong approach but here is how I'm doing it:

I have three functions to return booleans for now:

Code: Select all

	bool IsCollision(BoundingBox *a, BoundingBox *b);
	bool IsCollision(BoundingBox *a, BoundingBox *b,Vector2 &normal);

	bool IsOrientedCollision(BoundingBox *a, BoundingBox *b);

The idea is you call one of the first two and if the orientation isn't at 0 then it'll jump to whatever else.

So the first functions body, basic of basic collision as well as a check for orientation:

Code: Select all

bool Eternal::IsCollision(BoundingBox *a, BoundingBox *b) {
	if ( a->r != 0 || b->r != 0 ) {
		return IsOrientedCollision(a,b);
	}
	if ( a->x + b->w > b->x
		&& a->x - b->w < b->x
		&& a->y + b->h > b->y
		&& a->y - b->h < b->y ) {
		return true;
	}
	return false;
}

So when rotated as seen in the video it goes here:

Code: Select all

bool Eternal::IsOrientedCollision(BoundingBox *a, BoundingBox *b) {
   
	int i_minX = 0, i_minY = 0, i_maxX = 0, i_maxY = 0;

	float last = a->GetVert(0).x;
	// Far left
	for ( int i = 1;i < 4;i++ ) {
		if ( a->GetVert(i).x < last ) {
			last = a->GetVert(i).x;
			i_minX = i;
		}
	}
    
	// Far right
	last = a->GetVert(0).x;
	for ( int i = 1;i < 4;i++ ) {
		if ( a->GetVert(i).x > last ) {
			last = a->GetVert(i).x;
			i_maxX = i;
		}
	}

	// Far top
	last = a->GetVert(0).y;
	for ( int i = 1;i < 4;i++ ) {
		if ( a->GetVert(i).y < last ) {
			last = a->GetVert(i).y;
			i_minY = i;
		}
	}

	// Far bottom
	last = a->GetVert(0).y;
	for ( int i = 1;i < 4;i++ ) {
		if ( a->GetVert(i).y > last ) {
			last = a->GetVert(i).y;
			i_maxY = i;
		}
	}

	bool left_y = false, right_y = false, bottom_y = false, top_y = false;
	
	if ( b->r == 0 ) {
		if ( a->GetVert(i_minX).x < b->x + (b->w/2) ) {
			left_y = true;
		}
		if ( a->GetVert(i_maxX).x > b->x - (b->w/2) ) {
			right_y = true;
		}
		if ( a->GetVert(i_minY).y < b->y + (b->h/2) ) {
			top_y = true;
		}
		if ( a->GetVert(i_maxY).y > b->y - (b->h/2) ) {
			bottom_y = true;
		}
	}
	else {

	}

	printf("left vert- %i\nright vert- %i\nBottom vert- %i\nTop vert- %i\n\n",i_minX,i_maxX,i_maxY,i_minY);

	if ( left_y && right_y && top_y && bottom_y ) {
		return true;
	}

   return false;
}

Doesn't support the second rectangles orientation right now but whatever. So from the little I could find on this topic you have to get the vertex locations and "project" them so you find a overlap like so:

So....Help?

EDIT:
Just in case you miss the problem, look near the end of the video and it detects a collision under weird circumstances.

Posted: **Tue Mar 29, 2011 7:14 pm**

N64vSNES wrote: Result:

That's not a bad attempt

Posted: **Tue Mar 29, 2011 9:19 pm**

the weird circumstances are because it's seeing an overlap on the X axis, and taking that as meaning it's colliding. Avansc did a VERY good tutorial on the SAT here: http://elysianshadows.com/phpBB3/viewto ... art=999999. One thing that might interest you is that the axis that separates two convex polygons is always perpendicular to one of the edges (ie. like _|_ where the __ is the edge and | is the axis), so if you project the polygons onto each edge, you'll cover every possible axis.

Posted: **Tue Mar 29, 2011 9:36 pm**

Your "projections" are incorrect. You're missing a fundamental linear algebra concept here.

n64vsnes wrote:

Your axis-aligned "projection" is correct, but your oriented one is NOT a projection. You're merely taking one component of each vertex.

You need to learn about vector projections. You're supposed to be taking the dot product of each of your geometry's vertices with each of its axes to "project" each vertex onto a direction vector.

The reason that your axis-aligned case works correctly (and you are able to remain ignorant of linear algebra) is that taking the dot product of any vertex with the x or y axis essentially drops a vector component since one of its components is multiplied by zero.

Vector Projection onto the X axis:
X axis = <1.0, 0.0>
Vector = <3.0, 4.0>

Projection (dot product): 1.0 * 3.0 + 0.0 * 4.0 = 3.0

Whadya know? It's like you dropped the y component... because that's what you did. You had no idea you were actually taking a dot product there...

Posted: **Thu Mar 31, 2011 2:34 pm**

You figured it out, yet? I'd be glad to help.

1) Look at avansc's article
2) Watch my first video tutorial (2D vectors/linear algebra)
3) Watch Kendall's education in ESRev1, where she discusses the algorithm on a whiteboard.

Keep in mind that you are projecting onto each axis OF EACH POLYGON. In the case of AABBs and OBBs, (since they are both parallelograms), there are only 4 axes to project onto (2 for each object), because two sides of a a rectangle are axis-aligned with two other sides. Since you are normalizing these axes, they are literally the same (save yourself the math).

Get your ass to work.

Posted: **Thu Mar 31, 2011 3:48 pm**

GyroVorbis wrote:You figured it out, yet? I'd be glad to help.

1) Look at avansc's article
2) Watch my first video tutorial (2D vectors/linear algebra)
3) Watch Kendall's education in ESRev1, where she discusses the algorithm on a whiteboard.

Keep in mind that you are projecting onto each axis OF EACH POLYGON. In the case of AABBs and OBBs, (since they are both parallelograms), there are only 4 axes to project onto (2 for each object), because two sides of a a rectangle are axis-aligned with two other sides. Since you are normalizing these axes, they are literally the same (save yourself the math).

Get your ass to work.

I've spent the past two days doing those exact three things!

I think I'm understanding how the polygons are getting projected a lot better now as at first I was being a idiot and thinking about projecting 8 times instead of 4 (because two faces of a 4 face polygon is parallel) and I wasn't thinking about projecting to a perpendicular axis.

I've drawn some diagrams and I can see how it's working now but getting it down in actual code is a struggle, for example:

Here is two oriented rectangles with a perpendicular axis:

I have no idea how I should calculate that axis (blue line) and when projecting the polygons I'm confused to why that line makes a difference?

I think I might be trying to overcomplicate this actually

I'm going to read avansc's thread again.

Posted: **Thu Mar 31, 2011 5:37 pm**

N64vSNES wrote: I have no idea how I should calculate that axis (blue line) and when projecting the polygons I'm confused to why that line makes a difference?

The blue line is correct, but the green ones are not. You're not projecting along the y-axis, you're projecting onto the blue line.

: obb.png (6.65 KiB) Viewed 2135 times

This would be the projection on one of the axes. There are four axis total you need to project them onto. As Falco already pointed out, you don't understand what a projection onto an axis is. Go check out the resources he gave you.

Elysian Shadows

OpenGL Rotation

OpenGL Rotation

Re: Rotation

Re: Rotation

Re: Rotation

Re: Rotation

Re: Rotation

Re: Rotation

Re: Rotation

Re: OpenGL Rotation

Re: OpenGL Rotation

Re: OpenGL Rotation

Re: OpenGL Rotation

Re: OpenGL Rotation

Re: OpenGL Rotation

Re: OpenGL Rotation