Derivatives

In today's blog post we test out an idea I had around using the second derivateive of a curve (or a 2d image, like a heightmap) to approximate a curve

What is a derivative

A derivative of a curve generates a new curve a new curve where the y axis shows therate of change (slope) or the original for the same x value.

When the curve is perfectly horizontal, the derivative at that x value is 0. When the curve is steep, the derivative is high (or low if sloping down left-to-right)

You can calculate a second derivative, by performing the same function on the first derivative.

Here, to get the derivative I'm comparing the y values for two neighbouring x values (and then scaling the result).

In the demo below you can see

• The input curve in red - just a random curve, click to randomize
• The first derivative, in green
• The second derivative, in blue

You can see that the second derivative (blue) crosses the line y=0 when the original curve (red) is the straightest, and it has high/low values when the red curve's angle is changing dramatically

Approximating the curve

Hypothesis 1: We can approxomate the curve by selecting random x values from the second derivative that have high or low y values, as it indicates changes in the original curve

Here we are

• chosing a few (3) random points at a time
• picking the x value with the highest (absolute) y value (indicated by vertical dotted lines)
• joining up those points (where the y value is sampled from the original curve)

This works for the most part. Sometimes the random samples aren't near the high/low points on the second derivative, and sometimes the selected x values are quite crowded. In general, this still beats picking consecuttive points in a straight line.

Derivatives in 2D

So we can apply the same logic in 2D. Here we're applying it to a grayscale image.

Again, to calculate the derivative we're comparing neighbouring values ( abs(current - left) + abs(current - above) )/2. This is similar to the "find edges" algorithm. We end up with white values when the colour changes the most.

The second derivative again is the same function but applied to the first derivative. For sharp transitions, this results in a white line either side of the transition. Gradual "curving" gradients in the original image result in a few lines, or some middle-ground grey values.

Approximating an image using triangles

Hypothesis 2: In 2D we can use the second derivative to work out the best points to use to approximate a 2d greyscale image.

Like the 1D example, we're picking points at random. I won't go into detail here, but we're breaking the image into a grid, then performing a few random samples per square. Just like the 1D example, we're picking the best of 3, plus we've also got a threshold so if the second derivative is too low (black) then we don't place a point at all.

We're going to gloss over it, but this (almost) uses delaunay triangulation. All of the selected points are joined by triangles, and those triangles are filled by the colour of the original image (sampled from the average of the points of each triangl1)

Usages in heightmaps

The plan was that this could be used in heightmaps, rather than a grid of vertices. We'll have to see if I dig this up for a future game project 😉