粒子动力学

6

我正在对3D空间中的粒子进行建模。

Particle Interpolation

{0} 粒子从已知位置P0和速度V0开始运动,起始时间为t0。速度是使用其在t-1时刻的已知先前位置P-1计算出来的。

{1} 粒子被定向到在t1时刻以已知速度V1到达P1。

{..} 粒子尽可能快地移动,不会出现抖动(C1连续),受一组约束限制,这些约束单独夹紧沿x、y和z方向的加速度。最大沿x、y和z方向的加速度/减速度是已知的,并且分别为Xa、Ya和Za。沿x、y和z方向加速度的最大变化率由Xr、Yr和Zr定义。

{n} 在未知的时间步数后,它以速度Vn在某个时间(称为tn)到达Pn。

{n+1} 它将在tn+1时刻移动到Pn+1。

我的问题是计算从P0到Pn的最短转换时间,并生成其中间位置和速度方向。次要目标是平稳加速,而不是应用导致抖动的加速度。

当前方法:

  1. 找到需要花费最长时间从起点P0到终点Pn对齐的尺寸{x、y或z}。这将是关键的尺寸,并决定了总时间。这相当简单,我可以编写一些类似的代码。

  2. 在所有尺寸上平滑插值,从P0到Pn,使得Pn处的速度符合预期,而不会出现抖动。我不确定如何解决这个问题。

任何已经执行此操作的输入/物理引擎都将非常有用。这是一个商业项目,我不能在其上添加具有限制性许可证的大型第三方库的依赖项。

注意:P0和Pn处的粒子几乎没有加速度。


2
你有研究过变分法吗?它可以用来解决类似的问题。 - c2huc2hu
1
那么,如果初始状态已知,并且速度/加速度是从先前的状态计算出来的,路径是否就是100%确定的呢?如果是这样,你如何定义“最小”时间?此外,如果时间步数未知,你怎么知道Pn - meowgoesthedog
1
@meowgoesthedog 加速度不是由先前的状态确定的。 - Nelfeal
1
这里中间位置显然是未知的。据我理解,问题是找到每个点的加速度,以便从(P0,V0)到(Pn,Vn)的最短路径。 - Nelfeal
1
@Ram,我在动力学课程中学习了基础知识。不幸的是,由于该课程大多数内容都是在黑板上讲解,所以我没有相关链接。维基百科提供了一个不错的概述,但没有关于如何实现它的内容。 - c2huc2hu
显示剩余13条评论
3个回答

5
如果我理解正确,您有一个点(P0,V0),其中V0 = P0-P-1,以及一个点(Pn,Vn),其中Vn = Pn-Pn-1 ,您希望通过调整每个时间步长的加速度来找到最少的中间点。
让我们定义ti时刻的加速度:Ai = Vi-Vi-1,其中abs(Ai)<= mA。在这里,由于问题与轴无关,abs是成员绝对值而不是范数(或向量大小),mA是最大加速度向量,在每个维度上为正。我们还需要考虑Pn> P0(逐成员)。
从中,我们得到Vi = Vi-1 + Ai,因此Pi = Pi-1 + Vi-1 + Ai
如果您需要以尽可能快的方式从某个点到达另一个点,则无论初始速度如何,显然要做的事情是尽可能加速直到达到目标。但是,由于您的问题是离散的,并且具有终端速度Vn,因此使用该方法可能会导致太远并具有不同的终端速度。
但是,您可以从终点开始相反地做同样的事情。如果同时从两个点开始,您将在每个维度上交叉两条路径(不一定在3D中交叉,但是在每个维度中,两条路径的相对方向在某些“交叉”点处发生变化)。
让我们以一维示例为例。(P0,V0)=(0,-2)(Pn,Vn)=(35,-1) mA = 1
第一条路径,其中Ai = mA,如下所示:
(0, -2) -> (-1, -1) -> (-1, 0) -> (0, 1) -> (2, 2) ->
(5, 3) -> (9, 4) -> (14, 5) -> (20, 6) -> (27, 7) -> ...

第二条路径是相反的,Ai = -mA,步骤如下:
(35, -1) <- (36, 0) <- (36, 1) <- (35, 2) <- (33, 3) <-
(30, 4) <- (26, 5) <- (21, 6) <- (15, 7) <- ...

你可以看到路径在20和21之间以相同的速度交叉。这给出了你需要的最快加速和减速部分的路径,但这两个部分并不连通。但是,通过找到相同速度的最近点,很容易将它们连接起来;让我们称这些点为PqPr。在这里,Pq = (20,6)Pr = (21,6)。由于该速度是在当前点和上一个点之间计算的,因此取Pq之前的点(例如示例中的Pq-1(14,5))和点Pr,并尝试连接它们。
如果Pq >= Pr >= Pq - 2mA,则可以直接通过保持Pq-1不变,并使用 Vr = Pr - Pq-1 连接Pr
否则,取Pq-2Pr-1(其中Vr-1 = Vr - mA,因为它是反向的),并尝试通过添加中间点连接它们。由于这些点具有 mA 的速度差异,因此您可以仅搜索速度相同的中间点 Vs,使得 Vq-2 <= Vs <= Vr-1
如果仍然找不到解决方案,则取Pq-3Pr-2并使用更多中间点重复该过程。
在我所取的示例中,Pq < Pr,因此我们必须尝试Pq-2 = (9,4)Pr-1 = (26,5)。我们可以使用3个点的序列连接这些点,例如(9,4) -> (13,4) -> (17,4) -> (21,4) -> (26,5)
无论如何,这种方法将为您提供最少的中间点数量,这意味着P0Pn之间的最快路径。
如果您想减少 jerk ,则可以忘记先前计算的点,并对您现在知道的 最小数量的点进行插值。

是的。然而,您可以通过缩小每个点的速度来轻松地在特定维度上添加更多点。或者只需使用该方法获取点数并进行插值即可。 - Nelfeal
尝试过这个方法,但结果并不如预期。该方法即使在不需要的情况下也会以最高允许速率加速和减速所有维度。此外,在终点处,速度伴随着最大加速度出现,将该加速度从最大值降至0是不可行的。 - Ram
1
那么你需要更清楚地定义你的问题。你没有提到最后一个要求。 - Nelfeal
1
除非你想让加速度有些连续,否则这不是问题。如果 Vn 接近所需的 Vn+1,那么将 An+1 设为接近零的值可以实现位置和速度方面的终止条件。如果你不能从 An = -mA 转移到 An+1 ≈ 0,那么你的问题描述中可能缺少某种限制条件。是否有一个跃度值的限制?这将对离散点产生“连续”的加速度。 - Nelfeal
1
你的答案产生了一个非常不连贯的中间点集,与我想要的相差甚远。由于我从实施这种方法中理解到了我想要的东西,所以我会给你的答案点赞。但它仍然不是我想要的方法。我已经更新了问题并表达了我的理解。 - Ram
显示剩余3条评论

3
在尝试了一些想法后,我提出了另一个解决方案,比我之前的答案更准确,可能更快,如果正确执行的话。然而,这相当复杂,需要相当多的数学,虽然不是非常复杂的数学。此外,这还在进行中:我仍在研究一些领域。尽管如此,从我所尝试的来看,它已经产生了非常好的结果。
问题
定义和目标
在本答案中,“p [n]”指第n个点的位置,“v [n]”指其速度,“a [n]”指其加速度,“j [n]”指其急加速度(加速度的导数)。第n个点的速度仅取决于其位置和上一个点的位置。同样对于加速度和急加速度,但是分别使用点的速度和加速度。
我们有起点和终点,分别为p[0]p[n],它们都带有关联速度v[0]v[n]。目标是在它们之间放置n-1个点,其中n是任意的,使得在X、Y和Z轴上,这些点(以及p[n])的加速度和极限值分别低于一些限制,分别为加速度的aMaxXaMaxYaMaxZ,以及抖动的jMaxXjMaxYjMaxZ的绝对值。
我们想要找到所有i∈[1; n-1]p[i]的值。因为p[i] = p[i-1] + v[i],所以这等同于找到v[i]。同样的推理,有v[i] = v[i-1] + a[i]a[i] = a[i-1] + j[i],这也等同于找到a[i]j[i]

a[0]a[n+1]被假定为零。

观察和简化

由于问题的限制与维度无关,我们可以分别解决每个维度的问题,只要在每种情况下获得的点数相同。因此,我只会使用aMaxjMax来解决问题的一维版本,而不考虑轴。

* [WIP] * 确定要先解决的最坏情况,然后解决其他情况,知道点数。

这两个给定点的实际位置并不重要,重要的是它们之间的相对距离,我们可以将其定义为 P = p[n] - p[0]。同时,让我们定义区间为R = [1; n]R* = [1; n+1]

由于问题的离散性质,我们可以得到以下等式。请注意,∑{i∈R}(x[i])是所有i∈Rx[i]的总和。

Ⓐ ∑{i∈R}(v[i]) = P
Ⓑ ∑{i∈R}(a[i]) = v[n] - v[0]
Ⓧ ∑{i∈R*}(j[i]) = 0

Ⓧ源于假设a[0] = a[n+1] = 0
通过Ⓐ和v[i] = v[i-1] + a[i], i∈R,我们可以推断:

Ⓒ ∑{i∈R}((n+1-i)*a[i]) = P - n*v[0]

通过同样的逻辑,从 Ⓑ、Ⓒ 和 a[i] = a[i-1] + j[i], i∈R,我们可以推断出:
Ⓨ ∑{i∈R}((n+1-i)*j[i]) = v[n] - v[0]
Ⓩ ∑{i∈R}(T[n+1-i]*j[i]) = P - n*v[0]

在此,T[n]是第n个三角形数,由T[n] = n*(n+1)/2定义。
方程式 Ⓧ、Ⓨ和Ⓩ是接下来部分的相关方程式。
方法:
为了将n最小化,我们可以从一个较小的值(1、2?)开始寻找解决方案。然后,如果max{i∈R}(abs(a[i])) > aMaxmax{i∈R}(abs(j[i])) > jMax,我们可以递增n并重复这个过程。
* [WIP] * 查找n的下限,以避免从较小的n值进行不必要的计算。或者估算正确的n值,并通过测试解决方案来确定它。
寻找解决方案需要找到所有i∈R*j[i]的值。我尚未找到j[i]的最佳形式,但定义j*[i]r[i]s[i],使得
j[i] = j*[i] + r[i]v[0] + s[i]v[n]
效果很好。

*[WIP]* 寻找更好的j[i]形式

通过这样做,我们将n-1个未知数(j[i], i∈R, 注意j[n+1] = -∑{i∈R}(j[i]))转化为3(n-1)个更易于找到的未知数。现在,我们可以从Ⓧ、Ⓨ和Ⓩ中推断出一些东西。

∑{i∈R*}(r[i]) = 0
∑{i∈R*}(s[i]) = 0
∑{i∈R}((n+1-i)*r[i]) = -1
∑{i∈R}((n+1-i)*s[i]) = 1
∑{i∈R}(T(n+1-i)*r[i]) = -n
∑{i∈R}(T(n+1-i)*s[i]) = 0

作为提醒,这里有Ⓧ、Ⓨ和Ⓩ。
Ⓧ ∑{i∈R*}(j[i]) + j[n+1] = 0
Ⓨ ∑{i∈R}((n+1-i)*j[i]) = v[n] - v[0]
Ⓩ ∑{i∈R}(T[n+1-i]*j[i]) = P - n*v[0]

现在的目标是找到足够的特殊情况来帮助我们确定这些未知数。

特殊情况

v[0] = v[n] = 0

通过尝试不同的加速度值,我发现将j[i], i∈R*全部作为抛物线的一部分可以极大地减少加速度和加加速度。虽然这不是最佳拟合,但我还没有找到更好的方法。

把加速度值看作抛物线的直觉是,如果位置的值要遵循一个多项式,那么它的次数必须至少为5,可以是5。如果你考虑速度值遵循一个4次多项式的情况,这会更容易理解。设置了v[0]v[n]的约束条件,以及a[0] = a[n+1] = 0,并且它在[0; n]上的积分必须等于P,这个多项式必须至少有4次。这适用于连续和离散的情况。最后,似乎选择最小的次数可以使加速度更平稳,并且更容易计算。

这是一个连续案例的示例,其中位置用紫色表示,速度用蓝色表示,加速度用黄色表示,而加加速度则用红色表示。

Example curves for position, velocity, acceleration, and jerk

如果您想尝试一下,以下是如何根据np[0]p[n]v[0]v[n](其他的只是导数)来定义位置曲线。
a = (-3(v[n]+v[0]) + 6(p[n]-p[0])) / n^5
b = (n(7v[n]+8v[0]) - 15(p[n]-p[0])) / n^4
c = (-n(4v[n]+6v[0]) + 10(p[n]-p[0])) / n^3
p[x] = ax^5 + bx^4 + cx^3 + v[0]x + p[0]

如果v[0] = v[n] = 0,那么j[i] = j*[i], i∈R*。这意味着j*[i]的值遵循二次多项式。因此,我们想要找到αβγ,使得Ⓟ成立。
Ⓟ j*[i] = αi^2 + βi + γ, i∈R*

从 Ⓧ、Ⓨ 和 Ⓩ 中,按照以下方程式。

α*∑{i∈R*}(i^2) + β*∑{i∈R*}(i) + c*∑{i∈R*}(1) = 0
α*∑{i∈R}((n+1-i)*i^2) + β*∑{i∈R}((n+1-i)*i) + c*∑{i∈R}(n+1-i) = 0
α*∑{i∈R}(T(n+1-i)*i^2) + β*∑{i∈R}(T(n+1-i)*i) + c*∑{i∈R}(T(n+1-i)) = P

解决这个系统可以得到 αβγ,它们可以与 Ⓟ 一起用于计算 j*[i], i∈R*。请注意,j*[i] = j*[n+2-i],因此只需要完成计算的上半部分。
如果 v[0] = v[n] = 1/n,那么 j[i] = 0, i∈R*。这意味着 Ⓠ 成立。
Ⓠ r[i] + s[i] = -n*j[i], i∈R*

v[0] = 0, j[i∈L] = J, j[h] = 0, j[i∈U] = -J

LU分别是R*的下半部分和上半部分,如果n+1为奇数,则h为中间值。换句话说:

if n is odd:
L = [1; (n+1)/2]
U = [(n+3)/2; n+1]
if n is even:
L = [1; n/2]
h = n/2+1
U = [n/2+2; n]

这种特殊情况对应于在最小化abs(j[i]), i∈R*的同时,p[0]p[n]之间的最大总加速度。 在这里,Ⓩ给出了以下方程式。
∑{i∈R}(T[n+1-i]*j[i]) = P
∑{i∈L}(T[n+1-i])*j[1] + ∑{i∈U}(T[n+1-i])*j[n+1] = P
j[1] = P / [ ∑{i∈L}(T[n+1-i]) - ∑{i∈U}(T[n+1-i]) ]

这给出了j[1],因此对于每个j[i],i∈R*都是如此。然后我们可以使用Ⓨ计算v[n]

将各个部分组合在一起

每个特殊情况都为某些v[0]v[n]P的值提供了一个形式为
αj*[i] + βr[i] + γs[i] = δ的关系。
通过处理三种特殊情况(假设它们不相似,即它们不会给出相同的关系),我们得到了一个包含三个方程的系统,一旦解决,就可以为所有i∈R*j*[i]r[i]s[i]的值提供解决方案。

作为结果,我们可以针对每个n的值计算j[i]的值,这取决于v[0]v[n]P。它们可以预先计算,这意味着对于任何n的值进行测试都可以非常快速地完成。因此,只要我们预先计算了到足够大的n值的值,我们就可以非常快速地找到轨迹所需的最少点数的良好估计,以及最佳轨迹的良好近似。

1

答案

我建议您采用以下函数:

X(n) = Xstart + Vxstart n+ (-6xstart+3Vxstart+6xend-3Vxend+c/2) n^2 + (8xstart+3Vxstart-8xend+5Vxend-c) n^3 + (-3Xstart-Vxstart+3xend-2Vxend+c/2) n^4

(对于每个坐标X,Y,Z)

这里是一些图表,展示了这个函数的效果,我为每个样本取了c=3:

对于xstart=1,vstart=1,xend=3,vstart=-2,这给出:

X(n)= 1 + n + 16 n^2 -25 n^3 + 10 n^4

enter image description here

对于xstart=-4,vstart=-4,xend=4,vend=0,这将得到: (-4-4n+61n^2-78n^3+29yn^4)

enter image description here

其中c是从0.1到5的一个数字,由您决定,c越高,函数到达该点的速度就越快(但如果c>4,则可能需要返回)。 (请参见下面的图表)。

多项式来自以下计算:其中a = x0,b = v0,c = xe,d = v2,e =魔法常数

enter image description here

解释

根据Nelfeal的答案,我的想法是尝试用多项式来解决给定的问题。

我们可以将问题改变为定义一个新的轴,该轴沿着P[last]-P[0]走,从而将问题降低到1维。

我们可以将问题看作连续数学而不是离散数学(例如使用函数而不是序列),然后回到离散世界,这只是连续世界的特例。

我们可以更改时间和空间的单位,使时间为1,距离为1,以简化问题:

找到一个函数,满足以下条件:

  1. (0) = 0且(1) = 1
  2. '(0) = 0且'(1) = 0
  3. 对于x∈ℝ |''(x)| < c,其中c是最大速度

我们有

P(X) = ∑{i∈ℕ} Ai Xi

P'(X) = ∑{i∈ℕ} (i+1) Ai+1 Xi

P''(X) = ∑{i∈ℕ} (i+2)(i+1) Ai+2 Xi

我们需要:

  1. P(0) = 0
  2. P(1) = 1
  3. P'(0) = 0
  4. P'(1) = 0
  5. -c <= P''(x) <= c

因此,它的意思是:

a0 = 0(来自1.) a1 = 0(来自3.)

P(1) = ∑{i∈ℕ} Ai = 1

P'(1) = ∑{i∈ℕ} (i+1) Ai = 0

P''(x) = ∑{i∈ℕ} (i+2)(i+1) Ai Xi in [-c,c]

第三个方程式最为复杂,可以简化为P(1)=c。

我们将让c变化以观察变化情况。

在求解3x3矩阵的逆后,得到以下结果:

P(x) = (c/2+6) x^2 - (c+8) x^3 + (c/2+3) x^4

当c=0.15时,结果为:

enter image description here

对于c=1,这样做:

enter image description here

对于c=4,我们看到一个反弹:

enter image description here

如果我们将c从0.1变化到6,我们会得到以下的3D图表:

enter image description here

请注意,我们已经解决了4次多项式的问题,但您可以对更高次数的多项式进行相同的操作(如果您愿意),以获得更多功能的可能性。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接