Spline Help

Hello,

I am using Megafiers to create a path in my game. I am making it so the path can be changed in real time and everything is working great except one issue. I cannot figure out the math to add a "knot" in the middle of an already existing curve that does not change the shape of the original curve. So if you look at the attached images. I start with the first curve, and then want to add point C in the middle and adjust the "A Out Vector, C In Vector" and "C Out Vector, and B In Vector" so that the original shape does not change. Anyone already know this math or have some thoughts on how I can achieve this?



Adding point on the curve

 

I don't know the math but are you familiar with Inkscape? It is a free open source vector graphic editing tool and it has an "insert point" function that clearly does precisely this math, adjusting the control points of the original two points and the newly added point.

Just google Inkscape and you can find where to download its source code, and after that it's just a slog through to look for the "insert point" code.

The actual button text helper says "Insert new nodes into selected segments" if that is any help to your search.

 

Thanks for responding!

I tried hunting through that source code but it was a little overwhelming. I was able to come up with a solution that works perfectly for what I need. It is difficult for me to type out the explanation, but basically I just used Vector3.Lerp to follow the process shown in the image below.

I was able to get the "t" of Point C along the segment and used that to lerp (P0,P1) then (P1,P2) then (P2,P3) to get to the second graph. Then lerp those to get the last graph which has the handle points I needed for C. Not sure if this is the most precise method but it works great for me!

 

Huh! I'd love for a mathematician to weigh in on whether this is "the right answer" or "close enough for game work." I've seen other geometry-based tricks like what you posted for other contexts, so wouldn't surprise me if this was technically correct.

Thanks for the enlightenment.

 

that is one of the methods to generate bezier splines. it works fine for simple splines but it grows astronomically more expensive to calculate as more points are added to the curve, primarily due to the math it takes to find the binomial coefficients needed to weigh each anchor for a single point on the spline. take a look at the example you posted. you started with 4 anchor points which you then calculated to find 3 imaginary anchor points, you then ran the pass again to find 2 more imaginary anchors, and then another pass once a again on those two to find the final anchor point which becomes a point on the spline. the growth is so fast that if the binomialCoefficient function isn't written properly it can quickly overflow after a handful of anchors
.

The simple solution to that is to keep the spline subdivided into multiple splines. The common practice is for each spline to have 3 or 4 anchors (depending on total anchors, or style) and then "stitch" one spline seamlessly to the other. In order to pull this off you'll need the last anchor point to mirror the 1st anchor point of the next spline, then you also need to make sure that the last two anchors of the 1st spline is colinear with the first two anchor points of the 2nd spline. this is required in order for the two splines to appear seamlessly stitched together.

 

Thank you so much for your insight!

I think I understand what you are saying, and I am essentially doing what you suggest. I am looking at each new point as adding it between just the two closest points with the "out vector" and nearest point below, and the "in vector" and nearest point above the new point. So I can ignore the rest of the spline no matter how complex it gets and only split the relevant segment of the spline.

 

What you described is the De-Casteljau algorithm which are the basis of Bézier-Splines. You should google that, Bézier-Splines are segments of n De-Boor splines.

But this alone does not solve the issue you have with adding a controll point into an existing spline. Or have you found a solution yet? Because what you need is to find those points on the spline mesh which lead to point C.

Also if you are able to add a controll point to a spline can depend on the type of spline you use. For some splines it might not work and for others it can become more complicated. But it should work with Bézier-Splines.
EDIT: I overlooked the previous post of his, that is of course a method to do.

 

He should already have access to those points. Referring back to the 3 spline graphs he posted, group the anchors shown by their level as levels a,b, and c.


Then splitting the spline at control point C the anchor points of the 1st spline should be:
P0a, P0b, P0c, and C. i.e the1st point from each level

while the 2nd spline would have anchors:
C, P1c, P2b, and P3a. i.e the last point from each level