多段Bézier曲线变换效果

TheBooksofShaders ShaderToy
OpenGL Tutorial
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

24game 写了:
做了测试,范围是 X[-250, 250], Y[-250, 250](黄色线框部分) , 把跑过的最远坐标(绝对值)通过终端输出:
rangetest.png
如果不画图,可以跑到 [470, 470] 左右。

作图:
假设上一线段的c,d点刚好坐落在对角线上,为使得新的曲线相对平滑,a,b点线段与其形成对称(在同一条直线上)
新的 d, c 点坐标在[-250, 250] 以内随机取值
attemp.png
(34.42 KiB) 已下载 1691 次
当 d, c 点越来越靠近a点时,曲线的远端越来越接近红色正方形的顶点(但是无法和顶点重合)。
最后还是干脆点,假设a b c d在同一条直线上,且(a c d) 3点重合,b点在距离 a(cd) 100mm的地方,最后形成的线的长度会是多少?
straight100.png
(6.41 KiB) 已下载 1687 次
大致比例 (可能会有一点点偏差)
0.4441
24game
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

用 Mathematica 做了计算
P0 = 0; P1 = 1;
exp2 = P0 (1 - t)^2 + 2 P1 t (1 - t) + P0 t^2 ;
exp3 = P0 (1 - t)^3 + 3 P1 t (1 - t)^2 + 3 P0 t^2 (1 - t) + P0 t^3;
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;

Print["求导"]
D[exp2, t]
D[exp3, t]
D[exp4, t]

Print["求极点 t 值"]
Solve[D[exp2, t] == 0, t]
Solve[D[exp3, t] == 0, t]
Solve[D[exp4, t] == 0, t]

Print["求第一个极点的精确表达式值"]
exp2 /. t -> Solve[D[exp2, t] == 0, t][[1, 1, 2]]
exp3 /. t -> Solve[D[exp3, t] == 0, t][[1, 1, 2]]
exp4 /. t -> Solve[D[exp4, t] == 0, t][[1, 1, 2]]

Print["数值方式求第一个极点的表达式值"]
FindMaximum[exp2, {t, 0.4}]
FindMaximum[exp3, {t, 0.4}]
FindMaximum[exp4, {t, 0.4}]

Plot[exp2, {t, 0, 1}];
Plot[exp3, {t, 0, 1}];
Plot[exp4, {t, 0, 1}];
输出
求导
2 (1 - t) - 2 t
3 (1-t)^2 - 6 (1-t) t
4 (1-t)^3 - 12 (1-t)^2 t

求极点 t 值
{{t -> 1/2}}
{{t -> 1/3}, {t -> 1}}
{{t -> 1/4}, {t -> 1}, {t -> 1}}

求第一个极点的精确表达式值
1/2
4/9
27/64

数值方式求第一个极点的表达式值
{0.5, {t -> 0.5}}
{0.444444, {t -> 0.333333}}
{0.421875, {t -> 0.25}}
图片
图片
图片


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

3 次曲线在 t=1/3 时有极值 4/9 ~= 0.444444444444......
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

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
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

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

曲线弧长用积分计算, 尝试得出长度函数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/
关键代码段截取
/**
* finds the point that is 'distance' along the path from 'location'. this method returns both the x,y location of the point and also
* its 'location' (proportion of travel along the path); the method below - _pointAlongPathFrom - calls this method and just returns the
* point.
*/
var _pointAlongPath = function(curve, location, distance) {
var _dist = function(p1,p2) { return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); },
prev = _pointOnPath(curve, location),
tally = 0,
curLoc = location,
direction = distance > 0 ? 1 : -1,
cur = null;
while (tally < Math.abs(distance)) {
curLoc += (0.005 * direction);
cur = _pointOnPath(curve, curLoc);
tally += _dist(cur, prev);
prev = cur;
}
return {point:cur, location:curLoc};
};

特定形式的 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
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

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

可能那个博主把贝塞尔曲线的文章删了,奇怪
24game
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

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

可能那个博主把贝塞尔曲线的文章删了,奇怪
终于决定把这个博客重新开起来,去年我一次误操作把原来的博客全部删掉了,几乎没有留下任何痕迹
有一些老帖的备份, 但恐怕也残缺
https://web.archive.org/web/20131022094 ... .com/blog/

此扒坟神网 存在也有些年了, 我竟然才知道
https://archive.org/web/
24game
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

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

按弧长等分
图片

按 t 值线性分段
图片

以上图形由 Mathematica 10 绘制, 分点坐标由下文的 C 代码中 PointOnCubicBezier 函数计算得到
Mathematica 10 代码
Needs["Splines`"]

pts = {{-31, -33}, {30, -36}, {-25, 28}, {33, 6}};

pps = {{-31.000000, -33.000000}, {-26.473223, -33.100813}, \
{-21.803112, -32.900533}, {-17.181859, -32.293437}, {-12.692476, \
-31.144602}, {-8.405203, -29.239359}, {-4.712460, -26.475325}, \
{-1.850744, -22.848809}, {0.068124, -18.613653}, {1.204749, \
-14.075212}, {1.833144, -9.500808}, {2.253196, -4.918588}, {2.785189, \
-0.247070}, {3.872591, 4.229112}, {6.350148, 8.141665}, {10.399117,
10.227684}, {15.030105, 10.588897}, {19.565813,
10.029625}, {24.141002, 8.952093}, {28.544624,
7.596929}, {33.000000, 6.000000}};

tps = {{-31.000000, -33.000000}, {-22.691375, -32.966625}, \
{-15.951000, -32.043000}, {-10.607125, -30.343875}, {-6.488000, \
-27.984000}, {-3.421875, -25.078125}, {-1.237000, -21.741000}, \
{0.238375, -18.087375}, {1.176000, -14.232000}, {1.747625, \
-10.289625}, {2.125000, -6.375000}, {2.479875, -2.602875}, {2.984000,
0.912000}, {3.809125, 4.054875}, {5.127000, 6.711000}, {7.109375,
8.765625}, {9.928000, 10.104000}, {13.754625,
10.611375}, {18.761000, 10.173000}, {25.118875,
8.674125}, {33.000000, 6.000000}};
Graphics[{Spline[pts, Bezier],
Point[pts], {RGBColor[1, 0, 0], Point[pps]}}]
Graphics[{Spline[pts, Bezier],
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 值. 仍可优化加速
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define SQR(x) ((x)*(x))
#define EPS (1e-3) /* EPS 积分步长, 一个小正数, 在运算范围内, 此值越小, 积分计算越准确, 但耗时也会越长 */
#define EPS_DIV_2 (EPS / 2)
#define ONE (999999e-6)

/*

3 阶曲线参数方程:
B(t) = P0 (1 - t)^3 + 3 P1 t (1 - t)^2 + 3 P2 t^2 (1 - t) + P3 t^3;

二维平面坐标分量参数方程:
x(t) = P0x (1 - t)^3 + 3 P1x t (1 - t)^2 + 3 P2x t^2 (1 - t) + P3x t^3;
y(t) = P0y (1 - t)^3 + 3 P1y t (1 - t)^2 + 3 P2y t^2 (1 - t) + P3y t^3;


分量微分 (x 分量微分 和 y 分量微分)
-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
-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

弧长微分 = Sqrt( x 分量微分 ^ 2 + y 分量微分 ^ 2 ) (原理为勾股定理, 如果是 3 维或更高维曲线, 则将所有 坐标分量微分的平方 求总和再开方)

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]

*/

typedef struct {
double x;
double y;
}
Point2D;

// 3 阶曲线在 t 处的弧长微分

double BezierDegree3_dL(Point2D* cps, double t) {
// 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 +
// (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);

double v1, v2, v3, v4;
v1 = (-1 + t);
v2 = (-1 + 4 * t - 3 * t * t);
v3 = (cps[0].x * SQR(v1) + t * (-2 * cps[2].x + 3 * cps[2].x * t - cps[3].x * t) + cps[1].x * v2);
v4 = (cps[0].y * SQR(v1) + t * (-2 * cps[2].y + 3 * cps[2].y * t - cps[3].y * t) + cps[1].y * v2);

return 3 * sqrt(SQR(v3) + SQR(v4));
}

// 3 阶曲线的全长 (辛普森积分法)
// Integrate[f(t), {t, a, b}] ~= (f(a)+4*f(m)+f(b)) * (b-a) / 6 ; 其中 m = (a + b) / 2
// 此处积分步长 b-a = EPS

double BezierDegree3_Length(Point2D* cps) {
double a, m, b, bl;
bl = 0;
for (a = 0, m = a + EPS_DIV_2, b = a + EPS; a < ONE; a = b, b += EPS, m += EPS) {
bl += BezierDegree3_dL(cps, a) + 4 * BezierDegree3_dL(cps, m) + BezierDegree3_dL(cps, b);
}
return bl * EPS / 6;
}

// 把曲线等分成 numOfParts 段, 获取曲线上 从 P0 起始, 到全长的 i_of / numOfParts 点处的 t 值
// 例: 曲线被分成 numOfParts = 20 段, 从起点到终点一共 21 个分点;
// i_of = 3, 将返回第 3 个分点 Q (P0~~Q 的弧长 = 曲线全长 * 3 / 20) 处的 t 值

double get_t_of_BezierDegree3_Equal_parts(Point2D* cps, int i_of, int numOfParts) {
double a, m, b, bl, len;

if (i_of <= 0 || numOfParts <= 0) return 0;
if (i_of >= numOfParts) return 1;

// 要达到的长度
len = BezierDegree3_Length(cps) * i_of / numOfParts * 6 / EPS;

bl = 0;
for (a = 0, m = a + EPS_DIV_2, b = a + EPS; a < ONE; a = b, b += EPS, m += EPS) {
bl += BezierDegree3_dL(cps, a) + 4 * BezierDegree3_dL(cps, m) + BezierDegree3_dL(cps, b);
if (bl >= len) return a;
}
return 1;
}

// 返回由控制点集 cps 确定的曲线上, t 处的坐标, 结果存储在 pPoint 指向的二维坐标组中

void PointOnCubicBezier(Point2D* pPoint, Point2D* cps, double t) {
if (pPoint == NULL) return;

double v, vSQ, tSQ, c0, c1, c2, c3;
v = (1 - t);
vSQ = SQR(v);
tSQ = t * t;
c0 = vSQ * v; // (1 - t)^3
c1 = 3 * t * vSQ; // 3 t (1 - t)^2
c2 = 3 * tSQ * v; // 3 t^2 (1 - t)
c3 = tSQ * t; // t^3

// B(t) = P0 (1 - t)^3 + 3 P1 t (1 - t)^2 + 3 P2 t^2 (1 - t) + P3 t^3;

pPoint -> x = cps[0].x * c0 + cps[1].x * c1 + cps[2].x * c2 + cps[3].x * c3;
pPoint -> y = cps[0].y * c0 + cps[1].y * c1 + cps[2].y * c2 + cps[3].y * c3;
}

int main() {
// pts = {{-31, -33}, {30, -36}, {-25, 28}, {33, 6}};
Point2D cps[] = {
{-31, -33},
{30, -36},
{-25, 28},
{33, 6}
};

// 计算并输出曲线的全长
double bl;
bl = BezierDegree3_Length(cps);
printf("BezierDegree3_Length is %f\n", bl);

int i, numOfParts = 20;
double t;
Point2D pps[numOfParts + 1]; // 用于存储分点坐标

printf("弧长等分点\n");
for (i = 0; i <= numOfParts; i++) {
t = get_t_of_BezierDegree3_Equal_parts(cps, i, numOfParts);
PointOnCubicBezier(pps + i, cps, t);
printf("%d, %f, {%f, %f}\n", i, t, (pps + i)->x, (pps + i)->y);
}

printf("t 线性分点\n");
for (i = 0; i <= numOfParts; i++) {
t = (double) i / numOfParts;
PointOnCubicBezier(pps + i, cps, t);
printf("%d, %f, {%f, %f}\n", i, t, (pps + i)->x, (pps + i)->y);
}

return 0;
}
运行输出
BezierDegree3_Length is 92.896940
弧长等分点
0, 0.000000, {-31.000000, -33.000000}
1, 0.026000, {-26.473223, -33.100813}
2, 0.056000, {-21.803112, -32.900533}
3, 0.090000, {-17.181859, -32.293437}
4, 0.129000, {-12.692476, -31.144602}
5, 0.175000, {-8.405203, -29.239359}
6, 0.227000, {-4.712460, -26.475325}
7, 0.284000, {-1.850744, -22.848809}
8, 0.343000, {0.068124, -18.613653}
9, 0.402000, {1.204749, -14.075212}
10, 0.460000, {1.833144, -9.500808}
11, 0.519000, {2.253196, -4.918588}
12, 0.583000, {2.785189, -0.247070}
13, 0.653000, {3.872591, 4.229112}
14, 0.733000, {6.350148, 8.141665}
15, 0.807000, {10.399117, 10.227684}
16, 0.864000, {15.030105, 10.588897}
17, 0.907000, {19.565813, 10.029625}
18, 0.943000, {24.141002, 8.952093}
19, 0.973000, {28.544624, 7.596929}
20, 1.000000, {33.000000, 6.000000}
t 线性分点
0, 0.000000, {-31.000000, -33.000000}
1, 0.050000, {-22.691375, -32.966625}
2, 0.100000, {-15.951000, -32.043000}
3, 0.150000, {-10.607125, -30.343875}
4, 0.200000, {-6.488000, -27.984000}
5, 0.250000, {-3.421875, -25.078125}
6, 0.300000, {-1.237000, -21.741000}
7, 0.350000, {0.238375, -18.087375}
8, 0.400000, {1.176000, -14.232000}
9, 0.450000, {1.747625, -10.289625}
10, 0.500000, {2.125000, -6.375000}
11, 0.550000, {2.479875, -2.602875}
12, 0.600000, {2.984000, 0.912000}
13, 0.650000, {3.809125, 4.054875}
14, 0.700000, {5.127000, 6.711000}
15, 0.750000, {7.109375, 8.765625}
16, 0.800000, {9.928000, 10.104000}
17, 0.850000, {13.754625, 10.611375}
18, 0.900000, {18.761000, 10.173000}
19, 0.950000, {25.118875, 8.674125}
20, 1.000000, {33.000000, 6.000000}
上次由 24game 在 2016年10月06日 20:35,总共编辑 1 次。
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

24game 写了:等分3阶曲线的数值积分函数
感谢分享,代码先拿来用了,效率不错
图片
happy886rr
渐入佳境
渐入佳境
帖子: 45
注册时间: 2016年09月27日 16:11
联系:

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

帖子 happy886rr »

24game 写了:等分3阶曲线的数值积分函数
get_t_of_BezierDegree3_Equal_parts函数写的好,很精彩!
happy886rr
渐入佳境
渐入佳境
帖子: 45
注册时间: 2016年09月27日 16:11
联系:

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

帖子 happy886rr »

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

在线用户

正浏览此版面之用户: 没有注册用户 和 0 访客