Sign in to follow this  
Paul C Skertich

Help on Picking Ray to Triangle \ Intersection

Recommended Posts

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:

[code]

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);

[/code]

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.

[code]
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;

}


[/code]


Thanks for the help.

Share this post


Link to post
Share on other sites
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?

[code]
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;


}
[/code]

Anyone?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
No, the edges are just v2 - v1 and v3 - v1. The [u]normal[/u] 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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
[CODE]
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;
}
[/CODE]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this