Triangle and Line Segment Intersection

This is a discussion on Triangle and Line Segment Intersection within the C Programming forums, part of the General Programming Boards category; I am looking to find some code either in C or Objective-C that will allow me to determine (true or ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    84

    Triangle and Line Segment Intersection

    I am looking to find some code either in C or Objective-C that will allow me to determine (true or false) whether a line intersects with a triangle in 3D.

    I've looked at some different graphics libraries, but none of these make the handling of this problem easy to decipher and I'm wondering if someone could provide a clear layout...

    I found a C++ version at:
    http://geometryalgorithms.com/Archiv...rithm_0105.htm

    I'd particularly like to be able to operate with a single function

    3DTriangle_Point1_Coordinates = x, y, z
    3DTriangle_Point2_Coordinates = x, y, z
    3DTriangle_Point3_Coordinates = x, y, z

    3DLineSeg1_Point1_Coordinates = x, y, z
    3DLineSeg1_Point1_Coordinates = x, y, z

    Does_Intersect: 3DTriangle1 AND 3DLineSeg1 ?
    if yes: ... on vertex, on edge, etc ?
    if no: ...


    thanks so much!

  2. #2
    Registered User
    Join Date
    Feb 2008
    Posts
    84
    how do i set up a struct for a single point and then another one for a triangle (a set of three points)?

    If I need to compute
    u = Triangle.Vertex1 - Triangle.Vertex0

    presumably I need to do this for each x, y, z of the vertex.

    Can someone provide a sample of the setup?

    thanks

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    Code:
    struct point
    {
        double x, y, z;
    };
    
    struct triangle
    {
        struct point p1, p2, p3;
    };
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Feb 2008
    Posts
    84
    Thanks,
    Please have a look at the code below.
    What I am trying to do here is have the user input the coordinates of 8 vertices, and then have the program organize triangles using particular relationships of those input vertices.

    So, for instance:

    tri_data[0] = v_data[0], v_data[1], v_data[3];

    is intended to have "triangle 0" contain "vertex 0", "vertex 1", and "vertex 3"

    this doesn't seem to work at the moment.

    what's wrong?

    thanks so much!


    Code:
    #import <stdio.h>
    #import <stdlib.h>
    
    struct vertex
    	{
    		double x, y, z;
    	};
    	
    struct triangle
    	{
    		struct vertex p1, p2, p3;
    	};
    	
    	
    
    int main (void)
    {
    
    int j; // vertex number
    char input_buffer[160];
    int check_input;
    	
    struct vertex v_data[8];
    	
    	for(j=0;j<8;j++)
    		{
    			printf("Input vertex coordinates x y z: ");
    			fgets(input_buffer, sizeof input_buffer, stdin);
    			check_input = sscanf(input_buffer, "&#37;f %f %f", &v_data[j].x, &v_data[j].y, &v_data[j].z);
    			
    			while (check_input !=3)
    				{
    					printf("Improper format.");
    					return(0);
    				};
    				
    				struct triangle tri_data[12];
    				
    				tri_data[0] = v_data[0], v_data[1], v_data[3];
    				tri_data[1] = v_data[0], v_data[2], v_data[3];
    				tri_data[2] = v_data[0], v_data[1], v_data[7];
    				
    		};
    	
    
    	
    }

  5. #5
    Nub SWE
    Join Date
    Mar 2008
    Location
    Dallas, TX
    Posts
    133
    Code:
    tri_data[0].p1 = v_data[0];
    tri_data[0].p2 = v_data[1],
    tri_data[0].p3 = v_data[3];

  6. #6
    Registered User
    Join Date
    Feb 2008
    Posts
    84
    Cool, thanks...

    So, let's say I want to then work with the following:

    u = tri_data[1] - tri_data[0];

    where this will get a "u" value for the x, y, z of each called point of the triangle,
    will this do the substractions automatically?

    How do I do that?

  7. #7
    Nub SWE
    Join Date
    Mar 2008
    Location
    Dallas, TX
    Posts
    133
    It may do it automatically, but I am unsure. That's above my paygrade. I really don't think it does, however.

    This will work, though. Tedious to type out, but safe.
    Code:
    u_p1_x = tri_data[1].p1.x - tri_data[0].p1.x;
    u_p1_y = tri_data[1].p1.y - tri_data[0].p1.y;
    /* ... */
    Last edited by JDGATX; 04-08-2008 at 10:46 AM.

  8. #8
    Registered User
    Join Date
    Feb 2008
    Posts
    84
    Ideally, I would like to do this in an object oriented way because I want to be able to check each triangle (there are 12 of them) against intersection with each line segment (there are 24 of them).

    I would really like to do this with objective-c, but seems to be no good forums for that language...
    can anyone help me with an object oriented method??

    thanks!

  9. #9
    Nub SWE
    Join Date
    Mar 2008
    Location
    Dallas, TX
    Posts
    133
    Here is a solid baseline to build from. I'm not really sure what you're asking about on the last post, but this code compiles and takes in the 8 vertices correctly, storing them in the structs.
    Code:
    #include <stdio.h>
    
    typedef struct
    {
    	double x;
    	double y;
    	double z;
    } vertex;
    
    typedef struct
    {
    	vertex p1;
    	vertex p2;
    	vertex p3;
    } triangle;
    
    int main (void)
    {
    	int j;
    	char input_buffer[160];
    	int check_input;
    	double u;
    
    	vertex v_data[8];
    	triangle tri_data[12];
    
    	for ( j = 0; j < 8; j++)
    	{
    		printf("Input vertex coordinates x y z: ");
    		fflush(stdout);
    		fgets(input_buffer, sizeof input_buffer, stdin);
    		check_input = sscanf(input_buffer, "&#37;f %f %f", &v_data[j].x, &v_data[j].y, &v_data[j].z);
    
    		if (check_input !=3)
    		{
    			printf("Improper format.");
    			return 0;
    		}
    	}
    	
    	tri_data[0].p1 = v_data[0];
    	tri_data[0].p2 = v_data[1];
    	tri_data[0].p3 = v_data[3];
    	tri_data[1].p1 = v_data[0];
    	tri_data[1].p2 = v_data[2];
    	tri_data[1].p3 = v_data[3];
    	tri_data[2].p1 = v_data[0];
    	tri_data[2].p2 = v_data[1];
    	tri_data[2].p3 = v_data[7];
    	
    	u = tri_data[1].p1.x - tri_data[0].p1.x;
    	printf("%f", u);
    	
    	return 0;
    }
    Last edited by JDGATX; 04-08-2008 at 11:59 AM. Reason: Missed a few things.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you want to do it in an object-oriented way, you're not using C. In C++, you could overload the subtraction operator - for points.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    Ideally, I would like to do this in an object oriented way because I want to be able to check each triangle (there are 12 of them) against intersection with each line segment (there are 24 of them).
    What exactly do you have in mind?

    If you want to do it in an object-oriented way, you're not using C.
    That is not quite true, since one can simulate OO techniques in C.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Feb 2008
    Posts
    84
    Thanks.

    So here is the deal for my general implementation:

    The user will input a set of 8 vertices . As in, "vertex0 = 85, 30, 94" etc.

    Then, based upon a set of defined relationships, these input vertex components will be split up and used to provide the values of the components of the triangles and line segments that make up the cube.
    As in:
    Triangle0 = vertex0 vertex1 vertex3
    Triangle1 = vertex0 vertex2 vertex3
    ...etc...
    LineSegment0 = vertex0 vertex1
    LineSegment1 = vertex0 vertex2
    (This of course has to be able to access the components of each vertex)

    Now that Triangles and LineSegments have values (from the user input), I need to run a check for intersections between each Triangle with each LineSegment.
    I would like to define the intersection check function as an autonomous object so that later in the program, I can pass this function a particular Triangle and a particular LineSegment to check against each other.

    Here is a C++ implementation of the intersection checker that I found at http://geometryalgorithms.com/Archiv...rithm_0105.htm
    Code:
    // Copyright 2001, softSurfer (www.softsurfer.com)
    // This code may be freely used and modified for any purpose
    // providing that this copyright notice is included with it.
    // SoftSurfer makes no warranty for this code, and cannot be held
    // liable for any real or imagined damage resulting from its use.
    // Users of this code must verify correctness for their application.
    
    // Assume that classes are already given for the objects:
    //    Point and Vector with
    //        coordinates {float x, y, z;}
    //        operators for:
    //            == to test equality
    //            != to test inequality
    //            (Vector)0 = (0,0,0)         (null vector)
    //            Point  = Point &#177; Vector
    //            Vector = Point - Point
    //            Vector = Scalar * Vector    (scalar product)
    //            Vector = Vector * Vector    (cross product)
    //    Line and Ray and Segment with defining points {Point P0, P1;}
    //        (a Line is infinite, Rays and Segments start at P0)
    //        (a Ray extends beyond P1, but a Segment ends at P1)
    //    Plane with a point and a normal {Point V0; Vector n;}
    //    Triangle with defining vertices {Point V0, V1, V2;}
    //    Polyline and Polygon with n vertices {int n; Point *V;}
    //        (a Polygon has V[n]=V[0])
    //===================================================================
    
    #define SMALL_NUM  0.00000001 // anything that avoids division overflow
    // dot product (3D) which allows vector operations in arguments
    #define dot(u,v)   ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)
    
    // intersect_RayTriangle(): intersect a ray with a 3D triangle
    //    Input:  a ray R, and a triangle T
    //    Output: *I = intersection point (when it exists)
    //    Return: -1 = triangle is degenerate (a segment or point)
    //             0 = disjoint (no intersect)
    //             1 = intersect in unique point I1
    //             2 = are in the same plane
    int
    intersect_RayTriangle( Ray R, Triangle T, Point* I )
    {
        Vector    u, v, n;             // triangle vectors
        Vector    dir, w0, w;          // ray vectors
        float     r, a, b;             // params to calc ray-plane intersect
    
        // get triangle edge vectors and plane normal
        u = T.V1 - T.V0;
        v = T.V2 - T.V0;
        n = u * v;             // cross product
        if (n == (Vector)0)            // triangle is degenerate
            return -1;                 // do not deal with this case
    
        dir = R.P1 - R.P0;             // ray direction vector
        w0 = R.P0 - T.V0;
        a = -dot(n,w0);
        b = dot(n,dir);
        if (fabs(b) < SMALL_NUM) {     // ray is parallel to triangle plane
            if (a == 0)                // ray lies in triangle plane
                return 2;
            else return 0;             // ray disjoint from plane
        }
    
        // get intersect point of ray with triangle plane
        r = a / b;
        if (r < 0.0)                   // ray goes away from triangle
            return 0;                  // => no intersect
        // for a segment, also test if (r > 1.0) => no intersect
    
        *I = R.P0 + r * dir;           // intersect point of ray and plane
    
        // is I inside T?
        float    uu, uv, vv, wu, wv, D;
        uu = dot(u,u);
        uv = dot(u,v);
        vv = dot(v,v);
        w = *I - T.V0;
        wu = dot(w,u);
        wv = dot(w,v);
        D = uv * uv - uu * vv;
    
        // get and test parametric coords
        float s, t;
        s = (uv * wv - vv * wu) / D;
        if (s < 0.0 || s > 1.0)        // I is outside T
            return 0;
        t = (uv * wu - uu * wv) / D;
        if (t < 0.0 || (s + t) > 1.0)  // I is outside T
            return 0;
    
        return 1;                      // I is in T
    }
    Thanks for all your help so far. I am wondering if you could help me make sense of this so that I can do as I've described above (either in C or Objective-C). It is most important that the intersection check can be called in the program for the intersection of any particular Triangle and LineSegment.

    Thanks again!
    Last edited by hebali; 04-08-2008 at 12:16 PM.

  13. #13
    Registered User
    Join Date
    Feb 2008
    Posts
    84
    So, I've started implementing the code included in my previous posting...
    At the bottom of my implementation (below), I'm stuck... I'm confused about the ?pointer? in the *I = R.P0 + r * dir; line taken from the source code in my previous post...

    thanks

    Code:
    #include <stdio.h>
    #include <math.h>
    
    #define SMALL_NUM 0.00000001
    
    int Check_return_type;
    
    float a, b, r;
    
    float u_x, u_y, u_z;
    float v_x, v_y, v_z;
    float n_x, n_y, n_z;
    
    float dir_x, dir_y, dir_z;
    float w0_x, w0_y, w0_z;
    
    float tri_ptA_x, tri_ptA_y, tri_ptA_z;
    float tri_ptB_x, tri_ptB_y, tri_ptB_z;
    float tri_ptC_x, tri_ptC_y, tri_ptC_z;
    
    float seg_ptP_x, seg_ptP_y, seg_ptP_z;
    float seg_ptQ_x, seg_ptQ_y, seg_ptQ_z;
    
    // Triangle
    u_x = tri_ptB_x - tri_ptA_x; // u edge vector x-component
    u_y = tri_ptB_y - tri_ptA_y; // u edge vector y-component
    u_z = tri_ptB_z - tri_ptA_z; // u edge vector z-component
    
    v_x = tri_ptC_x - tri_ptA_x; // v edge vector x-component
    v_y = tri_ptC_y - tri_ptA_y; // v edge vector y-component
    v_z = tri_ptC_z - tri_ptA_z; // v edge vector z-component
    
    n_x = u_x * v_x;  //cross product of u and v x-components
    n_y = u_y * v_y;  //cross product of u and v y-components
    n_z = u_z * v_z;  //cross product of u and v z-components
    
    
    
    // LineSegment
    dir_x = seg_ptQ_x - seg_ptP_x; // ray direction vector x-component
    dir_y = seg_ptQ_y - seg_ptP_y; // ray direction vector y-component
    dir_z = seg_ptQ_z - seg_ptP_z; // ray direction vector z-component
    
    w0_x = seg_ptP_x - tri_ptA_x;
    w0_y = seg_ptP_y - tri_ptA_y;
    w0_z = seg_ptP_z - tri_ptA_z;
    
    // dot products
    a = -1 * (n_x * w0_x + n_y * w0_y + n_z * w0_z);
    b = (n_x * dir_x + n_y * dir_y + n_z * dir_z);
    
    r = a / b;
    
    if (fabs(b) < SMALL_NUM)
    	{
    		if (a == 0)
    			{
    				Check_return_type = 2;
    			}
    		else
    			{
    				Check_return_type = 0;
    			}
    	}
    	
    if (r < 0.0)
    	{
    		Check_return_type = 0;
    	}
    	
    if (r > 1.0)
    	{
    		Check_return_type = 0;
    	}
    	
    	
    	
    // WHAT IS THIS????
    // *I = R.P0 + r * dir;

  14. #14
    Registered User
    Join Date
    Feb 2008
    Posts
    84
    Ok, so here is my implementation...
    I'm having a hard time figuring out whether my IF statements and their Check_return_type functions will work in the same way that the code I am porting from did.

    Again, I am basing my implementation on the source code found at the following address (and is also duplicated in one of my earlier posts)
    http://geometryalgorithms.com/Archiv..._RayTriangle()

    Please have a look and let me know if this seems correct...

    Thanks


    Code:
    #include <stdio.h>
    #include <math.h>
    
    #define SMALL_NUM 0.00000001
    
    int Check_return_type;
    
    float a, b, r;
    
    float u_x, u_y, u_z;
    float v_x, v_y, v_z;
    float n_x, n_y, n_z;
    
    float dir_x, dir_y, dir_z;
    float w0_x, w0_y, w0_z;
    
    float tri_ptA_x, tri_ptA_y, tri_ptA_z;
    float tri_ptB_x, tri_ptB_y, tri_ptB_z;
    float tri_ptC_x, tri_ptC_y, tri_ptC_z;
    
    float seg_ptP_x, seg_ptP_y, seg_ptP_z;
    float seg_ptQ_x, seg_ptQ_y, seg_ptQ_z;
    
    float uu, uv, vv, wu, wv, D;
    
    float i_x, i_y, i_z;
    float w_x, w_y, w_z;
    
    float s, t;
    
    int main (void)
    {
    
    // Triangle
    u_x = tri_ptB_x - tri_ptA_x; // u edge vector x-component
    u_y = tri_ptB_y - tri_ptA_y; // u edge vector y-component
    u_z = tri_ptB_z - tri_ptA_z; // u edge vector z-component
    
    v_x = tri_ptC_x - tri_ptA_x; // v edge vector x-component
    v_y = tri_ptC_y - tri_ptA_y; // v edge vector y-component
    v_z = tri_ptC_z - tri_ptA_z; // v edge vector z-component
    
    n_x = u_x * v_x;  //cross product of u and v x-components
    n_y = u_y * v_y;  //cross product of u and v y-components
    n_z = u_z * v_z;  //cross product of u and v z-components
    
    
    
    // LineSegment
    dir_x = seg_ptQ_x - seg_ptP_x; // ray direction vector x-component
    dir_y = seg_ptQ_y - seg_ptP_y; // ray direction vector y-component
    dir_z = seg_ptQ_z - seg_ptP_z; // ray direction vector z-component
    
    w0_x = seg_ptP_x - tri_ptA_x;
    w0_y = seg_ptP_y - tri_ptA_y;
    w0_z = seg_ptP_z - tri_ptA_z;
    
    // dot products
    a = -1 * (n_x * w0_x + n_y * w0_y + n_z * w0_z);
    b = (n_x * dir_x + n_y * dir_y + n_z * dir_z);
    
    r = a / b;
    
    if (fabs(b) < SMALL_NUM)
    	{
    		if (a == 0)
    			{
    				Check_return_type = 2;
    			}
    		else
    			{
    				Check_return_type = 0;
    			}
    	}
    	
    if (r < 0.0 || r > 1.0)
    	{
    		Check_return_type = 0;
    	}
    	
    
    i_x = seg_ptP_x + r * dir_x;
    i_y = seg_ptP_y + r * dir_y;
    i_z = seg_ptP_z + r * dir_z;
    
    w_x = i_x - tri_ptA_x;
    w_y = i_y - tri_ptA_y;
    w_z = i_z - tri_ptA_z;
    
    uu = u_x * u_x + u_y * u_y + u_z * u_z;
    uv = u_x * v_x + u_y * v_y + u_z * v_z;
    uv = v_x * v_x + v_y * v_y + v_z * v_z;
    
    wu = w_x * u_x + w_y * u_y + w_z * u_z;
    wv = w_x * v_x + w_y * v_y + w_z * v_z;
    
    D = uv * uv - uu * vv;
    
    s = (uv * wv - vv * wu) / D;
    t = (uv * wu - uu * wv) / D;
    
    if (s < 0.0 || s > 1.0)
    	{
    		Check_return_type = 0;
    	}
    
    if (t < 0.0 || (s + t) > 1.0)
    	{
    		Check_return_type = 0;
    	}
    	
    	Check_return_type = 1; // IS THIS AN ELSE CLAUSE, how do I get it to return in proper conditions??
    
    }

  15. #15
    Nub SWE
    Join Date
    Mar 2008
    Location
    Dallas, TX
    Posts
    133
    Why global variables? And how is this an "object oriented" approach? I don't see a single data structure here.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. can some one please tell me the cause of the error ?
    By broli86 in forum C Programming
    Replies: 8
    Last Post: 06-26-2008, 09:36 PM
  2. Draw a triangle
    By Hikaru in forum C++ Programming
    Replies: 8
    Last Post: 08-13-2006, 03:26 PM
  3. Just in case: "Odd" Triangle Challenge (for me)
    By BB18 in forum C Programming
    Replies: 3
    Last Post: 10-09-2004, 01:02 AM
  4. normals for triangle strips (oGL)
    By Perspective in forum Game Programming
    Replies: 8
    Last Post: 04-01-2003, 06:59 PM
  5. Replies: 1
    Last Post: 01-30-2002, 01:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21