1

I have a triangle strip in 3D (see illustration). The triangles do not lie in one plane.

enter image description here

I would like to flatten the triangle strip so that all triangles lie in the plane of the first triangle.

The plan is to rotate the second triangle around its connecting edge with the first triangle so that it becomes in plane with the first triangle. Then I continue this method for the other triangles until all of them are in plane.

  1. I am looking for a fast algorithm to do that.
  2. Are there other methods to flatten the triangle strip?
user3384674
  • 759
  • 8
  • 28
  • I'm guessing this question is part of decomposing your prior interesting question on this subject (http://stackoverflow.com/questions/39691737/algorithm-to-calculate-the-shortest-path-between-two-points-on-the-surface-of-a). If so, I think it's a reasonable idea, but won't result in a shortest path. – danh Sep 30 '16 at 19:00
  • Also, before you solve this, you'll need find the right strip to flatten. That's not easy either. – danh Sep 30 '16 at 19:03
  • @danh Thanks for your comments. Yes, at the end I need the shortest path. I had a look at the different books, papers and stackoverflow discussions. It looks like this is not an easy task. However since I can reduce my problem from a complet mesh to a triangle strip with a few triangles (less than 20) I thought flattening the strip would be a solution. Or are ther better methods? – user3384674 Sep 30 '16 at 19:20
  • @danh You think it will not result in a shortest path? Why is that? – user3384674 Sep 30 '16 at 19:23
  • Yes, if you already know the shortest path strip, then the shortest 2D path with that strip flattened (then transformed back with the original rotations) seems like a reasonable idea for the shortest geodesic path. That could use a proof, too, but it seems very reasonable. – danh Sep 30 '16 at 22:12
  • In case you don't want to reinvent the wheel, the [CGAL](http://www.cgal.org) library provide a [geodesic shortest path](http://doc.cgal.org/latest/Surface_mesh_shortest_path/index.html#Chapter_Surface_mesh_shortest_path) package. – sloriot Oct 03 '16 at 05:33

4 Answers4

1

Keep in mind you are only going to be moving one point at a time. Since each triangle shares two points with the previous one, only the far point needs to move, and will move around the axis created by the other two points, until it lies on the desired plane. Repeat this process until done.

Neil N
  • 24,862
  • 16
  • 85
  • 145
1

If you just rotate every triangle, you have to rotate all the next triangles to keep geometry unchanged - this slow way with quadratic complexity.

Instead of this you can store mutual positions of triangle vertices and restore them in plane.

Possible way (I suppose that vertex numbering is sequential):

For N-th point C=P[N] calculate and store Len - length of it's projection to the line AB (A=P[N-2], B=P[N-1]) 

   Len = VectorLength(VectorProduct(UnitAB, AC))

enter image description here

and position of this projection at that line (as parameter t).

 t = DotProduct(AC, AB) / DotProduct(AB, AB)

To build C'=P'[N] in the plane, calculate 

C' = A' + t * A'B'  + Len * VectorProduct(UnitPlaneNormal, UnitA'B')
MBo
  • 77,366
  • 5
  • 53
  • 86
0

The fastest way doing this is 1) Compute the equation of the plane defined by the first triangle 2) Project all rest points onto this plane

Trifon
  • 1,081
  • 9
  • 19
  • Thanks your your answer. Could you please explain how you would do the projection? – user3384674 Sep 30 '16 at 18:58
  • 1
    I think the OP wishes to rotate, not project the mesh. If one of the triangles' planes is at a 90 degree angle to the first triangle, a projection will result in a line segment, not a triangle – danh Sep 30 '16 at 18:58
  • http://stackoverflow.com/questions/9605556/how-to-project-a-3d-point-to-a-3d-plane – Trifon Sep 30 '16 at 19:11
  • 1
    I think danh is right. The projection can give unwanted results. – user3384674 Sep 30 '16 at 19:24
0

I found this question having just implemented a 3D triangle-strip flattening algorithm myself in C++ for purposes unrelated to the original poster's goal of finding a shorted path. I basically took the route of rotating the second triangle around the common edge with the first, and repeating along the strip. However, due to the cumulative nature of the process, I have found that even with 20 or so triangles, errors in vertex positions pile up very quickly, giving noticeably different overall results when the vertex order is reversed.

I believe this is due to the mathematical complexities of working in 3D, so to answer the original question 2, I think a much better approach will just be to take the triangle side lengths and then rebuild the strip from scratch in 2D, where the maths is much simpler. It should then be easy enough to transform the whole thing back to restore the position and orientation of the first triangle if necessary, but I don't think the original poster needed this, and neither do I.

I am going to try this and will report back here.

EDIT: It didn't help. See my comment below.

Andrew Casson-du Mont
  • 1
  • 2
  • Tried it in 2D. Unfortunately it didn't make a lot of difference to the accumulation of errors, even with the complete avoidance of trig functions. Probably a lot quicker, but I don't care about that in my use case. – Andrew Casson-du Mont Dec 12 '22 at 09:53