Archived

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

vincoof

intersection between a triangle and a line

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 this post


Link to post
Share on other sites
Guest Anonymous Poster

//============================================================================
// 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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 test

test // test

#test test // test

#test test // test



- AH

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
strange, now it works. I must be too dumb to use them...

- AH

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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 !!!

Share this post


Link to post
Share on other sites