Range_lerp() to curve?

Erich_L

I'm working on a noise function for terrain. It solves for height for any Vector2 two by interpolated to ridges in 3D space that I've precomputed using distance. The ridges are Bezier curves, but because finding the distance to them is too expensive, I sample from the curve for a few points for each ridge. I couldn't get over this last problem- so I straightened all the ridge curves which looks fine from the ground but awful from high up. The problem is my range_lerp() function causes fractures on the inside of ridge curves where in 2d space one ridge line transitions to be closer than the last for the interpolation. If I could iron them out my research results would actually be pretty decent, seeing as I'm doing this at 1/6th the speed of Simplex and getting non-uniform features. These fractures, or bumps, even form when I fix all ridge heights to be equal as shown above. My code for final height calculation:

func lerpFromRidgeLine(pos : Vector2, peak : MountainPeak): #pos being x,z position, peak holds ridge points & other info
	var p = getClosestPointOnRidgeLine(pos) #p a Vector3
	var dist = Vector2(p.x,p.z).distance_to(pos)
	return range_lerp(dist, 0, peak.baseRadius, p.y, 0)

After telling myself for half a year I could figure this out if I tried long enough, it's time to ask for help.

Erich_L

Here's a look at a terrain with my noise that I want to save (still has curved ridges) and a close up at one of the areas (inside of a curve) that has nasty fractures. It hasn't been altered with noise yet to keep it as easy to see as possible.

xyz

Instead of one closest point, get all closest points on the ridge (inside some sample radius) and do a weighted average of their heights. Or in simpler version, average just the two closest points.

Erich_L

@xyz said: Or in simpler version, average just the two closest points.

I was hoping big that this would work as it would be much cheaper. I tried averaging the two different heights from the two nearest lines as well as their distances, both to this effect:

xyz

I'd say it's an improvement :) How do you calculate sample distance from a line?

xyz

You could try a trick from distance field blending. If h1 and h2 are two sampled heights: height = Vector2(h1, h2).length()/sqrt(2.0)

Just for fun I played with it in processing for a bit, just heightfields generated from lines:

Two lines blended using larger of two heights height = max(h1, h2)

Blended with above function: height = Vector2(h1, h2).length()/sqrt(2.0)

cybereality

That looks like it.

Erich_L

@xyz said: I'd say it's an improvement :) How do you calculate sample distance from a line?

The ridges are made of a list of points ordered from one peak to anther. The first and last points are the same as peak points. For each terrain point x,z I loop through and find the closest one at index i, then use the dot product to see if the points[i + 1] or points[i - 1] should be used to form a line in 3d space. I know this function looks gross but it has always seemed to work fine for finding that point on the 3d line that's closest to my 2d input point. I had to fiddle with it to cast the line to 2d then back to 3d.

# A and B start and end points on a 3d line segment. P the 2d terrain point.
func closestPointOnLineSegment(P : Vector2, A : Vector3, B : Vector3) -> Vector3:
	var d = Vector2(A.x,A.z).distance_to(Vector2(B.x,B.z))
	var t = 0
	var AP = P - Vector2(A.x,A.z)
	var AB = Vector2(B.x,B.z) - Vector2(A.x,A.z)
	var magnitudeAB : float = AB.length_squared()
	
	var ABAPproduct : float = AP.dot(AB)
	var distance : float = ABAPproduct / magnitudeAB
	if distance < 0:
		t = 0.0
	elif distance > 1.0:
		t = 1.0
	else:
		var p = Vector2(A.x,A.z) + AB * distance
		t = p.distance_to(Vector2(A.x,A.z)) / d
	var AB3d = B - A
	return A + (t * AB3d);

Erich_L

@xyz said: "Two lines blended using larger of two heights height = max(h1, h2) "

I had to try this first and it helps me understand my problem a bit. If the ridge points are far enough apart this works, otherwise this just pushes the problem around if a higher point could have overlapped a point three points down the ridge.

Erich_L

@xyz For a short term solution I reduced ridge point count where two ridge points get closer than an arbitrary amount. When you are available for worship lemme know.

xyz

@Erich_L You could make a small paradigm shift towards distance fields, as I did in the example :) Each line segment can be seen as a generator of a distance field. The strength of the field varies with elevation. Blend the fields together using the mentioned function and interpret them as heightmap values. Additional neat thing is that distance gradients can be modified using easing functions to get various slope profiles.

I'm available year round ;)

Erich_L

@xyz said: Instead of one closest point, get all closest points on the ridge (inside some sample radius) and do a weighted average of their heights.

I wanted to try your suggestion of doing a weighted average of their heights. This result might be good for... uhh... a specific sort of terrain? I guess? But I don't think I understand the math because the weights from each point won't add up to one. Here's me looping through the ridge point line segments.

	size -= 1
	for i in range(size):
		var point1 = curvePoints[i]
		var point2 = curvePoints[i + 1]
		var cp = closestPointOnLineSegment(pos,point1,point2)
		var dist = Vector2(cp.x,cp.z).distance_to(pos)
		var weight = clamp(dist / peak.baseRadius, 0.0,1.0)
		weights += weight
		dist *= weight
		total += range_lerp(dist, 0, peak.baseRadius, cp.y,0)
	if weights < 1.0:
		return total # added this to prevent random skyscrapers
	else:
		return total / weights

xyz

I think weighted average is not a very good idea. Have you tried the distance field blending thingy?

Erich_L

@xyz said: I think weighted average is not a very good idea. Have you tried the distance field blending thingy?

I'm scared of it because I don't just have two heights I can put into a Vec2. I have up to 9. It does look cool tho.

xyz

Try to add them up one by one, exclude ones that are out of range. You may need to do some normalization at the end.

EDIT: In fact just take the magnitude of a N dimensional vector and normalize the result height = sqrt(h1*h1+h2*h2+h3*h3+h4*h4...)

Megalomaniak

@xyz said: You ~~may~~ need to do some normalization at the end.

Words to live by.

Erich_L

Oh dear lord look at the difference. What also completely blew me away- I did all the normalization right and did what I was avoiding: performing interpolation from all lines. I thought this would slow things down too much but with that function it's just added multiplication then a square root which got rid of a bunch of if height comparisons. So... the algorithm actually ended up running faster! What I learned: avoid if statements and use math and built in functions more when possible :o

Edit: Ok six hours later the high wore off, the normalization step is making some peaks about 100 meters or so higher than where they're supposed to be. Switched from sqrt(addUp) to pow(addUp, 0.484). So much fun!

Erich_L

My mountains are still being classified wrong, but at least they’re no longer being classified as deserts! Hahaha.

I realized I’ve been ignoring a feature of mountainous regions that I’m sure is impacting my results: the minimum elevation of a mountainous region. I want to throw this into my height function by means of another range_lerp() function. I can put a point in the middle of the generated range with height = range min elevation. Then I can lerp a height to add to the terrain ranging from min elevation to zero. This will look like a big cone. So I wanted to ask if there’s a way to get this: a more of a bell shape to this. This way more of the range will get that minimum height data.

xyz

I already hinted on this - to change the shape of the slope, use easing functions on linear interpolation result.

Your mountains still look kind of weird. Seems like slopes are not entirely linear. Perhaps post a few more representative screenshots. I'm actually curious to see how this blending looks when extruded into 3d.

Btw that sqrt still needs to be divided by sqrt(n), where n is the number of height values.

Erich_L

@xyz said: I already hinted on this - to change the shape of the slope, use easing functions on linear interpolation result.

Your mountains still look kind of weird. Seems like slopes are not entirely linear. Perhaps post a few more representative screenshots. I'm actually curious to see how this blending looks when extruded into 3d.

Btw that sqrt still needs to be divided by sqrt(n), where n is the number of height values.

I see I'll give an easing function a try. That picture (improved part) I was only using that normalization func on the result heights from peaks, not the height that came from the ridge points for each peak. I ended up doing normalization on both and my peaks are getting very close to their intended height and I am really happy with the result. To test I divided those results by sqrt(n) and it completely squashed my peaks to about 7% of intended height. I think the reason might be that a lot of ridge point interpolation returned near zero values.

It's hard to see my lines through the sky but the peaks are almost right on target.