1
$\begingroup$

I would like to know how to evaluate 2D cubic Bézier curves at an interval when the Bézier coefficients themselves are intervals.

If the coefficients are not intervals, evaluating a Bézier curve on an interval amounts to computing an axis-aligned bounding box. The $x$ and $y$ derivatives of a cubic Bézier curve are quadratic polynomials. So, to evaluate a cubic Bézier curve over the interval $[a,b]$, we can compute the roots of these derivatives, say getting $t_{x,1}, t_{x,2}, t_{y,1}, t_{x,2}$. Discarding those roots that don't lie in $[a,b]$, we can evaluate the $x$ and $y$ components of the Bézier curve at the points $\{a, t_{x,i}, b\}$ and $\{a, t_{y,i}, b\}$, respectively, and compute the relevant axis-aligned bounding box by taking min&max over these values.

However, I'm not sure how to proceed if the Bézier coefficients are themselves intervals.
Suppose I try the same approach: I can formulate the same quadratic equations, and solve them using interval arithmetic. But this will return a collection of intervals, not a finite set of points. So, then, I have to evaluate the original cubic Bézier at these intervals... but that's precisely the problem I started with! Moreover, the intervals obtained from solving the quadratic equations aren't guaranteed to be smaller than the interval $[a,b]$ I started with.

Note that naively evaluating the Bézier curve, using e.g. de Casteljau's algorithm with interval arithmetic, is not a viable option, as it leads to very loose bounds. To illustrate, consider evaluating $f(t) = t - t^2$ over $[0,1]$. Naively performing interval arithmetic leads to $[0,1] - [0,1] = [-1,1]$, when the tightest interval containing $f([0,1])$ is actually $[0,0.25]$.

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose we want to evaluate $p(t) = \sum_i a_i t^i$ in interval arithmetic, where $a_i = [\underline{a_i}, \overline{a_i}]$ and $t=[\underline{t}, \overline{t}]$ are all intervals.

If $t \geqslant 0$, then, as $ x \mapsto x^i $ is monotonically increasing, the minimum value that $p(t)$ can reach is the minimum value of $\underline{p}(t) := \sum_i \underline{a_i} t^i$, while the maximum value it can reach is the maximum of $\overline{p}(t) :=\sum_i \overline{a_i} t^i$.
If $t \leqslant 0$, then we proceed similarly, using $\underline{a_0} + \overline{a_1} t + \underline{a_2} t^2 + \overline{a_3} t^3 + \cdots$ and $\overline{a_0} + \underline{a_1} t + \overline{a_2} t^2 + \underline{a_3} t^3 + \cdots$.
If neither $t \geqslant 0$ nor $t \leqslant 0$, apply the above logic to the two intervals $[\underline{t}, 0]$ and $[0,\overline{t}]$.

This reduces the problem of polynomial evaluation to the case of constant (non-interval) coefficients.

For Bézier curves, we can do pretty much the same thing, except now we are using the Bernstein basis

$$ b(s) = \sum_i \textrm{B}_i(s) a_i. $$

For $s \subseteq [0,1]$, this is a convex combination (the Bernstein polynomials are a partition of unity on $[0,1]$), so as long as $s \subseteq [0,1]$, we can proceed as in the $t \geqslant 0$ case above. If $s \not \subseteq [0,1]$, we have to split up the interval and inspect the signs of the Bernstein polynomials (it's straightforward but I haven't needed that generality yet).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .