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!

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.

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....

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

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.

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.

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.

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

Featured Post

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

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