Gradient descent (Not ML) on arbitrary meshes

Question

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

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:

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:

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?

Answer 1

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.