Help on Picking Ray to Triangle \ Intersection

Started by
6 comments, last by _WeirdCat_ 11 years, 7 months ago
Before anyone read this - just be sure to note that I'm using DX11 and never will use DX10 or 9. So, D3DXIntersect is not an option. Another note is that I'm very poor in math.

Anyways; In the editor I noticed when I move the mouse over the mesh the cursor sets to cross. This is good, however - calculation is totally wrong and off path. I believe I successfully Unprojected the 2D Mouse Coordiants to 3D World Space. This is what I did:



GetCursorPos(&MousePos);

ScreenToClient(DXWindow,&MousePos);

GetWindowRect(DXWindow,&DXWindowSize);
const XMVECTOR RayOrigion = camera.CameraPosition;
XMVECTOR Mouse2DSpace = XMVectorSet(MousePos.x,MousePos.y,0.0f,0.0f);
XMVECTOR Mouse3DSpace = XMVector3Unproject(Mouse2DSpace,0,0,m_screenWidth,m_screenHeight,0.0f,1.0f,camera.CameraProjectionMatrix,camera.CameraViewMatrix,XMMatrixIdentity());
RayDirection = Mouse3DSpace - RayOrigion;
RayDirection = XMVector3Normalize(RayDirection);
RayDirection = RayDirection * 100.0f;

XMVECTOR vEye;

XMVECTOR vDir;

XMStoreFloat3((XMFLOAT3*)&vEye,RayOrigion);

XMStoreFloat3((XMFLOAT3*)&vDir,RayDirection);

XMStoreFloat3(&MouseFloat3,RayDirection);



I stored the vectors into float3 because I can actually see what is going on. Onward the managed side, if the mouse moves inside the DX Window inside the editor; it goes back and calculates the intesection of Mouse point and Mesh Verticies.

I am having difficult time with finding p0, p1, p2 then finding center point of the triangle.


bool computeIntersection(XMFLOAT3 &p, XMFLOAT3 &target) {
bool result;
result = false;

float iX = (target.x );
float iY = (target.y );
float iZ = (target.z );

float iX1 = (target.x);
float iY1 = (target.y);
float iZ1 = (target.z);
t = XMFLOAT3((iX - p.x) + (iX1 - p.x),(iY - p.y) + (iY - p.y), 1.0f);





if(p.x > iX && p.y > iY) {
result = true;

}



return result;

}





Thanks for the help.
Game Engine's WIP Videos - http://www.youtube.com/sicgames88
SIC Games @ GitHub - https://github.com/SICGames?tab=repositories
Simple D2D1 Font Wrapper for D3D11 - https://github.com/SICGames/D2DFontX
Advertisement
I was trying to figure out was this:

TRIANGLE #1: (P0: 0.1.0, P1: -1,0,0, P2: 1,0,0)
IF MOUSE POINT IS INSIDE TRIANGLE #1 THEN HIT IS TRUE.
ELSE
HIT IS FALSE.
Game Engine's WIP Videos - http://www.youtube.com/sicgames88
SIC Games @ GitHub - https://github.com/SICGames?tab=repositories
Simple D2D1 Font Wrapper for D3D11 - https://github.com/SICGames/D2DFontX
I updated the Computing function to return the distance. Also, I updated when the mesh loads it loads the vertexes into TRI1, TRI2, TRI3 which would make up a triangle.

Now, inside the computing function where it calculates the position of the mouse point in 3D Space compared to the Triangle's Center - I need to know how to calculate either the distance or flag it true that the mouse is inside the mesh triangle. Is it best to calculate the distance between the center of the triangle or what?


float computeNearestPointDistance(XMFLOAT3 &p, std::vector<TRIANGLE> &target) {
float distance = 0.0f;
for(auto &i:target) {

XMVECTOR MouseVector = XMVectorSet(p.x,p.y,p.z,0.0f);
XMVECTOR DistanceVector = XMVectorSet(0,0,0,0);

XMFLOAT3 DistanceFLT3;
XMStoreFloat3(&DistanceFLT3,DistanceVector);
XMFLOAT3 TriangleCenter = XMFLOAT3((i.tr1.x - i.tr2.x - i.tr3.x),(i.tr1.y - i.tr2.y - i.tr3.y), (i.tr1.z - i.tr2.z - i.tr3.z));


distance = TriangleCenter.x - p.x * TriangleCenter.y - p.y * TriangleCenter.z - p.z;

}

return distance;


}


Anyone?
Game Engine's WIP Videos - http://www.youtube.com/sicgames88
SIC Games @ GitHub - https://github.com/SICGames?tab=repositories
Simple D2D1 Font Wrapper for D3D11 - https://github.com/SICGames/D2DFontX
This is a ray-triangle intersection code of mine in Python, from my raytracer. It will return the distance along the ray where the intersection occurs, or will return -1 if the ray doesn't intersect the triangle. For triangle picking, the ray should be the projected camera ray from the cursor's position, with the correct field of view. Note the precomputation steps with the three triangle vertices. Perhaps you can adapt it to your problem, I'm not quite sure what issue you are having - just throwing it out there, in case.

[source lang="python"]""" This is a triangle primitive. """
class Triangle(Primitive):
""" Creates a triangle, defined by three vertices. """
def __init__(self, material, v1, v2, v3):
super().__init__(material)
# Precompute the edges and normal
self.vertex = [v1, v2, v3]
self.edge = [v2 - v1, v3 - v1]
self.normal = normalize(cross(self.edge[0], self.edge[1]))

""" Intersects a ray with this triangle. """
def Intersect(self, ray):
# Compute some initial values
distance = ray.origin - self.vertex[0]
d = 1 / dot(s, self.edge[0])

# Calculate the first barycentric coordinate
s = cross(ray.direction, self.edge[1])
u = dot(distance, s) * d

# Reject the intersection if the barycentric coordinate is out of range.
if (u < -1e-6) or (u > 1.0 + 1e-6):
return -1

# Calculate the second barycentric coordinate.
s = cross(distance, self.edge[0])
v = dot(ray.direction, s) * d

# Reject the intersection if the barycentric coordinate is out of range.
if (v < -1e-6) or (u + v > 1.0 + 1e-6):
return -1

# Compute the final intersection point.
return dot(self.edge[1], s) * d

""" Returns the triangle's surface normal at a point. """
def Normal(self, point):
return self.normal
[/source]

This might be overkill for your needs, but at least it'll give you correct triangle picking if it's done properly.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

So, to find the edge1 - would perform a equation of :

SET V1 V2 V3 as XMVECTORS
FIND EDGE1 BY V2 - V1
FIND EDGE2 BY V3 - V1
THEN NORMALIZE BY CROSS PRODUCT OF EDGE1 AND EDGE2

???
Game Engine's WIP Videos - http://www.youtube.com/sicgames88
SIC Games @ GitHub - https://github.com/SICGames?tab=repositories
Simple D2D1 Font Wrapper for D3D11 - https://github.com/SICGames/D2DFontX
No, the edges are just v2 - v1 and v3 - v1. The normal is calculated by taking the cross product of these two edges, and normalizing that. You can ignore the normal's calculation if you are just doing intersection tests since you don't need it for that, I just added for completeness so I could copy-paste my whole class. The interesting part is in the Intersect() method.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

Just a question - if the Camera is positioned at (0,5,-25) and Looked At (0,5,0). Is this normal for a unprojected mouse coords to be (0.098,0.00973,0.089) for instance. I have the Debug::WriteLine printing out the values of MouseRayOrigion and MouseRayDirection.
Game Engine's WIP Videos - http://www.youtube.com/sicgames88
SIC Games @ GitHub - https://github.com/SICGames?tab=repositories
Simple D2D1 Font Wrapper for D3D11 - https://github.com/SICGames/D2DFontX

bool __fastcall LineIntersectFaceFromModel(int faceindex,TachoGLModel* model,
t3dpoint vLine[2],t3dpoint & interres)
{
int verticeCount = model->VBO_BE[faceindex].length;
Extended MATCH_FACTOR = 0.9999999999;
t3dpoint vNormal;// : ;
t3dpoint vIntersection;// : t3dpoint;
Extended originDistance;// : Extended;
Extended distance1;// : Extended;
Extended distance2;// : Extended;
t3dpoint vVector1;// : t3dpoint;
t3dpoint vVector2;// : t3dpoint;
double m_magnitude;// : Double;
t3dpoint vPoint;// : t3dpoint;
t3dpoint vLineDir;// : t3dpoint;
Extended Numerator;// : Extended;
Extended Denominator;// : Extended;
Extended dist;// : Extended;
Extended Angle,tempangle;// : Extended;
t3dpoint vA, vB;// : t3dpoint;
int i;// : integer;
Extended dotProduct;// : Extended;
Extended vectorsMagnitude;// : Extended;

//CLIP_POS.x = vline[0].x;
//CLIP_POS.y = vline[0].y;
//CLIP_POS.z = vline[0].z;
vNormal.x = 0.0;
vNormal.y = 0.0;
vNormal.z = 0.0;
originDistance = 0.0;
distance1 = 0.0;
distance2 = 0.0;
vPoint.x = 0.0f;
vPoint.y = 0.0f;
vPoint.z = 0.0f;
vLineDir.x = 0.0f;
vLineDir.y = 0.0f;
vLineDir.z = 0.0f;
Numerator = 0.0;
Denominator = 0.0;
dist = 0.0;
Angle = 0.0;

int istart = model->VBO_BE[faceindex].INDEX_START; //first poly vertex index
vVector1.x = model->VBO_V[istart+2].x - model->VBO_V[istart].x;
vVector1.y = model->VBO_V[istart+2].y - model->VBO_V[istart].y;
vVector1.z = model->VBO_V[istart+2].z - model->VBO_V[istart].z;
vVector2.x = model->VBO_V[istart+1].x - model->VBO_V[istart].x;
vVector2.y = model->VBO_V[istart+1].y - model->VBO_V[istart].y;
vVector2.z = model->VBO_V[istart+1].z - model->VBO_V[istart].z;

vNormal.x = ((vVector1.y * vVector2.z) - (vVector1.z * vVector2.y));
vNormal.y = ((vVector1.z * vVector2.x) - (vVector1.x * vVector2.z));
vNormal.z = ((vVector1.x * vVector2.y) - (vVector1.y * vVector2.x));

m_magnitude = sqrt((vNormal.x * vNormal.x) +
(vNormal.y * vNormal.y) +
(vNormal.z * vNormal.z) );

if ( m_magnitude == 0.0 ) return false;
vNormal.x = vNormal.x/m_magnitude;
vNormal.y = vNormal.y/m_magnitude;
vNormal.z = vNormal.z/m_magnitude;
if ( (IsNan(vNormal.x)== true) || (IsNan(vNormal.y)== true) || (IsNan(vNormal.z)== true) )
{
return false;
}
originDistance = -1.0f * ((vNormal.x * model->VBO_V[istart].x) +
(vNormal.y * model->VBO_V[istart].y) +
(vNormal.z * model->VBO_V[istart].z));

distance1 = ((vNormal.x * vLine[0].x) +
(vNormal.y * vLine[0].y) +
(vNormal.z * vLine[0].z)) + originDistance;
distance2 = ((vNormal.x * vLine[1].x) +
(vNormal.y * vLine[1].y) +
(vNormal.z * vLine[1].z)) + originDistance;
if(distance1 * distance2 >= 0.0f)
return false;
vLineDir.x = vLine[1].x - vLine[0].x;
vLineDir.y = vLine[1].y - vLine[0].y;
vLineDir.z = vLine[1].z - vLine[0].z;
m_magnitude = sqrt((vLineDir.x * vLineDir.x) +
(vLineDir.y * vLineDir.y) +
(vLineDir.z * vLineDir.z) );

vLineDir.x = vLineDir.x/m_magnitude;
vLineDir.y = vLineDir.y/m_magnitude;
vLineDir.z = vLineDir.z/m_magnitude;
Numerator = -1.0f * (vNormal.x * vLine[0].x +
vNormal.y * vLine[0].y +
vNormal.z * vLine[0].z + originDistance);

Denominator = ( (vNormal.x * vLineDir.x) + (vNormal.y * vLineDir.y) + (vNormal.z * vLineDir.z) );
if( Denominator == 0.0f) {
vIntersection = vLine[0];
interres = vIntersection;
} else {

dist = Numerator / Denominator;
vPoint.x = (vLine[0].x + (vLineDir.x * dist));
vPoint.y = (vLine[0].y + (vLineDir.y * dist));
vPoint.z = (vLine[0].z + (vLineDir.z * dist));
interres = vPoint; // Return the intersection point
}
//temp_intersect_v.x := vIntersection.x;
//temp_intersect_v.y := vIntersection.y;
//temp_intersect_v.z := vIntersection.z;
//temp_intersect_v2 := vPoint;
//CLIP_INTERSECT_POS := temp_intersect_v;
for (i = 0; i < verticeCount; i++) {

vA.x = model->VBO_V[istart+i].x - interres.x;
vA.y = model->VBO_V[istart+i].y - interres.y;
vA.z = model->VBO_V[istart+i].z - interres.z;

vB.x = model->VBO_V[istart+ ( (i + 1) % verticeCount )].x - interres.x;
vB.y = model->VBO_V[istart+ ( (i + 1) % verticeCount )].y - interres.y;
vB.z = model->VBO_V[istart+ ( (i + 1) % verticeCount )].z - interres.z;

dotProduct = ( (vA.x * vB.x) +
(vA.y * vB.y) +
(vA.z * vB.z) );

vectorsMagnitude = sqrt(
(vA.x * vA.x) +
(vA.y * vA.y) +
(vA.z * vA.z)
)
*
sqrt(
(vB.x * vB.x) +
(vB.y * vB.y) +
(vB.z * vB.z)
);
tempangle = ArcCos( dotProduct / vectorsMagnitude );

if(IsNan(tempangle) == true) tempangle = -1990.0f;

Angle = Angle + tempangle;
}

if(Angle >= (MATCH_FACTOR * (2.0f * 3.140f)) ) return true;

return false;
}

This topic is closed to new replies.

Advertisement