# Intersect a line with a bicubic Bezier Surface Patch.

This question mentions Bezier surfaces, but doesn't go into any detail. How do you going about finding the intersection between a line, $E_{pos} + E_{dir}*t$ and a Bezier surface patch, $P =$

$$\begin{bmatrix} P_{00} & P_{01} & P_{02} & P_{03} \\ P_{10} & P_{11} & P_{12} & P_{13} \\ P_{20} & P_{21} & P_{22} & P_{23} \\ P_{30} & P_{31} & P_{32} & P_{33} \end{bmatrix};$$

where a single component curve can be parametrized by $x(u) =$

$$\begin{bmatrix} u^3 & u^2 & u & 1 \end{bmatrix} \begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} P_{i0_x} \\ P_{i1_x} \\ P_{i2_x} \\ P_{i3_x} \end{bmatrix},$$

and similarly for $y(u)$ and $z(u)$, and similarly choosing columns rather than rows from the geometry matrix; and the whole surface can be parametrized by $x(u,v) =$

$$\begin{bmatrix} u^3 & u^2 & u & 1 \end{bmatrix} \begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} P_{00_x} & P_{01_x} & P_{02_x} & P_{03_x} \\ P_{10_x} & P_{11_x} & P_{12_x} & P_{13_x} \\ P_{20_x} & P_{21_x} & P_{22_x} & P_{23_x} \\ P_{30_x} & P_{31_x} & P_{32_x} & P_{33_x} \end{bmatrix} \begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} v^3 \\ v^2 \\ v \\ 1 \end{bmatrix}?$$

Foley and van Dam, Fundamentals mentions an algebraic form, but doesn't show how to get there from the set of points. It is this form that I assume is appropriate for standard root-solving methods, and looks like

$$\begin{matrix} x(u,v) & = & a_{11}u^3v^3 & + & a_{12}u^3v^2 & + & a_{13}u^3v & + & a_{14}u^3 \\ & + & a_{21}u^2v^3 & + & a_{22}u^2v^2 & + & a_{23}u^2v & + & a_{24}u^2 \\ & + & a_{31}uv^3 & + & a_{32}uv^2 & + & a_{33}uv & + & a_{34}u \\ & + & a_{41}v^3 & + & a_{42}v^2 & + & a_{43}v & + & a_{44} \end{matrix}$$

But where does the third parameter of the ray come into play?

-
You wrote "It is this form that I assume is appropriate for standard root-solving methods". For polynomials in one variable, that's true. The root-finding method will expect you to give it the algebriac coefficients. For problems involving many variables, this is not the case. The root-finding package will expect you to give it functions, not coefficients. –  bubba Apr 3 '13 at 11:12

Suppose your ray is $\mathbf R(t)$ and your surface patch is $\mathbf S(u,v)$. To find an intersection, you have to find $t,u,v$ such that $\mathbf R(t) = \mathbf S(u,v)$. Both $\mathbf R$ and $\mathbf S$ are three-dimensional, and you can consider the $x,y,z$ components of the equation $\mathbf R(t) = \mathbf S(u,v)$ separately. So, you get three equations that (in principle) you can solve to get $t,u,v$. The equations are fairly nasty, and you'll need to use numerical methods.

Your question already has the surface patch equations, partly. Changing the notation a little, you wrote:

$$S_x(u,v) = x(u,v) = \mathbf u \cdot \mathbf B \cdot \mathbf P_x \cdot \mathbf B^T \cdot \mathbf v^T$$

where $\mathbf B$ is the Bezier cubic basis matrix and $\mathbf P_x$ is the matrix containing the $x$-coordinates of the control points of the patch. You can write similar equations for the $y$ and $z$ coordinates of points on the patch:

$$S_y(u,v) = \mathbf u \cdot \mathbf B \cdot \mathbf P_y \cdot \mathbf B^T \cdot \mathbf v^T$$ $$S_z(u,v) = \mathbf u \cdot \mathbf B \cdot \mathbf P_z \cdot \mathbf B^T \cdot \mathbf v^T$$

The ray equation can be written as $x$, $y$, $z$ components, too. If the ray in vector form is $\mathbf R(t) = \mathbf A + t\mathbf W$, then we can write components: $$R_x(t) = A_x + tW_x$$ $$R_y(t) = A_y + tW_y$$ $$R_z(t) = A_z + tW_z$$

The three equations you need to solve are:

$$S_x(u,v) - R_x(t) = 0$$ $$S_y(u,v) - R_y(t) = 0$$ $$S_z(u,v) - R_z(t) = 0$$

There is no need to transform these equations into algebraic form. You just define

$$f_x(u,v,t) = S_x(u,v) - R_x(t) = 0$$ $$f_y(u,v,t) = S_y(u,v) - R_y(t) = 0$$ $$f_z(u,v,t) = S_z(u,v) - R_z(t) = 0$$

and you feed the three equations $f_x(u,v,t) = 0$, $f_y(u,v,t) = 0$, $f_z(u,v,t) = 0$ into your favorite numerical root finder.

You seem to want to find the algebraic coefficients -- the coefficients of $u^3v^3$, $u^3v^2$, and so on. You don't need to do this. It doesn't help. The numerical root finder doesn't care. You feed it functions, not algebraic coefficients.

There actually are more clever ways to intersect a ray and a (bicubic) Bezier patch. One relevant paper is: J. T. Kajiya "Ray Tracing Parametric Patches" Computer Graphics (Proc. SIGGRAPH 82), Vol. 16, No. 3, July 1982, pp. 245-254. He shows that a ray and a bicubic patch can be intersected by solving a single equation of degree 18. Of course, this has to be done numerically, too. I think this approach is probably more trouble than it's worth, and I would recommend the approach outlined above.

Also, take a look at this e-book.

-
I've got a reprint of that paper in the IEEE Tutorial: Image Synthesis. But I have difficulty seeing where to plug-in the points. ... Everybody says they're nasty equations! But no one's published them. –  luser droog Apr 2 '13 at 7:15
+1 You've already helped me clean up my variable names. –  luser droog Apr 2 '13 at 10:04
I added the equations into my answer –  bubba Apr 2 '13 at 13:21
Thank you. It's a much stronger presentation, now. I know I'm being stubborn but I really think I can do something with these equations. I'll probably accept your answer in the end. But it would, in a sense, mean defeat, you know? –  luser droog Apr 3 '13 at 5:02
You will get 3 equations of degree 3 in the variables $u$, $v$, and $t$. The best you'll be able to do is eliminate $u$ and $v$. The Kajiya paper shows you how to do this. You'll be left with an equation of degree 18 in $t$. –  bubba Apr 3 '13 at 11:02