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

Question

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?

Answer 1

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.

1. Directed, gradient-based 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.

Repeat the computation of the gradient at the new positions and repeat the movement along the new gradient direction. (See also gradient descent.)

This is suitable of you are already close to the desired solution and want to refine it. The movement of vertices from/to close-by regions to neighboring regions needing them should be included here.

2. Randomized, Monte-Carlo approach

Method 1 only performs a local optimization. However, for a global optimization random changes in the vertices might be more suitable. For every iteration, induce more drastic, random changes. For example, one could completely re-distribute 10% of the vertices to other random positions.

The trick is: only accept these changes if they improve the FOM, do accept them only with a very small probability if they make the FOM worse. (Typically one uses Exponential(-Constant * FOM-change) as acceptance probability (here FOM should be minimized)).

Then repeat this for a long time keep track of the best intermediate result (configuration with the best FOM). In the end, choose it. (See also Monte Carlo methods.)

If you want you could combine both, for example apply method 1 on the result of method 2.