Lecture 25: Bezier SubdivisionAnd he took unto him all these, and divided them in the midst, and laid each piece one against another: Genesis 15:101. Divide and ConquerIf we are going to build useful computer models of freeform shapes using Bezier curves and surfaces, we need procedures to do more than simply evaluate points along these curves and surfaces. We need algorithms to analyze their geometry. For example, to ray trace a Bezier patch, we need algorithms both for finding surface normals and for computing ray-surface intersections. In Lecture 24 we developed an algorithm for differentiating Bezier curves and surfaces, which allows us to find the surface normal of a Bezier patch at any parameter value by taking the cross product of the partial derivatives of the patch. Here we shall develop an algorithm that will permit us to compute the intersection of an arbitrary ray with a Bezier patch.The method we shall employ is a divide and conquer technique called Bezier subdivision. The main idea behind Bezier subdivision is that although globally Bezier curves and surfaces represent curved shapes, if we divide these curves and surfaces into a collection of small enough segments, each segment will be almost flat. Flat shapes like lines and planes are simple to analyze. For example, we can easily ray trace a planar polygon. Thus we shall analyze Bezier curves and surfaces by dividing these curves and surfaces into lots of small flat segments, analyzing the individual flat segments, and then recombining the results to build an understanding of the global geometry of the entire curve or surface.Bezier subdivision is a powerful tool with many applications. In this lecture we shall use Bezier subdivision to develop fast, robust rendering and intersection algorithms for Bezier curves and surfaces, We shall also use Bezier subdivision to prove the variation diminishing property for Bezier curves and to show how to connect two Bezier curves smoothly at their join.2. The de Casteljau Subdivision AlgorithmThe control points of a Bezier curve describe a polynomial curve with respect to a fixed parameter interval € [a,b]. Sometimes, however, we are interested only in the part of the polynomial curve in a subinterval of € [a,b]. For example, when rendering a Bezier curve, we may need to clip the curve to a window on the graphics terminal. Since any segment of a Bezier curve is itself a polynomial curve, we should be able to represent each segment of a Bezier curve as a Bezier curve with a new set of control points. Splitting a Bezier curve into smaller pieces is also useful as a divide and conquer strategy for rendering and intersection algorithms. The process of splitting aBezier curve into two or more Bezier curves that represent the exact same curve is called Bezier subdivision (see Figure 1)Figure 1: Bezier subdivision for a cubic Bezier curve. The Bezier curve € P(t) with control points P0,P1, P2,P3 is split into two Bezier curves: the left Bezier segment € Q(t) has control points € Q0,Q1,Q2,Q3; the right Bezier segment € R(t) has control points € R0,R1,R2,R3.The basic problem in Bezier subdivision is: given a collection of control points € P0,K,Pn that describe a Bezier curve over the interval € [a,b], find the control points € Q0,K,Qn and € R0,K,Rn that describe the segments of the same Bezier curve over the intervals € [a,c] and € [c,b]. Remarkably the solution to this problem is provided by the same de Casteljau algorithm that we use to evaluate points on a Bezier curve.The de Casteljau Subdivision AlgorithmLet € P(t) be a Bezier curve over the interval € [a,b] with control points P0,..., Pn. To subdivide € P(t) at € t = c, run the de Casteljau evaluation algorithm for € P(t) at € t = c. The points Q0,..., Qn that emerge along the left lateral edge of the de Casteljau diagram are the Bezier control points for the segment of the curve from € t = a to € t = c, and the points R0,..., Rn that emerge along the right lateral edge of the de Casteljau diagram are the Bezier control points for the segment of the curve from € t = c to € t = b (see Figure 2). Notice that when € c = (a + b) / 2 is the midpoint of the parameter interval € [a,b], then € (b −c) / (b − a) = 1 / 2 = (c − a) / (b − a), so the labels along all the edges in the de Casteljau subdivision algorithm evaluate to 1/2. Thus for midpoint subdivision the de Casteljau subdivision algorithm is independent of the parameter interval (see Figure 3). 2012€ Q3= R0€ b − c€ b − c€ b − c€ Q1€ ∇€ c − a€ c − a€ c − a€ Q0= P0€ P1€ P2€ P3= R3€ c − a€ b − c€ c − a€ b − c€ c − a€ b − c€ Q2€ R2€ R1Figure 2: The de Casteljau subdivision algorithm for a cubic Bezier curve with control points P0,P1, P2,P3. The points Q0,Q1,Q2,Q3 that emerge along the left edge of the triangle are the Bezier control points for the segment of the original curve from € t = a to € t = c; the points R0, R1, R2, R3 that emerge along the right edge of the triangle are the Bezier control points for the segment of the original curve from € t = c to € t = b.012€ Q3= R0€ 1 / 2€ Q1€ ∇€ Q0= P0€ P1€ P2€ P3= R3€ Q2€ R2€ R1€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2€ 1 / 2Figure 3: The de Casteljau subdivision algorithm for a cubic Bezier curve at the midpoint of the parameter interval. The labels along all the edges evaluate to 1/2, so midpoint subdivision does not depend on the choice of the parameter interval.We shall defer the proof of the de Casteljau subdivision algorithm till Lecture 26. In this lecture we will study the consequences of this subdivision algorithm. Figure 4 provides a geometric interpretation for the de Casteljau subdivision algorithm. 3Figure 4: Geometric interpretation of the de Casteljau subdivision algorithm for a cubic Bezier curve € P(t) with control points P0,P1, P2,P3. The points Q0,Q1,Q2,Q3 are the Bezier control points of the segment of the original curve from € t = a to € t = c, and the points R0, R1, R2, R3 are the Bezier