fling.mx raw
1 // SPDX-License-Identifier: Unlicense OR MIT
2
3 // Scroll fling physics.
4 // Ported from gioui.org/internal/fling (animation.go + extrapolation.go).
5
6 package gio
7
8 import (
9 "math"
10 "time"
11 )
12
13 // FlingAnimation models exponential deceleration of a fling gesture.
14 type FlingAnimation struct {
15 x float32
16 t0 time.Time
17 v0 float32
18 }
19
20 const (
21 minFlingVelocityDp Dp = 50
22 maxFlingVelocityDp Dp = 8000
23 thresholdVelocityPx = 1
24 flingDecay = -4.2 // pixels/second^2 drag constant
25 )
26
27 // FlingStart initiates a fling from the given velocity (pixels/second).
28 // Returns true if velocity is above the minimum threshold.
29 func (f *FlingAnimation) FlingStart(m Metric, now time.Time, velocity float32) bool {
30 min := float32(m.Dp(minFlingVelocityDp))
31 v := velocity
32 if -min <= v && v <= min {
33 return false
34 }
35 max := float32(m.Dp(maxFlingVelocityDp))
36 if v > max {
37 v = max
38 } else if v < -max {
39 v = -max
40 }
41 f.t0 = now
42 f.v0 = v
43 f.x = 0
44 return true
45 }
46
47 // FlingActive reports whether a fling is in progress.
48 func (f *FlingAnimation) FlingActive() bool { return f.v0 != 0 }
49
50 // FlingStop stops any active fling.
51 func (f *FlingAnimation) FlingStop() { f.v0 = 0 }
52
53 // FlingTick advances the fling and returns the distance to scroll.
54 func (f *FlingAnimation) FlingTick(now time.Time) int {
55 if !f.FlingActive() {
56 return 0
57 }
58 k := float32(flingDecay)
59 t := now.Sub(f.t0)
60 ekt := float32(math.Exp(float64(k) * t.Seconds()))
61 x := f.v0*ekt/k - f.v0/k
62 dist := x - f.x
63 idist := int(dist)
64 f.x += float32(idist)
65 v := f.v0 * ekt
66 if -thresholdVelocityPx < v && v < thresholdVelocityPx {
67 f.v0 = 0
68 }
69 return idist
70 }
71
72 // --- Velocity extrapolation ---
73
74 // FlingExtrapolation estimates fling velocity from a series of position samples.
75 // Uses Android's least-squares polynomial fit algorithm.
76 type FlingExtrapolation struct {
77 idx int
78 samples []flingSample
79 lastValue float32
80 cache [flingHistorySize]flingSample
81 values [flingHistorySize]float32
82 times [flingHistorySize]float32
83 }
84
85 type flingSample struct {
86 t time.Duration
87 v float32
88 }
89
90 // FlingEstimate is the estimated velocity and distance from extrapolation.
91 type FlingEstimate struct {
92 Velocity float32
93 Distance float32
94 }
95
96 const (
97 flingDegree = 2
98 flingHistorySize = 20
99 flingMaxAge = 100 * time.Millisecond
100 flingMaxGap = 40 * time.Millisecond
101 )
102
103 type flingCoeffs [flingDegree + 1]float32
104
105 // Sample records a position observation at time t.
106 func (e *FlingExtrapolation) Sample(t time.Duration, val float32) {
107 e.lastValue = val
108 if e.samples == nil {
109 e.samples = e.cache[:0]
110 }
111 s := flingSample{t: t, v: val}
112 if e.idx == len(e.samples) && e.idx < cap(e.samples) {
113 e.samples = append(e.samples, s)
114 } else {
115 e.samples[e.idx] = s
116 }
117 e.idx++
118 if e.idx == cap(e.samples) {
119 e.idx = 0
120 }
121 }
122
123 // SampleDelta records a delta sample relative to the last value.
124 func (e *FlingExtrapolation) SampleDelta(t time.Duration, delta float32) {
125 e.Sample(t, delta+e.lastValue)
126 }
127
128 // Estimate computes the velocity and distance from recorded samples.
129 func (e *FlingExtrapolation) Estimate() FlingEstimate {
130 if len(e.samples) == 0 {
131 return FlingEstimate{}
132 }
133 values := e.values[:0]
134 times := e.times[:0]
135 first := e.flingGet(0)
136 prev := first.t
137 for i := range e.samples {
138 p := e.flingGet(-i)
139 age := first.t - p.t
140 if age >= flingMaxAge || prev-p.t >= flingMaxGap {
141 break
142 }
143 prev = p.t
144 values = append(values, p.v)
145 times = append(times, float32(p.t-first.t)/float32(time.Second))
146 }
147 if len(values) == 1 {
148 return FlingEstimate{}
149 }
150 degree := flingDegree
151 if len(values) <= degree {
152 degree = len(values) - 1
153 }
154 coeffs, ok := flingPolyFit(times, values, degree)
155 if !ok {
156 return FlingEstimate{}
157 }
158 // Velocity is the derivative at t=0.
159 velocity := coeffs[1]
160 // Distance is the polynomial value at t=0 minus current.
161 distance := values[0] - first.v
162 return FlingEstimate{Velocity: velocity, Distance: distance}
163 }
164
165 func (e *FlingExtrapolation) flingGet(i int) flingSample {
166 n := len(e.samples)
167 idx := (e.idx + n + i - 1) % n
168 return e.samples[idx]
169 }
170
171 // flingPolyFit fits a polynomial of the given degree to (times, values).
172 // Returns coefficients [c0, c1, c2, ...] and whether the fit succeeded.
173 func flingPolyFit(times, values []float32, degree int) (flingCoeffs, bool) {
174 // Build the Vandermonde matrix A where A[i][j] = times[i]^j.
175 n := len(values)
176 cols := degree + 1
177 A := []float32{:n * cols}
178 for i, t := range times {
179 for j := 0; j < cols; j++ {
180 A[i*cols+j] = float32(math.Pow(float64(t), float64(j)))
181 }
182 }
183 // Solve the normal equations A^T A c = A^T b using Cholesky-like method.
184 // For simplicity, use Gaussian elimination on the normal matrix.
185 ATA := []float32{:cols * cols}
186 ATb := []float32{:cols}
187 for i := 0; i < cols; i++ {
188 for k := 0; k < n; k++ {
189 ATb[i] += A[k*cols+i] * values[k]
190 for j := 0; j < cols; j++ {
191 ATA[i*cols+j] += A[k*cols+i] * A[k*cols+j]
192 }
193 }
194 }
195 // Gaussian elimination with partial pivoting.
196 aug := []float32{:cols * (cols + 1)}
197 for i := 0; i < cols; i++ {
198 for j := 0; j < cols; j++ {
199 aug[i*(cols+1)+j] = ATA[i*cols+j]
200 }
201 aug[i*(cols+1)+cols] = ATb[i]
202 }
203 for col := 0; col < cols; col++ {
204 // Find pivot.
205 pivot := col
206 for row := col + 1; row < cols; row++ {
207 if math.Abs(float64(aug[row*(cols+1)+col])) > math.Abs(float64(aug[pivot*(cols+1)+col])) {
208 pivot = row
209 }
210 }
211 // Swap rows.
212 for j := 0; j <= cols; j++ {
213 aug[col*(cols+1)+j], aug[pivot*(cols+1)+j] = aug[pivot*(cols+1)+j], aug[col*(cols+1)+j]
214 }
215 if aug[col*(cols+1)+col] == 0 {
216 return flingCoeffs{}, false
217 }
218 // Eliminate.
219 for row := 0; row < cols; row++ {
220 if row == col {
221 continue
222 }
223 factor := aug[row*(cols+1)+col] / aug[col*(cols+1)+col]
224 for j := col; j <= cols; j++ {
225 aug[row*(cols+1)+j] -= factor * aug[col*(cols+1)+j]
226 }
227 }
228 }
229 var coeffs flingCoeffs
230 for i := 0; i < cols; i++ {
231 coeffs[i] = aug[i*(cols+1)+cols] / aug[i*(cols+1)+i]
232 }
233 return coeffs, true
234 }
235