1
$\begingroup$

I am analyzing the article Parameterization of triangular meshes (Michael S. Floater November 10, 2009) and have reached the point where the uniqueness of the solution to a system of linear equations.

We now describe a general method for constructing a parameterization of triangular mesh in $R^3$. We denote by $S$ the set of triangles in the mesh and $V$ its vertices and $E$ its edges. We let $Ω_S ⊂ R^3$ be the union of the triangles in $S$. Then we define a parameterization of $S$ as a continuous piecewise linear mapping $ψ : Ω_S → R^2$. Then $ψ$ maps each vertex, edge, and triangle of $S$ to a corresponding vertex, edge, and triangle in $R^2$. Such a mapping is completely determined by the points $ψ(v), v ∈ V$. Let $V_I$ denote the interior vertices of $S$ and $V_B$ the boundary ones. The boundary vertices of $S$ form a polygon $∂S$ in $R^3$ which we call the boundary polygon of $S$. Two distinct vertices $v$ and $w$ in $S$ are neighbours if they are the end points of some edge in $S$. For each $v ∈ V$ , let $$N_v = {w ∈ V : [w, v] ∈ E},$$ the set of neighbours of $v$, where $E = E(S)$ is the set of edges in $S$. The first step of the method is to choose any points $ψ(v) ∈ R^2$, for $v ∈ V_B$, such that the boundary polygon $∂S$ of $S$ is mapped into a simple polygon $ψ(∂S)$ in the plane. In the second step, for $v ∈ V_I$ , we choose a set of strictly positive values $λ_{vw}$, for $w ∈ N_v$, such that $$ \sum_{w∈N_v}λ_{vw} = 1. (3)$$ Then we let the points $ψ(v)$ in $R^2$, for $v ∈ V_I$ , be the unique solutions of the linear system of equations $$ ψ(v) = \sum_{w∈N_v}λ_{vw}ψ(w), v ∈ V_I . (4)$$ Since these equations force each point ψ(v) to be a convex combination of its neighbouring points $ψ(w)$, we call $ψ$ a convex combination mapping. Let us take a closer look at the linear system. We must show that it has a unique solution. To this end, note that it can be rewritten in the form $$ψ(v) − \sum_{w∈N_v∩V_I}λ_{vw}ψ(w) = \sum_{w∈N_v∩V_B}λ_{vw}ψ(w), v ∈ VI . (5)$$ This can be written as the matrix equation $$Ax = b,$$ where $x = (ψ(w))_{w∈V_I}$ is the column vector of unknowns in some arbitrary ordering, $b$ is the column vector whose elements are the right hand sides of (5), and the matrix $A = (a_{vw})_{v,w∈V_I}$ has dimension $n × n$, with $n = |V_I|$, and elements \begin{equation} a_{vw} = \begin{cases} 1, w = v,\\ −λ_{vw}, w ∈ Nv,\\ 0, otherwise \end{cases}\,. \end{equation}

I don't understand where the $a_{vw}$ values come from. How can this be calculated, please tell me?

$\endgroup$
4
  • $\begingroup$ They have written the definition of $a_{vw}$ they have not written the definition of $\lambda_{vw}$ though, at least in the excerpt you posted, i.e. "we choose a set of strictly positive values $\lambda_{vw}$". $\endgroup$
    – lightxbulb
    Commented Jan 4 at 7:39
  • $\begingroup$ @lightxbulb And another condition is that their sum must be equal to 1 $\endgroup$
    – e7min
    Commented Jan 9 at 6:52
  • $\begingroup$ @lightxbulb My question was rather how to get these 3 cases: 1, $- \lambda_{vw}$ and 0? $\endgroup$
    – e7min
    Commented Jan 9 at 6:55
  • $\begingroup$ It's just equation 5 rewritten in matrix-vector form: $\psi(v)- \sum_{w \in N_v\cap V_I} \lambda_{vw}\psi(w) = \sum_{w \in N_v \cap V_B} \lambda_{vw}\psi(w)$, now with the definition for $a_{vw}$ and $x= (\psi(w))_{w\in V_I}$ you may rewrite this as $\sum_{w} a_{vw} x_w = b_v$, and since you have $|V_I|$ such equations you can write it as $Ax = b$. $\endgroup$
    – lightxbulb
    Commented Jan 9 at 9:28

0

Your Answer

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

Browse other questions tagged or ask your own question.