So I am doing a gradient descent like algorithm on the surface of a mesh and I just noticed something:

enter image description here

The above is the geodesic gradient (the distance to a single vertex)

Look at where the ear connects with the head and notice how the discretized gradient behaves. It's almost pointing in opposite directions. This is not however an error, this occurs because the gradient at that region is fairly "turbulent".

My algorithm is fairly simple, grab a point in a triangle, compute its negative gradient, intersect the gradient with the triangle, move there, switch active triangle to the neighbour, repeat.

In other words you just follow the gradient down towards the source.

However, when I hit those turbulent regions, my algorithm gets stuck, because the gradient becomes essentially 0 and numerical errors prevent it from intersecting any of the edges of the triangle.

In pictures:

enter image description here

The green points are the path taken by my gradient descent algorithm. The cyan ones are the centres of the faces of the triangles and the yellow arrow is the gradient at the last point.

Notice that this result is correct.

However, at the ears:

enter image description here

As you can see the algorithm stops because the gradient is borderline 0.

And worse there are regions in the ears where the turbulence makes the gradient bounce and start travelling in the opposite direction.

Does anyone have tips on how I could handle the gradient in these regions?

  • 1
    $\begingroup$ You might wanna look into "Optimization on a manifold" which is literally the continuous analogous of what you're doing. Based on the manifold you work out "gradient","retraction" and "hessian", the use of the latter allows you to implement second order scheme which should behave better in theory. Discretizing these will give you the analogous on a mesh. $\endgroup$ – user8469759 Sep 10 '20 at 3:33

Maybe you can find a heuristic to detect when it gets stuck (e.g. gradient magnitude is too small, or it stays on the same triangle or returns to a recently visited triangle too many times in a row, or it hasn't moved at least X distance over the last N steps, etc) and just take a random step in some direction, e.g. to some randomly chosen neighboring triangle? That might help shake it out of the difficult region and get back to smooth descent.

For an even lower-tech solution, if you don't mind some randomness you could just inject occasional random moves all the time (without attempting to detect whether it's stuck). Kind of like stochastic gradient descent in ML.

If the gradient you're following is a geodesic distance, I think it can have saddle points, but not local minima (except for the global minimum), is that right? If that's a constraint you can rely on, you could try to use a second-order method, finding an estimate of the local Hessian and looking for eigenvectors with negative eigenvalues, which should be directions of principal curvature that will accelerate the gradient descent, and in particular, will pull you out of saddle points. I'm sure there must be a literature on such methods although I don't know much about it.

  • $\begingroup$ I am just getting into the topic of computational geometry so excuse my ignorance. When you say looking for negative eigenvectors, I assume you mean negative eigenvectors of the hessian, which must mean the hessian is a matrix. Is that correct? $\endgroup$ – Makogan Sep 9 '20 at 20:32
  • $\begingroup$ Yes (or in general, a linear operator). It contains all the second derivatives of the function along the mesh, just as the gradient contains the first derivatives. By finding the eigenvectors of the Hessian you get the principal curvature directions (of the graph of the function - not the curvatures of the mesh surface), and if one of those has negative curvature, that's the way out of the saddle point. $\endgroup$ – Nathan Reed Sep 9 '20 at 21:22

Your Answer

