4
$\begingroup$

I'm trying to unfold a 3D mesh onto a 2D plane. My general idea to do this, would be to cycle through all the faces of the meshes and perform a hierarchical transformation.

So I would start at the first face and transform it's vertices to the plane, then go to the next face and transform the vertices, that were not already transformed (since the mesh consists of triangles, each face shares 2 vertices with the next triangle) with the transformation of the last face and then add another transformation to get it to the plane.

The problem is I don't really have an idea how to calculate the transformation matrices. Can someone help me? Thanks.

$\endgroup$
2
  • 3
    $\begingroup$ What you're doing is quite similar to UV unwrapping, for which there are a few good algorithms. If you search for that, you'll probably find some existing code that could be adapted to your use case. $\endgroup$
    – Dan Hulme
    Commented Apr 18, 2019 at 11:33
  • $\begingroup$ Do you want the geometry of the unfolding to be arbitrary? In many problems, one seeks a geometrically very well structured unfolding. Often the choice is a type of discrete conformal mapping (also called conformal parametrization, or conformal uniformization), a discrete version of the continuous analytic conformal parametrization (uniformization). There are several different way of defining it in the case of meshes (see for example discretization.de/media/filer_public/2015/11/16/a01-10-bss.pdf) $\endgroup$ Commented Apr 19, 2019 at 13:52

2 Answers 2

2
$\begingroup$

When performing the unfolding the way you want, after you have unfolded one triangle in the plane, the next one should be one of the three triangles, adjacent to the unfolded one, i.e. the next triangle to be unfolded shares a common edge with the unfolded one.

Assume you have a triangle $ABC$ in three space with vertices $$A = [A_1, A_2, A_3], \,\, B = [B_1, B_2, B_3],\,\, C = [C_1, C_2, C_3]$$ which is one of the triangles from the 3D mesh.

If $ABC$ is the first triangle you are starting the unfolding with, then:

  1. calculate $l_{AB} = ||A - B|| = \sqrt{(A_1 - B_1)^2 + (A_2 - B_2)^2 + (A_3 - B_3)^2}$;
  2. set the 2D vertices $a = [0,0]$ and $b = [l_{AB}, 0]$ as well as $$l_{ab} = l_{AB};

Else if $ABC$ is a next triangle to be unfolded in the plane, i.e. you have already unfolded one of $ABC$'s adjacent (neighboring) triangles, therefore one of $ABC$'s edges is already unfolded in the plane. Say that this edge is $AB$ and it is unfolded in the plane as the edge with vertices $a = [a_1, a_2]$ and $b = [b_1, b_2]$, where $l_{ab} = ||a-b|| = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2} = ||A-B|| = l_{AB}$.

Either way, for the triangle $ABC$ you already have the edge $AB$ unfolded as $ab$ in the plane, so that $l_{ab} = l_{AB}$ (i.e. you already know $a, \, b$ and $l_{ab}$). The question is, how do you find the coordinates of the third vertex $c = [c_1, c_2]$ so that $l_{bc} = l_{BC}$ and $l_{ca} = l_{CA}$? We impose the latter two conditions because two triangles that have pairwise equal edge-lengths are congruent (isometric, i.e. identical copies of each other).

For your information, I will write vectors like $B - A = [B_1 - A_1, \, B_2 - A_2, \, B_3 - A_3]$ and $C - A = [C_1 - A_1, \, C_2 - A_2, \, C_3 - A_3]$ and $b-a = [b_1 - a_1, b_2-a_2]$ and will use dot product $\cdot$ and cross product $\times$ between vectors. You already know what $||B-A|| = l_{AB}$ and $||C-A|| = l_{CA}$ are and that $l_{AB} = l_{ab} = \|b-a\|$.

  1. Calculate $$s = \frac{\|(B-A)\times(C-A)\|}{l_{ab}^2}$$

  2. Calculate $$c = \frac{(B-A)\cdot(C-A)}{l_{ab}^2}$$

  3. Calculate both pairs of coordinates \begin{align} &c'_1 = a_1 + c(b_1-a_1) - s(b_2 - a_2)\\ &c'_2 = a_2 + c(b_2-a_2) + s(b_1 - a_1) \end{align} and \begin{align} &c''_1 = a_1 + c(b_1-a_1) + s(b_2 - a_2)\\ &c''_2 = a_2 + c(b_2-a_2) - s(b_1 - a_1) \end{align}

  4. You have two candidate points $c' = [c'_1, c'_2]$ and $c'' = [c''_1, c''_2]$

  5. Perform a check whether $c'$ is on the same side of the edge $ab$ as the triangle unfolded right before $ABC$.

If it is not, then $c = c'$

else if it is, then $c = c''$

As a result of this procedure, you have constructed the planar unfolding $abc$ of triangle $ABC$ and the next triangle from the 3D mesh to be unfolded (if any), should be the one that shares either edge $BC$ or $CA$ with $ABC$. Either way, for that next triangle, you already know the unfolding $bc$ of the edge $BC$ and the unfolding $ca$ of $CA$ (whichever is relevant), so you can apply the same procedure for that next triangle. And so on and so forth, until you have unfolded all triangles from the mesh.

Have in mind that there are 3D meshes that do not posses unfolding that do not self overlap, no matter what you do. For such meshes there no greedy algorithms or any other algorithm that can do it.

$\endgroup$
7
  • $\begingroup$ Hi, thank you for your response. I'm not sure if I can follow your solution. For matrix m I don't know any of these points? $\endgroup$
    – Anima
    Commented Apr 20, 2019 at 5:43
  • $\begingroup$ @Anima I thought you had those. In your question you are asking about the transformation matrices. So do you need a method for calculating the coordinates of the vertices in the plane? $\endgroup$ Commented Apr 20, 2019 at 13:34
  • $\begingroup$ The coordinates on the plane, do not matter for me (it can be transformed to any position on the plane), I'd only need to do this transformation to the plane of the first triangle and then accordingly transform all other triangles too. I'm sorry if i was unclear :( $\endgroup$
    – Anima
    Commented Apr 20, 2019 at 14:19
  • $\begingroup$ @Anima Do you want each triangle from the 3D mesh to be transformed isometrically, i.e. the original triangle and the triangle in the plane to be congruent (to be identical copies of each other)? In this case the unfolding may self-intersect. Or is there any other geometric requirement? And what matrices are you asking about, because an infolding does not necessarily require matrices (angles or edge-lengths are enough), unless you want to transform points inside the triangles. $\endgroup$ Commented Apr 20, 2019 at 14:53
  • $\begingroup$ @Anima Are you trying to rotate the whole 3D mesh so that one triangle ends up on the plane, then rotate it again, for the next triangle to land on the plane and so on? Like rolling the 3D mesh on the plane? $\endgroup$ Commented Apr 20, 2019 at 15:03
0
$\begingroup$

Unfolding the mesh the way you describe it, most likely you will end up with overlapping triangles in the 2D plane unless your 3D geometry is simple. If that's ok, one laborious way is to compute the distances of the triangle sides and the angles and construct the triangle again in the 2D plane. For example, set:

a = (0,0)

b = (0,D1)

c = (D2*cos(phi), D2*sin(phi))

where

D1 is the distance between a and b in 3D,

D2 is the distance between a and c in 3D,

and phi is the angle at the a point.

Then using an affine transformation you can transform the triangle where you want.

UV unwrapping, which was mentioned, is the way to go only if its not important to keep the shapes of the 3D triangles intact.

$\endgroup$
1
  • $\begingroup$ Hi, thank you for your response! The overlaps will/should be removed by an greedy algorithm I plan to implement later, but for now I just want to unfold it to get a better feeling of what is happening (so no blind programming needs to be done). I understand how I get to the 2D - triangle with your solution, but I'm not sure how I can "stick" the triangle together again with affine transformation, since here I lose all information of the real place of the triangle, do I? $\endgroup$
    – Anima
    Commented Apr 20, 2019 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.