# Thread: Triangle and Line Segment Intersection

1. ## 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. 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. Code:
```struct point
{
double x, y, z;
};

struct triangle
{
struct point p1, p2, p3;
};```

4. 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. Code:
```tri_data[0].p1 = v_data[0];
tri_data[0].p2 = v_data[1],
tri_data[0].p3 = v_data[3];```

6. 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. 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;
/* ... */```

8. 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. 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;
}```

10. 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. 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.

12. 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!

13. 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. 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. Why global variables? And how is this an "object oriented" approach? I don't see a single data structure here.