Projection on a 2D plane for barycenter calculations

Question

I have three vertices that make up a plane / polygon in 3D space, v0, v1 and v2.

To calculate the barycentric coordinates for a three-dimensional point on this plane, I must first project the plane and the point into two-dimensional space.

After trawling on the Internet, I have a good understanding of how to calculate barycentric coordinates in 2D space, but I am stuck in finding a better way to project my 3D points into a suitable 2D plane.

I was suggested that the best way to achieve this is to "lower the axis with the smallest projection." Without checking the area of ​​the polygon formed when projecting on each world axis (xy, yz, xz), how can I determine which projection is better (has the largest area) and therefore is most suitable for calculating the most accurate barycentric coordinate

Answer 1

After much discussion, there is actually a fairly simple way to solve the original problem - to find out which axis is omitted when projecting into 2D space. The answer is described in 3D Math Primer for graphics and game development as follows:

“The solution to this dilemma is to select the projection plane so that to maximize the area of ​​the predicted triangle. This can be done by examining the normal plane; the coordinate that has the greatest absolute value is the coordinate that we will drop. For example, if normal - [- 1, 0, 0], then we discard the values ​​of x vertices and p protruding on the y2 plane.

My initial decision, which included calculating the grade on the axis (using a sub-delta), was wrong, since you can create a zero point for all three axes, in which case the axis of incidence remains undefined.

Using the normal of the collision plane (which can be pre-calculated for efficiency) to determine which axis is omitted when projecting in 2D is the best approach.

Answer 2

An example of the calculation of barycentric coordinates in three-dimensional space at the request of the OP. Given:

• 3D points v0, v1, v2 that define a triangle
• A 3D point p lying on the plane defined by v0, v1 and v2 and inside a triangle stretched to the same points.

"x" stands for the transverse product between two 3D vectors.
"len" indicates the length of the 3D vector.
"u", "v", "w" are barycentric coordinates belonging to v0, v1 and v2, respectively.

triArea = len((v1 - v0) x (v2 - v0)) * 0.5 u = ( len((v1 - p ) x (v2 - p )) * 0.5 ) / triArea v = ( len((v0 - p ) x (v2 - p )) * 0.5 ) / triArea w = ( len((v0 - p ) x (v1 - p )) * 0.5 ) / triArea => p == u * v0 + v * v1 + w * v2 

Cross product is defined as follows:

 v0 x v1 := { v0.y * v1.z - v0.z * v1.y, v0.z * v1.x - v0.x * v1.z, v0.x * v1.y - v0.y * v1.x } 

Answer 3

A WARNING. Almost everything that I know about using barycentric coordinates and using matrices to solve linear equations was learned last night because I found this question so interesting. So the following may be wrong, wrong, wrong - but some of the test values ​​that I set do work. Guys and girls, please feel free to tear it apart if I completely messed up, but here it goes.

Search for barycentric coords in 3D space (with a little help from Wikipedia)

Given:

 v0 = (x0, y0, z0) v1 = (x1, y1, z1) v2 = (x2, y2, z2) p = (xp, yp, zp) 

Find the barycentric coordinates: b0, b1, b2 of the point p relative to the triangle defined by v0, v1 and v2

Knowing that:

 xp = b0*x0 + b1*x1 + b2*x2 yp = b0*y0 + b1*y1 + b2*y2 zp = b0*z0 + b1*z1 + b2*z2 

What can be written as

 [xp] [x0] [x1] [x2] [yp] = b0*[y0] + b1*[y1] + b2*[y2] [zp] [z0] [z1] [z2] 

or

 [xp] [x0 x1 x2] [b0] [yp] = [y0 y1 y2] . [b1] [zp] [z0 z1 z2] [b2] 

rebuilt as

  -1 [b0] [x0 x1 x2] [xp] [b1] = [y0 y1 y2] . [yp] [b2] [z0 z1 z2] [zp] 

3x3 matrix determinant:

 det = x0(y1*z2 - y2*z1) + x1(y2*z0 - z2*y0) + x2(y0*z1 - y1*z0) 

its conjugate is

 [y1*z2-y2*z1 x2*z1-x1*z2 x1*y2-x2*y1] [y2*z0-y0*z2 x0*z2-x2*z0 x2*y0-x0*y2] [y0*z1-y1*z0 x1*z0-x0*z1 x0*y1-x1*y0] 

giving:

 [b0] [y1*z2-y2*z1 x2*z1-x1*z2 x1*y2-x2*y1] [xp] [b1] = ( [y2*z0-y0*z2 x0*z2-x2*z0 x2*y0-x0*y2] . [yp] ) / det [b2] [y0*z1-y1*z0 x1*z0-x0*z1 x0*y1-x1*y0] [zp] 

If you need to check several points against a triangle, stop here. Calculate the above 3x3 matrix once for a triangle (dividing it also by the determinant), and then the point product, which will cause each point to receive barycentric coordinates for each point.

If you do this only once per triangle, then the above is multiplied (kindly provided by Maxima):

 b0 = ((x1*y2-x2*y1)*zp+xp*(y1*z2-y2*z1)+yp*(x2*z1-x1*z2)) / det b1 = ((x2*y0-x0*y2)*zp+xp*(y2*z0-y0*z2)+yp*(x0*z2-x2*z0)) / det b2 = ((x0*y1-x1*y0)*zp+xp*(y0*z1-y1*z0)+yp*(x1*z0-x0*z1)) / det 

These are quite a few additions, subtractions and multiplications - three divisions, but not sqrts or trigger functions. Obviously, this takes longer than pure 2D calculations, but depending on the complexity of the projection heuristic and calculations, this may turn out to be the fastest way.

As I mentioned - I have no idea what I'm talking about, but maybe it will work, or maybe someone else can come and fix it.

Answer 4

Update: ignore, this approach does not work in all cases

I think I found the right solution to this problem.

NB: I need a projection on a 2D space, and not on working with three-dimensional barycentric coordinates, since I am invited to make the most efficient algorithm. The additional overhead incurred when finding a suitable projection plane should still be less than the overhead incurred when using more complex operations like sqrt or sin () cos () functions (I think I could use lookup tables for sin / cos, but that would increase memory and hit the target of this assignment).

My first attempts found a delta between the min / max values ​​on each axis of the polygon, and then deleted the axis with the smallest delta. However, as @PeterTaylor suggested, there are cases where a falling axis with the smallest delta can cause a straight line rather than a triangle when projecting into two-dimensional space. THIS IS REQUIRED .

So my revised solution is as follows:

• Find each sub delta on each axis for the polygon {abs (v1.x-v0.x), abs (v2.x-v1.x), abs (v0.x-v2.x)}, this result in 3 scalar values on the axis.
• Then multiply these scaling values ​​to calculate the score. Repeat this, calculating the score for each axis. (Thus, any 0 deltas force the count 0, automatically eliminating this axis, avoiding the degeneration of the triangle)
• Eliminate the axis with the lowest score to form a projection, for example. If the lowest score is on the x axis, project it onto the yz plane.

I did not have time for unit test this approach, but after preliminary tests it works pretty well. I would like to know if this is really the best approach?

Answer 5

To project the point p onto the plane defined by the vertices v0, v1 and v2, you must calculate the rotation matrix. We call the projected point pd

 e1 = v1-v0 e2 = v2-v0 r = normalise(e1) n = normalise(cross(e1,e2)) u = normalise(n X r) temp = p-v0 pd.x = dot(temp, r) pd.y = dot(temp, u) pd.z = dot(temp, n) 

Now pd can be projected onto a plane by setting pd.z = 0. Also pd.z is the distance between a point and a plane defined by three triangles. those. if the projected point lies inside the triangle, pd.z is the distance to the triangle.

Another remark given above is that after rotation and projection onto this plane, the vertex v0 lies at the origin, and v1 lies along the x axis.

NTN

Answer 6

I'm not sure if the offer is actually the best. It is not too difficult to project onto a plane containing a triangle. I am assuming here that p is indeed in this plane.

Let d1 = sqrt ((v1-v0). (V1-v0)) - that is, the distance v0-v1. Similarly, let d2 = sqrt ((v2-v0). (V2-v0))

v0 → (0,0)
v1 → (d1,0)

What about v2? Well, you know the distance v0-v2 = d2. All you need is angle v1-v0-v2. (v1-v0). (v2-v0) = d1 d2 cos (theta). Wlog you can take v2 as positive y.

Then apply a similar process to p, with one exception: you cannot consider it positive y. Instead, you can check if it has the same y sign as v2 by taking the sign (v1-v0) x (v2-v0). (V1-V0) x (p-y0).

---

As an alternative solution, you can use the linear algebra solver in the matrix equation for the tetrahedral case, taking v0 + (v1-v0) x (v2-v0) tetrahedron as the fourth vertex and normalizing if necessary.

Answer 7

You do not need to determine the optimal area to find a decent projection.

It’s not necessary to look for the “best” projection in general, it’s good enough, and it does not degenerate into a line when projecting in 2D.

EDIT - an algorithm removed due to a degenerate case, I did not think about