Hello, i want to pick mesh (oh no, this is no really mesh but group of vertices?) and i found tut on the web but it only describes how to do this when you have mesh and i don't have it, i know i have to use *IntersectTri but i dunno' how Please, throw me some sample

Your post is confusing me. You wrote you have a collection of vertices that do not form a mesh. The term "mesh" is usually used for a surface consisting of adjacent faces, defined by vertices and edges, where each face is bounded by edges and each edge reaching from a vertex to another one. A mesh may also mean a wireframe mesh, i.e. the same as the former one but without the faces. Both of these kinds of meshes can be hit tested using a couple of ray-face (often ray-triangle) tests. (The wireframe mesh can be seen as being temporarily provided with faces for this purpose.)

If you really have a "soup of vertices" only, you can compute a bounding volume, e.g. an axis-aligned bounding box, oriented bounding box, bounding sphere, bounding cylinder, or whatever else seems you meaningful. Then do a ray-bounding volume hit test; the ray-triangle test is then seldom of interest.

So, what exactly do you mean with "oh no, this is no really mesh but group of vertices"?

D3DVERTEX Block[] = { { 1.0f, -1.0f, 5.0f, 0.0f, 2.0f },
{ 3.0f, -1.0f, 5.0f, 2.0f, 2.0f },
{ 1.0f, 1.0f, 5.0f, 0.0f, 0.0f },
{ 3.0f, 1.0f, 5.0f, 2.0f, 0.0f },

{ 3.0f, -1.0f, 5.0f, 0.0f, 2.0f },
{ 3.0f, 1.0f, 5.0f, 0.0f, 0.0f },
{ 3.0f, -1.0f, 7.0f, 2.0f, 2.0f },
{ 3.0f, 1.0f, 7.0f, 2.0f, 0.0f },

{ 1.0f, -1.0f, 5.0f, 2.0f, 2.0f },
{ 1.0f, 1.0f, 5.0f, 2.0, 0.0f },
{ 1.0f, -1.0f, 7.0f, 0.0f, 2.0f },
{ 1.0f, 1.0f, 7.0f, 0.0f, 0.0f },

{ 1.0f, -1.0f, 5.0f, 0.0f, 0.0f },
{ 3.0f, -1.0f, 5.0f, 0.0f, 2.0f },
{ 1.0f, -1.0f, 7.0f, 2.0f, 0.0f },
{ 3.0f, -1.0f, 7.0f, 2.0f, 2.0f },

{ 1.0f, 1.0f, 5.0f, 0.0f, 0.0f },
{ 3.0f, 1.0f, 5.0f, 0.0f, 2.0f },
{ 1.0f, 1.0f, 7.0f, 2.0f, 0.0f },
{ 3.0f, 1.0f, 7.0f, 2.0f, 2.0f },

{ 1.0f,-1.0f,7.0f, 0.0f, 2.0f },
{ 3.0f,-1.0f,7.0f, 2.0f, 2.0f },
{ 1.0f, 1.0f,7.0f, 0.0f, 0.0f },
{ 3.0f, 1.0f,7.0f, 2.0f, 0.0f } };

This is my cube, its not loaded as mesh from .x

...
This is my cube, its not loaded as mesh from .x

But it nevertheless defines a face mesh. The vertices are explicit, while the edges and faces are implicit. The faces are given as quadrangles. Solely because it isn't given as a D3D mesh doesn't mean that it isn't a mesh at all ...

You have several options from here:

1. You can use the bounding volume method. In the given example an OBB would fit the mesh perfectly, but that is of course not the general case. So this method may be too restricted, or at least just useful for a first fast pre-test.

2. You can write an iterator that grants access to the sequence of faces of a mesh. This way the inner structure of the mesh would be abstracted away from the ray-face test. But you then have to invoke a virtual function for each face.

3. You can write a loop over the faces of the mesh, and invoke the ray-face test from inside the loop. This would also abstract away the inner structure but also avoids invoking a virtual function for each face.

For the sake of clarity to the OP (and IMHO 2 errors in the code) here some comments on the shown code snippet:


float Pick(D3DVERTEX* model, D3DXMATRIX ObjectsWorldSpace, float mouseX, float mouseY)
{
//Transform 2D pick position on screen space to 3D ray in View space
D3DXVECTOR3 pickRayViewSpace; // <-- (1)
pickRayViewSpace.x = ((( 2.0f * mouseX) / ClientWidth ) - 1 ) / Projection(0,0);
pickRayViewSpace.y = -((( 2.0f * mouseY) / ClientHeight) - 1 ) / Projection(1,1);
pickRayViewSpace.z = 1.0f;

D3DXVECTOR3 pickRayViewSpacePos(0.0f, 0.0f, 0.0f);
D3DXVECTOR3 pickRayViewSpaceDir(pickRayViewSpace.x, pickRayViewSpace.y, pickRayViewSpace.z); // <-- (2)

// Transform 3D Ray from View space to 3D ray in World space
D3DXMATRIX pickRayWorldSpace;
D3DXMatrixInverse(&pickRayWorldSpace, 0, &View);

D3DXVec3TransformCoord(&pickRayViewSpacePos, &pickRayViewSpacePos, &pickRayWorldSpace); // <-- (3)
D3DXVec3TransformNormal(&pickRayViewSpaceDir, &pickRayViewSpaceDir, &pickRayWorldSpace); // <-- (3)
// ^-- (4)

// Transform 3D Ray from World space to each objects/models own local space // <-- (5)
int closestObject = -1;
float closestObjectDist = FLT_MAX;

// Transform 3D Ray from World space to each objects/models own local space

D3DXMATRIX pickRayLocalSpace;
D3DXMatrixInverse(&pickRayLocalSpace,NULL,&ObjectsWorldSpace);

D3DXVECTOR3 pickRayLocalSpacePos,pickRayLocalSpaceDir;

D3DXVec3TransformCoord(&pickRayLocalSpacePos,&pickRayViewSpacePos,&pickRayLocalSpace);
D3DXVec3TransformNormal(&pickRayLocalSpaceDir,&pickRayViewSpaceDir,&pickRayLocalSpace);
D3DXVec3Normalize(&pickRayLocalSpaceDir,&pickRayLocalSpaceDir);

//Set hitDistance to FLT_MAX in case there was no intersection
float hitDistance = FLT_MAX;

//Now you would want to test the bounding box if you had one, or just test the actual object
//If you were using a mesh, you can easily test using the intersect method of the mesh interface
//But, since you don't have a mesh, you can do this manually

//I'm going to assume the first three values of your vertex structure are the position

//Loop through each triangle in the object
for(int i = 0; i < NumFaces; i++)
{
//Triangle's vertices V1, V2, V3
D3DXVECTOR3 tri1V1 = D3DXVECTOR3(0.0f, 0.0f, 0.0f);
D3DXVECTOR3 tri1V2 = D3DXVECTOR3(0.0f, 0.0f, 0.0f);
D3DXVECTOR3 tri1V3 = D3DXVECTOR3(0.0f, 0.0f, 0.0f);

//Get triangle
tri1V1 = model[(i*3)+0].pos;
tri1V2 = model[(i*3)+1].pos;
tri1V3 = model[(i*3)+2].pos;
// ^-- (6)

//Transform vertice's local space to objects world space
D3DXVec3TransformCoord(&tri1V1, &tri1V1, &ObjectsWorldSpace);
D3DXVec3TransformCoord(&tri1V2, &tri1V2, &ObjectsWorldSpace);
D3DXVec3TransformCoord(&tri1V3, &tri1V3, &ObjectsWorldSpace);
// ^-- (7)

//Find the normal using U, V coordinates
D3DXVECTOR3 U = D3DXVECTOR3(0.0f, 0.0f, 0.0f);
D3DXVECTOR3 V = D3DXVECTOR3(0.0f, 0.0f, 0.0f);
D3DXVECTOR3 faceNormal = D3DXVECTOR3(0.0f, 0.0f, 0.0f);

U = tri1V2 - tri1V1;
V = tri1V3 - tri1V1;

//Comput face normal using U, V
D3DXVec3Cross(&faceNormal, &U, &V);

D3DXVec3Normalize(&faceNormal, &faceNormal);

//Calculate a point on the triangle for the plane equation
D3DXVECTOR3 triPoint = (tri1V1 + tri1V2 + tri1V3)/3;

//Get plane equation "Ax + By + Cz + D = 0" Variables
float tri1A = faceNormal.x;
float tri1B = faceNormal.y;
float tri1C = faceNormal.z;
float tri1D = (-tri1A*triPoint.x - tri1B*triPoint.y - tri1C*triPoint.z);

//Now we find where the ray intersects with the triangles plane

float ep1, ep2, t = 0.0f; //Parts of the equation to find where the line intersects
float planeIntersectX, planeIntersectY, planeIntersectZ = 0.0f;
D3DXVECTOR3 pointInPlane = D3DXVECTOR3(0.0f, 0.0f, 0.0f);

ep1 = (tri1A * pickRayLocalSpacePos.x) + (tri1B * pickRayLocalSpacePos.y) + (tri1C * pickRayLocalSpacePos.z);
ep2 = (tri1A *pickRayLocalSpaceDir.x) + (tri1B * pickRayLocalSpaceDir.y) + (tri1C * pickRayLocalSpaceDir.z);

//Make sure there are no divide-by-zeros
if(ep1 != ep2)
t = -(ep2 + tri1D)/(ep1 - ep2);
// ^-- (8)

planeIntersectX = (pickRayLocalSpacePos.x * t) + (pickRayLocalSpaceDir.x * (1 - t));
planeIntersectY = (pickRayLocalSpacePos.y * t) + (pickRayLocalSpaceDir.y * (1 - t));
planeIntersectZ = (pickRayLocalSpacePos.z * t) + (pickRayLocalSpaceDir.z * (1 - t));
// ^-- (9)

pointInPlane = D3DXVECTOR3(planeIntersectX, planeIntersectY, planeIntersectZ); // <-- (10)

//Call function to check if point is in the triangle
if(PointInTriangle(tri1V1, tri1V2, tri1V3, pointInPlane))
{
float distX = pointInPlane .x - pickRayLocalSpacePos.x;
float distY = pointInPlane .y - pickRayLocalSpacePos.y;
float distZ = pointInPlane .z - pickRayLocalSpacePos.z;

hitDistance = sqrt(distX*distX + distY*distY + distZ*distZ);
// ^-- (11)

//Return the distance to the hit, so you can check all the other pickable objects in your scene
//and choose whichever object is closes to the camera
return hitDistance; // <-- (12)
}
}
}


(1) pickRayViewSpace is a misleading name, because ...Space is used in all other cases for a space transformation matrix, but here it is used for a vector.

(2) pickRayViewSpaceDir is a 1:1 copy of pickRayViewSpace.

(3) Using pickRayViewSpace... as target is misleading, because the pickRayViewSpace... will store world space co-ordinates.

(4) All code until here is executed for each object, although it is needed only once for all objects.

(5) Comment doesn't describe the functionality of the following code.

(6) This assumes that the faces are triangles, but in the OP they are quads. (This is one of the reasons I suggested to separate mesh iteration and ray intersection test.)

(7) This is a bug: You compute the vertices' world co-ordinates and use them together with the ray's model local co-ordinates (see computation of ep1 and ep2). This conversion is needless.

(8) What is computed here?

IMHO there is a ray given as
r( t ) := r[sub]0[/sub] + t * r[sub]d[/sub]
and the plane in "Hessian Form"
( p - o ) . n = 0
so that, using A to D as abbreviations of tri1A to tri1D from the code,
p[sub]x[/sub] * A + p[sub]y[/sub] * B + p[sub]z[/sub] * C + D = 0
where the "point of interest" p is given by the ray r(t), so that
e[sub]1[/sub] + t * e[sub]2[/sub] + D = 0
where e[sub]1[/sub] and e[sub]2[/sub] are ep1 and ep2 in the code snippet. Solving this for t gives
t = - ( e[sub]1[/sub] + D ) / e[sub]2[/sub]
what differs from the computation in the code.

BTW: The computation will detect objects behind the camera as well.

(9) In the sequel of (8), the point of intersection is computed here as a Barycentric co-ordinate of a position vector on the one side and a direction vector on the other?

However, considering (8) it would be sufficient to compute
r[sub]0[/sub] + t * r[sub]d[/sub]
or, in terms of the code
planeIntersectX = pickRayLocalSpacePos.x + pickRayLocalSpaceDir.x * t;
...

(10) Just a 1:1 copy.

(11) Assuming that the spaces are not scaled, for a comparison it would be sufficient to directly use t as a distance measure. This would avoid additional computations in the loop, especially the costly sqrt. Even if scaling plays a role, the sqrt can be omitted and the comparison can be done using the square of the real distance.

(12) The if-clause causes the loop to be terminated at the first face that is hit. This draws the routine to be not suitable for situations where object meshes may intersect.



Please correct me if I'm wrong.

I took my picking and collision detection functions and through them together, knowing there would probably be mistakes, I was only putting something out there he could work with and fix up.
...
I'll look at it some time tonight and try to repost a more clear and efficient function. Thanks for looking through that though, I really should have spent a little more time going through it, I knew it wasn't perfect but I had to go to work

I already assumed something similar, so I've chosen to start the post with "to clarify ..." I assume that the OP is happy about any help though.

A couple things you mentioned did cross my mind though, mainly how objects behind will be picked Too, and triangles after the first detected pick would not be checked (I thought that might save a little computation time since the point was when an objects picked, its picked)...

Breaking the loop on the first hit is okay in general. But there are 2 caveats (although both can be seen as extreme cases and hence ignored):

1. At least in a modeler, objects may intersect (this may or may not be an issue in a given use case). So the ray with increasing t e.g. enters object A, then enters object B, then leaves object A, then leaves object B. Now, if a backface of object A is found first, and a frontface of object B is found first, then object B will be picked although object A is in front.

2. Objects may touch. If a backface of the object in front and a front face of the object behind is picked, numerical inaccuracies will prefer the one or the other object (typical z fighting issue). But using only frontside hits give you a better chance to compare really distinct points of both objects.

... About the objects behind the camera getting picked, shouldn't be difficult to fix since the rays position is used to find t, so if t is greater than 1, then skip the rest of that triangles check.

Assuming that the ray's origin is located at the camera's eye-point, any t less than 0 would denote a hit behind the camera. However, when one wants to use orthogonal projection, too, it may be wise to investigate whether t is in range of the near and far clipping plane instead. That would resemble the range of visibility.