1 /****************************************************************************
2 **
3 ** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the Qt3D module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL3$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPLv3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or later as published by the Free
28 ** Software Foundation and appearing in the file LICENSE.GPL included in
29 ** the packaging of this file. Please review the following information to
30 ** ensure the GNU General Public License version 2.0 requirements will be
31 ** met: http://www.gnu.org/licenses/gpl-2.0.html.
32 **
33 ** $QT_END_LICENSE$
34 **
35 ****************************************************************************/
36
37 #include "functionrangefinder_p.h"
38
39 QT_BEGIN_NAMESPACE
40
41 namespace Qt3DAnimation {
42 namespace Animation {
43
44 /*!
45 \internal
46 \class FunctionRangeFinder finds the lower bound index of a range that encloses a function value
47
48 Given a vector of function values (typically abscissa values of some other function), this
49 class can find the lower bound index of a range that encloses the requested value. This is
50 very useful for finding the two points that sandwich a value to which you later wish to
51 interpolate for example.
52 */
53
54 /*
55 \internal
56
57 int findLowerBound (float x)
58
59 Finds the lower bound index of a range that encloses the requested value \a x.
60
61 We use a technique which tries to be better than a simple bisection. Often when
62 performing interpolations, subsequent points are correlated with earlier calls.
63 This is especially true with time based lookups. If two calls are determined to
64 be correlated, then the next subsequent call will use the hunt function to search
65 close to the last returned value first. The hunt algorithms searches outward in
66 increasing step sizes until a sandwiching range is found. Traditional bisection
67 is then used to refine this result.
68
69 If the previous results are uncorrelated, a simple bisection is used.
70 */
71
FunctionRangeFinder(const QVector<float> & x)72 FunctionRangeFinder::FunctionRangeFinder(const QVector<float> &x)
73 : m_x(x)
74 , m_previousLowerBound(0)
75 , m_correlated(0)
76 , m_rangeSize(2)
77 , m_correlationThreshold(1)
78 , m_ascending(true)
79 {
80 updateAutomaticCorrelationThreshold();
81 if (!m_x.isEmpty())
82 m_ascending = (m_x.last() >= m_x.first());
83 }
84
85 /*!
86 \internal
87 Locates the lower bound of a range that encloses \a x by a bisection method.
88 */
locate(float x) const89 int FunctionRangeFinder::locate(float x) const
90 {
91 if (m_x.size() < 2 || m_rangeSize < 2 || m_rangeSize > m_x.size())
92 return -1;
93
94 int jLower = 0;
95 int jUpper = m_x.size() - 1;
96 while (jUpper - jLower > 1) {
97 int jMid = (jUpper + jLower) >> 1;
98 if ((x >= m_x[jMid]) == m_ascending)
99 jLower = jMid;
100 else
101 jUpper = jMid;
102 }
103
104 m_correlated = std::abs(jLower - m_previousLowerBound) <= m_correlationThreshold;
105 m_previousLowerBound = jLower;
106
107 return std::max(0, std::min(m_x.size() - m_rangeSize, jLower - ((m_rangeSize - 2) >> 1)));
108 }
109
110 /*!
111 \internal
112 Hunts outward from the previous result in increasing step sizes then refines via bisection.
113 */
hunt(float x) const114 int FunctionRangeFinder::hunt(float x) const
115 {
116 if (m_x.size() < 2 || m_rangeSize < 2 || m_rangeSize > m_x.size())
117 return -1;
118
119 int jLower = m_previousLowerBound;
120 int jMid;
121 int jUpper;
122 if (jLower < 0 || jLower > (m_x.size() - 1)) {
123 jLower = 0;
124 jUpper = m_x.size() - 1;
125 } else {
126 int increment = 1;
127 if ((x >= m_x[jLower]) == m_ascending) {
128 for (;;) {
129 jUpper = jLower + increment;
130 if (jUpper >= m_x.size() - 1) {
131 jUpper = m_x.size() - 1;
132 break;
133 } else if ((x < m_x[jUpper]) == m_ascending) {
134 break;
135 } else {
136 jLower = jUpper;
137 increment += increment;
138 }
139 }
140 } else {
141 jUpper = jLower;
142 for (;;) {
143 jLower = jLower - increment;
144 if (jLower <= 0) {
145 jLower = 0;
146 break;
147 } else if ((x >= m_x[jLower]) == m_ascending) {
148 break;
149 } else {
150 jUpper = jLower;
151 increment += increment;
152 }
153 }
154 }
155 }
156
157 while (jUpper - jLower > 1) {
158 jMid = (jUpper + jLower) >> 1;
159 if ((x >= m_x[jMid]) == m_ascending)
160 jLower = jMid;
161 else
162 jUpper = jMid;
163 }
164
165 m_correlated = std::abs(jLower - m_previousLowerBound) <= m_correlationThreshold;
166 m_previousLowerBound = jLower;
167
168 return std::max(0, std::min(m_x.size() - m_rangeSize, jLower - ((m_rangeSize - 2) >> 1)));
169 }
170
171 } // namespace Animation
172 } // namespace Qt3DAnimation
173
174 QT_END_NAMESPACE
175