Archived

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

intersection between a triangle and a line

This topic is 5867 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I''m looking for a function which gives me information about a intersectionpoint. horniestly the function should look like this: vect3 findintersection( vect3 trianglepoints[3], vect3 linestart, vect3 lineend ); I need a triangle and the line to test. is the line goes throught the triangle, the function should return the intersectionpoint. if the returnvalue = lineend, the line did not vcontact the triangle. can anyone help me ? (i know, my english is godlike ))

Share on other sites
//============================================================================// triray.cpp : ray-triangle intersection routine. Given a ray R and a triangle//   ABC, determines first whether R hits the infinite plane containing ABC;//   then if the plane is hit, the hit point is determined to be inside or//   outside of the triangle on the plane (2D problem). Inside-outside test//   proceeds as follows: 3D triangle and the 3D point are projected onto the//   plane corresponding the largest component in the triangle normal vector//   being equal to zero (i.e. if Z is the largest, then project onto XY-plane).//   Then the 2D triangle and point is sent to the 2D inside-outside test://   point is checked against each edge of the triangle using an inside-outside//   half-space check using the cross-product.//============================================================================#include "vect2d.hpp"#include "vect3d.hpp"// HANDY UNIVERSAL ABSOLUTE VALUE FUNCTION#define ABS(x) (((x)<0)?(-(x))x)) //----------------------------------------------------------------------------// CHECKS IF 2D POINT P IS IN TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT//   Given a triangle ABC and a point P, determines if P is inside//   of ABC (regardless of vertex ordering - CCW or CW). 2D version only, but//   this handles the 3D case if appropriately projected to the XY, YZ, or XZ//   planes (by dropping corresponding component; i.e. drop Z in XY projection).//----------------------------------------------------------------------------int Pt2dInTri(Vect2d A, Vect2d B, Vect2d C, Vect2d P){	// FIRST CHECK THE SIGN OF THE Z-COMPONENT OF THE NORMAL BY CALCULATING	// THE CROSS-PRODUCT (ABxBC). THIS WILL DETERMINE THE ORDERING OF THE	// VERTICES. IF NEGATIVE, VERTICES ARE CLOCKWISE ORDER; OTHERWISE CCW.	// THEN EVALUATE SIGN OF Z-COMPONENTS FOR ABxAP, BCxBP, and CAxCP TO	// DETERMINE IF P IS IN "INSIDE" HALF-SPACE FOR EACH EDGE IN TURN ("INSIDE"	// IS DETERMINED BY SIGN OF Z OF NORMAL (VERTEX ORDERING).	// NOTE: FULL CROSS-PRODS ARE NOT REQUIRED; ONLY THE Z-COMPONENTS	Vect2d dAB=B-A, dBC=C-B;  // "REPEATS"	if ((dAB.x*dBC.y-dAB.y*dBC.x) < 0) // CW	{		if (dAB.x*(P.y-A.y) >= dAB.y*(P.x-A.x)) return(0);           // ABxAP		if (dBC.x*(P.y-B.y) >= dBC.y*(P.x-B.x)) return(0);           // BCxBP		if ((A.x-C.x)*(P.y-C.y) >= (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP	}	else // CCW	{		if (dAB.x*(P.y-A.y) < dAB.y*(P.x-A.x)) return(0);           // ABxAP		if (dBC.x*(P.y-B.y) < dBC.y*(P.x-B.x)) return(0);           // BCxBP		if ((A.x-C.x)*(P.y-C.y) < (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP	}	return(1); // "INSIDE" EACH EDGE''S IN-HALF-SPACE (PT P IS INSIDE TRIANGLE)	};//----------------------------------------------------------------------------// CHECKS IF 3D POINT P IS IN 3D TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT.// USES 2D VERSION AFTER PROJECTED SINCE THE 3D TRIANGLE IS PROJECTED ON ONE OF // THE PLANES FORMED BY THE PRINCIPAL AXES (XY, YZ, and XZ). N=Normal//---------------------------------------------------------------------------- int Pt3dInTri(Vect3d A, Vect3d B, Vect3d C, Vect3d P, Vect3d N){  // DETERMINE LARGEST COMPONENT OF NORMAL (magnitude, since we want the largest projection)  N.x=ABS(N.x); N.y=ABS(N.y); N.z=ABS(N.z);    // PROJECT ONTO PLANE WHERE LARGEST COMPONENT IS SET TO ZERO  if (N.x>=N.y && N.x>N.z)     // X IS LARGEST SO PROJECT ONTO YZ-PLANE    return( Pt2dInTri(Vect2d(A.y,A.z),Vect2d(B.y,B.z),Vect2d(C.y,C.z),Vect2d(P.y,P.z)) );	else if (N.y>N.x && N.y>N.z) // Y IS LARGEST SO PROJECT ONTO XZ-PLANE    return( Pt2dInTri(Vect2d(A.x,A.z),Vect2d(B.x,B.z),Vect2d(C.x,C.z),Vect2d(P.x,P.z)) );  else                         // Z IS LARGEST SO PROJECT ONTO XY-PLANE    return( Pt2dInTri(Vect2d(A.x,A.y),Vect2d(B.x,B.y),Vect2d(C.x,C.y),Vect2d(P.x,P.y)) );};//----------------------------------------------------------------------------// Given a Ray (Start Point(S) and Direction(D)) and a Plane, determines if the ray// intersects the infinite plane (in point-normal form). If it does intersect, // then TRUE (1) is returned and the distance to the HitPt is calculated (HitDist); // otherwise, the function returns FALSE (0) and no HitDist is calculated.// Norm = normal to the plane, Dist = -Distance along normal to the plane.//----------------------------------------------------------------------------int RayPlaneIntersect(Vect3d S, Vect3d D, Vect3d Norm, float Dist, float* HitDist){	float Denom = Norm*D;	if (Denom!=0) 	{	  float Numer = -(Norm*S + Dist);	  *HitDist = Numer/Denom;	  if (*HitDist > 1) return 1;	}          		return 0;};

- AH

Share on other sites
I don''t use the ''source'' tags anymore. They suck. They screw up source. You''ll have to go with non-highlighted code.

- AH

Share on other sites
Thank you for the guy who wanted this help.
Hope it will help him.

As for the source tag thingy, please remember that non-tagged source is annoying when smileys or tags are into the code.
(there'' one smiley in the code above)
you can''t write ":" and "(" without a white space, and you can''t write "array[" and "i" and "]" without spaces.

Anyhow, thanx for the code.

Share on other sites
I just copy''n''pasted the code. It''s rather simple to remove smileys, since they follow strict ''syntax rules''

The problem with source tags is, that they seem to have a formatting bug with certain combinations of characters. But, I''m still not really sure, if it''s the tag or me, to be honest

  test test // test testtest // test#test test // test#test test // test

- AH

Share on other sites
strange, now it works. I must be too dumb to use them...

- AH

Share on other sites
HI, Cyanide again (i hate firewalls)

big thanks to vincoof. he postet my question here ! when i am at home i go and try it out !!! THANKS !!!