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.

Quote:

---

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

---

Again, you're on the right track.

Code:

---

        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;

---

Those definitions above can be substituted for our dot notation. Remember, we're passing in two parameters to our DoesIntersect function. We pass tri and seg. See my above post for the prototype of the function. Instead of 'void', you would have those two parameters.

Then, we can use tri and seg in our DoesIntersect function.

Code:

---

tri.p1.x = 0;
tri.p1.y = 0;
tri.p1.z = 0;
/* And so on. */
seg.p1.x = 0;
seg.p2.x = 0;
/* And so on. */

---

I'm tinkering with the rest of your code. Keep posting questions while I work with it.

And I would recommend more descriptive variable names. It took me five minutes just to figure out what a and b and r and u_u_ux are.

***EDIT***

Here is an updated version of your main:

Code:

---

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

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

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

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

int DoesIntersect(triangle tri, segment seg);

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

        /** POPULATE YOUR TRIANGLE WITH THREE POINTS HERE. */
        printf("TRIANGLE 1, POINT 1-> Input coordinates x y z: ");
        fflush(stdout);
        fgets(input_buffer, sizeof(input_buffer), stdin);
        check_input = sscanf(input_buffer, "&#37;f %f %f", &tri.p1.x, &tri.p1.y, &tri.p1.z);
        if (check_input !=3)
        {
                printf("Improper format.");
                return 0;
        }
       
        printf("TRIANGLE 1, POINT 2-> Input coordinates x y z: ");
        fflush(stdout);
        fgets(input_buffer, sizeof(input_buffer), stdin);
        check_input = sscanf(input_buffer, "%f %f %f", &tri.p2.x, &tri.p2.y, &tri.p2.z);
        if (check_input !=3)
        {
                printf("Improper format.");
                return 0;
        }
       
        printf("TRIANGLE 1, POINT 3-> Input coordinates x y z: ");
        fflush(stdout);
        fgets(input_buffer, sizeof(input_buffer), stdin);
        check_input = sscanf(input_buffer, "%f %f %f", &tri.p3.x, &tri.p3.y, &tri.p3.z);
        if (check_input !=3)
        {
                printf("Improper format.");
                return 0;
        }
       
        /** POPULATE YOUR LINE SEGMENT WITH TWO POINTS HERE. */
        printf("SEGMENT 1, POINT 1-> Input coordinates x y z: ");
        fflush(stdout);
        fgets(input_buffer, sizeof(input_buffer), stdin);
        check_input = sscanf(input_buffer, "%f %f %f", &seg.p1.x, &seg.p1.y, &seg.p1.z);
        if (check_input !=3)
        {
                printf("Improper format.");
                return 0;
        }
       
        printf("SEGMENT 1, POINT 2-> Input coordinates x y z: ");
        fflush(stdout);
        fgets(input_buffer, sizeof(input_buffer), stdin);
        check_input = sscanf(input_buffer, "%f %f %f", &seg.p2.x, &seg.p2.y, &seg.p2.z);
        if (check_input !=3)
        {
                printf("Improper format.");
                return 0;
        }
       
        /** RUN YOUR INTERSECTION CHECKER HERE. */
        result = DoesIntersect(tri, seg);
       
        return 0;
}

---

Can you understand what I'm doing? Notice how I only worry about ONE triangle and ONE line segment, not 8 or 12 or whatever. Start small.

Thanks, this is great... and I do understand what you're doing... but there is one problem:

Here is the flow: (and why the user is not actually inputting triangles)

Program flow:
1) User inputs x y z for each of 8 vertices of a cube: input vertices.
2) Input vertices are run through an equation. The equation outputs: output vertices
3) program takes output vertices and according to a function (NOT CURRENTLY INCLUDED IN THIS CODE).
This function will essentially say: take vertex 0, 1, 3 and copy these values to the variable Triangle1
and take vertex 0,1 and copy these values to the variable LineSegment1
4) Then the main function asks the Does_Intersection function whether certain triangles collide with certain linesegments
5) if any collisions occur, we go back to step 2. (regenerating one output vertex from input and then checking the whole set again for intersections)

I think I've given you the underlying structure of this program. It will be up to you to tailor that structure to meet your assignment requirements. You know the assignment better than I do. I can only critique the code you give me. I've done that. You'll see in my main how to populate the data structures. Feel free to use that code and fit it into your assignment.

What do you need to do? We need to wrap a loop around the triangle input so that we can input 8 triangles instead of just 1. Then we need to create an array of eight triangle objects instead of just one triangle object.

Code:

---

triangle tri[NUM_TRIANGLES];

/* Put your loop code here and whatever else you need... */

check_input = sscanf(input_buffer, "%f %f %f", &tri[k].p2.x, &tri[k].p2.y, &tri[k].p2.z);

---

...where k is your loop variable.

Edit:

Now you're talking about cubes, haha. We need a different data structure for that, similar to our triangle structure but with eight "point"s instead of three.

You'll see how the code I've given you is still useful in establishing the basics of your program.

Not sure if it still pertains to your program, but here's your DoesIntersect function but compilable and with dot notation:

Code:

---

int DoesIntersect(triangle tri, segment seg)
{
        int result;

        float a, b, r;

        float u_x, u_y, u_z;
        float v_x, v_y, v_z;
        float cross_prod_x, cross_prod_y, cross_prod_z;

        float dir_x, dir_y, dir_z;
        float w0_x, w0_y, w0_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.p2.x - tri.p1.x;
        u_y = tri.p2.y - tri.p1.y;
        u_z = tri.p2.z - tri.p1.z;

        v_x = tri.p3.x - tri.p1.x;
        v_y = tri.p3.y - tri.p1.y;
        v_z = tri.p3.z - tri.p1.z;

        cross_prod_x = u_x * v_x;
        cross_prod_y = u_y * v_y;
        cross_prod_z = u_z * v_z;


        /** Line Segment */
        dir_x = seg.p2.x - seg.p1.x; // ray direction vector x-component
        dir_y = seg.p2.y - seg.p1.y; // ray direction vector y-component
        dir_z = seg.p2.z - seg.p1.z; // ray direction vector z-component

        w0_x = seg.p1.x - tri.p1.x;
        w0_y = seg.p1.y - tri.p1.y;
        w0_z = seg.p1.z - tri.p1.z;

        // dot products
        a = -1 * (cross_prod_x * w0_x + cross_prod_y * w0_y + cross_prod_z * w0_z);
        b = (cross_prod_x * dir_x + cross_prod_y * dir_y + cross_prod_z * dir_z);

        r = a / b;

        if (fabs(b) < SMALL_NUM)
        {
                if (a == 0)
                {
                        result = 2;
                }
                else
                {
                        result = 0;
                }
        }

        if (r < 0.0 || r > 1.0)
        {
                result = 0;
        }


        i_x = seg.p1.x + r * dir_x;
        i_y = seg.p1.y + r * dir_y;
        i_z = seg.p1.z + r * dir_z;

        w_x = i_x - tri.p1.x;
        w_y = i_y - tri.p1.y;
        w_z = i_z - tri.p1.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)
        {
                result = 0;
        }

        if (t < 0.0 || (s + t) > 1.0)
        {
                result = 0;
        }

        result = 1;
}

---

I have no idea if this does what you want, but there it is. I'm trusting that you have all of the formulas correct.

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

Quote:

---

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.