3
$\begingroup$

This question is regarding a homework assignment (want to be upfront because many people on stack exchange don't like helping with homework questions).

I have a triangular mesh, which is defined by a set of vertices and a set of faces. I want to calculate the discrete gradient of the mesh, and I even got instructions on how to implement it. The problem is that even after reading them multiple times, I don't understand them...

The implementation instructions:

enter image description here

My Problem:

I don't understand how to implement the marked sum, which in turn prevents me from constructing the following E matrix.

I would appreciate any help. I'm not looking for specific code examples, rather an explanation/example of the calculation for a single triangle.

$\endgroup$
1
$\begingroup$

A function $f$ on your triangulated surface is an assignment of real numbers on the vertices of the triangulation and therefore $f \in \mathbb{R}^{|\mathcal{V}|}$. According to the continuous theory, the gradient should be a linear (differential) operator that takes a function and spits out a vector field. Hence, in the discrete theory, the gradient should be a linear operator that takes a function $f \in \mathbb{R}^{|\mathcal{V}|}$ and spit out some kind of a discrete version of a vector field. In your case, the vector field is given as an assignment of a vector to each triangle of the triangulation. That is why the discrete gradient operator should be a linear operator, i.e. a linear transformation $$\text{grad} : \mathbb{R}^{\mathcal{|V|}} \to \mathbb{R}^{3|\mathcal{F}|}$$
which is represented by a matrix $\text{grad} \in \mathbb{R}^{3|\mathcal{F}| \times |\mathcal{V}|}$. In the continuous theory, the gradient is determined only by local data, i.e. the behaviou of the function near the point at which the gradient is being calculated and by the geometry near that point. Therefore, in the discrete theory, the gradient is determined only by the geometry of one triangle and the values of the function at the triangle's vertices. Let the triangle $j \in \mathcal{F}$ have vertices denoted (according to the instructions' convention) by $1, 2, 3$. The labels are set up so that the vertices $1,2,3$ define the labels of the opposing edges $\vec{e}_{j_1}, \vec{e}_{j_2}, \vec{e}_{j_3}$, i.e. for the vertex $i$ the edge opposite to the vertex $i$ is denoted by $\vec{e}_{j_i}$, where the latter vector is oriented so that the vectors form a closed chain of vectors summing to zero in a counterclockwise direction.
Hence, the gradient can be defined as $$(\text{grad}\,f)(j) = \frac{1}{2\text{Area}(j)}\, \sum_{i=1}^{3} f_i\, J\vec{e}_{j_i}$$ Or to write it in coordinates, $$\begin{bmatrix} (\text{grad}\,f)(j)_1\\ (\text{grad}\,f)(j)_2\\(\text{grad}\,f)(j)_3\end{bmatrix} = \frac{1}{2\text{Area}(j)}\left( f_1\, \begin{bmatrix} (Je_{j_1})_1\\ (Je_{j_1})_2\\(Je_{j_1})_3\end{bmatrix} + f_2\, \begin{bmatrix} (Je_{j_2})_1\\ (Je_{j_2})_2\\(Je_{j_2})_3\end{bmatrix} + f_3\, \begin{bmatrix} (Je_{j_3})_1\\ (Je_{j_3})_2\\(Je_{j_3})_3\end{bmatrix}\right)$$ and in matrix form $$\begin{bmatrix} (\text{grad}\,f)(j)_1\\ (\text{grad}\,f)(j)_2\\(\text{grad}\,f)(j)_3\end{bmatrix} = \frac{1}{2\text{Area}(j)}\, \begin{bmatrix} (Je_{j_1})_1 & (Je_{j_2})_1 & (Je_{j_3})_1 \\ (Je_{j_1})_2 & (Je_{j_2})_2 & (Je_{j_3})_2\\(Je_{j_1})_3 & (Je_{j_2})_3 & (Je_{j_3})_3 \end{bmatrix} \begin{bmatrix} f_1\\ f_2\\f_3\end{bmatrix} $$ So, for the matrix $E \in \mathbb{R}^{3|\mathcal{F}|\times|\mathcal{V}|}$ is defined as follows. Let $j$ be a triangle and $i$ one of its vertices. Take the edge $e_{j_i}$ of triangle $j$ opposite to the vertex $i$, and consider the vector $\vec{e}_{j_i}$ along the edge, starting from one vertex, different from $i$, to the other vertex, different from $i$, oriented so that the the vector follows counterclockwise orientation of the boundary of the triangle $j$. Then rotate the vector $\vec{e}_{j_i}$ by $90^{\circ}$ so that it points inside the triangle $j$. Denote this rotated vector by $$J\vec{e}_{j_i} = \begin{bmatrix} (Je_{j_i})_1\\ (Je_{j_i})_2\\(Je_{j_i})_3\end{bmatrix}$$ Then fill up the following entries of the matrix $E \in \mathbb{R}^{3|\mathcal{F}|\times|\mathcal{V}|}$:
\begin{align} &E(j,i) = (Je_{j_i})_1\\ &E(j + |\mathcal{F}|, i) = (Je_{j_i})_2\\ &E(j + 2|\mathcal{F}|, i) = (Je_{j_i})_3 \end{align}
You can rotate the vector $\vec{e}_{j_i}$ by using the cross-product operation twice. Take two of the edge-vectors of the triangle $j$, say $\vec{e}_{j_1}$ and $\vec{e}_{j_2}$, and calculate the unit normal vector to the triangle $j$: $$\vec{n}_j = \frac{1}{\|\vec{e}_{j_1} \times \vec{e}_{j_2}\|}\,\Big(\vec{e}_{j_1} \times \vec{e}_{j_2}\Big)$$ It doesn't matter whcih two out of the three edge-vector you would choose, the result is always the same unit normal $\vec{n}_j$. Then $$J\vec{e}_{j_i} = \vec{n}_j \times \vec{e}_{j_i}$$

$\endgroup$
  • $\begingroup$ Thank you very much for the time you took to write this explanation. $\endgroup$ – Mark.F May 16 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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