How to add a point to a Curve3D without changing its shape (ex. for splitting a curve)

[paper42]

Godot Version

Godot 4.2.1

Question

Hi, I am trying to add a point to a curve programatically with gdscript without changing its shape. I want to do this to then be able to easily split into two curves at that point, add a road intersection and a navigation point for AStar3D in my game.

I think I will need to adjust the previous point’s out vector, compute the new point’s in&out vectors and adjust the next point’s in vector. Is there some algorithm that could do this?

I tried searching and found the De Casteljau algorithm, but it’s only for 2D and I have not been able to adapt it for 3D.
I also tried computing the tangent and in&out surrounding vector intersection points, but failed to do so, maybe partially because two 3D lines don’t have to intersect as opposed to (non-parallel) lines in 2D, so I guess I would have to try intersecting a line and a box-shape?

Which way would be the easiest? I am a bit lost and I think I might be going about it the wrong way.

[Timberjaw]

This one’s a doozy, but doable. The De Casteljau algorithm is applicable to 3D, despite most of the readily available resources only explaining it in 2D.

Left = exploded view. Right = reassembled. This started as a Curve3D with 4 points. The spheres are debug display for the curve points and control points.

Gist linked below. My overall approach is:

1. Decompose the Curve3D to cubic sub-curves
2. Sample the overall curve to get the split point
3. Loop the sub-curves to determine which one the split point belongs to
4. Calculate the local offset within the target sub-curve by taking the offset length of the split point in the original curve, minus the cumulative lengths of the segments before the target sub-curve, then turning that into a local-segment % for De Casteljau.
5. Split the target sub-curve using De Casteljau’s algorithm
6. Stitch the sub-curves back together
7. Drag the inspector slider back and forth for 10 minutes and watch the bits move

I’m not a mathematician and haven’t worked with bezier curves programmatically before, so pardon the spaghetti:

https://gist.github.com/Timberjaw/2efcf766fafb82098b347819fec3f846

[paper42]

Thank you a lot, this helped me understand it better and I was able to add splitting curves to my project after many unsuccessful attempts.

[Timberjaw]

Glad you’ve got it working! I’d love to see a screenshot of how you’re using it.