1// Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB).
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#include "functionrangefinder_p.h"
5
6QT_BEGIN_NAMESPACE
7
8namespace Qt3DAnimation {
9namespace Animation {
10
11/*!
12 \internal
13 \class FunctionRangeFinder finds the lower bound index of a range that encloses a function value
14
15 Given a vector of function values (typically abscissa values of some other function), this
16 class can find the lower bound index of a range that encloses the requested value. This is
17 very useful for finding the two points that sandwich a value to which you later wish to
18 interpolate for example.
19 */
20
21/*
22 \internal
23
24 int findLowerBound (float x)
25
26 Finds the lower bound index of a range that encloses the requested value \a x.
27
28 We use a technique which tries to be better than a simple bisection. Often when
29 performing interpolations, subsequent points are correlated with earlier calls.
30 This is especially true with time based lookups. If two calls are determined to
31 be correlated, then the next subsequent call will use the hunt function to search
32 close to the last returned value first. The hunt algorithms searches outward in
33 increasing step sizes until a sandwiching range is found. Traditional bisection
34 is then used to refine this result.
35
36 If the previous results are uncorrelated, a simple bisection is used.
37 */
38
39FunctionRangeFinder::FunctionRangeFinder(QList<float> *x)
40 : m_x(x)
41 , m_previousLowerBound(0)
42 , m_correlated(0)
43 , m_rangeSize(2)
44 , m_correlationThreshold(1)
45 , m_ascending(true)
46{
47 updateAutomaticCorrelationThreshold();
48 if (!m_x->isEmpty())
49 m_ascending = (m_x->last() >= m_x->first());
50}
51
52/*!
53 \internal
54 Locates the lower bound of a range that encloses \a x by a bisection method.
55*/
56int FunctionRangeFinder::locate(float x) const
57{
58 if (m_x->size() < 2 || m_rangeSize < 2 || m_rangeSize > m_x->size())
59 return -1;
60
61 qsizetype jLower = 0;
62 qsizetype jUpper = m_x->size() - 1;
63 while (jUpper - jLower > 1) {
64 qsizetype jMid = (jUpper + jLower) >> 1;
65 if ((x >= m_x->at(i: jMid)) == m_ascending)
66 jLower = jMid;
67 else
68 jUpper = jMid;
69 }
70
71 m_correlated = std::abs(x: jLower - m_previousLowerBound) <= m_correlationThreshold;
72 m_previousLowerBound = jLower;
73
74 return qMax(a: 0, b: qMin(a: m_x->size() - m_rangeSize, b: jLower - ((m_rangeSize - 2) >> 1)));
75}
76
77/*!
78 \internal
79 Hunts outward from the previous result in increasing step sizes then refines via bisection.
80 */
81int FunctionRangeFinder::hunt(float x) const
82{
83 if (m_x->size() < 2 || m_rangeSize < 2 || m_rangeSize > m_x->size())
84 return -1;
85
86 qsizetype jLower = m_previousLowerBound;
87 qsizetype jMid;
88 qsizetype jUpper;
89 if (jLower < 0 || jLower > (m_x->size() - 1)) {
90 jLower = 0;
91 jUpper = m_x->size() - 1;
92 } else {
93 qsizetype increment = 1;
94 if ((x >= m_x->at(i: jLower)) == m_ascending) {
95 for (;;) {
96 jUpper = jLower + increment;
97 if (jUpper >= m_x->size() - 1) {
98 jUpper = m_x->size() - 1;
99 break;
100 } else if ((x < m_x->at(i: jUpper)) == m_ascending) {
101 break;
102 } else {
103 jLower = jUpper;
104 increment += increment;
105 }
106 }
107 } else {
108 jUpper = jLower;
109 for (;;) {
110 jLower = jLower - increment;
111 if (jLower <= 0) {
112 jLower = 0;
113 break;
114 } else if ((x >= m_x->at(i: jLower)) == m_ascending) {
115 break;
116 } else {
117 jUpper = jLower;
118 increment += increment;
119 }
120 }
121 }
122 }
123
124 while (jUpper - jLower > 1) {
125 jMid = (jUpper + jLower) >> 1;
126 if ((x >= m_x->at(i: jMid)) == m_ascending)
127 jLower = jMid;
128 else
129 jUpper = jMid;
130 }
131
132 m_correlated = std::abs(x: jLower - m_previousLowerBound) <= m_correlationThreshold;
133 m_previousLowerBound = jLower;
134
135 return qMax(a: 0, b: qMin(a: m_x->size() - m_rangeSize, b: jLower - ((m_rangeSize - 2) >> 1)));
136}
137
138} // namespace Animation
139} // namespace Qt3DAnimation
140
141QT_END_NAMESPACE
142

source code of qt3d/src/animation/backend/functionrangefinder.cpp