2
$\begingroup$

In the unconstrained case, the shortest path between two points in arbitrary dimension is given by a straight line, which is also a Bezier curve of degree one, with two control points corresponding to the desired start and end positions.

If additional constraints apply (initial / end velocities and acceleration), the constraints are expressed using additional control points, one per constraint.

For instance, if the initial velocity is constrained, a Bezier curve of degree at least 2 is required to satisfy the constraints (3 control points).

I. Is the Bezier curve of minimum length satisfying the constraints given by the Bezier curve of minimum degree? This means, adding additional control points will not allow to find a shortest curve.

When the initial / end velocities are either unconstrained or constrained to be 0, this intuition is trivially verified.

One argument, not a proof, in favor of this theory is that the length of a Bezier curve is bounded by the perimeter of its control points: additional control points can only increase this bound.

EDIT: For this question, the answer has been proven to be no. However I think my second question stands. The minimum time seems to be a compromise between the shortest path and the minimum curvature of a curve

II. Considering linear bounds on the admissible velocities and acceleration, is the curve connecting two states in the minimum amount of time a curve of minimal degree?

EDIT 2: For this question, we'll consider a change of variable to integrate unnormalized time. If s, 0 <= s <= 1 is the parametric variable, we can introduce a total time T for the curve $\mathbf{B}(s)$ and use a change of variable to obtain a curve $\mathbf{C}(t) = \mathbf{B}(\frac{t}{T})$, which means $s = \frac{t}{T}$.

The derivatives of $\mathbf{C}(t)$ are obtained similarly to those of $\mathbf{B}(s)$, but each derivative is then premultiplied by $\frac{1}{T}$:

$\mathbf{C}'(t) = \frac{1}{T} B'(\frac{t}{T})$

We are then interested in finding the minimum value of $T$ such that the velocity / acceleration bounds are satisfied.

If for instance, the start velocity is constrained but not the end velocity, with a minimal number of control points (3), T is uniquely defined. If more control points are added, there are multiple options for both the end velocity and the minimal value of T.

My question is whether the minimum T in the minimal case T is the minimum over all possible curves of any degree that match the constraints.

$\endgroup$
2
$\begingroup$

If by velocity you mean $\mathbf{B}'(t)$, then the diagram below shows that the answer to your first question is no. The red curve is the quadratic Bézier $(ACB)$, the green curve is the quintic Bézier $APDEQB$. Control points $P$ and $Q$ satisfy $AP/AC=BQ/BC=2/5$, so that initial and final velocities are the same for both curves. But green curve is shorter.

EDIT.

Initial velocity is $\mathbf{B}'(0)=2(C-A)$ for the quadratic Bézier and $\mathbf{B}'(0)=5(P-A)$ for the quintic Bézier. But $PA/CA=2/5$, hence those two results are equal, both in direction and magnitude. The same holds for $\mathbf{B}'(1)$.

enter image description here

EDIT 2.

With your definition of velocity, every Bézier curve is covered in unit time: $$ t=\int_0^L{ds\over v}=\int_0^1{|\mathbf{B}'(t)|dt\over|\mathbf{B}'(t)|}= \int_0^1dt=1. $$

Which, after all, is obvious: a point on any Bézier joining $A$ and $B$ "starts" from $A$ at $t=0$ and "arrives" at $B$ at $t=1$.

$\endgroup$
  • $\begingroup$ Hi, thanks. Similarly to the below answer however, I am not just interested in the direction, but also in the norm of the derivatives. In these examples C is necessarily the second and the one before last control point, otherwise this constraint is not satisfied $\endgroup$ – Steve T. Mar 2 at 13:10
  • $\begingroup$ The derivatives also have the same length, with that choice of $P$ and $Q$. $\endgroup$ – Aretino Mar 2 at 14:21
  • $\begingroup$ I added an explanation to my answer. $\endgroup$ – Aretino Mar 2 at 14:47
  • $\begingroup$ I forgot that the degree of the curve matters in the computation of the velocity, I see thanks. $\endgroup$ – Steve T. Mar 2 at 22:20
  • $\begingroup$ I think my second question still stands though. It seems the green curve has a curvature that prevents following it at the same velocity than the red one, and so I wonder whether, in spite of being longer, the red curve can't be traveled faster ? $\endgroup$ – Steve T. Mar 3 at 8:59
1
$\begingroup$

This picture shows two curves: enter image description here

The blue one is cubic (degree 3). The red one is quartic (degree 4). The two curves have the same starting and ending first derivatives (i.e. the same starting and ending "velocities" in your terminology). More specifically, the start/end derivatives have the same directions and the same lengths.

The red curve is obviously shorter.

So, the answer to your first question is "no".

$\endgroup$
0
$\begingroup$

The answer to your first question is "no".

Take the case where we constrain starting/ending locations and starting/ending directions. Suppose the start point is $A$, the end point is $C$, and the start and end tangents intersect at $B$. Clearly a quadratic Bezier curve with control points $A, B, C$ satisfies the constraints.

However, consider the cubic curve with control points $A$, $(1-k)A + kB$, $kB + (1-k)C$, $C$. If $k$ is small (say $k = 0.1$, for example), then the cubic curve is shorter than the quadratic one. In fact, as $k \to 0$, the cubic curve becomes the straight line between $A$ and $C$.

Note also that the hull of the cubic curve is contained within the hull of the quadratic one (here "hull" is a shorthand term for the convex hull of the control points). This counters your argument that increasing degree will expand hulls.

$\endgroup$
  • $\begingroup$ Thanks, however I think I disagree.With these control points, the constraints are not satisfied anymore ! This is not just about the direction, but the norm count as well . When I say velocity and acceleration, I consider the values, and not just directions. Regarding the hull, I agree that it is not necssarily increased (for a single segment you can add many control points between A and C, this wont change the length nor the hull). However it certainly does not decrease. $\endgroup$ – Steve T. Mar 2 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.