Heat Method (Crane et Al) How do we pick u?

Question

The heat method is a very interesting paper for distance computation:

https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/paperCACM.pdf

The idea behind the paper is that, heat travels along the surface of an object essentially in a geodesic like fashion. And so the time it takes for heat to travel from a hot spot to any point on a surface is irreconcilably correlated with the geodesic distance.

The paper first considers the general, analytic case and then suggests discretization approaches. What I am very confused about is the mention of the heat flow function $u$ across the paper. Consider this equation for example:

That is the discrete laplacian operator applied to $u$ or $\Delta u$. There are multiple other sections in the paper that mention $u$. From my reading, $u$ seems to be a suitable function that approximates heat flow on the surface of a manifold?

I don't really see an equation of the form $u = \text{expression}$ nor do I see descriptions of its properties nor suggestions for a good $u$ function. What is $u$? Where did $u$ come from? Where did $u$ go? Where did $u$ come from? cotan, i, o?

Answer 1

From my reading, u seems to be a suitable function that approximates heat flow on the surface of a manifold?

$u$ is the function that describes how your quantity behaves/evolves in a certain field. In the paper, the quantity is the temperature or heat flux, I guess. However, most of the time there is no analytical solution/formula for $u$. This is where methods like Finite Elements (FEM) come into play. By discretizing your field, you can piecewise approximate your function $u$.

In your case, you would use your mesh, which is already a discretization of your surface. Your elements are the triangles and you need to define how the nodal quantities are interpolated inside each triangle. --- Here, linear interpolation is probably the way to go. Otherwise, you need to remesh your geometry or introduce additional nodes for higher-order approximations.

Then you have to assign to each Node/Vertex an initial value $u_0$ as written in the answer of gilgamec. Afterwards, you build and solve your finite element system and get the nodal distribution of $u$ that actually solves your equation or system of equations. The finer your mesh gets, the better the solution. Higher-order interpolations will also help with accuracy.

So $u$ or its nodal values are what you are actually looking for as lightxbulb said in his comment. It's your unknown quantity.

If this doesn't help, you might want to read some literature about the finite element method. Can't tell how helpful the following links are, but a short glimpse looked promising. You will see, that they use $u$ all over the place. So I hope one of them will help you:

• A gentle introduction to the Finite Element Method
• PE281 Finite Element Method Course Notes
• Introduction to the finite element method
• finite element analysis by hand

I also had a link to a good online tutorial similar to the last link I provided that helped me a lot in understanding the fundamentals. If I find the link, I ll add it to my answer.

---

Found the link I was referring to. Unfortunately, it is in german:

• FEM Handrechnung

Answer 2

Yes, the field $u$ is in this case an approximated heat diffusion across the surface. It's found by starting with the "initial set" of vertices; these will be the source of the diffusion, and end up as local minima in the distance field. An initial distribution $u_0$ is set up, with value 1 on the initial set and 0 everywhere else. (This is described on page 92 of the paper you linked, immediately under Algorithm 1.)

The first step of the algorithm is to run a single step of the heat equation by solving the linear equation $(I - t\nabla)u = u_0$ (equation 3 in the paper). The field $u$ you get there is the approximated heat diffusion that you further process to get the distance field.