1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
local gtable = require "gears.table"
-- port of https://github.com/WebKit/WebKit/blob/da934454c84ac2dcbf9fca9e5f4ac2644ef25d72/Source/WebCore/platform/graphics/UnitBezier.h
local bezier = {}
function bezier:sample_x(t)
-- `ax t^3 + bx t^2 + cx t' expanded using Horner's rule.
return ((self.ax * t + self.bx) * t + self.cx) * t
end
function bezier:sample_y(t)
return ((self.ay * t + self.by) * t + self.cy) * t
end
function bezier:sample_derivative_x(t)
return (3.0 * self.ax * t + 2.0 * self.bx) * t + self.cx
end
function bezier:solve_x(x, epsilon)
local x2, d2
local t2 = x
-- First try a few iterations of Newton's method -- normally very fast.
for _ = 1, 8 do
x2 = self:sample_x(t2) - x
if math.abs(x2) < epsilon then
return t2
end
d2 = self:sample_derivative_x(t2)
if math.abs(d2) < 1e-6 then
break
end
t2 = t2 - x2 / d2
end
-- Fall back to the bisection method for reliability.
local t0 = 0
local t1 = 1
t2 = x
if t2 < t0 then
return t0
end
if t2 > t1 then
return t1
end
while t0 < t1 do
x2 = self:sample_x(t2)
if math.abs(x2 - x) < epsilon then
return t2
end
if x > x2 then
t0 = t2
else
t1 = t2
end
t2 = (t1 - t0) * 0.5 + t0
end
-- Failure.
return t2
end
function bezier:solve(x, epsilon)
return self:sample_y(self:solve_x(x, epsilon))
end
local function new(x1, y1, x2, y2)
local obj = gtable.crush({}, bezier)
-- Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1).
obj.cx = 3.0 * x1
obj.bx = 3.0 * (x2 - x1) - obj.cx
obj.ax = 1.0 - obj.cx - obj.bx
obj.cy = 3.0 * y1
obj.by = 3.0 * (y2 - y1) - obj.cy
obj.ay = 1.0 - obj.cy - obj.by
return obj
end
return setmetatable(bezier, {
__call = function(_, ...)
return new(...)
end,
})
|
