Jump to content
  • Advertisement
Sign in to follow this  

[SOLVED] Ray Picking Math

This topic is 3403 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been trying to implement a simple Ray Picking algorithm into my current project and I'm having a bit of trouble finding a method that works to get a ray through my geometry based on the camera information and the click position on-screen. My code currently is like this
vec3f CalculatePickingRay(unsigned int ScreenX, unsigned int ScreenY, M3DMatrix44f Transform)
{
	vec3f Up(Transform[4], Transform[5], Transform[6]);
	vec3f Forward(Transform[8], Transform[9], Transform[10]);
	vec3f Right(Transform[10], Transform[9], Transform[8]);

	float fViewX =  ((float)ScreenX - (WINDOW_WIDTH  / 2.0f)) / (WINDOW_WIDTH  / 2.0f);
	float fViewY = -((float)ScreenY - (WINDOW_HEIGHT / 2.0f)) / (WINDOW_HEIGHT / 2.0f);

	vec3f PickingRay(Forward.x + (Right.x * fViewX / 2.0f), Forward.y + (Up.y * fViewY / 2.0f), Forward.z + (Right.z * fViewX / 2.0f));

	return PickingRay;
}
but I am getting a ray that is not exactly correct, and for all I know, this could be completely wrong. Since I could not find a method online that met the limits of the information I have access to in my program, I basically devised what you see above, and here are the basics: 1) Obtain the Up, Forward, and Right vectors given a matrix from the camera (The camera only has one matrix, and I'm not sure if it's the projection or transform or whatever... I really don't know what it is technically. I only know that the vectors I made are correct because I've tested them thoroughly.) 2) Get the ViewX and ViewY values as a number from -1.0 to 1.0 based on the position of the mouse on screen. (-1.0 for left and 1.0 for right, then -1.0 for bottom and 1.0 for top) 3) Create a Picking ray that takes the current Forward direction and adds to it the weighted (based on ViewX and Y) Right and Up vectors divided by 2 (to factor in the fact that my viewport is a 45 degree angle, not a 90 degree angle) I'm sure I'm doing this wrong because the ray I get is below where it should be. When I return the value, I set one vector to the camera's origin and another to the origin plus the picking ray, then I move the camera away to check if it's right, and it's always too low. Any help would be appreciated. [Edited by - ShinkaFudan on January 26, 2009 7:36:17 PM]

Share this post


Link to post
Share on other sites
Advertisement
Well, this looks fishy.

vec3f Up(Transform[4], Transform[5], Transform[6]);
vec3f Forward(Transform[8], Transform[9], Transform[10]);
vec3f Right(Transform[10], Transform[9], Transform[8]);

Forward is the same as right, except in reverse order? I would expect 0,1,2 to show up in there.

Secondly, this doesn't seem right

vec3f PickingRay(Forward.x + (Right.x * fViewX / 2.0f), Forward.y + (Up.y * fViewY / 2.0f), Forward.z + (Right.z * fViewX / 2.0f));

I'd expect something more like

vec3f PickingRay = Forward + Right*fViewX + Up*fViewY;

Share this post


Link to post
Share on other sites
I've tried utilizing a method like that.

I eventually ended up with this:


PickingRay = Forward + ((Right - Forward) * fViewX / 2.0f) + ((Up - Forward) * fViewY / 2.0f);


...but in that actually gives the exact same ray, I believe. From testing, it seems to always return the same value. It's facing over to the right far too much, and is not correct in it's Y value either.

The reason I had to do the subtraction of vectors within it is because I only want to add the difference of the two weighted by the ViewX and ViewY. The problem then becomes the fact that the Y is basing itself in a way that subtracts the Forward, and therefore gains an X and Z that is irrelevant and creates a strange addition to the PickingRay that throws it off.

I wish there was a simple way to just create it given the information I have available. Does anyone know?


EDIT:

I'm very close to getting it right with my latest changes


vec3f Up(Transform[4], Transform[5], Transform[6]);
vec3f Forward(Transform[8], Transform[9], Transform[10]);
vec3f Right(-Transform[10], Transform[9], Transform[8]);

float fWindowWidth = (WINDOW_WIDTH != 0) ? (float)WINDOW_WIDTH : 1.0f;
float fWindowHeight = (float)WINDOW_HEIGHT;

float fViewX = ((float)ScreenX - (fWindowWidth / 2.0f)) / (fWindowWidth / 2.0f) * (float)(fWindowHeight / fWindowWidth);
float fViewY = -((float)ScreenY - (fWindowHeight / 2.0f)) / (fWindowHeight / 2.0f) * (float)(fWindowWidth / fWindowHeight);

vec3f PickingRay;
PickingRay = interpolate(Forward, Right, fViewX / 2.0f);
PickingRay.y = Forward.y + Up.y / 2.0f * fViewY;

return PickingRay;


I can tell that the ray is directly related to my 2d mouse position, but it's not perfect... It's still off based on the weighting, which I must be doing wrong.

[Edited by - ShinkaFudan on January 23, 2009 12:52:28 AM]

Share this post


Link to post
Share on other sites
You're doing the same kind of stuff wrong as you were in the first example. >_<


vec3f CalculatePickingRay(unsigned int ScreenX, unsigned int ScreenY, M3DMatrix44f Transform)
{
vec3f Right(Transform[0], Transform[1], Transform[2]);
vec3f Up(Transform[4], Transform[5], Transform[6]);
vec3f Forward(Transform[8], Transform[9], Transform[10]);

float fViewX = ((float)ScreenX/(float)(WINDOW_WIDTH-1))*2.0f-1.0f;
float fViewY = -((float)ScreenY/(float)(WINDOW_HEIGHT-1))*2.0f+1.0f;

vec3f PickingRay = Forward + Right*fViewX + Up*fViewY;
PickingRay.Normalize();

return PickingRay;
}


You might need to invert your transform though. I'll assume it's an orthogonal matrix, so you'd need something like this instead:


vec3f Right(Transform[0], Transform[4], Transform[8]);
vec3f Up(Transform[1], Transform[5], Transform[9]);
vec3f Forward(Transform[2], Transform[6], Transform[10]);


Also, you're not taking into account where the ray originates from with this function.

I'd recommend stepping through and checking values as they get calculated. It should help you adjust for any errors.

Finally, if your matrix library supports matrix*vector type operations, which I assume it does, then you can do this:


vec3f CalculatePickingRay(unsigned int ScreenX, unsigned int ScreenY, M3DMatrix44f Transform)
{
vec4f v ( (float)ScreenX/(float)(WINDOW_WIDTH-1))*2.0f-1.0f,
-((float)ScreenY/(float)(WINDOW_HEIGHT-1))*2.0f+1.0f,
1.0f, // might want -1.0f here. dunno what your handedness is
0.0f );

vec3f PickingRay = Transform * v;
PickingRay.Normalize();

return PickingRay;
}

Share this post


Link to post
Share on other sites
My matrix implementation has no 4x4 Matrix multiplied by 4 x 1 Vector method. By any chance could you walk me through what that would entail? Matrix math is foreign to me still.

Edit: I have an implementation for multiplying a 4x4 Matrix by a 4x4 Matrix.... but I'm not sure if that's even useful in this case.

[Edited by - ShinkaFudan on January 23, 2009 4:31:27 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by ShinkaFudan
My matrix implementation has no 4x4 Matrix multiplied by 4 x 1 Vector method. By any chance could you walk me through what that would entail? Matrix math is foreign to me still.

Edit: I have an implementation for multiplying a 4x4 Matrix by a 4x4 Matrix.... but I'm not sure if that's even useful in this case.


Matrix multiplication is explained here
http://en.wikipedia.org/wiki/Matrix_multiplication

Share this post


Link to post
Share on other sites
I think I might have it. I'll test a bit and tinker around to try to figure it out.


#define A(row,col) a[(col<<2)+row]
#define B(row) b[row]
#define P(row,col) product[(col<<2)+row]

///////////////////////////////////////////////////////////////////////////////
// Multiply a 4x4 Matrix with a 4-value Vector
void m3dMatrixbyVector44d(M3DMatrix44d product, const M3DMatrix44d a, const M3DVector4d b)
{
for (int i = 0; i < 4; i++) {
double ai0=A(i,0), ai1=A(i,1), a-2=A(i,2);
P(i, 0) = ai0 * B(0) + ai1 * B(0) + ai2 * B(0);
P(i, 1) = ai0 * B(1) + ai1 * B(1) + ai2 * B(1);
P(i, 2) = ai0 * B(2) + ai1 * B(2) + ai2 * B(2);
}
}

#undef A
#undef B
#undef P


If you see anything out of place, please let me know.

EDIT: Scratch that... I'm returning a matrix, so obviously I'm doing it wrong.

EDIT:


#define A(row,col) a[(col<<2)+row]
#define B(row) b[row]
#define P(row) product[row]

void m3dMatrixbyVector44f(M3DVector4f product, const M3DMatrix44f a, const M3DVector4f b)
{
P(0) = A(0,0) * B(0) + A(1,0) * B(1) + A(2,0) * B(2);
P(1) = A(0,1) * B(0) + A(1,1) * B(1) + A(2,1) * B(2);
P(2) = A(0,2) * B(0) + A(1,2) * B(1) + A(2,2) * B(2);
}

#undef A
#undef B
#undef P


Ok I think this is it. There is definitely a direct correlation between the click location and the point now. I'll experiment with this and see if I can figure it out before posting back.

[Edited by - ShinkaFudan on January 23, 2009 6:50:31 PM]

Share this post


Link to post
Share on other sites
I'm at my wit's end. I have no clue what I'm doing right or wrong anymore.

I've uploaded my current build. There really is no way to describe what's going on, as I'm not even sure of the correlation between the clicking and ray creation.

Notes:
- The camera can be controlled with WASD and the arrow keys.

- Clicking will generate the ray, but since the start point of the ray is the camera location, you need to move the camera to see it. The red dot is the start (where the camera was) and the green dot is the end (basically it starts at the camera, runs along a normalized vector * X, and stops at a point, indicated by the green dot)

- The green dot seems to go the opposite way of the point on screen being clicked. Clicking near the center a few times when the program first starts will show you what I mean.

- The call to the ray picking algorithm, as well as the rendering of the ray and such, is all in (State_MainGame.cpp) and it should be easy for most people to follow. It's commented and doesn't have much going on in it to confuse anyone.





If anyone can help me get back on the right track here, it would be greatly appreciated. I am so lost.

[FILE REMOVED DUE TO PROBLEM BEING SOLVED]

[Edited by - ShinkaFudan on February 1, 2009 11:18:08 PM]

Share this post


Link to post
Share on other sites
Allow me to make 3 suggestions.

1. Spend some time practicing linear algebra until you understand it better. It's *really* helpful when you reach the point where you don't need to think very much about 3d math stuff.

2. You have a camera class with Up and Forward vector members and with functions GetXAxis, GetYAxis, GetZAxis. Instead of passing the matrix to CalcRay, just pass the camera or the 3 vectors. Making a matrix and then plucking out the vectors you built the matrix from doesn't make any sense.

The code is essentially going to look exactly like this:

vec3f PickingRay = Forward + Right*(((float)ScreenX/(float)(WINDOW_WIDTH-1))*2.0f-1.0f) + Up*(((float)ScreenY/(float)(WINDOW_HEIGHT-1))*2.0f-1.0f);


3. In StateMainGame, you have the following code:

m_Camera.SetOrigin(-1.7352445f, 1.25f, 0.93903923f);
m_Camera.SetForwardVector(0.95823556f, -0.28595340f, 0.0021118342f);

The funny numbers aside, I suspect you're killing your matrix here. The camera needs *two* vectors (forward and up) in order to be well defined - and it looks like they need to be orthogonal as well. I'd recommend testing with the default camera and when you get things working, then mess with the camera.

Share this post


Link to post
Share on other sites
Quote:
Original post by jdindia
Allow me to make 3 suggestions.

1. Spend some time practicing linear algebra until you understand it better. It's *really* helpful when you reach the point where you don't need to think very much about 3d math stuff.

2. You have a camera class with Up and Forward vector members and with functions GetXAxis, GetYAxis, GetZAxis. Instead of passing the matrix to CalcRay, just pass the camera or the 3 vectors. Making a matrix and then plucking out the vectors you built the matrix from doesn't make any sense.

The code is essentially going to look exactly like this:

vec3f PickingRay = Forward + Right*(((float)ScreenX/(float)(WINDOW_WIDTH-1))*2.0f-1.0f) +
Up*(((float)ScreenY/(float)(WINDOW_HEIGHT-1))*2.0f-1.0f);


3. In StateMainGame, you have the following code:

m_Camera.SetOrigin(-1.7352445f, 1.25f, 0.93903923f);
m_Camera.SetForwardVector(0.95823556f, -0.28595340f, 0.0021118342f);

The funny numbers aside, I suspect you're killing your matrix here. The camera needs *two* vectors (forward and up) in order to be well defined - and it looks like they need to be orthogonal as well. I'd recommend testing with the default camera and when you get things working, then mess with the camera.



This project is basically me trying to learn to use Linear Algebra a bit better. That's the problem, heh.

I started passing the camera in by reference right after posting my zip file. I've been testing that way since. I couldn't do it originally due to how I had things set up, but after I posted the URL to my file I realized there was no longer a reason to not pass it in.

This is what I have for the vector now


vec3f CalculatePickingRay2(unsigned int ScreenX, unsigned int ScreenY, GLFrame& Cam)
{
M3DVector3f ForwardM3D;
vec3f Forward;
Cam.GetForwardVector(ForwardM3D);
Forward.x = ForwardM3D[0];
Forward.y = ForwardM3D[1];
Forward.z = ForwardM3D[2];

vec3f Right;
Right.x = Forward.z * -1.0f;
Right.y = Forward.y;
Right.z = Forward.x;

M3DVector3f UpM3D;
vec3f Up;
Cam.GetUpVector(UpM3D);
Up.x = UpM3D[0];
Up.y = UpM3D[1];
Up.z = UpM3D[2];

return vec3f(Forward + Right*(((float)ScreenX/(float)(WINDOW_WIDTH-1))*2.0f-1.0f) +
Up*(((float)ScreenY/(float)(WINDOW_HEIGHT-1))*2.0f-1.0f)) * vec3f(1.0f, -1.0f, 1.0f);
}


and what I'm getting is a direct correlation between distance from the center and the ending point. It's just going a bit too far. I describe it in more detail here:

http://www.gamedev.net/community/forums/topic.asp?topic_id=521167&whichpage=1�

EDIT: I discovered that the correlation was not exponential. It was multiplying the X value by around 3.0 and the Y value by about 5/2. I went about manually multiplying the values back, and now it works perfectly. Obviously it's a hack, but it will have to do for now, as I really want to continue my project.

Your code was pretty much exactly what I needed (+rank), save a few small changes. I'll post the new source in a bit to see if you or anyone else knows just why I would have to do the hack to get it to work.

[Edited by - ShinkaFudan on January 25, 2009 1:56:31 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!