3
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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:

bezier-patch

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$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for this extreme good explanation!! you saved my day! =) $\endgroup$
    – Thomas
    Commented Feb 23, 2019 at 18:21

You must log in to answer this question.

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