Range_lerp() to curve?

Erich_LErich_L Posts: 699Member
edited November 2021 in 3D

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.

Comments

  • Erich_LErich_L Posts: 699Member

    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.

  • xyzxyz Posts: 940Member
    edited November 2021

    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_LErich_L Posts: 699Member

    @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:

  • xyzxyz Posts: 940Member

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

  • xyzxyz Posts: 940Member

    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)

  • cyberealitycybereality Posts: 5,318Moderator

    That looks like it.

  • Erich_LErich_L Posts: 699Member
    edited November 2021

    @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_LErich_L Posts: 699Member
    edited November 2021

    @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_LErich_L Posts: 699Member

    @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.

  • xyzxyz Posts: 940Member
    edited November 2021

    @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_LErich_L Posts: 699Member

    @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
    
  • xyzxyz Posts: 940Member

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

  • Erich_LErich_L Posts: 699Member

    @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.

  • xyzxyz Posts: 940Member
    edited November 2021

    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...)

  • MegalomaniakMegalomaniak Posts: 4,803Admin

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

    Words to live by.

  • Erich_LErich_L Posts: 699Member
    edited November 2021



    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_LErich_L Posts: 699Member

    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.

  • xyzxyz Posts: 940Member
    edited December 2021

    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_LErich_L Posts: 699Member

    @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.

  • Erich_LErich_L Posts: 699Member


    Finally getting the results that I want. Thanks for the help.

  • Erich_LErich_L Posts: 699Member

    "Hey I know what I'll do, I'll make some cool terrain! I'm sure whatever game idea I have later will need procedural terrain!"
    Builds fruit factory game in space.

  • Erich_LErich_L Posts: 699Member

    Alright @xyz we are almost done, then it's nothing but fruit and cogs for miles and miles.


    But before that I figured I should give you a chance to look over your work lolol. Or anyone else, if there's any "obvious" things here that need fixing lemme know <3 <3

  • xyzxyz Posts: 940Member

    @Erich_L said:
    "Hey I know what I'll do, I'll make some cool terrain!"

    That's how the most gamedev horror stories begin.

  • MegalomaniakMegalomaniak Posts: 4,803Admin

    @xyz said:

    @Erich_L said:
    "Hey I know what I'll do, I'll make some cool terrain!"

    That's how the most gamedev horror stories begin.

    That's how they all start.

  • Erich_LErich_L Posts: 699Member

    MY PAPER GOT ACCEPTED BY A JOURNAL HAHAHA!!!

  • Erich_LErich_L Posts: 699Member
    edited May 18

    Results of my paper answer the question: can I take this team's amazing work which is slow and creates a terrain of fixed size and create a real time noise-like version? They used Orometry, so did I to place mountains.


    My mountains over 192 km compared to regular simplex noise.

    Is it possible? ya. Would I use it in a project? Not sure. Main personal discovery to share: 120 or so Vector3s is enough for 190 km of mountainous terrain as a sparse representation with interpolation. In the future I want to make asteroids as a sparse representation of a few feature points, then use interpolation to form the meshes when players near.

    The paper itself is all in Chinese. Yuck, had an English version but all the pictures weren't great.

Leave a Comment

BoldItalicStrikethroughOrdered listUnordered list
Emoji
Image
Align leftAlign centerAlign rightToggle HTML viewToggle full pageToggle lights
Drop image/file