Selecting a tile with the mouse in a 3D Terrain enviroment (Ray picking.. vertex picking..?)

Hi All,

I am in the process of developing a 3D terrain engine.  Most has gone well, it looks good, textures good, rotates good and draws at a nice frame rate.  Everything I wanted so far.  Now, for the fun bit.  I want to be able to interact with the terrain with the mouse.  My maths not being great, I sort of hit a brick wall.  I've done some searching on the web and found bits and bobs related to "ray picking", but nothing I've yet been able to get my head around.  So, I've turned my attention here as I'd like to spend some of my points getting a good answer.

My terrain is stored in a vertex buffer (obviously) and draw to the screen.  I have the vertex information in an untransformed buffer.  The buffer basically contains a bunch of vertices for each "tile" in my terrain.

Given a screen co-ordinate of x,y I'd like to be able to see if the mouse is "clicking" on a tile.  To do this, I'm guessing I need to check each triangle that makes up each "tile" and if it intersects either of them, that's the tile I want.  

I'd also like to extend this routine at some point to determine which corner vertex is nearest to the mouse.


If you need more info, let me know, but basically that's what I want to do!


Thanks in advance guys
LVL 1
Moo-JuiceAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

davebytesCommented:
Well, if you transform the terrain yourself into 2D, you can sort and order things and find the best 2D pick yourself.

If you leave it in 3D, you have a lot more work.  One way is to find the approximate Z value of the click location (pull the Z from the Z-buffer and reverse transform it), and also then reverse project the 2D x/y screen click location into 3D space.  OpenGL has functions to do some of this for you, but I can't remember if DX does.

Once you have your approximate click location in 3D, you can search through your vertices (hope you have them ordered decently!) for reasonably nearest vertex.  From there, there are too many possible ways to 'interact' with a vertex to write up here, using mouse or keyboard to change either just its Z value, possibly using 'spring' systems to pull nearby verts along with it, etc.

If you've never looked at the Torque engine (or Tribes 2), I recommend it.  They have a great little terrain editor built in with 'brush' size support (like Photoshop) for how big a group of vertices to interact with.

-d
0
Moo-JuiceAuthor Commented:
Hi davebytes,

Thanks for your comments.  I read what you say and I know where you're going, but herein lies the problem.  What you say on the surface makes perfect sense, how actually achieving that result is another matter (did I mention that when it comes to maths and me, the wheel's going but the hamster's dead? :)).  To give you some more info, the vertex buffer contains a 20 x 20 tile set (each tile with 6 vertices, going top left, to bottom left, to bottom right to top right).  I know I can optimise this using index buffers, but for the moment I'm keeping things simple.  The vertices are organised in rows, left to right, top to bottom.

They are renderered on to the screen using a transformation that centres them around 0.0, 0.0, 0.0.  


I have done some reading on the D3DXUnproject() function or whatever it's called.  I also looked at a D3DXPlaneIntersect() function, but couldn't figure out how to get these functions to tell me "Yes, it's in that vertex right there".  If I can get an answer to that question, the rest comes easier....

TIA.
0
kvoziCommented:
http://www.gametutorials.com/Tutorials/opengl/OpenGL_Pg3.htm there is tutorial called:
Object Selection in 3d with a mouse, id you're interested download the following project:
http://www.gametutorials.com/download/OpenGL/ObjectSelection_OGL.zip
Maybe it'll help you, Good luck
0
Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

davebytesCommented:
Well, you need to use unproject to take the x/y of the mouse in screen coords, and the z at the mouse in screen coords, to make you a 3D world-space vertex.

Then, you want to do quick distance approximation checks against say the center vertex (or so) of each of the buffers, to figure out which is nearest.  In theory, z-buffering should give you the best approximate Z nearest to a triangle/vert of interest, so should just work.

V0 is the Unprojected world-space vertex.
V1 is the vertex you test against in the block.

you start with:
V = (V1-V0)
which is the difference between the vectors.

if using vectors, you can then just take V.length() (or whatever the equivalent function is) for a precise measurement.
length = sqrt(vx*vx + vy*vx + vz*vz)

Of course, you can also skip the square root, and do rough approximations using the pre-sqrt values (since if something tests to be less before the sqrt, it'll be less after...).

That gives you the tile-set that seems closest. Note that you could have up to 2 (or 4) tile sets that are all really close, and might be worth taking up to 4 within some error margin.

Then, for a given tileset, do the same distance compare walking the vertices of the tileset.  In theory, you should sort of binary-search things, so you don't look at every vertex -- but it should be pretty fast to to vector subtraction and squares for a 6x6 grid, so worry about optimization later. ;)

you should end up with one vertex that has the smallest difference/length to the mouse vertex, and there's your answer.

-d
0
Moo-JuiceAuthor Commented:
Thankyou davebytes, I think I am almost there.  What I've managed to do so far (and almost got what I want), is:

CONVERT MOUSE POINTS to 3D SPACE:

                  D3DVIEWPORT9 vp;
                  gpD3DDevice->GetViewport(&vp);

                  D3DXVec3Unproject(&vecOrigin,
                                            &D3DXVECTOR3(pt.x, pt.y, 0.0f),
                                            &vp,
                                            &m_projectionMatrix,
                                            &m_viewMatrix,
                                            pmatInverse);
                  D3DXVec3Unproject(&vecDir,
                                            &D3DXVECTOR3(pt.x, pt.y, 1.0f),
                                            &vp,
                                            &m_projectionMatrix,
                                            &m_viewMatrix,
                                            pmatInverse);

pmatInverse is a ptr to a D3DXMATRIX which is the final transformation of the view position.  Given vecOrigin and VecDir:

                  D3DXPLANE plane1, plane2;
                  Geometry::Point<UINT> pos;
                  const ISOMETRIC_VERTEX* pVertex(m_pVertexData);
                  for(pos.x = 0; pos.x < szViewport.cx; pos.x++)
                  {
                        for(pos.y = 0; pos.y < szViewport.cy; pos.y++)
                        {
                              // First triangle
                              D3DXPlaneFromPoints(&plane1,
                                                            &pVertex[0].vt,
                                                            &pVertex[1].vt,
                                                            &pVertex[2].vt);
                              D3DXPlaneFromPoints(&plane2,
                                                            &pVertex[3].vt,
                                                            &pVertex[4].vt,
                                                            &pVertex[5].vt);
                              if(D3DXPlaneIntersectLine(&vecIntersect, &plane1, &vecDir, &vecOrigin))
                              {
                                    pt.x = m_rcView.x + (vecIntersect.x / szTile.cx);
                                    pt.y = m_rcView.y + (vecIntersect.z / szTile.cy);
                                    return(true);
                              }
                              else if(D3DXPlaneIntersectLine(&vecIntersect, &plane2, &vecDir, &vecOrigin))
                              {
                                    pt.x = m_rcView.x + (vecIntersect.x / szTile.cx);
                                    pt.y = m_rcView.y + (vecIntersect.z / szTile.cy);
                                    return(true);
                              };
                        };
                  };

Which iterates through.  m_rcView is my world rectangle.  szTile is the tile size I am using.  This works pretty well on mostly flat terrain and comes back with the right tile.  However when it comes to raised terrain I need to somehow take the TRANSFORMED z-buffer in to account.  Do you know how I can do this?

Thankyou very much for your help so far... I think I'm almost there.  If you have any comments like ("The above code may work, but xyz is better..."), please let me know.


Cheers!


0
Moo-JuiceAuthor Commented:
PS: at the end of the inner y loop above, "pVertex+=6" is present, to move the vertices on...
0
davebytesCommented:
There's a few approaches, as I've said.  If you want to get the z-buffer value, you need to lock the z-buffer and read particular pixel(s) back.  Pretty simple.  There might be flags to set in initial setup of surfaces to say you'll want to be able to lock the zbuf (I can't remember at the moment).

The alternatives if you don't want to read the zbuf might be things like finding all polys that the mouse 2D XY coords are within (circulation tests on transformed polys), and you should be reasonably able to pick the one with the nearest Z, or use the projected-into-3D XY coords of the mouse into the untransformed vertex data to find nearest polys, then nearest Z.

-d
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Moo-JuiceAuthor Commented:
Thanks davebytes.

I'm pretty much there bar a few hiccups which I'm working on, but you got me in the right direction.  Sorry for delay in marking, the world of real-world non-game coding took my attention for a while :)

Cheers


Moo-Juice
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.