• Advertisement

Archived

This topic is now archived and is closed to further replies.

The ol' 2D click -> 3D world coordinate question

This topic is 5800 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 searched the archives for this problem and didn''t find a satisfactory answer. I''m basically trying to find out where the player clicked on "terrain" in an RTS no matter what the position of the camera is (I don''t care about rotation much, though, just scaling with zoom and pan). I''m using DirectX 8 and Visual Basic 6.0. One person suggested using D3DXVec3Unproject to get the points on the near and far planes, and then use D3DXPlaneIntersectLine (using a plane based on the "terrain") to find where the point would be at the terrain. Great. Except... in VB D3DXPlaneIntersectLine returns another plane, not a vector. I''m having trouble figuring out what the a, b, c, and d in the plane type mean, or if there''s another, more elegant way of doing what I want to do. Any help? Again, forgive me since this has been asked before. This is my first post here.

Share this post


Link to post
Share on other sites
Advertisement
In the DX8 SDK there is a D3D sample app that can identify the triangle of a 3D object (A tiger in this case) using the position of the cursor, maybe this would help?

  Downloads:  ZeroOne Realm

Share this post


Link to post
Share on other sites
The a, b, c, and d components of the Plane are the coefficients used to define the plane in the plane equation. You can pretty much ignore them for now. Instead, use D3DXPlaneFromPoints() to create a plane out of a triangle. Then, since, as you said, the VB version of D3DPlaneIntersectLine() returns a plane (o.O), you will need to check around the net to find the equation for a ray-plane intersection. You should be able to figure it out from there.

Z,

Share this post


Link to post
Share on other sites
Thanks, I''ll look for the ray-plane intersection equation.

Like I said, I''m not really looking at this for picking a triangle or mesh, but finding where a unit in my game should move to. I''ll post any solution I find for anyone else interested.

Share this post


Link to post
Share on other sites
One way that can be made to be fairly robust:

When the user clicks:

Encode the X, Y, Z positions of the terrain as color (R = X, Y = G, B = Z) and draw the terrain (but don't present it onscreen!)

Now, look at the resulting picture (you could either lock the back buffer or render into a texture) and find the value of RGB at the point where the mouse is.

Voila! you have the position. (the render also interpolates...) Now, clear the back buffer and continue!

Depending on the amount of precision you need, you may have to get more clever about how you pack the colors, but this is a nice place to start. One of the problems with vector methods is that one tall mountain could really screw you up. Unless you check all the triangles, clicking on a mountain could seem like a click on terrain behind it. It becomes a question of whether it's faster to render and check or loop through all the geometry. In some cases, you could try to render just that one pixel to speed things up (I've done this in OpenGL, but not DX8). Remember to turn off lighting, textures, etc. This can be pretty zippy if done right.
Also, it can make for a good general solution draw the whole scene with all objects:

R = 0 for terrain and 1-255 for vehicles
G = X for terrain, 0 for vehicles
B = Y for terrain, 0 for vehicles

(clever packing could yield better results)

Render the scene and check the value. If red is not 0, then you selected vehicle[R], if it is 0, then read the position for G and B and index that into your height map to get Z.

Vertex shaders also open up many possibilities...


Edited by - CrazedGenius on September 8, 2001 6:57:06 PM

Share this post


Link to post
Share on other sites
That''s an interesting idea, CrazedGenius, but if you want more resolution than 256x256, you''ll need to step up to more than 24-bits of color (which I think you mentioned). Like I said, a mountain wouldn''t obscure the clicking too much since I don''t do much rotation. It''s a consideration, though.

Being that I expect around 200 units to be in play at once, memory is at more of a premium than processor cycles, so finding a quicker solution isn''t as important as finding one that can work with the data I already have (a mesh).

I appreciate everyone''s comments so far. It''s rare to have people come up with productive answers instead of just telling me to use C++ and buzz off. Still, other than the offscreen buffer method, I haven''t been able to come up with a more robust way of doing this. Most of what I''ve found on ray-plane intersection seems redundant with using the D3DX function. Why the $@!~@$#^ does it have to return a plane??

Share this post


Link to post
Share on other sites
First thing, take a look at Magic Software''s free code. In there you''ll find routines for ray/bounding box intersections as well as many, many other useful functions.

If you want to pick entire objects in a 3d scene, rather than individual polygons, stick to using bounding boxes.

Secondly, you need convert the mouse click into a 3d ray, I''m not going to try and explain the theory behind that, but there is sample code in the DX SDK.

Here''s a cut n'' paste from my project code that shows how simple the whole process is. You won''t be able to use it directly but it should make for some interesting reading..

  
///////////////////////////////////////////////////////////////////////////////

// CheckModelSelect()

// See if the user has clicked any of the on-screen models

// by testing if the click was inside any of the models

// bounding boxes

//

unsigned int CMouseView::CheckModelSelect(float x, float y, CMattsDirect3D *D3D)
{
D3DMATRIX matProj;
D3D->lpDevice->GetTransform( D3DTRANSFORMSTATE_PROJECTION, &matProj );

// Compute the vector of the pick ray in screen space

Mgc::Vector3 v;
v[0] = ( ( ( 2.0f * x ) / m_fScWidth ) - 1 ) / matProj._11;
v[1] = -( ( ( 2.0f * y ) / m_fScHeight ) - 1 ) / matProj._22;
v[2] = 1.0f;

// Transform the screen space pick ray into 3D space

m_cPickRay.Direction() = Mgc::Vector3(
v[0]*m_cInverseViewMatrix._11 + v[1]*m_cInverseViewMatrix._21 +
v[2]*m_cInverseViewMatrix._31,
v[0]*m_cInverseViewMatrix._12 + v[1]*m_cInverseViewMatrix._22 +
v[2]*m_cInverseViewMatrix._32,
v[0]*m_cInverseViewMatrix._13 + v[1]*m_cInverseViewMatrix._23 +
v[2]*m_cInverseViewMatrix._33);

m_cPickRay.Origin() = Mgc::Vector3( m_cInverseViewMatrix._41,
m_cInverseViewMatrix._42,
m_cInverseViewMatrix._43);

// cycle through all the models..

for (unsigned int t = 0; t < m_uiNumModels; t++)
{
ComputeSelectedBoundingBox( t );

// TO DO: Check against all bounding boxes, and return the first timed intersection

if( Mgc::TestIntersection( m_cPickRay, m_cSelectedBox ) )
return t;

}

return MV_NONSELECTED;
}



The variables should be self explanatory either by their names or their use, sorry I don''t have the time to explain it more thoroughly.

Just take advantage of that Magic Software source code. If you have any trouble using it in your project let me know.

Cheers

Matt




Share this post


Link to post
Share on other sites
Just something to think about.... using bounding boxes around irregularly shaped objects could create issues. Imagine many units crowded together. If the boxes overlap, which one are you clicking on?? The color approach always works because it "sees" exactly what the user sees. Using the full 24 bits for units let''s you manage ALOT of units...

Share this post


Link to post
Share on other sites
hm.. raytracing for intersection knows this, too.. it returns a t-value, and the lowest one is the object you clicked on..

and dont render your scene 2 times.. doing it offline is much faster..

we wanna play, not watch the pictures

Share this post


Link to post
Share on other sites
Well, I still haven''t figured out how to do this seemingly simple problem. I have been messing with the plane that D3DX returns and if I correlate a and b to x and y, it does seem to be the right direction, but the wrong distance. It always comes up short and I have no idea why. I''m probably just missing the bigger picture here, since my 3D math isn''t as good as it should be for doing game programming. I did fail Calc II twice. Badly. Although that shouldn''t matter unless the solution lies in me integrating something. But anyway...

Correct me if I''m wrong, but the intersection between a line and a plane is a point, right? I''m still wondering why it''s returning a plane. 3dModelMan, thanks for the code, but I''m more interested in WHERE the mouse was clicked, not IF it intersects something. The site you gave was very helpful, but it seems to be centered around using the guy''s game engine. Still very useful, though, thanks.

Share this post


Link to post
Share on other sites
R u looking for the mathematics for finding out the intersecting point of a ray through a plane ?? If that''s the case.... then i guess i could help u. But if u r looking for something else.... then i''m afraid this post wont help u much. Anyways, lemme assume that u actually want to know how to calculate the co-ordinate of the intersection of a ray through a plane. Letz work out the problem ......

We all know that the equation of a plane is
r.n = k
where
r = position vector of any point on the plane.
n = normal ( perpendicular ) vector of the plane
k = constant

NB: k = n.c ( where "c" is any position vector [ co-ordinate ] on the plane )

Then we also know the vector equation of a straight line

r = a + µb
where
r = position vector of any point on the line
a = position vector of one point on the line
µ = arbitary constant
b = a vector parallel to the direction of the line

Equation of the plane: r.n = k
Equation of the line : r = a + µb

combining both we get : ( our primary goal is to find µ )

(a + µb).n = k
a.n + µ(b.n) = k
µ = (k - a.n)/(b.n)

now put the value of µ in (r = a + µb)

r = a + ( (k - a.n)/(b.n) ) b

Here r is the position vector of the intersection of the ray through the plane. Now itz all upto you how u manipulate ur program.

Since you have planes then u must have equations for ur planes too.
Hence you know "n" and "k" automatically.

"a" is nothing but just the screen coodinate of the mouse. "b" is the direction you are looking at. So calculating "r" wont be that difficult i hope.

My apologies for any mistake i made in my post.

For any questions plz feel free to write........

browny.

Share this post


Link to post
Share on other sites
Okay, I think I have it figured out. I found out that my original method was working after all. The problem was that the plane returned seems to be using a different coordinate system than the one my unit uses. So, if I tell the unit to move using the coordinates returned, they''re way off. My terrain seems to be have the bounding box of (-103,-274)-(321,91), but when I move the unit to the edges of the terrain it''s coordinates show (1029,900)-(3195,-2750) for the lower-left and upper-right bounds. Obviously this has something to do with local vs. world coordinates, right?

Here''s what I do so far:

-Normalize the X,Y mouse clicks
-Multiply the terrain matrix by the identity matrix
-Do two D3DXVec3Unproject''s, one for z=0, one for z=1
-Create three points with the bounding box given by ComputeBoundingBoxFromMesh
-Use those points to create a plane with a common z
-Use D3DXPlaneIntersectLine to see where the line hit the plane (I think; I''m assuming a=x, b=y and c=z)

Using a=x and b=y gives me somewhat correct numbers, but like I said, the coordinate systems seem to be off. I''m still trying to wrap my brain around the plane math, so it might be incredibly idiotic of me to assume that a=x and so on, but it''s the closest thing I can figure out. I think I''m going to try browny''s method next.

Share this post


Link to post
Share on other sites
I found these D3DX functions today after reading your post:

//Projects a vector from object space into screen space.
D3DXVECTOR3* D3DXVec3Project(
D3DXVECTOR3* pOut,
CONST D3DXVECTOR3* pV
CONST D3DVIEWPORT8* pViewport,
CONST D3DXMATRIX* pProjection
CONST D3DXMATRIX* pView,
CONST D3DXMATRIX* pWorld
);

//Projects a vector from screen space into object space.
D3DXVECTOR3* D3DXVec3Unproject(
D3DXVECTOR3* pOut,
CONST D3DXVECTOR3* pV
CONST D3DVIEWPORT8* pViewport,
CONST D3DXMATRIX* pProjection
CONST D3DXMATRIX* pView,
CONST D3DXMATRIX* pWorld
);

I tested them, and Project works well and it swaps a position in 3d space for a screen location. Unfortunately, Unproject works in some odd way I am not sure what it''s doing. Perhaps if you combined this with some sort of ray casting you could get your position.

It sounds like it would work.

Share this post


Link to post
Share on other sites
Hmm, would anybody have any working code on this subject?
I havent a clue what you guys are talking about, and the "Magic Software''s free code" requires a password.

Thanks.

Share this post


Link to post
Share on other sites
Hmm you''re correct that D3DXVec3Project works from screen to world however from world to screen I believe that you should use
D3DXVec3Transform or D3DXVec3TransformCoord... not sure thought

// Fredrik

Share this post


Link to post
Share on other sites
Dont you have it backwards?
D3DXVec3Project:
Projects a vector from object space into screen space.

Anyways, could anyone please explain how to use this?

[edited by - hello2k1 on March 30, 2002 9:23:56 PM]

Share this post


Link to post
Share on other sites
Quick note; with 16bit color that would be something on the range of 65535 units, which is a heck of alot

Also, if you have a quadtree of occtree, finding intersection points becomes alot easier, or possibly even more so if you have a PVS system for the current cell (user cannot click on what they cannot see).

You really have three choices:

1. Use a srtucture (e. Quadtree) and intersect the ray with the bounding volumes to greatly reduce the set. After getting a positive intersection from the bounding volumne, test intersect the ray with the two planes formed by the heights at the corners of the quadtree (two planes because a quad must be decomposed into two triangles). Whenever you encounter an intersection with a plane, test to see if the t value, along the ray ( r(x) = o + dt [o&d are vectors]) is less than the current one stored, if it is not, you can stop recursion there, as no intersections will be closer than the one you currently have.

2. Project the ray onto the terrain. Find the intersection of the ray and a horizontal plane (formed by matching with the lowest point on the terrain). Then, ignore the vertical component and use a method like bresenhams line algo to step through the heightmap, checking to see if the ray crossed from above to below. Once you find the region, it is best to take a sample of the planes of a couple of heightmap points around, to give sub-pixel accuracy. This is the best method i can think of that does not require any precomputations.

3. Brute force intersection with heightmap triangles using some method; occtree, sphere-tree, all the usual collision detection structures. Might want to avoid BSP trees.

For a good reference to any intersection testing routines, lookup the book Real Time Rendering, or its website www.realtimerendering.com

[edited by - Smoogle on April 1, 2002 2:32:57 AM]

Share this post


Link to post
Share on other sites
Well right now my terrain is flat, so #2 shoudl work fine. BUt I have no idea as to how i''d cast a ray. Is it possible that you could just whip up some quick code 4 me? (the y coord for terrain is 0)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well you could just use D3DXVec3Project to project the position vectors of your units into screen space and check if they are close enough to your mouse coords. This is at least what i did with my terrain editor.

Share this post


Link to post
Share on other sites
It seems like I''m going in circles.. But how do I use D3DXVec3Project?

Would it be possible for someone to just pass up some quick code?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This is my vertex selection code. You will probably want to
check with only those units that are in your screen for better
performance. This is in delphi but you should be able to make it
out. MatIdentity is your world matrix and SelV is the index of
selected vertex. You can use
Abs(unit.x/y - mouse.x/y) < something
instead of those CompareValues.

// Get current viewport
FD3DDevice.GetViewport(FD3DViewport);

// Project all terrain vertices to screen space and compare
// them with mouse coordinates
for f := 0 to (VBLength-2) do
begin
D3DXVec3Project(SWV1, fVertices[f].position, FD3DViewport,
matProj, matView, matIdentity);
if (CompareValue( X, SWV1.x, 6.0 ) = 0 ) and (CompareValue( Y,
SWV1.y, 6.0 ) = 0 ) then SelV := f;
end;

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Ok, well I''m not too much of a VB fan myself, so correct me if I''m wrong. But basically this projects a ray from fVertices[f].position (where did you get that value btw?) Then tests whether SWV1 (???) is equal to 6. And what does SelV := f mean?
// Get current viewport
FD3DDevice.GetViewport(FD3DViewport);

// Project all terrain vertices to screen space and compare
// them with mouse coordinates
for f := 0 to (VBLength-2) do
begin
D3DXVec3Project(SWV1, fVertices[f].position, FD3DViewport,
matProj, matView, matIdentity);
if (CompareValue( X, SWV1.x, 6.0 ) = 0 ) and (CompareValue( Y,
SWV1.y, 6.0 ) = 0 ) then SelV := f;
end;

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
fVertices[].position is your pos. vector in world space( position of
your little soldier for example, or if you have a vertex buffer, lock it and get the position or store all your positions in an array ).

Then it projects this to screen space coordinate SWV1
( just a temporary vertex ), where x and y are 2d screen
coordinates and z is depth value witch is not used here.

Yeah, the CompareValue thing is not self-explanatory, but you
can replace it with

if ( Abs( mouse.x - SWV1.x ) < 6 ) and
( Abs( mouse.y - SWV1.y ) < 6 )

This just tests if if the distange between mouse x-coord and
your vertex-position-in-screen-space x-coord is less than 6
and does the same for y-coordinates.

SelV := f means that the currenly tested vertex( with index of f)
will be the salected vertex.

And sorry if I mixed vertices and vector, but I am not so sure
about their usage.

Share this post


Link to post
Share on other sites
Hmm.. Seems awfully expensive cpu wise. Wouldnt it be possible to use D3DXVec3UnProject() to make that a bit more efficient?

Basically what I want to do is use D3DXVec3UnProject() to send a ray from my cursor and follow it until it hits (y=0), then get the x/z coords. Any ideas on how to pull that off? I have been trying at it for a while now.. But I have no idea how to get it to work.

Share this post


Link to post
Share on other sites

  • Advertisement