Line intersect spline surface

Question

The intersection of a line with a bi-n surface is the solution of $A+Bt=Cu^nv^n+...$, where A, B, C, etc. are 3-vectors. The first step in solving this system is eliminating to get two bi-n equations in u and v. These can be manipulated to get a polynomial of degree m. For n=1,2,3, $m=2n^2$. My question: does this relationship hold for higher n and where is the proof?

Answer 1

This is a good starting point: http://tom.cs.byu.edu/~557/text/cagd.pdf The section on algebraic geometry.

Then this paper should cover this: https://www.sciencedirect.com/science/article/pii/0734189X84901403

Note that a line intersects a parametric polynomial surface in at most its implicit algebraic degree. The paper above shows the surface's degree to be $2n^2$ for a $n$-by-$n$ degree patch. It turns out to be true even for a rational polynomial patch. A spline surface can be decomposed into a series of Bezier surfaces so they are algebraically the same thing.

---

Quadratic Bezier and Spline surfaces are pretty common in CAD and, in the general case, they correspond to surfaces of the form:

---

$a_{100}x+a_{001}z+\ldots+a_{110}xy+a_{200}x^2+\ldots+a_{404}x^4z^4+\ldots=0$

---

Cubic surfaces are also quite common and they would be even more complicated, such as:

---

$a_{100}x+a_{001}z+a_{213}x^2yz^3+a_{600}x^6+a_{666}x^6 y^6 z^6 +\ldots=0$

---

Sederberg in his CAGD book says: "A tensor surface generally has an implicit equation of degree $2mn$. Thus, a bicubic patch generally has an implicit equation $f(x,y,z)=0$ of degree $18$. Such an equation has $1330$ terms!"

The $2mn$ result is true in complex projective space. I have not seen anything published on how many real roots there could be. It is quite possible that due to some symmetry you can never reach $2mn$ roots in practice.

---

As a last note, when intersecting two cubic Bezier (or spline) patches the algebraic degree of the intersection curve can be as high as $18*18=324$. In CAD software such curves have to be traced numerically since there is no hope of finding a parameterization in the general case.

Answer 2

You can proceed by implicitization, as described in the answer by @Jap88, and it seems that this is the approach you had in mind. In addition to Sederberg's work, the cubic case was covered in some detail in an old paper by Jim Kajiya: "Ray Tracing Parametric Patches" Computer Graphics (Proc. SIGGRAPH 82), Vol. 16, No. 3, July 1982, pp. 245-254.

I know this isn't what you asked, but in my view this approach isn't very practical. It might be OK for quadratic surfaces, but even with cubics you end up with a polynomial of degree 18 with 1330 terms. In CAD systems, surfaces of degree 5 through 8 are common, degree 15 is not unusual, and degrees up to around 25 are often supported. For these, the number of terms in the univariate polynomial gets completely unmanageable. You're better off using numerical methods to solve the original problem in three variables (two surface parameters and one curve parameter). Some further details in this answer.