Algorithm to flatten a 3D triangle strip

1
votes

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?
3
algorithmgraphics3dgeometrycomputational-geometry
I'm guessing this question is part of decomposing your prior interesting question on this subject (stackoverflow.com/questions/39691737/…). If so, I think it's a reasonable idea, but won't result in a shortest path. – danh
Also, before you solve this, you'll need find the right strip to flatten. That's not easy either. – danh
@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
@danh You think it will not result in a shortest path? Why is that? – user3384674
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

3 Answers

1
votes

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')
1
votes

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.

0
votes

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