# Finding a point on a bezier surface using De Casteljau's algorithm

Given $16$ control points $(x,y,z)$ of a bicubic bezier patch, how do I use De Casteljau's algorithm to generate a point $(s,t) = (0.5, 0.2)$ on the surface?

As far as I understand, this kind of bezier patch can be thought of $4$ curves along the $s$ parameter. To find the $z$ I mentioned above I have to solve each of the $4$ $s$-curves for the value $s=0.5$. How do I do this? Using $4$ points means I have a $n=3$ bezier curve with a starting point and an ending point as well as two respective points for the tangents. Solving this I should have $4$ new points to make up a new curve which I can evaluate at $t=0.2$.

Where do I start and what do I need to do? How is the Bernstein Polynomial related to this?

You can find the points here: https://i.sstatic.net/FYE2u.png

Please excuse me my not-so-good english skills or wrong usage of mathematical terminologyas it's not my first language.

## 1 Answer

There's a good explanation starting on this web page.

I recommend that you read the three sections on Bezier surfaces in "Unit 8".

The process you described in your question is roughly correct.

Let's call the 16 points: $$P_{11}, P_{12}, P_{13}, P_{14}$$ $$P_{21}, P_{22}, P_{23}, P_{24}$$ $$P_{31}, P_{32}, P_{33}, P_{34}$$ $$P_{41}, P_{42}, P_{43}, P_{44}$$

And let $\phi_1$, $\phi_2$, $\phi_3$, $\phi_4$ be the Bernstein polynomials of degree 3.

Suppose we want to evaluate a point on the surface with parameter values $(s,t) = (0.5, 0.2)$.

The first thing we do is use the 16 points four at-a-time to construct four curves. We start with the points of the first row: $P_{11}$, $P_{12}$, $P_{13}$, $P_{14}$. We can use them to construct a Bezier curve $$C_1(s) = \phi_1(s)P_{11} + \phi_2(s)P_{12} + \phi_3(s)P_{13} + \phi_4(s)P_{14} = \sum_{j=1}^4 \phi_j(s)P_{1,j}$$ Then, on this curve, we can calculate the point $Q_1 = C_1(0.5)$ at value $s=0.5$. $$Q_1 = C_1(0.5) = \sum_{j=1}^4 \phi_j(0.5)P_{1,j}$$ You can calculate $Q_1$ by the normal de Casteljau algrorithm, or any other method.

We do the same things with the other three rows of points. For each row, we construct a Bezier curve, and then we calculate the point at parameter value $s=0.5$. We get points $$\text{second row:}\quad Q_2 = C_2(0.5) = \sum_{j=1}^4 \phi_j(0.5)P_{2,j}$$ $$\text{third row:}\quad Q_3 = C_3(0.5) = \sum_{j=1}^4 \phi_j(0.5)P_{3,j}$$ $$\text{fourth row:}\quad Q_4 = C_4(0.5) = \sum_{j=1}^4 \phi_j(0.5)P_{4,j}$$ We can write all this more tidily as: $$Q_i = C_i(0.5) = \sum_{j=1}^4 \phi_j(0.5)P_{ij} \quad (i=1,2,3,4)$$

Now we just do the Bezier thing in the other direction -- we use the points $Q_1$, $Q_2$, $Q_3$, $Q_4$ to construct a Bezier curve Q(t) given by $$Q(t) = \phi_1(t)Q_1 + \phi_2(t)Q_2 + \phi_3(t)Q_3 + \phi_4(t)Q_4 = \sum_{i=1}^4 \phi_i(t)Q_i$$ Then our final surface point is the point at parameter value $t=0.2$ on the curve $Q(t)$: $$X(0.5, 0.2) = Q(0.2) = \sum_{i=1}^4 \phi_i(0.2)Q_i$$ Again, you can calculate this point using the de Casteljau algorithm or any other method.

To understand how all this relates to the surface equation, let's substitute the expressions for the $Q_i$ into our last equation. We get $$X(0.5, 0.2) = \sum_{i=1}^4 \phi_i(0.2)Q_i = \sum_{i=1}^4 \phi_i(0.2)\left(\sum_{j=1}^4 \phi_j(0.5)P_{ij}\right)$$ Rearranging this gives: $$X(0.5, 0.2) = \sum_{i=1}^4 \sum_{j=1}^4 \phi_j(0.5) \phi_i(0.2) P_{ij}$$ You should recognize the right-hand side as the formula for a Bezier surface.

Here's a picture:

The blue curves are $C_1$, $C_2$, $C_3$, $C_4$, the red dots are $Q_1$, $Q_2$, $Q_3$, $Q_4$, and the red curve is $Q$.

• Thanks a lot for this extreme good explanation!! you saved my day! =) Commented Feb 23, 2019 at 18:21