Dividing a Bezier curve into equal segments
Tags: go, gamedev, tutorial
Published: 2020-09-24 09:21:01

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](https://github.com/faiface/pixel) game library. I'll use [Bezier curves](https://en.wikipedia.org/wiki/B%C3%A9zier_curve) 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](https://github.com/gonum/plot) package. So that's the import section:

```go
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:

```go
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:

```go
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:

```go
// 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.

```go
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:

```go
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:

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

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

```go
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()`:

```go
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:

![The Bezier curve graph](https://dev-to-uploads.s3.amazonaws.com/i/2zmwm0y31igur3if76xt.png)

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:

    ```go
        // 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.

    ```go
        // 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.

    ```go
        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:

    ```go
        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:

    ```go
        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:

![Equally segmented Bezier curve](https://dev-to-uploads.s3.amazonaws.com/i/mh5hhnkwmre2lqvp1nm1.png)

Well, that's much better. Thank you for reading. Here's the [source code](https://github.com/zergon321/segmented-curve).