来自 Web前端 2020-04-29 17:43 的文章
当前位置: 网上澳门金莎娱乐 > Web前端 > 正文

根据贝塞尔曲线上的点反算t值

时间: 2019-09-07阅读: 81标签: 曲线

看这篇文章之前,请确保你有基本的前端知识,知道Canvas最基本的使用方法,知道贝塞尔曲线在CSS3中的使用。本文章忽略了贝塞尔曲线的历史,不了解可自行谷歌百度。

这是一个项目中遇到的实际需求。 场景是一个智能仓库管理系统,场景里面有直线和曲线构成的环穿轨道。环穿轨道上面会有小车运动,后台推动小车的两个点位A和B,其中A和B都会在轨道上面,前端需要根据这两个推送点,自动播放小车从A点沿轨道到B点的动画。下面是项目截图:

三次贝塞尔曲线方程

项目中使用的是二次贝塞尔曲线,所以本文也主要以二次贝塞尔曲线为讲解重点。 要实现上述动画,需要首先确定A点和B点在曲线上面的比例值tsuba/sub和tsubb/sub

先看一下贝塞尔曲线的生成方法

最终的需求变成:“根据贝塞尔曲线上的点反算t值”。 大概有以下几种方法。现假设贝塞尔曲线上的点为点P(后续会用到该点)。

二次贝塞尔曲线

分片迭代

图片 1Quadratic Bezier Curve

分片迭代是一种近似的方法。我们知道,二次贝塞尔曲线的公式如下: B(t) = (1-t)2 * P0 + 2t(1-t) * P1 + t2 * P2 其中: $t in $[0,1],P0为二次贝塞尔曲线的起始点,P1为控制点,P2为终止点。

三次贝塞尔曲线

四次贝塞尔曲线

从以上公式,我们可以得到,对于任意给定的比例值t,可以求出对应该比例值的点B(t)。分片迭代思路是:现在加设把范围[0,1]平均分成N(比如100)等份,形成一系列的比例值t,对于每一个t值,求取对应的点B(t) ,然后让点B(t)和已知在贝塞尔曲线上的点P进行比较,如果点B(t)和点P之间的直线距离在一定的误差范围之内,则认为B(t)等于P,而此时的t值,就是我们要求的t值。 以下是主要代码:

图片 2Cubic Bezier Curve

function computeT(p0,p1,p2,p) { var t = 0; for(var i = 0;i  1000;i ++){ var point = getPointOnQuadraticCurve(p0,p1,p2,t);//根据二次贝塞尔曲线公式求B(t),其中point = B(t) if(distance(point,p)  0.01){ // 判断point和p点的距离是否在特定误差之内 return t; } t+= 0.001; } return null;}

这是二次贝塞尔曲线、三次贝塞尔曲线、以及四次贝塞尔曲线的生成示意图,我们可以用平实的文字总结一下这些图形表达的含义:对于给定的曲线起点与终点以及一系列控制点,分别将起点与第一控制点,第一控制点与第二控制点,以此类推直至最后一个控制点与终点相连,然后分别将这些线段对应的相同比例部分的点相连,记此比例为t,再将这些二次连线上t位置的点相连,依次类推直到不存在第二条线段,最后这条线段t位置上的点就在贝塞尔曲线上,而当t∈[0,1]时这些点的集合就是贝塞尔曲线本身。

上述分片迭代的方法,思路最简单,最直观。在精度要求不高的情况下是可以满足的。而在精度要求高的时候,即代码中的“特定误差”值要很小,可能会出现函数返回值为null的情况,在精度要求高的时候要能够计算出值,就要增加迭代次数,此时会极大增加性能消耗。比如上面代码的迭代次数可能会变成10000甚至10000。

三次贝塞尔曲线就是如此计算的:

迭代方法同样适用于三次贝塞尔曲线和更加高阶的贝塞尔曲线。

 Q0:P0 + t Q1:P1 + t Q2:P2 + t

 A0:Q0 + t A1:Q1 + t

 B = A0 + t

分片迭代优化版本

将所有点换成使用P0P1P2P3的表达式进行化简,即可化简为

上面提到在精度要求高的情况下,要得到正确结果,要极大的增加迭代次数,造成性能的极大消耗。 有没有办法既提高精度,又不大量增加迭代次数呢? 经过笔者的思考,发现是可以的。想想假设要求的t值在0.5附近,那么我们只需要在0.5附近加大分片的数量,而不需要在其他地方(0.1~0.4,0.6~1.0)增加分片的数量。 应此升级版本的思路就是,先用比较粗的分片初步确定t值的一个大致范围,再在该范围之类,比较细的分片确定t值。注意这是个递归的过程,如果在第二次比较细的分片情况下,仍然不能确定t值,那么就确定一个t值的更小分范围;重复上面过程,直到找到t值为止。 大致步骤如下:

B = P0³ + 3P1t² + 3P2t² + P3t³

首先,通过一个小的迭代次数进行分片迭代;在迭代的过程中如果找到了符合的比例值t,直接返回;在迭代的过程中同时记录离目标点P最近的t值,如果上一步未找到符合的t值,则进行下一步操作。上一步找到了离目标点P最近的t值,在t值的附近(t

化简过程涉及到换元,目的是抽象贝塞尔曲线的通用表达式,所以结果不是那么直观,不过这些都是数学细节,感兴趣可以去维基百科,平常接触最多的就是三次贝塞尔曲线,所以我们这里着重探讨的就是特殊的三次贝塞尔曲线而非普遍结论。

  • step,t + step)(其中step为上一次分片的步进值)进行分片迭代查找,在迭代的过程中如果找到了符合的比例值t,直接返回。如果没找到,重复上面的不断缩小范围并加大分片精度的过程。 直到找到t值为止。

这一表达式中的变量t就是我们说的“各条线段上的比例”,在这里我们直接使用了一个字面量来表示一个点,实际上编程时我们会将点分成xy坐标分别进行计算。

下面是示例代码:

图片 3贝塞尔曲线动态生成截图这里我将贝塞尔曲线的生成方法实现成了一个使用canvas绘制的过程例子,你可以直接拖动滑块改变描线速度。

function computeT(p0, p1, p2, p,startT = 0,endT = 1) { var t = startT; var minDistance = Infinity, minDistanceT = null; var step = (endT - startT) / 100; for (var i = 0; i  100; i++) { var point = getPointOnQuadraticCurve(p0, p1, p2, t); var dst = distance(point,p); if (dst  minDistance) { minDistance = dst; minDistanceT = t; } if (dst  0.0001) { return t; } t += step; } return computeT(p0, p1, p2, p, minDistanceT - step,minDistanceT + step);}

给定t拿到运动位置并非难事,因为我们已经有了曲线对应的函数表达式,直接代入参数t即可求得x,y坐标。

以上过程虽然增加了一定的迭代次数,但是是常量级别的增加,而非数量级别的增加,所以会极大提高性能。 比如目标t值在0.5附近,第一次通过100次迭代可以确定t值的范围在0.4 ~ 0.6之间;然后进行第二次迭代,第二次迭代此次数仍然为100次,假设确定t值的范围在0.51 ~ 0.53之间;然后进行第三次迭代,第三次迭代此次数仍然为100次,此时可以获取t值为0.516,可以看出最多值迭代了300次。 假设总共经过第N次迭代,每次迭代次数为M,才找到t值,那么总共的迭代次数是N * M。

比如目前我们希望让物体位于某已知贝塞尔曲线的t位置,则我们需要的位置为

该迭代方法同样适用于三次贝塞尔曲线和更加高阶的贝塞尔曲线。而且相对于未优化的版本,该方法的性能好了很多。是适合所有贝塞尔曲线的比较好的反算t值的方法。

var x = P0x³ + 3P1xt² + 3P2xt² + P3xt³;var y = P0y³ + 3P1yt² + 3P2yt² + P3yt³;// position handler , e.g. // oBox.style.transform = `translate(${x}px,${y}px)`;

二分法

图片 4沿贝塞尔曲线运动截图

二分法的思路是:

这里是Canvas实现的沿着曲线路径运动的圆

首先确定一个起始t值和结束t值tsub0/sub和tsub1/sub,初始值tsub0/sub = 0,tsub1/sub = 1。取tsub0/sub和tsub1/sub的中间值tsubm/sub = (tsub0/sub+tsub1/sub)/2通过tsubm/sub计算出点Psubm/sub,如果Psubm/sub和目标点P之间的距离在误差值范围之内,则tsubm/sub为需要计算的目标t值。如果上一步Psubm/sub和目标点P之间的距离不在误差值范围之内,则判断Psubm/sub和目标点P的前后顺序,如果Psubm/sub在目标点P的前面,则把tsubm/sub赋值给tsub1/sub;否则把tsubm/sub赋值给tsub0/sub。重复以上步骤直到找到合适的tsubm/sub值。

当然,这里我们要注意的是:我们并没有在时间维度控制动画,或者说目前这个沿曲线运动的圆目前能做到的也仅仅是“沿着曲线运动”,我们目前还没有控制它的匀速、加速等速度模式。

上述步骤有一个难点: 如何判断Psubm/sub和目标点P的前后顺序? 对于二次贝塞尔曲线,如下图所示:

想要实现canvas描线动画,首先我们应该知道canvas动画的实现方式:不断的绘制与擦除。既然我们需要的是一个描线动画,那么我们就可以将研究目标转向另一个问题:如何绘制从起始点开始到达三次贝塞尔曲线上给定一点的曲线线段?

其中,P0为起始点,P2为终止点,P1为控制点。 二次贝塞尔曲线有如下特点: 线段(P1,P0)、(P1,P2)和曲线相切,这也就意味着曲线一定在三角形(P0,P1,P2)之内,而且二次贝塞尔曲线本身不会自身相交,所有我们可以有如下结论,

图片 5贝塞尔曲线的截取方法

对于曲线上面的点A,直线(P1,A)和线段(P0,P1)相交于点a;对于曲线上面的点B,直线(P1,B)和线段(P0,P1)相交于点b。点A和点B的先后顺序与点a和点b的先后顺序是一致的,而直线上面的点(a和b)的前后顺序是容易判断的。 也就是说如果点a在点b的前面,则点A也在点B的前面,反之亦然。如下图所示:

实际上,我们已经知道了如何绘制三次贝塞尔曲线:不断运动的点所构成的线,那我们已经知道了t的位置,那实际上就是已经知道了绘制到给定点时对应的Q0,Q1,A0,而Q0A0就是这段贝塞尔曲线的控制点,而B2便是终点值。

本文由网上澳门金莎娱乐发布于Web前端,转载请注明出处:根据贝塞尔曲线上的点反算t值

关键词: