3D Interpolation across a triangle

Discussion in 'Programming' started by Joe Ellis, Feb 25, 2017.

  1. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    Hi, I was wondering if anyone knows how to calculate what the texture coords would be at a 3d point on a 3d triangle, linearly interpolated between the coords at each vertex?

    I know its quite simple but I cant get my head around how it actually works,

    I need to interpolate between each 2d texcoord, depending on how far(in 3d space) the point is from each vertex

    the point is always on the actual surface of the triangle

    I've looked on google but the explanations are quite general and I cant find anything explaining how to solve this exact problem, just wondered if anyone knows how you'd do it?

    Triangle Interpolation.png
     
  2. sp202

    sp202 Member

    Joined:
    Sep 26, 2016
    Posts:
    968
    So you're trying to calculate u and v at a point on the triangle given that you know d?
     
  3. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
  4. sp202

    sp202 Member

    Joined:
    Sep 26, 2016
    Posts:
    968
    Pretty sure you'd need at least 2 out of the 3 co-ordinate values, because there is a whole line of points with the same d value.
     
  5. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    well yeah iv got those aswell, i just didnt put it on the picture,
    if I get v1-v2, v1-v3, v2-v3, and p-v1, p-v2, p-v3, what would I need to do to get the correct value?

    I basically need to reproduce the same type of linear interpolation that shaders use passing the texcoords from each vertex interpolated across the triangles that the groups of 3 vertices create, as I'm doing this calculation in a fragment shader, with the triangle vertices and texcoords passed into it through uniforms, I cant make it automatically get the texcoord at a certain point in the triangle
    Actually, shaders use perpective correct interpolation during the rasterization to pixel, I need just standard interpolation between 3 points as the projection and view matrices are irrelavant, only the world pos coords are taken into account

    I'm starting to think this is nowhere near as simple as it sounds, even though my brain can roughly work out what the coords should be just by looking at the picture
     
    Last edited: Feb 25, 2017
  6. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    I think I just worked out a way that works, not sure if its 100% accurate but it seems to be fairly accurate, i spose now the best way to test it would be to make it draw a pixel on the texture at the position of the point

    Just in case anyone would have any use for this here's the method I worked out:

    Code:
    p = point position
    
    v1p = vertex1 position
    v2p = vertex2 position
    v3p = vertex3 position
    
    v1v = vertex1 value
    v2v = vertex2 value
    v3v = vertex3 value
    
    v1d = distance(v1p,p)
    v2d = distance(v2p,p)
    v3d = distance(v3p,p)
    
    td = v1d+v2d
    
    r12 = v1d/td
    
    v12 = lerp(v1v,v2v,r12)
    
    p12 = lerp(v1p,v2p,r12)
    
    d12 = distance(p12,p)
    
    td = d12 + v3d
    
    r123 = d12/td
    
    v123 = lerp(v12,v3v,r123)
    
     
  7. orange451

    orange451 Member

    Joined:
    Jun 22, 2016
    Posts:
    108
    Joe Ellis likes this.
  8. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Hi, this thread may be a bit old, but I have been trying to get this to work on my own for days, and still haven't figured out a good way of doing it.
    I've been trying to program my own script based off of 321looloo's code snippet posted earlier.
    I cannot figure out a good way of doing this.
    I've also tried Barycentric Coordinates mentioned by orange451, and still cannot get any luck.
    This is really frustrating to say the least.

    Can anyone help? It would be greatly appreciated. Thanks.
     
  9. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    EDIT:

    The best solution I've found so far I found here:
    https://gamedev.stackexchange.com/q...efficient-way-to-find-barycentric-coordinates

    note: below is not gml code.
    Code:
       //p = point, a,b,c = triangle verts
       v0 = b - a, v1 = c - a, v2 = p - a;
       d00 = Dot(v0, v0);
       d01 = Dot(v0, v1);
       d11 = Dot(v1, v1);
       d20 = Dot(v2, v0);
       d21 = Dot(v2, v1);
       denom = d00 * d11 - d01 * d01;
       v = (d11 * d20 - d01 * d21) / denom;
       w = (d00 * d21 - d01 * d20) / denom;
       u = 1 - v - w;
    
    take those barycenter coordinates (u,v,w) and use them as the weights for the values from each vertex.
     
    Last edited: Dec 15, 2017
  10. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Hi flyingsaucerinvasion.

    I've looked through all of the posts on this exact page before, but still have not been able to get my code working - it really sucks.
    I cannot for my life seem to get the code just right... I've spent too much time on this already, but I'll keep trying.
    I really do appreciate the help, but apparently I'm too stupid to get this working.

    Looks like the v, w, and u were the problem. I just need to figure out a way to return those nicely.
     
  11. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Ok, I've got almost all of this code down in GML now (wrote my own dot product function). Still cannot figure out how to get the triangle points' distances from each other: v0, v1, and v2.
    The post you have is in C code, so how can I get from: v0=b-a to GML code? If I can get this part working, I can also do it for v1, and v2, and hopefully the code will work from here.
     
  12. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    here's an example of gml code. Here interpolating color at a 3d point:
    Code:
        //arguments:  point,  vert1 pos,  vert2 pos,  vert3 pos,  vert1 color,  vert2 color,  vert3 color,  out (rgb)
        //            0 1 2   3 4 5       6 7 8       9 10 11     12 13 14      15 16 17      18 19 20      21
        var _v0x = argument[6] - argument[3];
        var _v0y = argument[7] - argument[4];
        var _v0z = argument[8] - argument[5];
        var _v1x = argument[9] - argument[3];
        var _v1y = argument[10] - argument[4];
        var _v1z = argument[11] - argument[5];
        var _v2x = argument[0] - argument[3];
        var _v2y = argument[1] - argument[4];
        var _v2z = argument[2] - argument[5];
        var _d00 = _v0x * _v0x + _v0y * _v0y + _v0z * _v0z;
        var _d01 = _v0x * _v1x + _v0y * _v1y + _v0z * _v1z;
        var _d11 = _v1x * _v1x + _v1y * _v1y + _v1z * _v1z;
        var _d20 = _v2x * _v0x + _v2y * _v0y + _v2z * _v0z;
        var _d21 = _v2x * _v1x + _v2y * _v1y + _v2z * _v1z;
        var _denom = _d00 * _d11 - _d01 * _d01;
        var _v = (_d11 * _d20 - _d01 * _d21) / _denom;
        var _w = (_d00 * _d21 - _d01 * _d20) / _denom;
        var _u = 1 - _v - _w;
        var _out = argument[21];  
        _out[@0] = argument[12] * _u + argument[15] * _v + argument[18] * _w;
        _out[@1] = argument[13] * _u + argument[16] * _v + argument[19] * _w;
        _out[@2] = argument[14] * _u + argument[17] * _v + argument[20] * _w;
     
  13. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    I thought that the GML code would be really long for this... This helps a lot, thank you, flyingsaucerinvasion!
    But, what if I only want to get the Z height of my player so I can place him on the triangle properly? I don't need colors - the triangle is already there and colored in the room. Could I do this without the functions for colors?

    On a side not, can't there be only 15 arguments in GML total?
     
  14. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    there can be more than 16 arguments if you use an argument array.

    You could just us u,v,w to interpolate the z of the three vertices. But, I have a feeling that if you are just trying to find the height on some terrain, the math can be a lot simpler.
     
  15. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    That's interesting that you can do that for GML - never knew...
    Well, if I were using a height map with equally spaced triangles, then the math would be a lot more simple. But, I want all of my triangles to have different sizes - it gives variety, and it doesn't feel like the same thing over and over again.
    So, in my function would I return the u,v, and w? I believe so.

    Edit: I can now move the player from one triangle edge to another very smoothly.
    However, it doesn't work for the other. Right now I'm only returning the u from the function.
    How can I return the weights for the 3 vertices like you mentioned?
    I tried returning u+v+w, but that didn't work either...
     
    Last edited: Dec 15, 2017
  16. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    @MrQuetch

    you could drop the z dimension in these calculations, and then that simplifies the math. It would be even simpler if you could assume you are dealing with right triangles, but this should work for any shape triangles. Try it and tell me if it works for you. One question though, how are you determining which triangles to test?

    Code:
        //arguments:  point, vert1 xy, vert2 xy, vert3 xy, vert1 z, vert2 z, vert3 z
        //            0 1    2 3       4 5       6 7       8        9        10
        var _x =   argument0 - argument2;
        var _y =   argument1 - argument3;
        var _e1x = argument4 - argument2;
        var _e1y = argument5 - argument3;
        var _e2x = argument6 - argument2;
        var _e2y = argument7 - argument3;
        var _id = 1 / (_e1x * _e2y - _e1y * _e2x);
        var _x0 = _x *  _e2y * _id + _y * -_e2x * _id;
        var _y0 = _x * -_e1y * _id + _y *  _e1x * _id;
        return argument8 * (1-_x0-_y0) + argument9 * _x0 + argument10 * _y0;
     
  17. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    I'm beginning by checking which triangle the player is in by using the "point_in_triangle" function provided by GML.
    Then I'm using my "bary" function inside of that which has the code from above.
    Right now I'm using it like this: obj_player.z = bary(arguments here);

    I'll try the other code, and see if it works even better. I really do appreciate all of the help. You're going above and beyond. :)
     
  18. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    doing point in triangle for every triangle on the terrain, will bet pretty expensive wont it? This might be a good use for a quadtree, to only check triangles that are actually near the point. By the way, that last code section i posted can be modified easily to double as a point in triangle collision test.
     
  19. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Yes, it would be - but I only have one triangle simply for the testing.
    Ok, we're getting close now. I can still only go up one edge just fine, when I go on the opposite edge I sink below the triangle.
    Any more ideas? All advice you have gave so far has been great!

    How do you get your code so fast? It almost feels like you have an entire library of GML scripts.
     
  20. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    I like tackling different problems on the forums a lot more than I do working on my own projects :) I've been messing around with this problem off and on since yesterday.

    Let's see the code you are using. In all the tests I've done so far, the methods I've posted have produced correct results. I'd like to see why it doesn't work for you exactly.
     
  21. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    You said the script you had could work for any triangle, but is that true? Just to clarify, my triangle is not a right triangle, and each vertex point has a different height. I'll get my code up.

    Edit:

    player step event:
    //obj_p1, obj_p2, and obj_p3 are objects for triangle points (for now)

    if (point_in_triangle(x, y,obj_p1.x,obj_p1.y,
    obj_p2.x,obj_p2.y,
    obj_p3.x,obj_p3.y))
    {
    obj_player.z = bary(obj_player.x,obj_player.y,
    obj_p1.x,obj_p1.y,
    obj_p2.x,obj_p2.y,
    obj_p3.x,obj_p3.y,
    obj_p1.z,obj_p2.z,obj_p3.z);

    };
     
  22. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    yeah, i've tested it a lot with randomly generated triangles, and compared the computed results against what I measure in photoshop (interpolating colors instead of z). It seems to be accurate with any triangle. So which code are you currently using in bary()? Also, how are you verifying the results?
     
  23. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    Hi everyone!

    you have to get the area of the triangle (cross product), then get the area of each sub triangle (created by the point and each vertex of the triangle) then divide those by the area of the triangle to get the ratio of each vertex value (it can be anything, normals, colours, texturecoords)
    times each vertex value by its ratio, then add them together, that will give the interpolated value at the point in the triangle

    this is the post I found this out from and its the best explaination about it Iv found so far

    https://answers.unity.com/questions/383804/calculate-uv-coordinates-of-3d-point-on-plane-of-m.html
     
    Last edited: Dec 24, 2017
  24. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    Out of interest did mrquetch get it working?
     
    Last edited: Dec 24, 2017
  25. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Hey, everyone. I know it's been a few months since I've last been here.
    Though I have had progress with many other things, I still cannot get a point in a triangle.
    All I want is to be able to get an object's height value equal to the interpolate value of the height values of the three vertices of any single triangle.
    That being said, no matter where the object is in the triangle, it's height will be lerped between the height values of the triangle.

    I have looked at the link for the C code in Unity, but am having trouble trying to figure out how that would look in GML.
    Something I should note... I have tried returning the new height value of an object, but cannot get that working either.
    Any help at all is appreciated. Hopefully, I can solve part of my problem in the meantime.

    In pure honesty, this is really ironic; because I'm somehow able to program a camera with trigonometry, but can't get the height of a point on a triangle.
     
  26. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    @MrQuetch

    Did you ever try this code?

    Code:
       //arguments:  point, vert1 xy, vert2 xy, vert3 xy, vert1 z, vert2 z, vert3 z
       //            0 1    2 3       4 5       6 7       8        9        10
       var _x =   argument0 - argument2;
       var _y =   argument1 - argument3;
       var _e1x = argument4 - argument2;
       var _e1y = argument5 - argument3;
       var _e2x = argument6 - argument2;
       var _e2y = argument7 - argument3;
       var _id = 1 / (_e1x * _e2y - _e1y * _e2x);
       var _x0 = _x *  _e2y * _id + _y * -_e2x * _id;
       var _y0 = _x * -_e1y * _id + _y *  _e1x * _id;
       return argument8 * (1-_x0-_y0) + argument9 * _x0 + argument10 * _y0;
    
     
  27. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Hi there, flyingsaucerinvasion.

    I apologize for my late reply. I don't think I saw this piece of code here before - otherwise I would have tried it months ago.
    The code works! I cannot thank you enough! I'm not sure you know how much this means to you... But, it means a lot to me.
    My games will now begin to have more of a "professional" feel to them.
    Hopefully, I will be able to port this to other languages now.
     
  28. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    @flyingsaucerinvasion

    I'm not sure if this is the right place for another question regarding triangles, but is it possible to find the inclination or depth of a triangle?
    It would be nice if I could tell the player to check the angle, and if it is too steep, then he/she is unable to walk on the surface.
     
  29. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    @MrQuetch Hi. You could get the normal vector of the triangle, and then the "inclination" or steepness could be the z component of the normal vector. If you want the angle of the slope in degrees you could do darccos(normal.z).

    This is for a clockwise triangle... i.e. if the verts look clockwise to you, then the normal vector should be pointing more toward you than away from you (at least in a left-handed coordinate system).
    Code:
        //scr_triangle_normal( x1, y1, _z1, x2, y2, z1, x3, y3, z3, out: vec3 );
        //computes normal vector for triangle
        //returns false if _a and _b are parallel or either is zero length (indicating one or more verticies in the same place)
        //------------------------------------------------------------------------------
            var _out = argument9;
            var _ax = argument3 - argument0;
            var _ay = argument4 - argument1;
            var _az = argument5 - argument2;
            var _bx = argument6 - argument0;
            var _by = argument7 - argument1;
            var _bz = argument8 - argument2;
            _out[@0] = _ay * _bz - _az * _by;
            _out[@1] = _az * _bx - _ax * _bz;
            _out[@2] = _ax * _by - _ay * _bx;
            var _d = sqrt(_out[0] * _out[0] + _out[1] * _out[1] + _out[2] * _out[2] );
            if (_d == 0) { return false; }
            _d = 1 / _d;
            _out[@0] *= _d;
            _out[@1] *= _d;
            _out[@2] *= _d;
            return true;
        //------------------------------------------------------------------------------
    
     
    Last edited: Mar 30, 2018
  30. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Hey again, @flyingsaucerinvasion.

    Thank you for the code. I will try it out.
    I have never seen the "_out" or "@" in GML code before; what does that mean?
     
  31. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    @MrQuetch just passing in an array as one of the arguments to the script and accessing its elements with @, that way you don't have to continuously create new arrays for a return value.
     
  32. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    I know this is even older now. But, does anyone know how to convert the function flyingsaucerinvasion gave to see if a point sits inside a 3D triangle?
    Here's what I've got so far, but it doesn't do anything different.

    Code:
    var _x =   argument0 - argument2;
    var _y =   argument1 - argument3;
    var _z =   0; // ???
    
    var _e1x = argument4 - argument2;
    var _e1y = argument5 - argument3;
    var _e1z = 0; // ???
    
    var _e2x = argument6 - argument2;
    var _e2y = argument7 - argument3;
    var _e2z = 0; // ???
    
    var _id = 1 / (_e1x * _e2y - _e1y * _e2x);
    var _x0 = _x *  _e2y * _id + _y * -_e2x * _id;
    var _y0 = _x * -_e1y * _id + _y *  _e1x * _id;
    var _z0 = _x *  _e3y * _id + _y * -_e3x * _id; // ???
    
    return argument8 * (1-_x0-_y0) + argument9 * _x0 + argument10 * _y0;
     
  33. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    If you project the point onto the triangle's plane, then you can create 3 sub_triangles from the point to each edge, then use the areas to determine whether the point is inside or not, if the 3 sub_areas are more than the area of the triangle, it means the point must be outside.

    Code:
    ///point_in_triangle_areas(triangle, px, py, pz)
    
    var
    t = argument0, px = argument1, py = argument2, pz = argument3, d, p;
    
    var
    nx = t[_tri.nx],
    ny = t[_tri.ny],
    nz = t[_tri.nz];
    
    d = dot_product_3d(, px - t[_tri.x1], py - t[_tri.y1], pz - t[_tri.z1])
    
    p[0] = px - (nx * d)
    p[1] = py - (ny * d)
    p[2] = pz - (nz * d)
    
    var
    v1 = t[_tri.vertex1], v2 = t[_tri.vertex2], v3 = t[_tri.vertex3];
    
    var
    total_area = cross(v1, v2, v3), //the cross script should return a vec4(length, x, y, z)
    sub_area1 = cross(p, v1, v2),
    sub_area2 = cross(p, v2, v3),
    sub_area3 = cross(p, v3, v1);
    
    return (sub_area1[0] + sub_area2[0] + sub_area3[0]) - total_area[0] < 0.001 //cutoff val used to prevent precision errors
    Triangle Areas.png

    Or you can do it using dot products, make 3 triangles using each edge and the point, get the cross products to get perpendicular vectors and do the dot product to see if they're facing inwards towards the main triangle or away from it, if all the triangles are facing inwards (angle differences are more than 90 degrees) the projected point will be inside, if one of them is facing away from the main triangle the point must be outside.

    Code:
    ///point_in_triangle_dot(triangle, px, py, pz)
    
    var
    t = argument0, px = argument1, py = argument2, pz = argument3,
    nx, ny, nz, vx, vy, vz, ex, ey, ez, d, p, j;
    
    nx = t[_tri.nx]
    ny = t[_tri.ny]
    nz = t[_tri.nz]
    
    j = 0
    repeat 3
    {
    vx = px - t[_tri.x1 + j]
    vy = py - t[_tri.y1 + j]
    vz = pz - t[_tri.z1 + j]
    ex = t[_tri.e1x + j]
    ey = t[_tri.e1y + j]
    ez = t[_tri.e1z + j]
    if dot_product_3d_normalised(vz * ey - vy * ez, vx * ez - vz * ex, vy * ex - vx * ey, nx, ny, nz) <= 0 //for collision should be biased eg. <= 0.3
    {break}
    ++j
    }
    
    return j == 3
    
    /* for spherical collision
    if j = 3
    {
    d = dot_product_3d(nx, ny, nz, px, py, pz)
    if d < mask_radius
    {
    d = mask_radius - d
    px += nx * d
    py += ny * d
    pz += nz * d
    }
    }
    */
    
    Triangle dot product.png

    Oh here's the cross script I was using:

    Code:
    ///cross(v1, v2, v3)
    
    var
    v1 = argument0, v2 = argument1, v3 = argument2, v;
    
    var
    v12x = v2[_vertex.x] - v1[_vertex.x],
    v12y = v2[_vertex.y] - v1[_vertex.y],
    v12z = v2[_vertex.z] - v1[_vertex.z],
    v13x = v3[_vertex.x] - v1[_vertex.x],
    v13y = v3[_vertex.y] - v1[_vertex.y],
    v13z = v3[_vertex.z] - v1[_vertex.z];
    
    v[3] = v12x * v13y - v12y * v13x
    v[2] = v12z * v13x - v12x * v13z
    v[1] = v12y * v13z - v12z * v13y
    v[0] = point_distance_3d(0, 0, 0, v[1], v[2], v[3])
    
    return v
     
    Last edited: Sep 28, 2019
  34. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Thank you very much, Joe Ellis!

    Just out of curiosity, if I wanted to input the actual X, Y, and Z for the three points of the triangle - how would I go about doing that?

    I noticed your functions get a reference to the triangle, and the X, Y, and Z for the point that is to be checked.

    So, how would the code look inside if the input for the functions were, ///point_in_triangle_areas(v1x, v1y, v1z, v2x, v2y, v2,z v3x, v3y, v3z, px, py, pz) instead?

    I know the function looks more convoluted that way. But, since I'm still learning, I like to see how literally everything works.

    The idea for this is that I also like porting my GML code to other languages - like C.

    Edit: Is there a good way to check the distance from a triangle to a point?
     
    Last edited: Sep 28, 2019
  35. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    No problem, here's the version of the scripts with individual coords, no arrays, enums or script calls:

    Code:
    ///point_in_triangle_areas_coords(px, py, pz, x1, y1, z1, x2, y2, z2, x3, y3, z3)
    
    var
    px = argument0, py = argument1, pz = argument2,
    x1 = argument3, y1 = argument4, z1 = argument5,
    x2 = argument6, y2 = argument7, z2 = argument8,
    x3 = argument9, y3 = argument10, z3 = argument11,
    cx, cy, cz, nx, ny, nz, d, vx, vy, vz;
    
    //First get the triangle's normal
    
    //Edge vectors
    var
    v12x = x2 - x1,
    v12y = y2 - y1,
    v12z = z2 - z1,
    v13x = x3 - x1,
    v13y = y3 - y1,
    v13z = z3 - z1;
    
    //Cross product
    cx = v12y * v13z - v12z * v13y
    cy = v12z * v13x - v12x * v13z
    cz = v12x * v13y - v12y * v13x
    
    //Normalize the cross product
    d = 1 / point_distance_3d(0, 0, 0, cx, cy, cz)
    
    nx = cx * d
    ny = cy * d
    nz = cz * d
    
    //Get vector from point to vertex 1
    vx = px - x1
    vy = py - y1
    vz = pz - z1
    
    //Get the distance from the point to the plane
    d = dot_product_3d(nx, ny, nz, vx, vy, vz)
    
    //Multiplying the normal by the distance and subtracting it from the point moves the point onto triangle's plane
    px -= (nx * d)
    py -= (ny * d)
    pz -= (nz * d)
    
    //Now to get the areas
    //The length of a cross product is double the triangle's area
    //So we can use the differences to determine whether the point is in the triangle
    var total_area = point_distance_3d(0, 0, 0, cx, cy, cz);
    
    //Get area(p, v1, v2)
    v12x = x1 - px
    v12y = y1 - py
    v12z = z1 - pz
    v13x = x2 - px
    v13y = y2 - py
    v13z = z2 - pz
    
    cx = v12x * v13y - v12y * v13x
    cy = v12z * v13x - v12x * v13z
    cz = v12y * v13z - v12z * v13y
    var sub_area1 = point_distance_3d(0, 0, 0, cx, cy, cz);
    
    //Get area(p, v2, v3)
    v12x = x2 - px
    v12y = y2 - py
    v12z = z2 - pz
    v13x = x3 - px
    v13y = y3 - py
    v13z = z3 - pz
    
    cx = v12x * v13y - v12y * v13x
    cy = v12z * v13x - v12x * v13z
    cz = v12y * v13z - v12z * v13y
    var sub_area2 = point_distance_3d(0, 0, 0, cx, cy, cz);
    
    //Get area(p, v3, v1)
    v12x = x3 - px
    v12y = y3 - py
    v12z = z3 - pz
    v13x = x1 - px
    v13y = y1 - py
    v13z = z1 - pz
    
    cx = v12x * v13y - v12y * v13x
    cy = v12z * v13x - v12x * v13z
    cz = v12y * v13z - v12z * v13y
    var sub_area3 = point_distance_3d(0, 0, 0, cx, cy, cz);
    
    return (sub_area1 + sub_area2 + sub_area3) - total_area < 0.001 //cutoff val used to prevent precision errors
    Code:
    ///point_in_triangle_dot_coords(px, py, pz, x1, y1, z1, x2, y2, z2, x3, y3, z3)
    
    var
    px = argument0, py = argument1, pz = argument2,
    x1 = argument3, y1 = argument4, z1 = argument5,
    x2 = argument6, y2 = argument7, z2 = argument8,
    x3 = argument9, y3 = argument10, z3 = argument11,
    cx, cy, cz, nx, ny, nz, vx, vy, vz, ex, ey, ez, d;
    
    //First get the triangle's normal
    
    //Edge vectors
    var
    v12x = x2 - x1,
    v12y = y2 - y1,
    v12z = z2 - z1,
    v13x = x3 - x1,
    v13y = y3 - y1,
    v13z = z3 - z1;
    
    //Cross product
    cx = v12y * v13z - v12z * v13y
    cy = v12z * v13x - v12x * v13z
    cz = v12x * v13y - v12y * v13x
    
    //Normalize the cross product
    d = 1 / point_distance_3d(0, 0, 0, cx, cy, cz)
    
    nx = cx * d
    ny = cy * d
    nz = cz * d
    
    //Create temp triangles from the point to each edge
    //and check that the cross products are all facing towards the main triangle \ facing in the opposite direction to the main triangle's normal
    
    //point to edge1
    vx = px - x1
    vy = py - y1
    vz = pz - z1
    ex = x2 - x1
    ey = y2 - y1
    ez = z2 - z1             //here the cross product is calculated straight into the argument to save assigning vars
    if dot_product_3d_normalised(vz * ey - vy * ez, vx * ez - vz * ex, vy * ex - vx * ey, nx, ny, nz) <= 0
    {return false}
    
    //point to edge2
    vx = px - x2
    vy = py - y2
    vz = pz - z2
    ex = x3 - x2
    ey = y3 - y2
    ez = z3 - z2
    if dot_product_3d_normalised(vz * ey - vy * ez, vx * ez - vz * ex, vy * ex - vx * ey, nx, ny, nz) <= 0
    {return false}
    
    //point to edge3
    vx = px - x3
    vy = py - y3
    vz = pz - z3
    ex = x1 - x3
    ey = y1 - y3
    ez = z1 - z3
    if dot_product_3d_normalised(vz * ey - vy * ez, vx * ez - vz * ex, vy * ex - vx * ey, nx, ny, nz) <= 0
    {return false}
    
    return true
    

    About checking the distance from a triangle to a point, the dot product of the triangle's normal and a vector from one of the triangle's vertices to the point gives the distance from the point to the triangles plane:

    distance = dot_product_3d(nx, ny, nz, px - x1, py - y1, pz - z1)

    This will return negative if the point is behind the triangle\the vector is pointing in the opposite direction to the triangle's normal, but this works fine for projecting as it will invert the normal, but if you need the actual distance just do abs(distance)

    But this only gets the distance to the nearest point on the triangle's plane, so if the projected point would land outside the triangle, the nearest point will be somewhere along the edge that failed the dot product check.

    To get this point:
    1. Get the dot product of the edge vector and the vector to the first vertex of the edge
    2. Divide it by the length of the edge vector
    3. Clamp the result to 0 to 1
    4. Lerp from vertex 1 to vertex 2 using this as a ratio

    Here's a distance_to_triangle script which uses these functions:
    Code:
    ///distance_from_triangle(px, py, pz, x1, y1, z1, x2, y2, z2, x3, y3, z3)
    
    var
    px = argument0, py = argument1, pz = argument2,
    x1 = argument3, y1 = argument4, z1 = argument5,
    x2 = argument6, y2 = argument7, z2 = argument8,
    x3 = argument9, y3 = argument10, z3 = argument11,
    cx, cy, cz, nx, ny, nz, vx, vy, vz, ex, ey, ez, d;
    
    //First get the triangle's normal
    
    //Edge vectors
    var
    v12x = x2 - x1,
    v12y = y2 - y1,
    v12z = z2 - z1,
    v13x = x3 - x1,
    v13y = y3 - y1,
    v13z = z3 - z1;
    
    //Cross product
    cx = v12y * v13z - v12z * v13y
    cy = v12z * v13x - v12x * v13z
    cz = v12x * v13y - v12y * v13x
    
    //Normalize the cross product
    d = 1 / point_distance_3d(0, 0, 0, cx, cy, cz)
    
    nx = cx * d
    ny = cy * d
    nz = cz * d
    
    //Create temp triangles from the point to each edge
    //and check that the cross products are all facing towards the main triangle \ facing in the opposite direction to the main triangle's normal
    
    //point to edge1
    vx = px - x1
    vy = py - y1
    vz = pz - z1
    ex = x2 - x1
    ey = y2 - y1
    ez = z2 - z1
    if dot_product_3d_normalised(vz * ey - vy * ez, vx * ez - vz * ex, vy * ex - vx * ey, nx, ny, nz) <= 0
    {
    //To get the nearest point on the edge:
    //Get the dot product of the edge vector and the vector to the first vertex of the edge
    //Divide it by the length of the edge vector
    //Clamp the result to (0, 1)
    //Then lerp from v1 to v2 using this ratio
    d = clamp(dot_product_3d(ex, ey, ez, vx, vy, vz) / point_distance_3d(0, 0, 0, ex, ey, ez), 0, 1)
    ex = x1 + (ex * d)
    ey = y1 + (ey * d)
    ez = z1 + (ez * d)
    return point_distance_3d(px, py, pz, ex, ey, ez)
    }
    
    //point to edge2
    vx = px - x2
    vy = py - y2
    vz = pz - z2
    ex = x3 - x2
    ey = y3 - y2
    ez = z3 - z2
    if dot_product_3d_normalised(vz * ey - vy * ez, vx * ez - vz * ex, vy * ex - vx * ey, nx, ny, nz) <= 0
    {
    d = clamp(dot_product_3d(ex, ey, ez, vx, vy, vz) / point_distance_3d(0, 0, 0, ex, ey, ez), 0, 1)
    ex = x2 + (ex * d)
    ey = y2 + (ey * d)
    ez = z2 + (ez * d)
    return point_distance_3d(px, py, pz, ex, ey, ez)
    }
    
    //point to edge3
    vx = px - x3
    vy = py - y3
    vz = pz - z3
    ex = x1 - x3
    ey = y1 - y3
    ez = z1 - z3
    if dot_product_3d_normalised(vz * ey - vy * ez, vx * ez - vz * ex, vy * ex - vx * ey, nx, ny, nz) <= 0
    {
    d = clamp(dot_product_3d(ex, ey, ez, vx, vy, vz) / point_distance_3d(0, 0, 0, ex, ey, ez), 0, 1)
    ex = x3 + (ex * d)
    ey = y3 + (ey * d)
    ez = z3 + (ez * d)
    return point_distance_3d(px, py, pz, ex, ey, ez)
    }
    
    //If not outside, the distance is the dot product of the triangle's normal and the vector from the point to one of the vertices
    return abs(dot_product(nx, ny, nz, vx, vy, vz))
     
    Last edited: Sep 28, 2019
  36. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    If what you're doing is extending a line starting at a point, in the normal direction of the triangle, and wanting to know if that line intersects the triangle, then....

    Adjusting the original response I made to this thread gives a fairly streamlined answer.
    Code:
        var _x0 = x1 - x0;
        var _y0 = y1 - y0;
        var _z0 = z1 - z0;
        var _x1 = x2 - x0;
        var _y1 = y2 - y0;
        var _z1 = z2 - z0;
        var _x2 = px - x0;
        var _y2 = py - y0;
        var _z2 = pz - z0;
        var _a = _x0*_x0 + _y0*_y0 + _z0*_z0;
        var _b = _x0*_x1 + _y0*_y1 + _z0*_z1;
        var _c = _x1*_x1 + _y1*_y1 + _z1*_z1;
        var _d = _x2*_x0 + _y2*_y0 + _z2*_z0;
        var _e = _x2*_x1 + _y2*_y1 + _z2*_z1;
        var _i = _a*_c - _b*_b;
        var _u = (_c*_d - _b*_e) / _i;
        var _v = (_a*_e - _b*_d) / _i;
        var in_triangle = ((_u + _v)<1) && (_u>0) && (_v>0);
    
    the triangle is x0,y0,z0, through x2,y2,z2, the 3d point is px,py,pz.
     
    Last edited: Sep 29, 2019
  37. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    I just worked out a really simple and fast method that's alot more efficient than the other 2 methods I was talking about.

    It basically uses edge tangents, which are calculated with the cross product of the triangle's normal and each edge vector, it returns a vector
    that is perpendicular to the normal and the edge, which essentially makes a vector that sticks out from the edge at 90 degrees and is parallel with the triangle's plane.

    Once you've got these tangents, all you need to do is get the dot_products of the point to each vertex and each edge tangent,
    if any of these return < 0 (more than 90 degrees difference) it means the point is outside of the triangle's projected prism. (or the point when projected
    will land outside the triangle)
    It's best if you precalculate these tangents and store them in the triangle array, otherwise the speed increase is alot less and puts it on similar ground to the dot product method I showed you before.

    Here's the script if calculating the tangents dynamically:
    Code:
    ///point_in_triangle_tangents(px, py, pz, x1, y1, z1, x2, y2, z2, x3, y3, z3)
    
    var
    px = argument0, py = argument1, pz = argument2,
    x1 = argument3, y1 = argument4, z1 = argument5,
    x2 = argument6, y2 = argument7, z2 = argument8,
    x3 = argument9, y3 = argument10, z3 = argument11;
    
    //Edge vectors
    var
    e1x = x2 - x1, e1y = y2 - y1, e1z = z2 - z1,
    e2x = x3 - x2, e2y = y3 - y2, e2z = z3 - z2,
    e3x = x1 - x3, e3y = y1 - y3, e3z = z1 - z3;
    
    //Triangle Normal (cross_product(edge vector 1, edge_vector 3))
    var
    nx = e1y * e3z - e1z * e3y,
    ny = e1z * e3x - e1x * e3z,
    nz = e1x * e3y - e1y * e3x;
    
    //Edge Tangents (cross_product(normal, edge_vector))
    var
    t1x = e1y * nz - e1z * ny,
    t1y = e1z * nx - e1x * nz,
    t1z = e1x * ny - e1y * nx,
    t2x = e2y * nz - e2z * ny,
    t2y = e2z * nx - e2x * nz,
    t2z = e2x * ny - e2y * nx,
    t3x = e3y * nz - e3z * ny,
    t3y = e3z * nx - e3x * nz,
    t3z = e3x * ny - e3y * nx;
    
    return //(dot_product(vec(point to edge vertex), each edge tangent)
       dot_product_3d(px - x1, py - y1, pz - z1, t1x, t1y, t1z) > 0
    && dot_product_3d(px - x2, py - y2, pz - z2, t2x, t2y, t2z) > 0
    && dot_product_3d(px - x3, py - y3, pz - z3, t3x, t3y, t3z) > 0

    And here's the script if the tangents are precalculated:
    Code:
    ///point_in_triangle_tangents(triangle, px, py, pz)
    
    var t = argument0, px = argument1, py = argument2, pz = argument3;
    
    return
       dot_product_3d(px - t[_tri.x1], py - t[_tri.y1], pz - t[_tri.z1], t[_tri.t1x], t[_tri.t1y], t[_tri.t1z]) > 0
    && dot_product_3d(px - t[_tri.x2], py - t[_tri.y2], pz - t[_tri.z2], t[_tri.t2x], t[_tri.t2y], t[_tri.t2z]) > 0
    && dot_product_3d(px - t[_tri.x3], py - t[_tri.y3], pz - t[_tri.z3], t[_tri.t3x], t[_tri.t3y], t[_tri.t3z]) > 0

    This might be the fastest & simplest way possible, and its easy to mix with other things like spherical collision and getting the nearest point along the edge if it's not inside. I'm pretty glad I worked this out, it should make my collision system about twice as fast.

    @flyingsaucerinvasion your method is pretty good aswell, comparing the two with the number of calculations, var assignments, var read, array reads and conditionals, this method has 65, and yours has 75, (when the vectors are precalculated wherever possible) so there's probably no real difference between them.
    Actually I just did a speed test of how many calls each script could do per step, mine could do 6990 and yours could do 4145,
    however when all the vectors were calculated dynamically, mine could do 2013 and yours could do 2488,
    but this also shows how precalculating the triangle's vectors makes a huge difference.
     
  38. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    @Joe Ellis

    I think this might do even better when you precompute a,b,c,d,e,f:

    triangle is x0,y0,z0 through x2,y2,z2, point is px,py,pz.
    Code:
        //precompute a,b,c,d,e,f:
        var _e0x = x1 - x0;
        var _e0y = y1 - y0;
        var _e0z = z1 - z0;
        var _e1x = x2 - x0;
        var _e1y = y2 - y0;
        var _e1z = z2 - z0;
        var _e2x = _e0y * _e1z - _e1y * _e0z;
        var _e2y = _e0z * _e1x - _e1z * _e0x;
        var _e2z = _e0x * _e1y - _e1x * _e0y;
        var _id = 1/(_e2x*_e2x+_e2y*_e2y+_e2z*_e2z);
        var _a =  (_e1y * _e2z - _e1z * _e2y) * _id
        var _b = -(_e0y * _e2z - _e0z * _e2y) * _id;
        var _c = -(_e1x * _e2z - _e1z * _e2x) * _id;
        var _d =  (_e0x * _e2z - _e0z * _e2x) * _id;
        var _e =  (_e1x * _e2y - _e1y * _e2x) * _id;
        var _f = -(_e0x * _e2y - _e0y * _e2x) * _id;
        //end of precomputation stuff
     
        //testing a point:
        var _sx = px - x0;
        var _sy = py - y0;
        var _sz = pz - z0;
        var _u = _a*_sx + _c*_sy + _e*_sz;
        var _v = _b*_sx + _d*_sy + _f*_sz;
        var in_triangle = (_u>0) && (_v>0) && ((_u + _v)<1);
    
    Actually, I just thought of a way to improve this even further.... back in a sec with an edit.
    EDIT:

    Adding precomputed g and h, so you don't need to subtract vertex zero from the 3d point. This also allows you to forego storing x0,y0,z0 (position of first vertex of triangle), becuase those are no longer used in the test.
    Code:
        var _g = _a*-x0 + _c*-y0 + _e*-z0;
        var _h = _b*-x0 + _d*-y0 + _f*-z0;
     
        //testing a point:
        var _u = _a*px + _c*py + _e*pz + _g;
        var _v = _b*px + _d*py + _f*pz + _h;
        var in_triangle = (_u>0) && (_v>0) && ((_u + _v)<1);
    
    you might get extra performance boost by using dot_product_3d, I haven't looked into that.

    It also occurred to me that in my previous attempt, "i" could have been divided into c, b, and a, and so could have been move to the precomputation part of the code.
     
    Last edited: Oct 1, 2019
  39. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    948
    @flyingsaucerinvasion

    Hi, yeah that method is faster.

    While I was testing I also found out that referencing arguments directly rather than declaring them as vars first gives around 1.5 speed increase, so after I changed all the vars to argument0, 1, 2... the results were:

    my method: 5834
    your method: 7345

    However if I nested the conditionals in mine or turned shortcircuit evaluations on it managed 11113,
    but I'm testing with completely randomized coordinates so that makes sense cus of the likely hood of the first dot product check failing, it only needs to do one dot product and 3 subtractions.
    But in a real game scenario using a quad tree its more likely the point will be inside the triangle than not, so I think your method will be the fastest.

    Btw, I tested various ways of laying it out and this one gave the best results:

    Code:
    var u = dot_product_3d(argument0[0], argument0[1], argument0[2], argument1, argument2, argument3) + argument0[3];
    
    if u > 0
    {
    var v = dot_product_3d(argument0[4], argument0[5], argument0[6], argument1, argument2, argument3) + argument0[7];
    return v > 0 && u + v < 1
    }
    
    return false
    I also tested whether dot_product_3d is faster than v*v + v*v + v*v
    and it is slightly faster,

    I tested 2 scripts that return dot_product_3d and v*v + v*v + v*v
    dot_product_3d could do 16196 and manual was 14623, so not alot of difference relatively but still 1573 extra per step.

    Thanks for sharing your method, I'm gonna test the two out in my collision system next and I'll post the results.

    EDIT- I just changed the way I was testing it and put the code straight into the while get_timer() - start_time < 15000
    and the results became even faster, your method peaked at around 19000 reps per step, and mine with shortcircuit evaluations off only managed around 7000,
    I also tested the average (total_reps += reps, mean_reps = total_reps / (++num_steps), as I thought this might be a more accurate test, and it gave: 13400 to 6500, so I think you have found the fastest way anyone knows of doing this :D
     
    Last edited: Oct 1, 2019
  40. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    Thank you... You guys are both awesome.
    This is the last thing I'm going to ask for on here, and I'll leave it be.

    Do you guys have GML code for line-triangle intersections? I've been trying to port various code from other languages to GML and I'm having a tough time with it.
    I would preferably like the code in the way Joe Ellis does it. As he stated, "with individual coords, no arrays, enums or script calls".

    Is that fine?
     
  41. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,169
    Well, you can get the intersection between a line and the plane formed by the triangle:
    Code:
    
        var _t = ((x0-px)*_e2x+(y0-py)*_e2y+(z0-pz)*_e2z)/(_dx*_e2x+_dy*_e2y+_dz*_e2z);
        var _ix = px + _dx*_t;
        var _iy = py + _dy*_t;
        var _iz = pz + _dz*_t;
    
    v (x0,y0,z0) = a vertex on the triangle (also a point on the plane formed by the triangle)
    p (px,py,pz) = a point on the line
    d (dx,dy,dz) = direction line points
    n (_e2x,_e2y,_e2z) = normal direction of triangle (and plane)
    _t = intersection (as proportion of d, starting from p).
    _ix,_iy,_iz = intersection point.

    (i - v) *n = 0 (dot product of plane normal direction (n) and difference between two points (i and v) on the plane, is always zero. meaning these vectors are perpendicular to each other).
    i is a point on the plane, but also a point on the line (in other words, it's the intersection point between the plane and the line).
    i = p+d*t (the point i, which is a point on the line (as well as the plane), equals a point on the line (p) + the direction of the line (d) * some factor (t).
    substitute p+d*t for i, because they are equal.
    (p+d*t - v)*n = 0
    (p-v)*n + d*n*t = 0
    solve for t:
    t = (v-p)*n/(d*n)
    important note: if the line is parallel to the plane, then d*n will be zero, and a divide by zero error will happen.

    I was already calculating the normal direction of the triangle in the stuff we were doing before:
    Code:
        var _e0x = x1 - x0;
        var _e0y = y1 - y0;
        var _e0z = z1 - z0;
        var _e1x = x2 - x0;
        var _e1y = y2 - y0;
        var _e1z = z2 - z0;
        //_e2 points in normal direction (n):
        var _e2x = _e0y * _e1z - _e1y * _e0z;
        var _e2y = _e0z * _e1x - _e1z * _e0x;
        var _e2z = _e0x * _e1y - _e1x * _e0y; 
    
    Once you have the intersection point, you could use the code we were working on previously to determine if that point lies inside of the triangle. There might be possible optimizations when combining these two things... I'll have a think about it.
     
  42. MrQuetch

    MrQuetch Member

    Joined:
    Feb 23, 2017
    Posts:
    29
    I'm aware this is getting older. But, if you've found another way of getting the intersection of a line and a triangle, I'd really love to see how you do it. Thank you!
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice