Subdivide Bezier Curves

Question

hi, i want to achieve that I can subdivide a Bezier Curve with a given distance. Now it works if the Bezier is a straight line, but if I change a Controll-Point so the Bezier get's curved, the Distance will be off what I wanted to achieve! => see pictures at the End of Post

How I get the Subdivision is:

  float t = Distance between subdividedParts / bezier length;
 //A,B,C,D = ControllPoints of Bezier
 GetPoint(A,B,C,D,t);
 
 //GetPoint equation:
 public static Vector3 GetPoint (Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t) {
         t = Mathf.Clamp01(t);
         float OneMinusT = 1f - t;
         return
             OneMinusT * OneMinusT * OneMinusT * p0 +
             3f * OneMinusT * OneMinusT * t * p1 +
             3f * OneMinusT * t * t * p2 +
             t * t * t * p3;
     }

I hope enough Information is provided. Dan

Straight

Curved

bezier-explenation

Answer 1

Best Answer

Answer by Bunny83 · Feb 10, 2019 at 02:57 AM

Ok, based on your new image and explanation I think we finally understand what's your goal. However it's not that easy to get it working for every kind of cubic bezier curve. The main issue is that certain points can have more than one point that is on the perimeter.

Bezier curves aren't linear in it's nature which makes it quite difficult to get some uniform pattern analytically. The best approach is to do some sort Newton's method to approach the desired point. So you would just nudge forward along the curve and measure the distance between your last point and the current position. Once distance is too large you would decrease the step size and nudge back until you are again below the target distance. Repeat to get as close as you want to your target distance.

One problem is that if your curve has a small sharp turn and your step size is too large that you jump over a possible solution and pick the next intersection instead. If that's not an issue this is probably the best solution. Since the "density" of the curve changes as you walk along the curve it's best to measure the relative distance after each step to adjust the step size accordingly.

Basically something like this:

 float targetLength;
 
 // determine worldspace length of a step of 0.001 units
 float L = (C(0.001f) - C(0)).magnitude;
 
 // normalized step size to achieve about 1/10 of our target length.
 float step = ((targetLength / 10) / L) * 0.001f; 
 
 Vector3 last = C(t);
 t += step;
 while (true)
 {
     while ((C(t) - last).sqrMagnitude < targetLength *targetLength && t < 1f)
         t += step;
     step /= 10f;
     while ((C(t) - last).sqrMagnitude > targetLength *targetLength && t > 0)
         t -= step;
     step /= 10f;
     if (Mathf.Abs((C(t) - last).sqrMagnitude - targetLength *targetLength) < 0.0001f || t<0 || t>1)
         break;
 }
 Vector3 next = C(t);

This is untested and should be seen as a pseudo script example.

Add comment · Show 9 · Share

dan_wipf · Feb 10, 2019 at 05:08 PM 0

Share

thanks for the explenation, makes now more sence to me.

just didn’t quite figure out what C and t stands for, could you give me a hint?

Bunny83 dan_wipf · Feb 10, 2019 at 08:05 PM 0

Share

"C()" simply stands for your curve function. So it's just the bezier function and the parameter is the normalized "t" value (0 to 1). "t" is just the normalized position along the curve. So you would start with a value of "0". Note that the code i've shown is just the code to calculate the "next point" on the curve.

I just realised i had already posted something similar over here, though the question was a bit different. He wanted to get the closest position on the curve from a given point.

dan_wipf Bunny83 · Feb 11, 2019 at 09:42 AM 0

Share

well I've tried out your code and for a moment I've got the next step in the curve.

I did now an implementation of what you suggested to achieve, but it's a heavy operation which bend's my system to it knees, (depends on how accurate I want to get the operation running)

 public Vector3[] GetPoints (float gap,float accuracy){
     SimpsonVec sv = SV_Setup(0);
     Vector3 last_spawn = Bezier.GetPoint(sv.A,sv.B,sv.C,sv.D,0);
 
     List<Vector3> allPoints = new List<Vector3>();
     allPoints.Add(last_spawn);
 
     for(float t = accuracy;t <= 1.0f; t +=accuracy){
         Vector3 trial = Bezier.GetPoint(sv.A,sv.B,sv.C,sv.D,t);
         if(Vector3.Distance(trial,last_spawn) >= gap){
             last_spawn = trial;
             allPoints.Add(trial);
         }
     }
     return allPoints.ToArray();
 }

List of accuracy:

0.001f = smooth working accurate (between 0.1 and 0.2 difference).

0.0001f = still smooth working accurate (between 0.01 and 0.02 difference).

0.00001f = buggy working accurate (between 0.001 and 0.002 difference).

0.000001f = up to 20 seconds waiting for respond, accurate (almost zero difference)

Runs in an editor script. Basically I want to get the most accurate result, but I need the best Performance.

Show more comments

Answer 2

Answer by BastianUrbach · Feb 08, 2019 at 05:14 PM

It's explained in this article.

Here is some code for cubic Beziers:

 void Subdivide(
     Vector3 a0, Vector3 a1, Vector3 a2, Vector3 a3, float t,
     out Vector3[] firstPart, out Vector3[] secondPart
 ) {
     var b0 = Vector3.Lerp(a0, a1, t); // Same as evaluating a Bezier
     var b1 = Vector3.Lerp(a1, a2, t);
     var b2 = Vector3.Lerp(a2, a3, t);
 
     var c0 = Vector3.Lerp(b0, b1, t);
     var c1 = Vector3.Lerp(b1, b2, t);
 
     var d0 = Vector3.Lerp(c0, c1, t); // This would be the interpolated point
 
     firstPart = new Vector3[] { a0, b0, c0, d0 }; // first point of each step
     secondPart = new Vector3[] { a3, b2, c1, d0 }; // last point of each step
 }

EDIT: Ah, now I understand what you meant (I'll leave the previous answer because it might be helpful for someone else). Unfortunately I think this might be quite a difficult problem. It's surely possible but it probably involves some nasty integrals. Depending on your requirements, an approximate solution might be enough. Here is one, it's a bit ugly but it kinda works. It takes any curve (could be Bezier), the number of subdivisions you want to perform and a value that determines how accurate the approximation will be. It returns an array of values such that evaluating the curve with those values yields evenly spaced points.

 float[] Subdivide(System.Func<float, Vector3> curve, int divisionCount, int approximationSteps) {
     // Estimate distances along the curve in regular intervals of t
     // by approximating the curve with a polyline
     float stepSize = 1f / approximationSteps;
     float[] distances = new float[approximationSteps + 1];
 
     Vector3 last = curve(0);
     Vector3 current;
 
     for (int i = 1; i < distances.Length; i++) {
         current = curve(i * stepSize);
         distances[i] = distances[i - 1] + Vector3.Distance(last, current);
         last = current;
     }
 
     // Walk through distance array to find the t for each subdivision
     float sectionLength = distances[distances.Length - 1] / (divisionCount + 1);
     float[] divisions = new float[divisionCount];
 
     int tInt = 0;
     float tFrac;
 
     for (int i = 0; i < divisionCount; i++) {
         float target = (i + 1) * sectionLength; // Where the next subdivision should be
         while (distances[tInt] < target) tInt++; // Skip until target is exceeded
         tFrac = Mathf.InverseLerp(distances[tInt - 1], distances[tInt], target);
         divisions[i] = (tInt - 1 + tFrac) / approximationSteps;
     }
 
     return divisions;
 }

Here is how it could be used:

 var divisions = Subdivide(t => Bezier(a, b, c, d, t), 10, 100);
 foreach (var t in divisions) {
     var p = Bezier(a, b, c, d, t);
     Gizmos.DrawLine(p + Vector3.down * 0.1f, p + Vector3.up * 0.1f);
 }

If you just need it to look right, this should be accurate enough: subdivided bezier curve

beziersubdivide.png (40.0 kB)

Add comment · Show 7 · Share

dan_wipf · Feb 08, 2019 at 06:51 PM 0

Share

Thank you for your example Code, this didn't do the Trick for me!.

well I've read this article, but couldn't use it. might I explain what I really want to achieve I want to divide the bezier into parts. (Vector3 positions) those part have an exactly length, now if I do GetPoint() I'll have to put in the 4 ControllPoints of the Bezier + value t (range 0 to 1) if I'd do a for loop like this:

 float segmentLength = 5;
 int validPositions = $$anonymous$$athf.FloorToInt(LengthOfBezier / segmentLength);
 float currentPos = 0;
 
 for(int i = 0; i< validPositions; i++){
         float currentLength = currentPos / LengthOfBezier;
         Vector3 WorldPos = GetPoint(A,B,C,D,currentLength);
         currentPos += segmentLength;
 }

this would give me 10 Vector3 WorldPosition on the Bezier. But if the Bezier is curved, the Distances between those WorldPosition is no more for Example 5.

dan_wipf · Feb 08, 2019 at 10:18 PM 0

Share

thanks alot for your edit! i’ll have a look to it! :)

dan_wipf · Feb 09, 2019 at 07:08 AM 0

Share

@coeusueoc well I think basically it's the solution you provided! and it's approximately enough. the only thing I'm worried about is if the curve turn's extremely sharp. the distance between the SubdividedParts will be off the expected result.

you can see in the Picture below, Distance 2 is 7.53.., and not 18.64.. like the other's is there a way to avoid this? like setting restriction on how much the Bezier can be curved?

Thanks a lot dan

Result's

offresult.jpg (147.2 kB)

Bunny83 dan_wipf · Feb 09, 2019 at 01:29 PM 0

Share

Actually the distance is correct. The distances are meant to be along the curve. The curve segment at the sharp turn has approximately the same length as the others. You just calculated the direct connection between the points. Since it's a curve it's in its nature to have different direct distances between two points on the curve depending on where you put them.

Some curves may need more "approximationSteps" than others. Those which sharp turns or extreme unpropotional segments need more than a "curve" which isn't "curved" that much.

If you don't understood what i meant, just imagine you double the subdivisions (so you just get another intermediate point on the curve between the current points). That means you get a point at the tip of the sharp curve. The distance betwen that tip and the two neighbors are approximately as long as all the other segments.

So his example works as intendet. $$anonymous$$aybe you have something else in $$anonymous$$d, but you have to be more clear in that case what you actually need. Can you take a picture of your curve and manually draw the marks where you want them to be?

dan_wipf Bunny83 · Feb 09, 2019 at 05:56 PM 0

Share

@Bunny83 well yes you both are right about the distances, they’re indeed correct if you take the length from the bezier.

but in my case i just want the points on the bezier but the distance must be a straight line between the points. because i want to spawn posts on the points and between connected a fixed length paling(distance)

Show more comments

BionicWombatGames · Feb 07 at 10:41 PM 0

Share

The original lerping example worked perfectly for basic bezier subdivision!

Answer 3

So the final code works now with connected beziers. thanks a lot, to @Bunny83 (Moved from Comment to Answer, due to. readability)

Structs:

     public struct SimpsonVec{
         [SerializeField]     public Vector3 A;
         [SerializeField]     public Vector3 B;
         [SerializeField]     public Vector3 C;
         [SerializeField]     public Vector3 D;    
     }
     public struct  BezierPoints
     {
         [SerializeField] public List<Vector3> bp_vector3;
         [SerializeField] public List<Vector3> bp_lastSpawn;    
     }

Code for a Vector3[] Array Output:

 public Vector3[] GetAllPoints(float gap,float acc){
 
     SimpsonVector = SV_SETUP_ALL();
     BezierPoints bp = new BezierPoints();
     bp.bp_vector3 = new List<Vector3>();
     bp.bp_lastSpawn = new List<Vector3>();
         
     for(int i = 0; i<points.Length / 3;i++){
         
         Vector3 ls = new Vector3();
         if(i == 0){
             ls = Bezier.GetPoint(SimpsonVector[0].A,SimpsonVector[0].B,SimpsonVector[0].C,SimpsonVector[0].D,0);
         }if (i > 0){
             ls = bp.bp_lastSpawn[i-1];
         }
         BezierPoints bp_temp = GetSegmentPoints(gap,acc,i,ls);
         bp.bp_lastSpawn.Add(bp_temp.bp_lastSpawn[0]);
         bp.bp_vector3.AddRange(bp_temp.bp_vector3);
         SimpsonVector_TEMP = SimpsonVector;
     }
     
     
     return bp.bp_vector3.ToArray();
 }
 
 BezierPoints GetSegmentPoints (float gap,float acc,int index, Vector3 ls)
 {
     SimpsonVec sv = SimpsonVector[index];
     Vector3 last_spawn = ls;
 
     BezierPoints bp = new BezierPoints();
     bp.bp_vector3 = new List<Vector3>();
     bp.bp_lastSpawn = new List<Vector3>();
 
     float step = 0.1f;
     float t = step;
     float lastT = new float();
 
     while (t >= 0 && t <= 1f)
     {
         while (t < 1f && Vector3.Distance(Bezier.GetPoint(sv.A,sv.B,sv.C,sv.D,t), last_spawn) < gap){
             t += step;}
         step /= acc;
         while (t > lastT && Vector3.Distance(Bezier.GetPoint(sv.A,sv.B,sv.C,sv.D,t), last_spawn) > gap){
             t -= step;}
         step /= acc;
         if (t > 1f || t < lastT){
             break;}
         if(step < 0.000001f){
             last_spawn = Bezier.GetPoint(sv.A,sv.B,sv.C,sv.D,t);
             bp.bp_vector3.Add(last_spawn + transform.position);
             lastT = t;
             step = 0.1f;
         }
     }
     bp.bp_lastSpawn.Add(last_spawn);
     return bp;
 }

Helper Methods

 public SimpsonVec SV_Setup(int index){
     SimpsonVec sv;
     sv.A = points[index];
     sv.B = points[index+1];
     sv.C = points[index+2];
     sv.D = points[index+3];
     return sv;
 
 }
 public SimpsonVec[] SV_SETUP_ALL(){
     SimpsonVec[] sv = new SimpsonVec[points.Length / 3];
     for(int i = 0; i<points.Length / 3;i++){
         sv[i] = SV_Setup(i*3);
     }
     return sv;
 }
 public Vector3 GetPoint (Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t) {
     t = Mathf.Clamp01(t);
     float OneMinusT = 1f - t;
     return
         OneMinusT * OneMinusT * OneMinusT * p0 +
         3f * OneMinusT * OneMinusT * t * p1 +
         3f * OneMinusT * t * t * p2 +
         t * t * t * p3;
 }

Subdivide Bezier Curves

3 Replies

Your answer

Follow this Question

Related Questions