从 3D 三次贝塞尔路径获得一致的法线 [英] Getting consistent normals from a 3D cubic bezier path

问题描述

我正在编写一个包含 BezierPoints 列表的 BezierPath 类.每个 BezierPoint 都有一个位置、一个 inTangent 和一个 outTangent:

BezierPath 包含用于从路径获取线性位置和切线的函数.我的下一步是提供从路径中获取法线的功能.

我知道 3D 中任何给定的线都会有无限多的垂直线，所以不会有固定的答案.

我的目标是让用户能够在每个 BezierPoint 指定法线(或滚动角?)，我将在它们之间进行插值以获得沿路径的法线.我的问题是我不知道如何选择起始切线(默认切线应该是什么?).

我第一次尝试获取起始切线是使用 Unity3D 方法 :

function computeBezierDerivative (t,a,b,c,d) {a = 3*(b−a)b = 3*(c-b)c = 3*(d-c)返回 a * (1-t)² + 2 * b * (1-t) * t + c * t²}

完成.计算导数非常简单(贝塞尔曲线的奇妙特性).

现在，为了获得法线，我们需要取某个值 t 处的归一化切向量，并将其旋转四分之一圈.我们可以在很多方向上转动它，所以进一步的限制是我们只想在由切向量定义的平面上转动它，切向量紧邻它"，相距无穷小.

任何贝塞尔曲线的切向量都是通过采用您拥有的多维数据并分别评估它们来形成的，因此对于 3D 曲线:

<代码> |computeBezierDerivative(t, x values) ||x'|切线(t) = |computeBezierDerivative(t, y 值) |=>|y'||computeBezierDerivative(t, z 值) ||z'|

同样，计算起来非常简单.为了归一化这个向量(或实际上任何向量)，我们只需对其长度进行向量除法:

<代码> |x'|NormalTangent(t) = |y'|除以 sqrt(x'² + y'² + z'²)|z'|

所以让我们把它们画成绿色:

现在唯一的技巧是找到旋转切线向量的平面，将切线变成法线.我们知道我们可以使用任意接近我们想要的值的另一个 t 值，并将其转换为该死在同一点附近的第二个切向量，以找到具有任意正确性的平面，因此我们可以这样做:

给定一个原始点 f(t1)=p 我们取一个点 f(t2)=q 和 t2=t1+e，其中 e 是一些像 0.001 这样的小值——这个点 q 有一个导数 q' = pointDerivative(t2)，并且为了为了让我们更轻松，我们将切线向量移动 pq 一点点，这样两个向量都开始"在 p 处.很简单.

然而，这等效于计算 p 处的一阶和二阶导数，然后通过将这两者相加来形成第二个向量，因为二阶导数给了我们在 a 处的切线的变化点，因此将二阶导数向量与一阶导数向量相加得到平面中 p 处的两个向量，而无需找到相邻点.这在导数中存在不连续性的曲线中很有用，即具有尖点的曲线.

我们现在有两个向量，从同一个坐标出发:我们的实切线和下一个"点的切线，它们非常接近以至于可能是同一个点.值得庆幸的是，由于贝塞尔曲线的工作方式，第二条切线永远不相同，但略有不同，我们只需要略有不同":如果我们有两个归一化向量，从同一点开始但是指向不同的方向，我们可以通过 ，而四分之一圈的特殊之处在于它们极大地简化了数学:在我们的旋转轴c上旋转一个点，旋转矩阵变成:

<代码> |c₁² c₁*c₂ - c₃ c₁*c₃ + c₂ |R = |c₁*c₂ + c₃ c₂² c₂*c₃ - c₁ ||c₁*c₃ - c₂ c₂*c₃ + c₁ c₃² |

其中 1、2 和 3 下标实际上只是我们向量的 x、y 和 z 分量.所以这仍然很容易，剩下的就是矩阵旋转我们的归一化切线:

n = R * 切线T"

是:

<代码> |T₁ * R₁₁ + T₂ * R₁₂ + T₃ * R₁₃ ||nx|n = |T₁ * R₂₁ + T₂ * R₂₂ + T₃ * R₂₃ |=>|纽约||T₁ * R₃₁ + T₂ * R₃₂ + T₃ * R₃₃ ||nz|

我们有我们需要的法线向量.完美！

除非我们可以做得更好:因为我们不是使用任意角度而是使用直角，所以我们可以使用一个重要的捷径.与向量 c 垂直于两条切线一样，我们的法线 n 垂直于 c 和正切线，所以我们可以再次使用叉积来找到正态:

 |nx|n = c × tangent₁ =>|纽约||nz|

这将为我们提供完全相同的向量，而且工作量更少.

如果我们想要内部法线，它是相同的向量，只需乘以 -1:

一旦你知道了技巧，就很容易了！最后，因为代码总是有用的.

使用普通的编程语言(例如 Java/Processing)来实现他们的 9 行算法需要做更多的工作:

ArrayListgetRMF(整数步){ArrayList帧 = 新的 ArrayList();双 c1, c2, step = 1.0/steps, t0, t1;PointVector v1、v2、riL、tiL、riN、siN；矢量帧 x0, x1;//从标准切线/轴/法线框架开始//与刚好在贝塞尔区间之前的曲线相关联.t0 = -步；frame.add(getFrenetFrame(t0));//开始构建 RM 帧for (; t0 <1.0; t0 += step) {//从前一个已知帧开始x0 = frame.get(frames.size() - 1);//获取下一帧:我们将扔掉它的轴和法线t1 = t0 + 步长；x1 = getFrenetFrame(t1);//首先我们将 x0 的切线和轴反射到 x1 上，通过//中点 x0--x1 处的反射平面v1 = x1.o.减(x0.o)；c1 = v1.dot(v1);riL = x0.r.minus(v1.scale(2/c1 * v1.dot(x0.r)));tiL = x0.t.minus(v1.scale(2/c1 * v1.dot(x0.t)));//然后我们在 x1 处的平面上进行第二次反射//使框架切线与曲线切线对齐:v2 = x1.t.minus(tiL);c2 = v2.dot(v2);riN = riL.minus(v2.scale(2/c2 * v2.dot(riL)));siN = x1.t.cross(riN);x1.n = siN;x1.r = riN;//我们记录那个帧，然后继续帧.添加(x1)；}//在我们返回之前，我们扔掉了第一帧，//因为它位于贝塞尔区间之外.删除(0)；返回帧；}

不过，这真的很好用.请注意 Frenet 框架是标准"切线/轴/法线框架:

VectorFrame getFrenetFrame(double t) {PointVector origin = get(t);PointVector tangent = 导数.get(t).normalise();PointVector normal = getNormal(t).normalise();返回新的 VectorFrame(原点、切线、法线)；}

对于我们的平面曲线，我们现在可以看到完美的法线:

并且在非平面曲线中，旋转最小:

最后，这些法线可以通过围绕相关切向量旋转所有向量来统一重新定向.

I'm writing a BezierPath class that contains a list of BezierPoints. Each BezierPoint has a position, an inTangent and an outTangent:

BezierPath contains functions for getting linear positions and tangents from the path. My next step is to provide functionality for getting the normals from the path.

I'm aware that any given line in 3D is going to have an unlimited number of lines that are perpendicular, so there isn't going to be a set answer.

My aim is for the user to be able to specify normals (or a roll angle?) at each BezierPoint which I will interpolate between to get normals along the path. My problem is that I don't know how to choose a starting tangent (what should the default tangent be?).

My first attempt at getting the starting tangents is using the Unity3D method Quaternion.LookRotation:

Quaternion lookAt = Quaternion.LookRotation(tangent);
Vector3 normal = lookAt * Vector3.up;
Handles.DrawLine(position, position + normal * 10.0f);

This results in the following (green lines are tangents, blue are normals):

For the most part this seems like a good base result, but it looks like there are sudden changes in certain orientations:

So my question is: Is there a good way for getting consistent default normals for lines in 3D?

Thanks, Ves

解决方案

Getting the normal for a point on a Bezier curve is actually pretty straight forward, as normals are simply perpendicular to a function's tangent (oriented in the plane of the direction of travel for the curve), and the tangent function of a Bezier curve is actually just another Bezier curve, 1 order lower. Let's find the normal for a cubic Bezier curve. The regular function, with (a,b,c,d) being the curve coordinates in a single dimension:

function computeBezier (t, a, b, c, d) {
  return a * (1-t)³ + 3 * b * (1-t)² * t + 3 * c * (1-t) * t² + d * t³
}

Note that Bezier curves are symmetrical, the only difference between t vs 1-t is which end of the curve represents "the start". Using a * (1-t)³ means the curve starts at a. Using a * t³ would make it start at d instead.

So let's define a quick curve with the following coordinates:

a = (-100,100,0)
b = (200,-100,100)
c = (0,100,-500)
d = (-100,-100,100)

In order to get the normal for this function, we first need the derivative:

function computeBezierDerivative (t,a,b,c,d) {
  a = 3*(b−a)
  b = 3*(c-b)
  c = 3*(d-c)
  return a * (1-t)² + 2 * b * (1-t) * t + c * t²
}

Done. Computing the derivative is stupidly simple (a fantastic property of Bezier curves).

Now, in order to get the normal, we need to take the normalised tangent vector at some value t, and rotate it by a quarter turn. We can turn it in quite a few directions, so a further restriction is that we want to turn it only in the plane that is defined by the tangent vector, and the tangent vector "right next to it", an infinitesimally small interval apart.

The tangent vector for any Bezier curve is formed simply by taking however-many-dimensions you have, and evaluating them separately, so for a 3D curve:

             | computeBezierDerivative(t, x values) |    |x'|
Tangent(t) = | computeBezierDerivative(t, y values) | => |y'|
             | computeBezierDerivative(t, z values) |    |z'|

Again, quite simple to compute. To normalise this vector (or in fact any vector), we simply perform a vector division by its length:

                   |x'|
NormalTangent(t) = |y'| divided by sqrt(x'² + y'² + z'²)
                   |z'|

So let's draw those in green:

The only trick is now to find the plane in which to rotate the tangent vector, to turn the tangent into a normal. We know we can use another t value arbitrarily close to the one we want, and turn that into a second tangent vector damn near on the same point, for finding the plane with arbitrary correctness, so we can do that:

Given an original point f(t1)=p we take a point f(t2)=q with t2=t1+e, where e is some small value like 0.001 -- this point q has a derivative q' = pointDerivative(t2), and in order to make things easier for us, we move that tangent vector a tiny bit by p-q so that the two vectors both "start" at p. Pretty simple.

However, this is equivalent to computing the first and second derivative at p, and then forming the second vector by adding those two together, as the second derivative gives us the change of the tangent at a point, so adding the second derivative vector to the first derivative vector gets us two vectors in the plane at p without having to find an adjacent point. This can be useful in curves where there are discontinuities in the derivative, i.e. curves with cusps.

We now have two vectors, departing at the same coordinate: our real tangent, and the "next" point's tangent, which is so close it might as well be the same point. Thankfully, due to how Bezier curves work, this second tangent is never the same, but slightly different, and "slightly different" is all we need: If we have two normalised vectors, starting at the same point but pointing in different directions, we can find the axis over which we need to rotate one to get the other simply by taking the cross product between them, and thus we can find the plane that they both go through.

Order matters: we compute c = tangent₂ × tangent₁, because if we compute c = tangent₁ × tangent₂ we'll be computing the rotation axis and resulting normals in the "wrong" direction. Correcting that is literally just a "take vector, multiply by -1" at the end, but why correct after the fact when we can get it right, here. Let's see those axes of rotation in blue:

Now we have everything we need: in order to turn our normalised tangent vectors into normal vectors, all we have to do is rotate them about the axes we just found by a quarter turn. If we turn them one way, we get normals, if we turn them the other, we get backfacing normals.

For arbitrary rotation about an axis in 3D, that job is perhaps laborious, but not difficult, and the quarter turns are generally special in that they greatly simplify the maths: to rotate a point over our rotation axis c, the rotation matrix turns out to be:

    |     c₁²     c₁*c₂ - c₃  c₁*c₃ + c₂ |
R = | c₁*c₂ + c₃      c₂²     c₂*c₃ - c₁ |
    | c₁*c₃ - c₂  c₂*c₃ + c₁      c₃²    |

Where the 1, 2 and 3 subscripts are really just the x, y, and z components of our vector. So that's still easy, and all that's left is to matrix-rotate our normalised tangent:

n = R * Tangent "T"

Which is:

    | T₁ * R₁₁ + T₂ * R₁₂ + T₃ * R₁₃ |    |nx|
n = | T₁ * R₂₁ + T₂ * R₂₂ + T₃ * R₂₃ | => |ny|
    | T₁ * R₃₁ + T₂ * R₃₂ + T₃ * R₃₃ |    |nz|

And we have the normal vector(s) we need. Perfect!

Except we can do better: since we're not working with arbitrary angles but with right angles, there's a significant shortcut we can use. In the same way that the vector c was perpendicular to both tangents, our normal n is perpendicular to both c and the regular tangent, so we can use the cross product a second time to find the normal:

                    |nx|
n = c × tangent₁ => |ny|
                    |nz|

This will give us exactly the same vector, with less work.

And if we want internal normals, it's the same vector, just multiply by -1:

Pretty easy once you know the tricks! And finally, because code is always useful this gist is the Processing program I used to make sure I was telling the truth.

What if the normals behave really weird?

For example, what if we're using a 3D curve but it's planar (e.g. all z coordinates at 0)? Things suddenly do horrible things. For instance, let's look at a curve with coordinates (0,0,0), (-38,260,0), (-25,541,0), and (-15,821,0):

Similarly, particularly curvy curves may yield rather twisting normals. Looking at a curve with coordinates (0,0,0), (-38,260,200), (-25,541,-200), and (-15,821,600):

In this case, we want normals that rotate and twist as little as possible, which can be found using a Rotation Minimising Frame algorithm, such as explained in section 4 or "Computation of Rotation Minimizing Frames" (Wenping Wang, Bert Jüttler, Dayue Zheng, and Yang Liu, 2008).

Implementing their 9 line algorithm takes a little more work in a normal programming language, such as Java/Processing:

ArrayList<VectorFrame> getRMF(int steps) {
  ArrayList<VectorFrame> frames = new ArrayList<VectorFrame>();
  double c1, c2, step = 1.0/steps, t0, t1;
  PointVector v1, v2, riL, tiL, riN, siN;
  VectorFrame x0, x1;

  // Start off with the standard tangent/axis/normal frame
  // associated with the curve just prior the Bezier interval.
  t0 = -step;
  frames.add(getFrenetFrame(t0));

  // start constructing RM frames
  for (; t0 < 1.0; t0 += step) {
    // start with the previous, known frame
    x0 = frames.get(frames.size() - 1);

    // get the next frame: we're going to throw away its axis and normal
    t1 = t0 + step;
    x1 = getFrenetFrame(t1);

    // First we reflect x0's tangent and axis onto x1, through
    // the plane of reflection at the point midway x0--x1
    v1 = x1.o.minus(x0.o);
    c1 = v1.dot(v1);
    riL = x0.r.minus(v1.scale( 2/c1 * v1.dot(x0.r) ));
    tiL = x0.t.minus(v1.scale( 2/c1 * v1.dot(x0.t) ));

    // Then we reflection a second time, over a plane at x1
    // so that the frame tangent is aligned with the curve tangent:
    v2 = x1.t.minus(tiL);
    c2 = v2.dot(v2);
    riN = riL.minus(v2.scale( 2/c2 * v2.dot(riL) ));
    siN = x1.t.cross(riN);
    x1.n = siN;
    x1.r = riN;

    // we record that frame, and move on
    frames.add(x1);
  }

  // and before we return, we throw away the very first frame,
  // because it lies outside the Bezier interval.
  frames.remove(0);

  return frames;
}

Still, this works really well. With the note that the Frenet frame is the "standard" tangent/axis/normal frame:

VectorFrame getFrenetFrame(double t) {
  PointVector origin = get(t);
  PointVector tangent = derivative.get(t).normalise();
  PointVector normal = getNormal(t).normalise();
  return new VectorFrame(origin, tangent, normal);
}

For our planar curve, we now see perfectly behaved normals:

And in the non-planar curve, there is minimal rotation:

And finally, these normals can be uniformly reoriented by rotating all vectors around their associated tangent vectors.

这篇关于从 3D 三次贝塞尔路径获得一致的法线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！