Jump to content

  • Log In with Google      Sign In   
  • Create Account

Help on Picking Ray to Triangle \ Intersection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 SIC Games   Members   -  Reputation: 617

Like
0Likes
Like

Posted 22 September 2012 - 02:46 PM

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


Sponsor:

#2 SIC Games   Members   -  Reputation: 617

Like
0Likes
Like

Posted 22 September 2012 - 03:03 PM

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


#3 SIC Games   Members   -  Reputation: 617

Like
0Likes
Like

Posted 22 September 2012 - 07:42 PM

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


#4 Bacterius   Crossbones+   -  Reputation: 8861

Like
1Likes
Like

Posted 22 September 2012 - 10:17 PM

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.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#5 SIC Games   Members   -  Reputation: 617

Like
0Likes
Like

Posted 22 September 2012 - 11:21 PM

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


#6 Bacterius   Crossbones+   -  Reputation: 8861

Like
1Likes
Like

Posted 22 September 2012 - 11:56 PM

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.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#7 SIC Games   Members   -  Reputation: 617

Like
0Likes
Like

Posted 23 September 2012 - 04:49 PM

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


#8 WiredCat   Members   -  Reputation: 314

Like
0Likes
Like

Posted 24 September 2012 - 02:46 PM


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;

}






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS