多段Bézier曲线变换效果

头像
523066680
Administrator
Administrator
帖子: 333
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 29 times
Been thanked: 22 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #11 523066680 » 2016年10月04日 10:47

24game 写了:


做了测试,范围是 X[-250, 250], Y[-250, 250](黄色线框部分) , 把跑过的最远坐标(绝对值)通过终端输出:
rangetest.png

如果不画图,可以跑到 [470, 470] 左右。

作图:
假设上一线段的c,d点刚好坐落在对角线上,为使得新的曲线相对平滑,a,b点线段与其形成对称(在同一条直线上)
新的 d, c 点坐标在[-250, 250] 以内随机取值
attemp.png
attemp.png (34.42 KiB) 查看 688 次
attemp.png
attemp.png (34.42 KiB) 查看 688 次


当 d, c 点越来越靠近a点时,曲线的远端越来越接近红色正方形的顶点(但是无法和顶点重合)。
最后还是干脆点,假设a b c d在同一条直线上,且(a c d) 3点重合,b点在距离 a(cd) 100mm的地方,最后形成的线的长度会是多少?
straight100.png
straight100.png (6.41 KiB) 查看 684 次
straight100.png
straight100.png (6.41 KiB) 查看 684 次


大致比例 (可能会有一点点偏差)
0.4441

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #12 24game » 2016年10月04日 12:09

用 Mathematica 做了计算

Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. P0 = 0; P1 = 1;
  2. exp2 = P0 (1 - t)^2 + 2 P1 t (1 - t) + P0 t^2 ;
  3. exp3 = P0 (1 - t)^3 + 3 P1 t (1 - t)^2 + 3 P0 t^2 (1 - t) + P0 t^3;
  4. exp4 = P0 (1 - t)^4 + 4 P1 t (1 - t)^3 + 6 P0 t^2 (1 - t)^2 + 4 P0 t^3 (1 - t) + P0 t^4;
  5.  
  6. Print["求导"]
  7. D[exp2, t]
  8. D[exp3, t]
  9. D[exp4, t]
  10.  
  11. Print["求极点 t 值"]
  12. Solve[D[exp2, t] == 0, t]
  13. Solve[D[exp3, t] == 0, t]
  14. Solve[D[exp4, t] == 0, t]
  15.  
  16. Print["求第一个极点的精确表达式值"]
  17. exp2 /. t -> Solve[D[exp2, t] == 0, t][[1, 1, 2]]
  18. exp3 /. t -> Solve[D[exp3, t] == 0, t][[1, 1, 2]]
  19. exp4 /. t -> Solve[D[exp4, t] == 0, t][[1, 1, 2]]
  20.  
  21. Print["数值方式求第一个极点的表达式值"]
  22. FindMaximum[exp2, {t, 0.4}]
  23. FindMaximum[exp3, {t, 0.4}]
  24. FindMaximum[exp4, {t, 0.4}]
  25.  
  26. Plot[exp2, {t, 0, 1}];
  27. Plot[exp3, {t, 0, 1}];
  28. Plot[exp4, {t, 0, 1}];


输出

Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. 求导
  2. 2 (1 - t) - 2 t
  3. 3 (1-t)^2 - 6 (1-t) t
  4. 4 (1-t)^3 - 12 (1-t)^2 t
  5.  
  6. 求极点 t 值
  7. {{t -> 1/2}}
  8. {{t -> 1/3}, {t -> 1}}
  9. {{t -> 1/4}, {t -> 1}, {t -> 1}}
  10.  
  11. 求第一个极点的精确表达式值
  12. 1/2
  13. 4/9
  14. 27/64
  15.  
  16. 数值方式求第一个极点的表达式值
  17. {0.5, {t -> 0.5}}
  18. {0.444444, {t -> 0.333333}}
  19. {0.421875, {t -> 0.25}}


图片
图片
图片


2 次曲线的 1/2 的极值是最高的, 高次曲线的极值不会超出这个

3 次曲线在 t=1/3 时有极值 4/9 ~= 0.444444444444......

头像
523066680
Administrator
Administrator
帖子: 333
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 29 times
Been thanked: 22 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #13 523066680 » 2016年10月04日 23:03

24game 写了:用 Mathematica 做了计算


学习了,重新去wikipedia看了公式,之前没看懂,这次终于有点头绪。
由于假设起点和终点坐标均在原点(0, 0),b控制点为设为(0.0, 1.0),可以对公式简化。

=====================================================================
有一个问题没搞定,即我调用Bezier的绘制函数 t 值从0 到 1,线性递增,但是点的离散程度是不一样的。如何使每个点的间距相同?

=====================================================================
资料收集
http://compgroups.net/comp.graphics.algorithms/divide-cubic-bezier-into-equal-lengt/2052757

https://www.geometrictools.com/Documentation/MovingAlongCurveSpecifiedSpeed.pdf#sthash.pEYxzQiW.dpuf

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #14 24game » 2016年10月05日 12:33

如何使每个点的间距相同?

曲线弧长用积分计算, 尝试得出长度函数L(t) 的反函数 t(L), 对此反函数线性增长求解 t , 或者求解积分方程

积分计算弧长
https://zh.wikipedia.org/wiki/%E5%BC%A7%E9%95%BF
图片

各种数值近似实现方案

对任意阶贝塞尔曲线适用的数值解法
pointAlongCurveFrom(curve, location, distance)

https://code.google.com/archive/p/jsbezier/
关键代码段截取
Code: [全选] [展开/收缩] [Download] (Untitled.js)
  1. /**
  2.      * finds the point that is 'distance' along the path from 'location'.  this method returns both the x,y location of the point and also
  3.      * its 'location' (proportion of travel along the path); the method below - _pointAlongPathFrom - calls this method and just returns the
  4.      * point.
  5.      */
  6.     var _pointAlongPath = function(curve, location, distance) {
  7.         var _dist = function(p1,p2) { return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); },
  8.             prev = _pointOnPath(curve, location),
  9.             tally = 0,
  10.             curLoc = location,
  11.             direction = distance > 0 ? 1 : -1,
  12.             cur = null;
  13.         while (tally < Math.abs(distance)) {
  14.             curLoc += (0.005 * direction);
  15.             cur = _pointOnPath(curve, curLoc);
  16.             tally += _dist(cur, prev); 
  17.             prev = cur;
  18.         }
  19.         return {point:cur, location:curLoc};           
  20.     };



特定形式的 3 次曲线等分
Bezier Curve - in Equal Segments
图片
http://sketchup.engineeringtoolbox.com/ ... c_157.html


2 次贝塞尔曲线等分实现
http://www.cnblogs.com/didi/archive/200 ... 63435.html
http://blog.csdn.net/flood_dragon/artic ... ls/8782065

3 次贝塞尔曲线等分近似实现 (原帖未找到, 图片存留的转帖也未找到)
http://blog.csdn.net/kongbu0622/article ... s/10124065

头像
523066680
Administrator
Administrator
帖子: 333
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 29 times
Been thanked: 22 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #15 523066680 » 2016年10月05日 14:58

最后一个连接引用的那个博客有大量好文
http://thecodeway.com/blog/
收藏,学习。

可能那个博主把贝塞尔曲线的文章删了,奇怪

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #16 24game » 2016年10月05日 15:09

523066680 写了:最后一个连接引用的那个博客有大量好文
http://thecodeway.com/blog/
收藏,学习。

可能那个博主把贝塞尔曲线的文章删了,奇怪



终于决定把这个博客重新开起来,去年我一次误操作把原来的博客全部删掉了,几乎没有留下任何痕迹


有一些老帖的备份, 但恐怕也残缺
https://web.archive.org/web/20131022094 ... .com/blog/

此扒坟神网 存在也有些年了, 我竟然才知道
https://archive.org/web/

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #17 24game » 2016年10月06日 19:28

等分3阶曲线的数值积分函数

按弧长等分
图片

按 t 值线性分段
图片

以上图形由 Mathematica 10 绘制, 分点坐标由下文的 C 代码中 PointOnCubicBezier 函数计算得到
Mathematica 10 代码
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. Needs["Splines`"]
  2.  
  3. pts = {{-31, -33}, {30, -36}, {-25, 28}, {33, 6}};
  4.  
  5. pps = {{-31.000000, -33.000000}, {-26.473223, -33.100813}, \
  6. {-21.803112, -32.900533}, {-17.181859, -32.293437}, {-12.692476, \
  7. -31.144602}, {-8.405203, -29.239359}, {-4.712460, -26.475325}, \
  8. {-1.850744, -22.848809}, {0.068124, -18.613653}, {1.204749, \
  9. -14.075212}, {1.833144, -9.500808}, {2.253196, -4.918588}, {2.785189, \
  10. -0.247070}, {3.872591, 4.229112}, {6.350148, 8.141665}, {10.399117,
  11.     10.227684}, {15.030105, 10.588897}, {19.565813,
  12.     10.029625}, {24.141002, 8.952093}, {28.544624,
  13.     7.596929}, {33.000000, 6.000000}};
  14.  
  15. tps = {{-31.000000, -33.000000}, {-22.691375, -32.966625}, \
  16. {-15.951000, -32.043000}, {-10.607125, -30.343875}, {-6.488000, \
  17. -27.984000}, {-3.421875, -25.078125}, {-1.237000, -21.741000}, \
  18. {0.238375, -18.087375}, {1.176000, -14.232000}, {1.747625, \
  19. -10.289625}, {2.125000, -6.375000}, {2.479875, -2.602875}, {2.984000,
  20.     0.912000}, {3.809125, 4.054875}, {5.127000, 6.711000}, {7.109375,
  21.     8.765625}, {9.928000, 10.104000}, {13.754625,
  22.     10.611375}, {18.761000, 10.173000}, {25.118875,
  23.     8.674125}, {33.000000, 6.000000}};
  24. Graphics[{Spline[pts, Bezier],
  25.   Point[pts], {RGBColor[1, 0, 0], Point[pps]}}]
  26. Graphics[{Spline[pts, Bezier],
  27.   Point[pts], {RGBColor[0, 0, 1], Point[tps]}}]



函数
double get_t_of_BezierDegree3_Equal_parts(Point2D* cps, int i_of, int numOfParts)

获取曲线上 从 P0 起始, 到全长的 i_of / numOfParts 点处的 t 值. 仍可优化加速

Code: [全选] [展开/收缩] [Download] (Untitled.c)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #define SQR(x) ((x)*(x))
  5. #define EPS (1e-3)              /* EPS 积分步长, 一个小正数, 在运算范围内, 此值越小, 积分计算越准确, 但耗时也会越长 */
  6. #define EPS_DIV_2 (EPS / 2)
  7. #define ONE (999999e-6)
  8.  
  9. /*
  10.  
  11.     3 阶曲线参数方程:
  12.     B(t) = P0 (1 - t)^3 + 3 P1 t (1 - t)^2 + 3 P2 t^2 (1 - t) + P3 t^3;
  13.  
  14.     二维平面坐标分量参数方程:
  15.     x(t) = P0x (1 - t)^3 + 3 P1x t (1 - t)^2 + 3 P2x t^2 (1 - t) + P3x t^3;
  16.     y(t) = P0y (1 - t)^3 + 3 P1y t (1 - t)^2 + 3 P2y t^2 (1 - t) + P3y t^3;
  17.  
  18.  
  19.     分量微分 (x 分量微分 和 y 分量微分)
  20.     -3 P0x (1 - t)^2 + 3 P1x (1 - t)^2 - 6 P1x (1 - t) t + 6 P2x (1 - t) t - 3 P2x t^2 + 3 P3x t^2
  21.     -3 P0y (1 - t)^2 + 3 P1y (1 - t)^2 - 6 P1y (1 - t) t + 6 P2y (1 - t) t - 3 P2y t^2 + 3 P3y t^2
  22.  
  23.     弧长微分 = Sqrt( x 分量微分 ^ 2 + y 分量微分 ^ 2 )  (原理为勾股定理, 如果是 3 维或更高维曲线, 则将所有 坐标分量微分的平方 求总和再开方)
  24.  
  25.     3*Sqrt[(P0x*(-1 + t)^2 + t*(-2*P2x + 3*P2x*t - P3x*t) + P1x*(-1 + 4*t - 3*t^2))^2 + (P0y*(-1 + t)^2 + t*(-2*P2y + 3*P2y*t - P3y*t) + P1y*(-1 + 4*t - 3*t^2))^2]
  26.  
  27.  */
  28.  
  29. typedef struct {
  30.     double x;
  31.     double y;
  32. }
  33. Point2D;
  34.  
  35. // 3 阶曲线在 t 处的弧长微分
  36.  
  37. double BezierDegree3_dL(Point2D* cps, double t) {
  38.     // return 3*sqrt((cps[0].x * (-1 + t)^2 + t*(-2*cps[2].x + 3*cps[2].x * t - cps[3].x * t) + cps[1].x * (-1 + 4*t - 3*t^2))^2 +
  39.     //  (cps[0].y * (-1 + t)^2 + t*(-2*cps[2].y + 3*cps[2].y * t - cps[3].y * t) + cps[1].y * (-1 + 4*t - 3*t^2))^2);
  40.  
  41.     double v1, v2, v3, v4;
  42.     v1 = (-1 + t);
  43.     v2 = (-1 + 4 * t - 3 * t * t);
  44.     v3 = (cps[0].x * SQR(v1) + t * (-2 * cps[2].x + 3 * cps[2].x * t - cps[3].x * t) + cps[1].x * v2);
  45.     v4 = (cps[0].y * SQR(v1) + t * (-2 * cps[2].y + 3 * cps[2].y * t - cps[3].y * t) + cps[1].y * v2);
  46.  
  47.     return 3 * sqrt(SQR(v3) + SQR(v4));
  48. }
  49.  
  50. // 3 阶曲线的全长 (辛普森积分法)
  51. // Integrate[f(t), {t, a, b}] ~= (f(a)+4*f(m)+f(b)) * (b-a) / 6   ; 其中 m = (a + b) / 2
  52. // 此处积分步长 b-a = EPS
  53.  
  54. double BezierDegree3_Length(Point2D* cps) {
  55.     double a, m, b, bl;
  56.     bl = 0;
  57.     for (a = 0, m = a + EPS_DIV_2, b = a + EPS; a < ONE; a = b, b += EPS, m += EPS) {
  58.         bl += BezierDegree3_dL(cps, a) + 4 * BezierDegree3_dL(cps, m) + BezierDegree3_dL(cps, b);
  59.     }
  60.     return bl * EPS / 6;
  61. }
  62.  
  63. // 把曲线等分成 numOfParts 段, 获取曲线上 从 P0 起始, 到全长的 i_of / numOfParts 点处的 t 值
  64. // 例: 曲线被分成 numOfParts = 20 段, 从起点到终点一共 21 个分点;
  65. // i_of = 3, 将返回第 3 个分点 Q (P0~~Q 的弧长 = 曲线全长 * 3 / 20) 处的 t 值
  66.  
  67. double get_t_of_BezierDegree3_Equal_parts(Point2D* cps, int i_of, int numOfParts) {
  68.     double a, m, b, bl, len;
  69.  
  70.     if (i_of <= 0 || numOfParts <= 0) return 0;
  71.     if (i_of >= numOfParts) return 1;
  72.  
  73.     // 要达到的长度
  74.     len = BezierDegree3_Length(cps) * i_of / numOfParts * 6 / EPS;
  75.  
  76.     bl = 0;
  77.     for (a = 0, m = a + EPS_DIV_2, b = a + EPS; a < ONE; a = b, b += EPS, m += EPS) {
  78.         bl += BezierDegree3_dL(cps, a) + 4 * BezierDegree3_dL(cps, m) + BezierDegree3_dL(cps, b);
  79.         if (bl >= len) return a;
  80.     }
  81.     return 1;
  82. }
  83.  
  84. // 返回由控制点集 cps 确定的曲线上, t 处的坐标, 结果存储在 pPoint 指向的二维坐标组中
  85.  
  86. void PointOnCubicBezier(Point2D* pPoint, Point2D* cps, double t) {
  87.     if (pPoint == NULL) return;
  88.  
  89.     double v, vSQ, tSQ, c0, c1, c2, c3;
  90.     v = (1 - t);
  91.     vSQ = SQR(v);
  92.     tSQ = t * t;
  93.     c0 = vSQ * v; //            (1 - t)^3
  94.     c1 = 3 * t * vSQ; //        3 t (1 - t)^2
  95.     c2 = 3 * tSQ * v; //        3 t^2 (1 - t)
  96.     c3 = tSQ * t; //            t^3
  97.  
  98.     // B(t) = P0 (1 - t)^3 + 3 P1 t (1 - t)^2 + 3 P2 t^2 (1 - t) + P3 t^3;
  99.  
  100.     pPoint -> x = cps[0].x * c0 + cps[1].x * c1 + cps[2].x * c2 + cps[3].x * c3;
  101.     pPoint -> y = cps[0].y * c0 + cps[1].y * c1 + cps[2].y * c2 + cps[3].y * c3;
  102. }
  103.  
  104. int main() {
  105.     // pts = {{-31, -33}, {30, -36}, {-25, 28}, {33, 6}};
  106.     Point2D cps[] = {
  107.         {-31, -33},
  108.         {30, -36},
  109.         {-25, 28},
  110.         {33, 6}
  111.     };
  112.  
  113.     // 计算并输出曲线的全长
  114.     double bl;
  115.     bl = BezierDegree3_Length(cps);
  116.     printf("BezierDegree3_Length is %f\n", bl);
  117.  
  118.     int i, numOfParts = 20;
  119.     double t;
  120.     Point2D pps[numOfParts + 1]; // 用于存储分点坐标
  121.  
  122.     printf("弧长等分点\n");
  123.     for (i = 0; i <= numOfParts; i++) {
  124.         t = get_t_of_BezierDegree3_Equal_parts(cps, i, numOfParts);
  125.         PointOnCubicBezier(pps + i, cps, t);
  126.         printf("%d, %f, {%f, %f}\n", i, t, (pps + i)->x, (pps + i)->y);
  127.     }
  128.  
  129.     printf("t 线性分点\n");
  130.     for (i = 0; i <= numOfParts; i++) {
  131.         t = (double) i / numOfParts;
  132.         PointOnCubicBezier(pps + i, cps, t);
  133.         printf("%d, %f, {%f, %f}\n", i, t, (pps + i)->x, (pps + i)->y);
  134.     }
  135.  
  136.     return 0;
  137. }


运行输出

Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. BezierDegree3_Length is 92.896940
  2. 弧长等分点
  3. 0, 0.000000, {-31.000000, -33.000000}
  4. 1, 0.026000, {-26.473223, -33.100813}
  5. 2, 0.056000, {-21.803112, -32.900533}
  6. 3, 0.090000, {-17.181859, -32.293437}
  7. 4, 0.129000, {-12.692476, -31.144602}
  8. 5, 0.175000, {-8.405203, -29.239359}
  9. 6, 0.227000, {-4.712460, -26.475325}
  10. 7, 0.284000, {-1.850744, -22.848809}
  11. 8, 0.343000, {0.068124, -18.613653}
  12. 9, 0.402000, {1.204749, -14.075212}
  13. 10, 0.460000, {1.833144, -9.500808}
  14. 11, 0.519000, {2.253196, -4.918588}
  15. 12, 0.583000, {2.785189, -0.247070}
  16. 13, 0.653000, {3.872591, 4.229112}
  17. 14, 0.733000, {6.350148, 8.141665}
  18. 15, 0.807000, {10.399117, 10.227684}
  19. 16, 0.864000, {15.030105, 10.588897}
  20. 17, 0.907000, {19.565813, 10.029625}
  21. 18, 0.943000, {24.141002, 8.952093}
  22. 19, 0.973000, {28.544624, 7.596929}
  23. 20, 1.000000, {33.000000, 6.000000}
  24. t 线性分点
  25. 0, 0.000000, {-31.000000, -33.000000}
  26. 1, 0.050000, {-22.691375, -32.966625}
  27. 2, 0.100000, {-15.951000, -32.043000}
  28. 3, 0.150000, {-10.607125, -30.343875}
  29. 4, 0.200000, {-6.488000, -27.984000}
  30. 5, 0.250000, {-3.421875, -25.078125}
  31. 6, 0.300000, {-1.237000, -21.741000}
  32. 7, 0.350000, {0.238375, -18.087375}
  33. 8, 0.400000, {1.176000, -14.232000}
  34. 9, 0.450000, {1.747625, -10.289625}
  35. 10, 0.500000, {2.125000, -6.375000}
  36. 11, 0.550000, {2.479875, -2.602875}
  37. 12, 0.600000, {2.984000, 0.912000}
  38. 13, 0.650000, {3.809125, 4.054875}
  39. 14, 0.700000, {5.127000, 6.711000}
  40. 15, 0.750000, {7.109375, 8.765625}
  41. 16, 0.800000, {9.928000, 10.104000}
  42. 17, 0.850000, {13.754625, 10.611375}
  43. 18, 0.900000, {18.761000, 10.173000}
  44. 19, 0.950000, {25.118875, 8.674125}
  45. 20, 1.000000, {33.000000, 6.000000}
上次由 24game 在 2016年10月06日 20:35,总共编辑 1 次。

头像
523066680
Administrator
Administrator
帖子: 333
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 29 times
Been thanked: 22 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #18 523066680 » 2016年10月06日 20:09

24game 写了:等分3阶曲线的数值积分函数


感谢分享,代码先拿来用了,效率不错
图片

happy886rr
渐入佳境
渐入佳境
帖子: 45
注册时间: 2016年09月27日 16:11
拥有现金: 锁定
储蓄: 锁定
Has thanked: 14 times
Been thanked: 14 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #19 happy886rr » 2016年10月06日 20:52

24game 写了:等分3阶曲线的数值积分函数

get_t_of_BezierDegree3_Equal_parts函数写的好,很精彩!

happy886rr
渐入佳境
渐入佳境
帖子: 45
注册时间: 2016年09月27日 16:11
拥有现金: 锁定
储蓄: 锁定
Has thanked: 14 times
Been thanked: 14 times
联系:

Re: 多段Bézier曲线变换效果

帖子 #20 happy886rr » 2016年10月06日 20:56

523066680 写了:效率不错

看图很低像DNA双螺旋,有空你写个DNA螺旋屏保吧,一定超火。骇客帝国数码雨、分形三角、贝兹曲线、再加个DNA双螺旋。你的作品集就完美了O(∩_∩)O~


回到 “OpenGL”

在线用户

用户浏览此论坛: 没有注册用户 和 0 访客