# Is there an algorithm to move vertices along a planar mesh to give an area more vertex without destroying the shape too much?

Currently, I am playing around with a terrain technique called Vector-Field terrain as created and used for the game Halo Wars. I have successfully recreated the technique. However, I'm having difficulty with trying to figure out how to adjust the vertex density for the overhangs in the terrain.

Vector-Field Terrains still suffer similar problems to height map terrains. Where any time there is a vertex with a vertical scalar that is too different from it's neighbor will have UV stretching.

The way that Vector-Field terrains eliminates this, is that you can pull surrounding vertexes to give the area more resolution by giving it more density without changing the topology.

I can not for the life of me come up with a way to do this in a none destructive manner and in an automated way. I'd like to be able to keep the final shape as close as possible to the source. And only pull in as many vertexes as needed to correct this.

Does anyone know of any algorithms to solve this problem?

• Would 'repeatedly nudging all vertexes towards the center of the adjacent vertices' destroy your shape too much? Maybe not with a high enough overall desity?
– Tau
Mar 26, 2018 at 16:39

Some kind of optimization algorithm should do the trick.

I assume that this is not a time critical task, rather done during development or initialization, not during game play. Furthermore, that you know if a given distribution of vertices keeps the final shape close to the source.

Ideally, you will have a function that assigns a number to each configuration of vertices and estimates how close the final shape is to the source. Let's call this function figure of merit (FOM). You want to optimize the FOM with a side-condition that the number of vertices stays constant.

I can imagine two methods, a directed, gradient-based approach and a randomized, Monte-Carlo approach.

The position coordinates of each vertex of the Vector-Field terrain are the parameters. Try to compute the derivatives of the FOM with respect to these parameters. One can approximate the derivative numerically by changing the positions only slightly and computing corresponding differences in the FOM (finite differences).

Then move a bit along this gradient direction (i.e. apply gradient times a suitable stepsize to update the positions). Choose the step size so, so that the FOM is best. Some vertices might get very close, meaning that they can be substituted by a fewer number of vertices.