Dividing a Bezier curve into equal segments

Sometimes in game development, there's a need to equally distribute homogeneous objects along a curved trajectory. I couldn't find any code solution for this, so here's mine.

Dependencies

For this tutorial I'll use Go programming language and Pixel game library. I'll use Bezier curves because they are flexible enough to create any trajectory and manually edit it, though the algorithm described here is applicable for curved trajectories of any kind. Bezier curve can be created using gonum package. So that's the import section:

import (
    "fmt"
    "time"

    "github.com/faiface/pixel"
    "github.com/faiface/pixel/imdraw"
    "github.com/faiface/pixel/pixelgl"
    colors "golang.org/x/image/colornames"
    "gonum.org/v1/plot/plotter"
    "gonum.org/v1/plot/tools/bezier"
    "gonum.org/v1/plot/vg"
)

As you can see, I also use colornames package for predefined colors.

Creating a curve

First we should create a new curve. I will use cubic Bezier curve with 4 control points:

controlPoints := []vg.Point{
        {X: 0.45, Y: 0.328},
        {X: 1.403, Y: 0.12},
        {X: 0.62, Y: 1.255},
        {X: 1.521, Y: 0.593},
}

As you can see, the numbers are pretty small. Don't worry, the curve will be scaled and translated to look good on the screen.

Also there are constants we'll need later:

const (
    screenWidth              = 1280
    screenHeight             = 720
    offsetX          float64 = 400
    offsetY          float64 = 300
    scaleX           float64 = 300
    scaleY           float64 = 300
    numberOfSegments         = 10
    epsilon          float64 = 0.001
    dt               float64 = 0.5
)

To create a new curve out of the control points:

// Form the curve.
curve := bezier.New(controlPoints...)

Now it's time to compute the curve's points. To obtain a single point of Bezier curve, you need to use parameter t, 0 ≤ t ≤ 1. Method (c Curve) Point(t float64) vg.Point returns a point of the curve corresponding to the parameter. For example, if t = 0.5, the method will return the middle point of the curve.

It's better to get as many Bezier curve points as possible. To do this, we'll use step dt. The lesser the step, the more points you'll obtain.

points := make(plotter.XYs, 0)

for t := 0.0; t < 100.0; t += dt {
    point := curve.Point(t / 100.0)

    points = append(points, plotter.XY{
        X: float64(point.X)*scaleX + offsetX,
        Y: float64(point.Y)*scaleY + offsetY})
}

Drawing the curve

To draw the points of the curve, I will create a new window and an IMDraw object:

cfg := pixelgl.WindowConfig{
    Title:  "Bezier curve",
    Bounds: pixel.R(0, 0, screenWidth, screenHeight),
}
win, err := pixelgl.NewWindow(cfg)
handleError(err)

imd := imdraw.New(nil)

Also I like to setup the FPS counter:

fps := 0
perSecond := time.Tick(time.Second)

Now we are ready to enter the application main loop and draw the curve each frame:

for !win.Closed() {
    win.Clear(colors.White)
    imd.Clear()

    // Draw the curve and other things.
    imd.Color = colors.Red

    for _, point := range points {
        imd.Push(gonumToPixel(point))
        imd.Circle(1, 1)
    }

    imd.Draw(win)

    win.Update()

    // Show FPS in the window title.
    fps++

    select {
    case <-perSecond:
        win.SetTitle(fmt.Sprintf("%s | FPS: %d", cfg.Title, fps))
        fps = 0

    default:
    }
}

By the way, everything written above must be placed inside run() function which is called in main():

func main() {
    pixelgl.Run(run)
}

It's required to make sure the main goroutine won't be assigned to another thread.

Now let's see what we got:

As you can see, the distance between any two adjacent points of the curve is not always the same. Moreover, the graph becomes especially less dense closer to the first and the last control points of the curve.

Actually, that's not what we would like to see. We need all the points to be scattered equally along the curve. To reach it, we must introduce an algorithm of dividing a curve into equal segments.

So let's define a new function getSegmentPoints(points plotter.XYs, numberOfSegments int) []pixel.Vec:

1. Connect the curve points with lines:
   

       // Create lines out of bezier
       // curve points.
       lines := []pixel.Line{}
   
       for i := 0; i < len(points)-1; i++ {
           line := pixel.L(gonumToPixel(points[i]),
               gonumToPixel(points[i+1]))
   
           lines = append(lines, line)
       }
   

   Note: function gonumToPixel(xy plotter.XY) pixel.Vec
   transforms a gonum vector into a pixel vector.

2. Compute the sum length of the lines.
   

       // Compute the length
       // of the bezier curve
       // interpolated with lines.
       length := 0.0
   
       for _, line := range lines {
           length += line.Len()
       }
   

3. Compute the step which is the length of a single segment.
   

       step := length / float64(numberOfSegments)
   

4. Well, we reduced it to a task of segmenting a polygonal chain. The more curve points are obtained, the more precise it will be to the segmenting of the original curve.

   First we should do some initialization:
   

       segmentPoints := []pixel.Vec{}
       lastLine := 0
       lastPoint := lines[0].A
       segmentPoints = append(segmentPoints, lastPoint)
   

   So lastPoint is the last point of the last formed segment. lastLine is the index of the line which contains the last point. Now to the loop:
   

       for i := 0; i < numberOfSegments; i++ {
           subsegments := []pixel.Line{}
           startLine := pixel.L(lastPoint, lines[lastLine].B)
   
           subsegments = append(subsegments, startLine)
           localLength := startLine.Len()
   
           for step-localLength > epsilon {
               line := lines[lastLine+1]
               subsegments = append(subsegments, line)
   
               localLength += line.Len()
               lastLine++
           }
   
           line := lines[lastLine]
   
           if localLength > step {
               difference := localLength - step
               t := difference / line.Len()
   
               lastPoint = pixel.V(t*line.A.X+(1-t)*line.B.X,
               t*line.A.Y+(1-t)*line.B.Y)
           } else {
               lastPoint = line.B
               lastLine++
           }
   
           segmentPoints = append(segmentPoints, lastPoint)
       }
   

   In this loop, we pick up lines until their sum length exceeds the length of the segment. When it happens, we compute the segmentation point located on the last line using linear interpolation. If it coincides with the end of the line, we increment the last line counter and start a new iteration with the next line.

Ok, now let's divide our curve into 10 equal segments:

Well, that's much better. Thank you for reading. Here's the source code.