Thread: Triangle and Line Segment Intersection

Ah, I see your point about global variables. (See below)

As of right now, I'm not certain that the Check_return_type stuff is set up properly...
But, if it was, my next concern would be as follows:

Ideally, I would like all of this code to be defined as a function to which I can pass information about a particular Triangle and LineSegment and get a return value about whether these two intersect (and if so, how)

If I make the variable local rather than global, I imagine this will help... since I am passing one Triangle and LineSegment after the next, I don't want the variables related to this function to become locked to the values associated with any instance of the Triangle and LineSegment.

But how do I take my present implementation and move it towards being an enclosed function...
An example of what I'd like:

Does_Intersect {Triangle: PtA x,y,z PtB x,y,z PtC x,y,z AND LineSeg: PtP x,y,z PtQ x,y,z}
and then this would return a value through Check_return_type to say if and how this triangle and lineseg intersect.

You see what I mean?

Thanks

As for the question about object-oriented...
As you can see, I'm new to programming, so I might have my meaning wrong... what I am trying to say is that I would like this intersection checker to be a separate function, so I can pass it different Triangles and LineSegments (as noted above)

Thanks again

Go back to this approach of defining structs:

Code:

typedef struct
{
	double x;
	double y;
	double z;
} point;

typedef struct
{
	point p1;
	point p2;
	point p3;
} triangle;

typedef struct
{
     point p1;
     point p2;
} line_seg;

Then, for your function, pass a triangle and a line_seg object:

Code:

int Does_Intersect(triangle tri, line_seg seg);

The function has a return type of int. Set to 1 if they match, set to 0 if they don't. Return that value.

Thanks.

Two questions:

1) I have set up the functions of the intersection checker to deal with component x y z
is it worth it to switch that? how would I implement those functions to work with the structs

2) How should I define all of the functions of the intersection checker to be part of one definition: "Does_Intersect" ?
Meaning, (I think) how should I bracket this function: is it a struct, a define, ...

Thanks

I guess I'm a little confused. I see your current implementation and I don't see "multiple intersection checker functions". I see one giant main.

You can take all of the processing out of the main and put it into a function like you suggested, DoesIntersect().

I gave you the prototype for that function above, the struct definitions, as well as how to populate the individual elements of those structs a few posts back. If you want, populate the structs that you need in the main. You need one triangle and one line segment for your DoesIntersect function, correct? So populate one triangle and one segment in main(). Then pass the triangle and the segment to DoesIntersect.

Here:

Code:

int main(void)
{
     triangle tri;
     line_seg seg;
     int result;

     /* Fill tri and seg with values using dot notation (see my previous post). */

     result = DoesIntersect(tri, seg);
     if (result)
     {
          printf("We have a match.\n");
     }

     return 0;
}

Get your program working with ONE triangle and ONE segment before you attempt to do multiple triangles and multiple segments.

Originally Posted by hebali

Thanks.

Two questions:

1) I have set up the functions of the intersection checker to deal with component x y z
is it worth it to switch that? how would I implement those functions to work with the structs

2) How should I define all of the functions of the intersection checker to be part of one definition: "Does_Intersect" ?
Meaning, (I think) how should I bracket this function: is it a struct, a define, ...

Thanks

1. That's pretty much what you've got here, isn't it? p1.x, p2.x, p1.y, p3.z, etc. That's going to be way way better than the piles of separate variables you've got now.

2. What do you mean? You've got, well, one function. It checks whether the line intersects the triangle. Start at the top, and when you get to the bottom, you're done.

Yes, sorry. The main is currently my general intersection checker. But as you suggested, I don't want that to be in the main but rather as a function: DoesIntersect()

Your implementation was right on. But it's gonna take me a bit to figure out how to make this into a working DoesIntersect() function...

I'm still not sure whether my Check_return_type is returning proper values...

thanks

From what I can see, Check_Return_Type is the same as my 'result' variable. It's just an integer. There's nothing really special to it. What you need to focus on is the following:

a) Get the two data structures populated. Fill triangle and line_seg with the values that the user gives you. Your original post (or one shortly following) had code which successfully gathered these values and assigned them to your structs. I believe I cleaned up and compiled it for you. That works. Start there.

b) Once you have the data structures properly populated, make your DoesIntersect function. You have a better idea than I do on how that works. Pass triangle and line_seg into the function as I said above and return an integer 1 if they match, 0 if they don't.

You're on the right track. Just keep it as simple as possible (one triangle, one segment).

Rereading your post, if you're concerned that the DoesIntersect function isn't working properly, post the code you have once you have it broken into functions, and I'll try to help you out with that too.

so, is this what you meant?
I'm not exactly sure how to implement DoesIntersect as a function.
Do I want "void" in its parenthesis... where do I define what variables can be passed values...?

Code:

#include <stdio.h>
#include <math.h>

typedef struct
{
	double x;
	double y;
	double z;
} vertex;

typedef struct
{
	vertex p1;
	vertex p2;
	vertex p3;
} triangle;

typedef struct
{
	vertex p1;
	vertex p2;
} segment;

int DoesIntersect(void);


// main
int main(void)
{
	triangle tri;
	segment seg;
	int result;
	
	int j;
	char input_buffer[160];
	int check_input;
	double u;

	vertex input_v_data[8];
	triangle input_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", &input_v_data[j].x, &input_v_data[j].y, &input_v_data[j].z);

			if (check_input !=3)
			{
				printf("Improper format.");
				return 0;
			}
		}
	
		input_tri_data[0].p1 = input_v_data[0];
		// etc...
		// later these should be force not input...
		
		// another function will come along here that takes input vertices, does a function to them, then outputs new vertices from which "force_tri_data" etc are derived...
		
		
} //main

int DoesIntersect(void)
{
	// FUNCTIONS OF INTERSECTION CHECKER GO HERE...
	// THE FUNCTIONS BELOW ARE JUST SAMPLE, AS I HAVE NOT CONVERTED THEM TO DOTTED POINT VERSIONS
	#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;

	// 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??
	
}

Thanks so much for your help.
It's actually not for an assignment. I'm not in a class... which makes it harder.
But I do think I understand the ideas you're implementing and I will put them into the context of this function and see how it goes.

I appreciate your taking the time.

one more question for now:
If I define the following

Code:

typedef struct
{
	double x;
	double y;
	double z;
} vertex;

typedef struct
{
        vertex v0;
        vertex v1;
        vertex v2;
        vertex v3;
        vertex v4;
        vertex v5;
        vertex v6;
        vertex v7;
} cube;

cube myCube[1];

How do I access a particular coordinate value with the following

Code:

mycube.v0.x

Will this give me the x value for vertex 0 of mycube?

thanks again

Originally Posted by hebali

Thanks so much for your help.
It's actually not for an assignment. I'm not in a class... which makes it harder.
But I do think I understand the ideas you're implementing and I will put them into the context of this function and see how it goes.

I appreciate your taking the time.

My pleasure . . .

Just remember to break the program into small, manageable chunks.

1) Create your data structures.
2) Populate your cube data structure using dot notation.
3) Pass the cube data structure to get updated output vertices.
4) Pass the cube to your mystery triangle creator.
5) Populate the triangle data structures using dot notation.
6) Populate the line segment structures using dot notation.
7) Call the DoesIntersect with your triangle and your line segment.
8) Call the DoesIntersect with your second triangle and line segment.
9) Repeat in a loop until we get all of our results.
10) Store those results (result = DoesIntersect(tri, seg)). If at any point result is 1, loop back to step 2.