1
$\begingroup$

I've recently completely reworked the code in my Kinross library that finds the intersection of Bézier curves. I've come a long way from first developing my own method and asking for better ones, then developing another method based on an answer I got there. The Bézier curves and almost all computations (arithmetic, root-finding, etc.) now handle polynomials only in the Bernstein basis, not the less stable power basis. Most of the techniques implemented are from Sederberg's Computer Aided Geometric Design (CAGD).

The new approach to curve intersection in Kinross is through implicitisation and curve inversion, both described in detail in CAGD. However, the book has a section describing how to invert curves using a nullspace computation (on p. 205), while its sections on implicitisation only describe how to obtain the implicit form of a Bézier curve using resultants (in particular determinants of matrices of polynomials, which NumPy doesn't support). I found a way to implicitise Bézier curves using little more than another nullspace computation, and the question here is asking why that method works.


The implicitisation task is this: given a Bézier curve $(x(t),y(t))$, find a polynomial $f(x,y)=0$ describing points on the (infinitely extended) curve. Since the curve has a known degree, the set of terms of $f$ that could possibly be non-zero is finite and known. For the common cubic curve, $f$ has the following form: $$c_0+c_1x+c_2y+c_3x^2+c_4xy+c_5y^2+c_6x^3+c_7x^2y+c_8xy^2+c_9y^3=0$$ All the monomials $x,y,x^3,y^3,\dots$ are themselves polynomials in $t$, and all can be computed in the Bernstein basis at a common degree using techniques described in CAGD. Thus I can write a linear system for $f$: $$\mathbf{Zc}=\begin{bmatrix}\bf1&\bf x&\bf y&\bf x^2&\bf xy&\bf y^2&\bf x^3&\bf x^2y&\bf xy^2&\bf y^3\end{bmatrix}\begin{bmatrix}c_0\\c_1\\c_2\\c_3\\c_4\\c_5\\c_6\\c_7\\c_8\\c_9\end{bmatrix}=\bf 0$$ Each boldface entry is a length-$10$ column vector $(a_0,a_1,\dots,a_{9})^T$ of Bernstein basis coefficients representing the corresponding monomial $t$-polynomial, $\sum_{k=0}^n\binom nk(1-t)^{n-k}t^ka_k$. $\bf xy^2$ represents $x(t)y(t)^2$ and so on.

The $n+1$ Bernstein basis polynomials of degree $n$ form a basis for the vector space of all polynomials with degree at most $n$. Thus, if $\mathbf c\ne\mathbf 0$ satisfies $\mathbf{Zc}=\mathbf0$, it will contain a correct set of coefficients for $f$.

What puzzles me is that $\bf Z$ always seems to be rank-deficient despite being a square matrix (in the cubic case), so a non-zero solution $\mathbf c$ can always be found (via QR decomposition among other means) and $f$ calculated – all without resorting to resultants.

Why is $\bf Z$ as I have constructed it, from the parametric polynomials $x(t)$ and $y(t)$, always rank-deficient?

My first guess was that the deficiency arises from the resultant's existence, but that argument feels unrigorous. Note that the columns of $\bf Z$ can be converted to and from the power basis by left-multiplying by appropriate invertible matrices, which may make the answer simpler.

I am asking this question to commemorate my reaching of $50000$ reputation.

$\endgroup$
  • $\begingroup$ Going a bit out on a limb here but isn't this a consequence from the fact that most cubic algebraic curves cannot be rationally parameterized? In other words, your Bezier curve (rational or not) will only span a small subset of all algebraic curves. I think this fact will manifest itself in a rank deficient matrix in your case. $\endgroup$ – Jap88 Jun 28 at 20:38

Your Answer

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

Browse other questions tagged or ask your own question.