1

I'm not sure what to search, so I haven't been able to find what I need.

Say I have a 3D triangle with points [0, 1, 1], [1, 0.5, 0.5], [0, 0, 0]. I discard the Z component to create a 2D triangle with points [0, 1], [1, 0.5], [0, 0]. (I think this is an orthographic projection?) Through an unimportant process I find some 2D point that lies within the 2D triangle, say [0.5, 0.5].

How do I take that 2D point and find what its Z value should be to have it lie on the plane formed by the original 3D triangle?

Answers (or dupe links!) that describe maths through code rather than mathematical symbols would be greatly appreciated; I struggle to read the types of answers you get on Math.SE.

Clonkex
  • 3,373
  • 7
  • 38
  • 55
  • The plane of the original triangle will have an equation like `z = a*x + b*y + c`. Find that equation and then just plug in the `x` and `y`. – John Coleman Nov 30 '20 at 00:45
  • @JohnColeman I'm unsure exactly what you mean. Are `a`, `b` and `c` the points of the triangle? I'm not sure if you're saying that equation somehow gives me the Z value. – Clonkex Nov 30 '20 at 00:56
  • The equation of a non-vertical line in 2 dimensions can be written as `y = a*x + b`. Similarly, the equation of a non-vertical plane in 3 dimensions can be written as `z = a*x + b*y + c`. The `a,b,c` in question are scalars which can be obtained in various ways. A standard way is to form the cross product of the vectors `PQ` and `PR` (where `P,Q,R` are the points in the original triangle.). `a,b,c` can be easily obtained from that cross product. Search for "equation of plane through 3 points". – John Coleman Nov 30 '20 at 01:05
  • @JohnColeman Honestly I was hoping to have to figure out less myself. If I have to figure out the maths myself I'll make mistakes and waste hours trying to find the bug in something I don't really understand. If I have to google "equation of [whatever]" I'm screwed because I only understand maths when it's described through code, unless it's simple algebra. It's a failing in my education, I know. When you say things like "the equation of a non-vertical line in 2d can be written as `y = a*x + b`" I can only stare blankly at it. What is y? What are x, a and b? How does that translate to code? – Clonkex Nov 30 '20 at 01:15
  • Maybe [this link](https://www.geeksforgeeks.org/program-to-find-equation-of-a-plane-passing-through-3-points/) will help. – John Coleman Nov 30 '20 at 02:15
  • @JohnColeman Well that helps a bit (and thanks for trying to help!), but I'm realising half the confusion is stemming from not understand what it means to have an equation of a plane passing through 3 points. For instance, at the bottom of that page it has `equation of plane is 26 x + 7 y + 9 z + 3 = 0.` but that still leaves a lot of meaningless variables and values. What do the scalars actually represent? What are the variables xyz? I just can't see what this means in any practical terms. Their `equation_plane` function doesn't return anything or even appear to calculate anything useful. – Clonkex Nov 30 '20 at 03:07
  • I don't think it's practically possible to implement a working solution without understanding the maths. – Beta Nov 30 '20 at 03:08
  • `x,y,z` are the standard symbols for the coordinates of points in 3 dimensional space. So if the point is `[2, 3, 0.5]` then `x = 2, y = 3, z = 0.5`. You were essentially asking for how to find `z` given `x,y` underneath the assumption that `[x,y,z]` lies on the plane through 3 vertices of the triangle. – John Coleman Nov 30 '20 at 03:13
  • @Beta I can typically understand the maths just fine, but only if it's described in the context of code, or with good visual representations. People often seem confused by this but I'm a very visual guy, and I learned maths by doing. I can visualise the results of code because there's no magic or abstract ideas, it's just purely functional and practical. You can directly _use_ code, you can't directly use "equation of a plane". – Clonkex Nov 30 '20 at 21:21

2 Answers2

3

You can use barycentric coordinates...

So you got 2D triangle q0,q1,q2 and corresponding 3D triangle p0,p1,p2 and want to convert 2D point q into 3D point p

  1. compute barycentric coordinates u,v of q within q0,q1,q2

    see how to compute barycentric coordinates

  2. convert u,v to cartessian using triangle p0,p1,p2

So when put together:

| u |           | (q1.x - q0.x) , (q2.x - q0.x) , q0.x |   | q.x |
| v | = inverse | (q1.y - q0.y) , (q2.y - q0.y) , q0.y | * | q.y |
| 1 |           |       0       ,       0       ,   1  |   |  1  |

p.x = p0.x + (p1.x - p0.x) * u + (p2.x - p0.x) * v
p.y = p0.y + (p1.y - p0.y) * u + (p2.y - p0.y) * v
p.z = p0.z + (p1.z - p0.z) * u + (p2.z - p0.z) * v
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Ahhh of course! Take the barycentric coords of the point in the 2D triangle and find what point would result on the 3D triangle with those same barycentric coords. I was thinking of doing it a similar way using squared distances and then interpolating the Z, but this is probably faster. Sebastian Lague has a great explanation of barycentric coords (https://www.youtube.com/watch?v=HYAgJN3x4GA), but as people in the comments pointed out, his implementation would fail if `A.y == C.y` because it divides by 0. There's fixes but I think I'll just google for a tested implementation. Thanks! – Clonkex Nov 30 '20 at 21:17
  • @Clonkex The inverse 3x3 matrix approach eliminates the problems with wrong order of computation of the system of equations... otehrwise you would need to have 2 solutions and use the most accurate one (that avoids division by zero or by too small value) – Spektre Nov 30 '20 at 21:59
  • For future reference I used [this implementation](https://gamedev.stackexchange.com/a/63203/48697) (though the accepted answer also works) and then did `float newX = tri.p0.x * u + tri.p1.x * v + tri.p2.x * w;` (obviously replacing all `x` with `y` and `z` for the other axes). I would have used your inverse matrix approach but I know almost nothing of matrix maths (a significant weakness for game programming, I realise) and couldn't easily figure out how to implement that in Unity (not that I spent much time on it). – Clonkex Dec 02 '20 at 01:47
  • @Clonkex see [Understanding 4x4 homogenous transform matrices](https://stackoverflow.com/a/28084380/2521214) ... doing 3D graphics without them is not a good idea. For matrix math there are libs like GLM... Or you can write your own here mine [ND math](https://stackoverflow.com/a/55439139/2521214) – Spektre Dec 02 '20 at 06:25
  • Thanks, that's useful. [3Blue1Brown](https://www.youtube.com/c/3blue1brown/videos) also has some excellent videos that explain some of the basics of linear algebra (visually, which helps me immensely!), which I've seen before but need to watch again. People are often surprised that I don't already know matrix maths, but while I certainly wouldn't want to write my own graphics engine without learning it, I've been a hobbyist game dev for most of my life and aside from some shader programming I've hardly had need of them. For 99% of the stuff I work with, simple vector maths is all I need. – Clonkex Dec 02 '20 at 07:28
  • @Clonkex matrices+vectors and linear algebra make things much easier (not just for graphics but also in math and geometry). Yes you can do stuff without them but its like counting on fingers instead of with calculator. – Spektre Dec 02 '20 at 07:40
  • Thanks to you my original theory is now [working in practice](https://imgur.com/a/wpbZM68)! I initially used the implementation from that other answer, but had issues where it would fail on certain triangles. I decided to try your way with matrices, but wasn't going to learn how to multiply matrices just to do that so I found an excellent [free matrix library](http://blog.ivank.net/lightweight-matrix-class-in-c-strassen-algorithm-lu-decomposition.html) ... and had the same bug. Eventually realised I was using degenerate triangles. I'll post my own answer later but yours will remain accepted :D – Clonkex Dec 03 '20 at 02:05
1

Expanding on @Spektre's excellent answer, this was how I implemented a working solution. I'm working with Unity, so I used Ivan Kutskir's awesome lightweight C# matrix class to handle the matrix maths. There's probably faster/cleaner ways to do this but this was very easy and works correctly.

Obviously you have to ensure that when you discard the Z axis, you don't end up with a degenerate triangle.

// tri is a 3D triangle with points p0, p1 and p2
// point is a 2D point within that triangle, assuming the Z axis is discarded

/*
Equivalent to this part of @Spektre's answer:

| u |           | (q1.x - q0.x) , (q2.x - q0.x) , q0.x |   | q.x |
| v | = inverse | (q1.y - q0.y) , (q2.y - q0.y) , q0.y | * | q.y |
| 1 |           |       0       ,       0       ,   1  |   |  1  |
*/

Matrix m1 = new Matrix(3, 3);
Matrix m2 = new Matrix(3, 1);
m1[0, 0] = tri.p1.x - tri.p0.x;
m1[0, 1] = tri.p2.x - tri.p0.x;
m1[0, 2] = tri.p0.x;
m1[1, 0] = tri.p1.y - tri.p0.y;
m1[1, 1] = tri.p2.y - tri.p0.y;
m1[1, 2] = tri.p0.y;
m1[2, 0] = 0;
m1[2, 1] = 0;
m1[2, 2] = 1;
m2[0, 0] = point.x;
m2[1, 0] = point.y;
m2[2, 0] = 1;
Matrix mResult = m1.Invert() * m2;
float u = (float)mResult[0, 0];
float v = (float)mResult[1, 0];

/*
Equivalent to this part of @Spektre's answer:

p.x = p0.x + (p1.x - p0.x) * u + (p2.x - p0.x) * v
p.y = p0.y + (p1.y - p0.y) * u + (p2.y - p0.y) * v
p.z = p0.z + (p1.z - p0.z) * u + (p2.z - p0.z) * v
*/

float newX = tri.p0.x + (tri.p1.x - tri.p0.x) * u + (tri.p2.x - tri.p0.x) * v;
float newY = tri.p0.y + (tri.p1.y - tri.p0.y) * u + (tri.p2.y - tri.p0.y) * v;
float newZ = tri.p0.z + (tri.p1.z - tri.p0.z) * u + (tri.p2.z - tri.p0.z) * v;
Vector3 newPoint = new Vector3(newX, newY, newZ);

Alternatively, you can achieve the same result without the matrix (though this may be a less robust method, I'm not sure). To calculate the barycentric coordinates I used this implementation, but the accepted answer also works.

// tri is a 3D triangle with points p0, p1 and p2
// point is a 2D point within that triangle, assuming the Z axis is discarded

// Find the barycentric coords for the chosen 2D point...
float u, v, w = 0;
Barycentric2D(point, new Vector2(tri.p0.x, tri.p0.y), new Vector2(tri.p1.x, tri.p1.y), new Vector2(tri.p2.x, tri.p2.y), out u, out v, out w);

// ...and then find what the Z value would be for those barycentric coords in 3D
float newZ = tri.p0.z * u + tri.p1.z * v + tri.p2.z * w;
Vector3 newPoint = new Vector3(point.x, point.y, newZ);

// https://gamedev.stackexchange.com/a/63203/48697
void Barycentric2D(Vector2 p, Vector2 a, Vector2 b, Vector2 c, out float u, out float v, out float w)
{
    Vector2 v0 = b - a;
    Vector2 v1 = c - a;
    Vector2 v2 = p - a;
    float den = v0.x * v1.y - v1.x * v0.y;
    v = (v2.x * v1.y - v1.x * v2.y) / den;
    w = (v0.x * v2.y - v2.x * v0.y) / den;
    u = 1.0f - v - w;
}
Clonkex
  • 3,373
  • 7
  • 38
  • 55