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
  • 719
  • 6
  • 22
  • 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

3 Answers3

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,402
  • 16
  • 83
  • 143
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
  • 72,080
  • 5
  • 47
  • 77
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,031
  • 9
  • 18
  • 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