File indexing completed on 2024-05-19 04:21:05
0001 /* 0002 * SPDX-FileCopyrightText: 2019-2023 Mattia Basaglia <dev@dragon.best> 0003 * 0004 * SPDX-License-Identifier: GPL-3.0-or-later 0005 */ 0006 0007 #include <QtTest/QtTest> 0008 0009 #include <vector> 0010 #include "math/bezier/solver.hpp" 0011 0012 using namespace glaxnimate; 0013 0014 class TestCase: public QObject 0015 { 0016 Q_OBJECT 0017 0018 private Q_SLOTS: 0019 #if 0 0020 void test_order() 0021 { 0022 math::BezierSolver<QVector2D> bs{ 0023 QVector2D{1, 2}, 0024 QVector2D{3, 4} 0025 }; 0026 QCOMPARE(bs.order(), 1); 0027 0028 bs = math::BezierSolver<QVector2D> { 0029 QVector2D{1, 2}, 0030 QVector2D{3, 4}, 0031 QVector2D{5, 6} 0032 }; 0033 QCOMPARE(bs.order(), 2); 0034 0035 bs = math::BezierSolver<QVector2D> { 0036 QVector2D{1, 2}, 0037 QVector2D{3, 4}, 0038 QVector2D{5, 6}, 0039 QVector2D{7, 8} 0040 }; 0041 QCOMPARE(bs.order(), 3); 0042 } 0043 0044 void test_solve_linear() 0045 { 0046 math::BezierSolver<QVector2D> bs{ 0047 QVector2D{20, 100}, 0048 QVector2D{40, 0} 0049 }; 0050 0051 QCOMPARE(bs.solve(0.0), QVector2D(20, 100)); 0052 QCOMPARE(bs.solve(.25), QVector2D(25, 75)); 0053 QCOMPARE(bs.solve(.50), QVector2D(30, 50)); 0054 QCOMPARE(bs.solve(.75), QVector2D(35, 25)); 0055 QCOMPARE(bs.solve(1.0), QVector2D(40, 0)); 0056 } 0057 0058 void test_solve_quadratic() 0059 { 0060 QVector2D a{20, 100}; 0061 QVector2D b{35, 50}; 0062 QVector2D c{40, 0}; 0063 0064 math::BezierSolver<QVector2D> bs{a, b, c}; 0065 0066 auto explicit_solve = [a,b,c](double t) { 0067 auto p1 = math::lerp(a, b, t); 0068 auto p2 = math::lerp(b, c, t); 0069 return math::lerp(p1, p2, t); 0070 }; 0071 0072 QCOMPARE(bs.solve(0.0), a); 0073 QCOMPARE(bs.solve(.25), explicit_solve(0.25)); 0074 QCOMPARE(bs.solve(.50), explicit_solve(0.50)); 0075 QCOMPARE(bs.solve(.75), explicit_solve(0.75)); 0076 QCOMPARE(bs.solve(1.0), c); 0077 } 0078 #endif 0079 0080 #define FUZZY_COMPARE(a, b) QCOMPARE(a.x(), b.x()); QCOMPARE(a.y(), b.y()); 0081 0082 void test_solve_cubic() 0083 { 0084 QVector2D a{20, 100}; 0085 QVector2D b{35, 50}; 0086 QVector2D c{50, -20}; 0087 QVector2D d{40, 0}; 0088 0089 math::bezier::CubicBezierSolver<QVector2D> bs{a, b, c, d}; 0090 0091 auto explicit_solve = [a,b,c,d](double t) { 0092 auto p1 = math::lerp(a, b, t); 0093 auto p2 = math::lerp(b, c, t); 0094 auto p3 = math::lerp(c, d, t); 0095 auto q1 = math::lerp(p1, p2, t); 0096 auto q2 = math::lerp(p2, p3, t); 0097 return math::lerp(q1, q2, t); 0098 }; 0099 0100 FUZZY_COMPARE(bs.solve(0.0), a); 0101 FUZZY_COMPARE(bs.solve(.25), explicit_solve(0.25)); 0102 FUZZY_COMPARE(bs.solve(.50), explicit_solve(0.50)); 0103 FUZZY_COMPARE(bs.solve(.75), explicit_solve(0.75)); 0104 FUZZY_COMPARE(bs.solve(1.0), d); 0105 } 0106 0107 #if 0 0108 void test_angle_linear() 0109 { 0110 math::scalar_type<QVector2D> angle = 1; 0111 QVector2D a{20, 30}; 0112 QVector2D b = a + math::from_polar(10, angle); 0113 0114 math::BezierSolver<QVector2D> bs{a, b}; 0115 QCOMPARE(bs.tangent_angle(0.00), angle); 0116 QCOMPARE(bs.tangent_angle(0.25), angle); 0117 QCOMPARE(bs.tangent_angle(0.50), angle); 0118 QCOMPARE(bs.tangent_angle(0.75), angle); 0119 QCOMPARE(bs.tangent_angle(1.00), angle); 0120 0121 b = a + math::from_polar(10, 2 * M_PI -1); 0122 angle = - 1; 0123 0124 bs = math::BezierSolver<QVector2D>{a, b}; 0125 QCOMPARE(bs.tangent_angle(0.00), angle); 0126 QCOMPARE(bs.tangent_angle(0.25), angle); 0127 QCOMPARE(bs.tangent_angle(0.50), angle); 0128 QCOMPARE(bs.tangent_angle(0.75), angle); 0129 QCOMPARE(bs.tangent_angle(1.00), angle); 0130 } 0131 0132 void test_angle_quadratic() 0133 { 0134 QVector2D sp{20, 30}; 0135 QVector2D h{30, 40}; 0136 QVector2D ep{40, 30}; 0137 0138 math::BezierSolver<QVector2D> bs{sp, h, ep}; 0139 QCOMPARE(bs.tangent_angle(0.00), M_PI/4); 0140 QVERIFY(bs.tangent_angle(0.1) > 0); 0141 QCOMPARE(bs.tangent_angle(0.50), 0); 0142 QVERIFY(bs.tangent_angle(0.9) < 0); 0143 QCOMPARE(bs.tangent_angle(1.00), -M_PI/4); 0144 } 0145 #endif 0146 0147 void test_angle_cubic() 0148 { 0149 QPointF sp{20, 30}; 0150 QPointF h1{20, 40}; 0151 QPointF h2{40, 20}; 0152 QPointF ep{40, 30}; 0153 0154 math::bezier::CubicBezierSolver<QPointF> bs{sp, h1, h2, ep}; 0155 QCOMPARE(bs.tangent_angle(0.00), M_PI/2); 0156 QVERIFY(bs.tangent_angle(0.1) > 0); 0157 QVERIFY(bs.tangent_angle(0.50) < 0); 0158 QVERIFY(bs.tangent_angle(0.9) > 0); 0159 QCOMPARE(bs.tangent_angle(1.00), M_PI/2); 0160 } 0161 0162 #if 0 0163 void test_solve_step() 0164 { 0165 QVector2D a{20, 30}; 0166 QVector2D b{15, 40}; 0167 QVector2D c{30, 10}; 0168 QVector2D d{40, 15}; 0169 0170 math::BezierSolver<QVector2D> bs{a, b, c, d}; 0171 double fac = 0.33; 0172 auto quad = bs.solve_step(fac); 0173 QCOMPARE(quad.size(), 3); 0174 auto q0 = math::lerp(a, b, fac); 0175 FUZZY_COMPARE(quad[0], q0); 0176 auto q1 = math::lerp(b, c, fac); 0177 FUZZY_COMPARE(quad[1], q1); 0178 auto q2 = math::lerp(c, d, fac); 0179 FUZZY_COMPARE(quad[2], q2); 0180 0181 bs = math::BezierSolver<QVector2D>{q0, q1, q2}; 0182 auto lin = bs.solve_step(fac); 0183 QCOMPARE(lin.size(), 2); 0184 auto l0 = math::lerp(q0, q1, fac); 0185 auto l1 = math::lerp(q1, q2, fac); 0186 FUZZY_COMPARE(lin[0], l0); 0187 FUZZY_COMPARE(lin[1], l1); 0188 0189 bs = math::BezierSolver<QVector2D>{l0, l1}; 0190 auto res = bs.solve_step(fac); 0191 QCOMPARE(res.size(), 1); 0192 FUZZY_COMPARE(res[0], math::lerp(l0, l1, fac)); 0193 FUZZY_COMPARE(res[0], (math::BezierSolver<QVector2D>{a, b, c, d}.solve(fac))); 0194 } 0195 #endif 0196 0197 void test_split_cubic() 0198 { 0199 QVector2D sp{20, 30}; 0200 QVector2D ep{80, 30}; 0201 QVector2D h1 = sp + QVector2D{10, 20}; 0202 QVector2D h2 = ep + QVector2D{-10, 20}; 0203 double mid_x = 50; 0204 0205 math::bezier::CubicBezierSolver<QVector2D> bs{sp, h1, h2, ep}; 0206 auto split = bs.split(0.5); 0207 0208 // First split 0209 // Begins with the starting point 0210 QCOMPARE(split.first[0], sp); 0211 // First tangent pointing up and right 0212 QVERIFY(split.first[1].x() > sp.x()); 0213 QVERIFY(split.first[1].x() < mid_x); 0214 QVERIFY(split.first[1].y() > sp.y()); 0215 // End point should be in the middle of the original 0216 QCOMPARE(split.first[3].x(), mid_x); 0217 QVERIFY(split.first[3].y() > sp.y()); 0218 // Second tangent points straight out of the mid point 0219 QVERIFY(split.first[2].x() > split.first[1].x()); 0220 QVERIFY(split.first[2].x() < split.first[3].x()); 0221 QCOMPARE(split.first[2].y(), split.first[3].y()); 0222 0223 // Second Split 0224 // Starts where the other left off 0225 QCOMPARE(split.second[0], split.first[3]); 0226 // First tangent points straight out of the mid point 0227 QVERIFY(split.second[1].x() > split.second[0].x()); 0228 QVERIFY(split.second[1].x() < split.second[2].x()); 0229 QCOMPARE(split.second[1].y(), split.second[0].y()); 0230 // Ends with the original end point 0231 QCOMPARE(split.second[3], ep); 0232 // Second tangent points down 0233 QVERIFY(split.second[2].x() < ep.x()); 0234 QVERIFY(split.second[2].x() > mid_x); 0235 QVERIFY(split.second[2].y() > ep.y()); 0236 } 0237 0238 #if 0 0239 void test_split_quadratic() 0240 { 0241 QVector2D sp{20, 30}; 0242 QVector2D ep{80, 30}; 0243 double mid_x = 50; 0244 QVector2D h{mid_x, 50}; 0245 0246 math::BezierSolver<QVector2D> bs{sp, h, ep}; 0247 auto split = bs.split_cubic(0.5); 0248 0249 // First split 0250 // Begins with the starting point 0251 QCOMPARE(split.first[0], sp); 0252 QCOMPARE(split.first[1], sp); 0253 // End point should be in the middle of the original 0254 QCOMPARE(split.first[3].x(), mid_x); 0255 QVERIFY(split.first[3].y() > sp.y()); 0256 // Second tangent points straight out of the mid point 0257 QVERIFY(split.first[2].x() > split.first[1].x()); 0258 QVERIFY(split.first[2].x() < split.first[3].x()); 0259 QCOMPARE(split.first[2].y(), split.first[3].y()); 0260 0261 // Second Split 0262 // Starts where the other left off 0263 QCOMPARE(split.second[0], split.first[3]); 0264 // First tangent points straight out of the mid point 0265 QVERIFY(split.second[1].x() > split.second[0].x()); 0266 QVERIFY(split.second[1].x() < split.second[2].x()); 0267 QCOMPARE(split.second[1].y(), split.second[0].y()); 0268 // Ends with the original end point 0269 QCOMPARE(split.second[3], ep); 0270 QCOMPARE(split.second[2], ep); 0271 } 0272 0273 0274 void test_split_linear() 0275 { 0276 QVector2D sp{20, 30}; 0277 QVector2D ep{80, 130}; 0278 auto midp = (sp+ep)/2; 0279 0280 math::BezierSolver<QVector2D> bs{sp, ep}; 0281 auto split = bs.split_cubic(0.5); 0282 0283 // First split 0284 // Begins with the starting point 0285 QCOMPARE(split.first[0], sp); 0286 QCOMPARE(split.first[1], sp); 0287 // End point should be in the middle of the original 0288 QCOMPARE(split.first[3], midp); 0289 QCOMPARE(split.first[2], midp); 0290 // Second Split 0291 // Starts where the other left off 0292 QCOMPARE(split.second[0], midp); 0293 QCOMPARE(split.second[1], midp); 0294 // Ends with the original end point 0295 QCOMPARE(split.second[3], ep); 0296 QCOMPARE(split.second[2], ep); 0297 } 0298 #endif 0299 0300 void benchmark_solve() 0301 { 0302 using VecT = QVector2D; 0303 VecT a{20, 30}; 0304 VecT b{15, 40}; 0305 VecT c{30, 10}; 0306 VecT d{40, 15}; 0307 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0308 QBENCHMARK{ 0309 for ( double t = 0; t <= 1; t += 0.01 ) 0310 bs.solve(t); 0311 } 0312 // Without cubic optimization 0313 // 0.17 msecs per iteration (total: 91, iterations: 512) 0314 // With the optimization 0315 // 0.017 msecs per iteration (total: 71, iterations: 4096) 0316 // 1 order of magnitude difference 0317 } 0318 0319 void benchmark_solve_qvec() 0320 { 0321 using VecT = QVector2D; 0322 VecT a{20, 30}; 0323 VecT b{15, 40}; 0324 VecT c{30, 10}; 0325 VecT d{40, 15}; 0326 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0327 QBENCHMARK{ 0328 for ( double t = 0; t <= 1; t += 0.01 ) 0329 bs.solve(t); 0330 } 0331 // Slightly faster but calculating tangents loses significant precision 0332 // 0.013 msecs per iteration (total: 57, iterations: 4096) 0333 } 0334 0335 void benchmark_solve_qpointf() 0336 { 0337 using VecT = QPointF; 0338 VecT a{20, 30}; 0339 VecT b{15, 40}; 0340 VecT c{30, 10}; 0341 VecT d{40, 15}; 0342 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0343 QBENCHMARK{ 0344 for ( double t = 0; t <= 1; t += 0.01 ) 0345 bs.solve(t); 0346 } 0347 // Slightly faster but calculating tangents loses significant precision 0348 // 0.013 msecs per iteration (total: 57, iterations: 4096) 0349 } 0350 #if 0 0351 void benchmark_solve_quadratic() 0352 { 0353 using VecT = QVector2D; 0354 VecT a{20, 30}; 0355 VecT b{15, 40}; 0356 VecT c{30, 10}; 0357 math::BezierSolver<VecT> bs{a, b, c}; 0358 QBENCHMARK{ 0359 for ( double t = 0; t <= 1; t += 0.01 ) 0360 bs.solve(t); 0361 } 0362 // Without optimization 0363 // 0.12 msecs per iteration (total: 65, iterations: 512) 0364 // With the optimization 0365 // 0.013 msecs per iteration (total: 57, iterations: 4096) 0366 } 0367 #endif 0368 0369 void test_box_line_simple() 0370 { 0371 using VecT = QPointF; 0372 VecT a{20, 30}; 0373 VecT d{130, 250}; 0374 math::bezier::CubicBezierSolver<VecT> bs{a, a, d, d}; 0375 auto bbox = bs.bounds(); 0376 QCOMPARE(bbox.first, a); 0377 QCOMPARE(bbox.second, d); 0378 } 0379 0380 void test_box_line_mix() 0381 { 0382 using VecT = QPointF; 0383 VecT a{130, 30}; 0384 VecT d{20, 250}; 0385 math::bezier::CubicBezierSolver<VecT> bs{a, a, d, d}; 0386 auto bbox = bs.bounds(); 0387 QCOMPARE(bbox.first, VecT(20, 30)); 0388 QCOMPARE(bbox.second, VecT(130, 250)); 0389 } 0390 0391 void test_box_simple() 0392 { 0393 using VecT = QPointF; 0394 VecT a{20, 30}; 0395 VecT b{20, 200}; 0396 VecT c{130, 100}; 0397 VecT d{130, 250}; 0398 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0399 auto bbox = bs.bounds(); 0400 QCOMPARE(bbox.first, a); 0401 QCOMPARE(bbox.second, d); 0402 } 0403 0404 void test_box_simple_transposed() 0405 { 0406 using VecT = QPointF; 0407 VecT a{30, 20}; 0408 VecT b{200, 20}; 0409 VecT c{100, 130}; 0410 VecT d{250, 130}; 0411 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0412 auto bbox = bs.bounds(); 0413 QCOMPARE(bbox.first, a); 0414 QCOMPARE(bbox.second, d); 0415 } 0416 0417 void test_box() 0418 { 0419 using VecT = QPointF; 0420 VecT a{30, 20}; 0421 VecT b{-40, 160}; 0422 VecT c{330, 370}; 0423 VecT d{250, 130}; 0424 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0425 auto bbox = bs.bounds(); 0426 FUZZY_COMPARE(bbox.first, VecT(21.1349479424, 20)); 0427 FUZZY_COMPARE(bbox.second, VecT(261.392510712, 239.272612647)); 0428 } 0429 0430 void test_extrema_ends() 0431 { 0432 using VecT = QPointF; 0433 VecT a{0, 0}; 0434 VecT b{10, 20}; 0435 VecT c{80, 90}; 0436 VecT d{100, 100}; 0437 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0438 auto minmax = bs.extrema(1); 0439 QCOMPARE(minmax.first, 0.); 0440 QCOMPARE(minmax.second, 1.); 0441 } 0442 0443 void test_extrema_start_mid() 0444 { 0445 using VecT = QPointF; 0446 VecT a{0, 0}; 0447 VecT b{0, 0}; 0448 VecT c{50, 200}; 0449 VecT d{100, 100}; 0450 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0451 auto minmax = bs.extrema(1); 0452 QCOMPARE(minmax.first, 0.); 0453 QCOMPARE(minmax.second, 0.8); 0454 } 0455 0456 void test_extrema_end_mid() 0457 { 0458 using VecT = QPointF; 0459 VecT a{0, 0}; 0460 VecT b{50, -100}; 0461 VecT c{100, 100}; 0462 VecT d{100, 100}; 0463 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0464 auto minmax = bs.extrema(1); 0465 QCOMPARE(minmax.first, 0.2); 0466 QCOMPARE(minmax.second, 1.); 0467 } 0468 0469 void test_extrema_mid() 0470 { 0471 using VecT = QPointF; 0472 VecT a{0, 0}; 0473 VecT b{50, -100}; 0474 VecT c{50, 200}; 0475 VecT d{100, 100}; 0476 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0477 auto minmax = bs.extrema(1); 0478 QVERIFY(minmax.first < 0.5); 0479 QVERIFY(minmax.first > 0); 0480 QVERIFY(minmax.second < 1.); 0481 QVERIFY(minmax.second > 0.5); 0482 } 0483 0484 void test_extrema_mid_swap() 0485 { 0486 using VecT = QPointF; 0487 VecT a{0, 0}; 0488 VecT b{00, 300}; 0489 VecT c{00, -200}; 0490 VecT d{100, 100}; 0491 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0492 auto minmax = bs.extrema(1); 0493 QVERIFY(minmax.first < 0.5); 0494 QVERIFY(minmax.first > 0); 0495 QVERIFY(minmax.second < 1.); 0496 QVERIFY(minmax.second > 0.5); 0497 } 0498 0499 void test_extrema_mid_values_100() 0500 { 0501 using VecT = QPointF; 0502 VecT a{0, 0}; 0503 VecT b{100, -100}; 0504 VecT c{0, 200}; 0505 VecT d{100, 100}; 0506 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0507 auto minmax = bs.extrema(1); 0508 float t = 0.146446609407; 0509 QCOMPARE(float(minmax.first), t); 0510 QCOMPARE(float(minmax.second), 1-t); 0511 float x = 32.3223; 0512 float y = 20.7107; 0513 QCOMPARE(float(bs.solve_component(minmax.first, 0)), x); 0514 QCOMPARE(float(bs.solve_component(minmax.first, 1)), -y); 0515 QCOMPARE(float(bs.solve_component(minmax.second, 0)), 100-x); 0516 QCOMPARE(float(bs.solve_component(minmax.second, 1)), 100+y); 0517 } 0518 0519 void test_extrema_mid_values_1() 0520 { 0521 using VecT = QPointF; 0522 VecT a{0, 0}; 0523 VecT b{1, -1}; 0524 VecT c{0, 2}; 0525 VecT d{1, 1}; 0526 math::bezier::CubicBezierSolver<VecT> bs{a, b, c, d}; 0527 auto minmax = bs.extrema(1); 0528 float t = 0.146446609407; 0529 QCOMPARE(float(minmax.first), t); 0530 QCOMPARE(float(minmax.second), 1-t); 0531 float x = 0.323223; 0532 float y = 0.207107; 0533 QCOMPARE(float(bs.solve_component(minmax.first, 0)), x); 0534 QCOMPARE(float(bs.solve_component(minmax.first, 1)), -y); 0535 QCOMPARE(float(bs.solve_component(minmax.second, 0)), 1-x); 0536 QCOMPARE(float(bs.solve_component(minmax.second, 1)), 1+y); 0537 } 0538 }; 0539 0540 QTEST_GUILESS_MAIN(TestCase) 0541 #include "test_bezier_solver.moc"