Update LaneSegments for multi-lane highly curvy roads

[TheDuckCow]

Right now lane segments added to very curvy roads with many lanes don't really stay in their lanes well enough. This was a known limitation of how we are creating lane segments, since we are creating new curve objects. We'l need to do some manual testing and perhaps some research to determine if there's a deterministic way to ensure an "offset" curve with constrained start/end points and the same number of overall points (2) can be reliably created to follow our road mesh generation.

Ok curves right now:

Problem curves (see how the sawtooth geo is not staying in the center of the lane, which would be very chaotic for AI traffic to try and follow!):

The intuition is that we'd need to calculate per curve point whether that lane's magnitude needs to be increased or decreased. Best to try this first with a few test examples in godot by hand (this addon I made may come in hand).

[TheDuckCow]

Doing some light research on this, it seems that the approximation listed here for offsetting cubic bezier should largely be what we need. While it's not going to create perfect parallel curves (impossible for general cubic Bezier whilst keeping the same number of control points), our roads should be pretty much safe as any such extreme angles that would break the approximation would also be breaking the mesh of the road itself, too.

Only thing that might still be tricky: making sure it works well with lane transitions.

[TheDuckCow]

Suggesting this as the spot where we will create some kind of utility to assist with offsetting:

@@ -292,17 +292,22 @@ func generate_lane_segments(_debug: bool = false) -> bool:
        if ln_dir != RoadPoint.LaneDir.REVERSE:
            new_ln.reverse_direction = true

+       # Call some utility here to do the offset cubic bezier functions
+       # to get the pos/in/out for each point of the curve,
+       # then below actually create these curve
+       offset_cubic_bezier(source, target, offset_amount)
+
        # TODO(#46): Swtich to re-sampling and adding more points following the
        # curve along from the parent path generator, including its use of ease
        # in and out at the edges.
        new_ln.curve.add_point(
            new_ln.to_local(in_pos),
-           curve.get_point_in(0),
-           curve.get_point_out(0))
+           curve.get_point_in(0), # needs to be re-sampled
+           curve.get_point_out(0)) # needs to be re-sampled
        new_ln.curve.add_point(
            new_ln.to_local(out_pos),
-           curve.get_point_in(1),
-           curve.get_point_out(1))
+           curve.get_point_in(1), # needs to be re-sampled
+           curve.get_point_out(1)) # needs to be re-sampled

[TheDuckCow]

Some discussion we've had on calculating the right angle

[bdog2112]

Here's the gist of how the "curve offset" calculation will work:

1. Calculate angles p and r, which equal angles q and s
2. Calculate the offsets from points i to f and j to g in the first diagram and from i to b and j to c in the second diagram (using sohcahtoa)
3. Project points a and b to e and i and d and c to h and j
4. Add the offsets to points i and j to find points f and g in the first diagram
5. Subtract the offsets from points b and c to find points i and j in the second diagram (see diagrams below)

Godot's "angle_to" function can be used to get the angles. But, it only works for the rainbow-shaped-curve scenario depicted in the first diagram. If the rainbow is inverted, then the calculated curves look wrong.

One consideration is the need to subtract offsets in the inverted-rainbow scenario versus adding them in the regular rainbow scenario. Determined that Godot's "signed_angle_to" function automatically sets the offsets to positive or negative as needed. Hence, we'll use that.

After some other minor +/- tweaks to certain values in the code, the logic seamlessly handles regular and inverted rainbows as well as an S-curve!

(TTD: Project secondary handles on to primary handles' planes to compensate for changes in elevation.)

Epilogue: When creating the drawings, the intent was to make the middle of the curves the same width as the ends of the curves. But, in doing so, the "actual" curve handles did not match the "depicted" handles. Actual handles were slightly longer. Lesson being that the expected outcome was theoretical and we would not always get the expected result. But, the results were still much better than doing nothing!

[bdog2112]

Hey @TheDuckCow, here is a WIP of the curve offset algorithm.

Check out the "Demo" scene. It contains two curves and two spatials representing RoadPoints. Press "7" on the numeric keypad to switch to top down view for best viewing results.

Select the "Spatial" object in the outliner to expose 2 export variables: 1 Lane Width, 2 Invert Rainbow. Experiment with different lane widths and positive/negative values and toggle Invert Rainbow to see how it looks. Changing these values will reset the scene.

Treat "RP1" and "RP2" as RoadPoints. Select, rotate, and move them. Be aware that there is such a thing as placing them TOO CLOSE together. Try it, observe, and decide what you think about the results.

"Path1" can be used to adjust the length of the primary curve handles. (There is no need to adjust Path2 as it is supposed to be calculated.)

Remember to select "RP1" or "RP2" if you wish to rotate/move the start or end points on the primary curve.

Also, I'm looking into an issue where the secondary curve curls in a funny way under certain conditions. This happens when RP1 is rotated too far clockwise or RP2 is rotated too far counter-clockwise.

[TheDuckCow]

Thanks for the updates @bdog2112, just tried out the demo project. Definitely a big improvement over any prior methods we had going on. I tried it with various rotations and different height levels, seems to handle gracefully enough. Large angles where the rp's create pinching do look off, but we knew those would not work well with this algorithm approx anyways, so no concerns there.

I realize there are some edge cases and maybe some improvements to consider, but I would really love to get even the current state into the road generator directly for the lane function, since we've been focussed on this one topic for over a month at this stage. Let's see how the improvement holds up there.

How much time before you think you can have a PR ready?

[bdog2112]

It's a work in progress. But, roads are looking pretty good. Here are some before/after screenshots highlighting the improved lane accuracy. (see below) It's still possible to get bad results if you make a RoadSegment really twisty. But, results look great on our select road curves!

In Progress: Making lane transitions work...

"Before" algorithm update

"After" algorithm update

[TheDuckCow]

Nice, love to see it @bdog2112! Indeed will still have some edge cases, but this will definitely hold us over for our needs for now. Excited to see the code integration.

For lane transitions, open for whatever solution you come up with - feel free to go for something simple. I'm thinking: on each end of the curve, almost forget about it being a transition and just treat the curve handle as though it were to stay the same number of lanes to the other end (so if it's a 2x2 going into a 2x4, the 2x2 side is just calculating offsets as though both sides are 2x2, and then the handle on the 2x4 side assumes as if 2x4 on both sides). If that really doesn't work then just let me know and we can evaluate how badly we want to try and fix multi lane changes in very curvy roads, I also see that as an edge case, and frankly, bad high way engineering practice anyways :)

[bdog2112]

Curve Offset logic is working pretty well. Ran it in the WS Project and it plotted a 6-lane road flawlessly in game.

At the moment, no changes have been made in order to facilitate or prevent transition RoadLanes. However, they are plotted correctly in the IDE using the new logic. (See screenshot below.)

Unfortunately, when the "+Next RoadPoint" button is used, the IDE freezes. It also seems to freeze when the "+Prior RoadPoint" button is used. Hence, troubleshooting is in progress.

Transition RoadLanes appear precisely as one would expect

[TheDuckCow]

Thanks for the update - on IDE freezes, could you create a WIP PR that has your progress so far (totally fine if you're planning to clean things up more later)? I could potentially help troubleshoot on that. Image above looks great though, glad to see that working well

[TheDuckCow]

Trying out the branch, I don't get much of a lag - but I do get some oddly placed road lanes (and possibly duplicate roadlanes, but might just be double backing on themselves). Did you get the big lag while also having "show roadlanes in editor"? If so, the slowness could actually just be the time taken for the immediate geometry to process, it's really not optimized.

Doing some troubleshooting, I have a feeling it's a discontinuity issue for small or zero angles.

Reference local diff

    # Calculate secondary curve handles and setup curves
    var angle_q = -vec_ab.signed_angle_to(vec_bc, a_basis_y) * 0.5
    var angle_s = vec_cd.signed_angle_to(vec_bc, d_basis_y) * 0.5
+   print("angle_q ", angle_q, " angle_s: ", angle_s)
    var offset_q = tan(angle_q) * in_offset
    var offset_s = tan(angle_s) * out_offset
+   print("offset_q ", offset_q, " offset_s: ", offset_s)

Scenario 1

Pressing Add road when the prior two roads are well aligned, I get this result and the following printouts:

Add prior RoadPoint
angle_q -1.531639 angle_s: 1.531639
offset_q 153.147761 offset_s: -153.147761
angle_q -1.531639 angle_s: 1.531639
offset_q 51.049254 offset_s: -51.049254
angle_q -1.531639 angle_s: 1.531639
offset_q -51.049254 offset_s: 51.049254
angle_q -1.531639 angle_s: 1.531639
offset_q -153.147761 offset_s: 153.14776

Also doing command undo didn't work unfortunately (I'd have to test in dev if that's new or pre-existing).

Scenario 2

Slightly turned the roadpoint, so that the new added one wouldn't have a flat on angle. Observation: there's still one lane that seems to over-extend for some reason

Add prior RoadPoint
angle_q 1.43727 angle_s: -1.43727
offset_q -44.667604 offset_s: 44.667604
angle_q 1.43727 angle_s: -1.43727
offset_q -14.889201 offset_s: 14.889201
angle_q 1.43727 angle_s: -1.43727
offset_q 14.889201 offset_s: -14.889201
angle_q 1.43727 angle_s: -1.43727
offset_q 44.667604 offset_s: -44.667604

In both cases, if I ever so slightly modify the position of the newly added roadpoint, it is immediately resolved. My guess is having any kind of different basis resolves it. See the angles after having done this slight movement (this was moving the roadpoint almost imperceptibly small amount along its local x axis). Notice how the radian angles here are substantially differnet, despite such a subtle difference.

Translate
angle_q 0.785429 angle_s: -0.785429
offset_q -6.000367 offset_s: 6.000367
angle_q 0.785429 angle_s: -0.785429
offset_q -2.000122 offset_s: 2.000122
angle_q 0.785429 angle_s: -0.785429
offset_q 2.000122 offset_s: -2.000122
angle_q 0.785429 angle_s: -0.785429
offset_q 6.000367 offset_s: -6.000367

Recording:

https://github.com/TheDuckCow/godot-road-generator/assets/2958461/d4b1feda-11f8-4a61-88bd-ed626865441d

Hope this troubleshooting helps.

[bdog2112]

I think you are on the right track in suspecting angles. After some number crunching, it appears that angles close to 90 degrees should be avoided. FYI: Moving two RoadPoints closer together to the point where the handles are practically overlapping is a quick and easy way to cause trouble. ;-)

In this screenshot, we see that tan(90) yields an extremely large number, which would be problematic if we tried to plot it.

The angle is largely determined by the relationship between the handles on the start and end RoadPoints of a segment. Hence, if we want to create a problem, we can just move a segment's handles into a 90 degree position.

I'll look at utilizing a default value when the angle is within a certain range of 90 degrees.

[bdog2112]

Well, doing some further testing it looks like there is still a scenario to be addressed.

Take a simple 2x2 Road and don't rotate or move anything... Now, pull the "out" handle so that it extends beyond the "in" handle or vice versa. (e.g. Pull the out handle past the in handle and close to the start point.) At that point, the RoadLanes will circle back onto themselves.

That doesn't really seem like a valid scenario. But, it's very easy for anyone to create. Hence, it warrants some consideration.

[bdog2112]

I tried this test, again, and it did not recreate the problem. Thus, the IDE may have simply been in an unstable state. It's working fine, now.

It is possible to create unwanted results by playing around with overlapping the handles near the center of a segment. But, generally speaking, this should be avoided. RoadPoints should be spaced a reasonable distance apart and their handles should not overlap.

[TheDuckCow]

Closing this as completed! While there may still be some funniness in terms of a duplicate recreation of roadlanes, the base goal of this issue has been resolved, so I'm marking this as completed.