fastbezier

README

fastbezier

Fast cubic bezier curve evaluation lookup table for curves (0, 0), (x0, y0), (x1, y1), (1, 1) in uint16 space.

• Trades off precision for performance.
• Particularly optimized for ARM cores.
• Includes a C code generator for embedded devices without a FPU (e.g. ESP8266).

Documentation

Overview

package fastbezier implements a fast cubic bezier curve evaluator for curves of type (0, 0), (x0, y0), (x1, y1), (1, 1), in the uint16 domain.

The implementation trades off precision for performance.

Index

• type LUT
  • func Make(x0, y0, x1, y1 float32, steps uint16) LUT
  • func MakeFast(x0, y0, x1, y1 float32, steps uint16) LUT
  • func (l LUT) Eval(x uint16) uint16
  • func (l LUT) String() string

Examples

• LUT.Eval
• Make
• MakeFast

Types

type LUT

type LUT []uint16

LUT is a fast cubic bezier curve evaluator over uint16 that uses a lookup table.

Values are constrained in the range [0, 65535] for both x and y. It forces points (0, 0) and (65535, 65535).

func Make

func Make(x0, y0, x1, y1 float32, steps uint16) LUT

Make returns a LUT object.

Memory allocation is 2*(steps+1) bytes.

It is only useful when the table is going to be stored as a precalculated table. Otherwise it is preferable to use `MakeFast`.

Example

l := Make(0, 0, 0.58, 1, 6)
fmt.Printf("%s\n", l)
// Each point is 16 bits.
fmt.Printf("%d\n", len(l))
fmt.Printf("%d\n", l.Eval(1000))

Output:
LUT{(0, 0), (13107, 20209), (26214, 37413), (39321, 51454), (52428, 61453), (65535, 65535)}
7
1541

func MakeFast

func MakeFast(x0, y0, x1, y1 float32, steps uint16) LUT

MakeFast returns a LUT object that is slightly less precise but takes half of the time to generate than `Make`.

With default steps, max error is 109 instead of 104, generally in the range of a delta 10 higher than with `Make`.

Example

l := MakeFast(0, 0, 0.58, 1, 6)
fmt.Printf("%s\n", l)
// Each point is 16 bits.
fmt.Printf("%d\n", len(l))
fmt.Printf("%d\n", l.Eval(1000))

Output:
LUT{(0, 0), (13107, 20191), (26214, 37402), (39321, 51305), (52428, 61207), (65535, 65535)}
7
1540

func (LUT) Eval

func (l LUT) Eval(x uint16) uint16

Example

const steps = 14
l := Make(0.42, 0, 0.58, 1, 0)
fmt.Println("  i    xf    xi   yfi    yf    yi delta   error")
for i := 0; i < steps; i++ {
	xf := float32(i) / float32(steps-1)
	yf := internal.CubicBezier(0.42, 0, 0.58, 1, xf)
	xi := uint16(uint32(i) * 65535 / uint32(steps-1))
	yi := l.Eval(xi)
	yfi := internal.FloatToUint16(yf * 65535.)
	delta := int(yfi) - int(yi)
	fmt.Printf("%3d %.3f %5d %.3f %5d %5d %5d %6.3f%%\n", i, xf, xi, yf, yfi, yi, delta, float32(delta)*100./65535.)
}

Output:
  i    xf    xi   yfi    yf    yi delta   error
  0 0.000     0 0.000     0     0     0  0.000%
  1 0.077  5041 0.012   758   791   -33 -0.050%
  2 0.154 10082 0.048  3121  3147   -26 -0.040%
  3 0.231 15123 0.110  7182  7200   -18 -0.027%
  4 0.308 20164 0.197 12927 12960   -33 -0.050%
  5 0.385 25205 0.308 20159 20165    -6 -0.009%
  6 0.462 30246 0.434 28438 28443    -5 -0.008%
  7 0.538 35288 0.566 37097 37091     6  0.009%
  8 0.615 40329 0.692 45376 45369     7  0.011%
  9 0.692 45370 0.803 52608 52574    34  0.052%
 10 0.769 50411 0.890 58353 58334    19  0.029%
 11 0.846 55452 0.952 62414 62387    27  0.041%
 12 0.923 60493 0.988 64777 64743    34  0.052%
 13 1.000 65535 1.000 65535 65535     0  0.000%

func (LUT) String

func (l LUT) String() string