Linear InterpolationWhat does ‘between’ mean?Using a “weighted average”The generalizationDescribing a line-segmentAnimating a line-segmentThe programming ideaThe ‘polyline’ structureThe ‘tweening.cpp’ demoStick manDrawing curvesHere’s the ideaKai’s ImplementationLabels used in recursionIn-class exerciseLinear InterpolationApplying “weighted averages” to some graphics problems: animations and curve-drawingWhat does ‘between’ mean?PGB1B2The green point G lies between the two blue points B1 and B2 .The pink point P does NOT lie between the two blue points B1 and B2.Using a “weighted average”•Suppose (x1,y1) and (x2,y2) are points•The point located half-way in-between is:midpoint = (½)(x1,y1) + (½)(x2,y2)•It’s the “average” of (x1,y1) and (x2,y2)•Here’s another point on the line-segment that lies between (x1,y1) and (x2,y2): (x’,y’) = (¼)(x1,y1) + (¾)(x2,y2)•It’s a “weighted average” of the endpointsThe generalization•Let B1 = (x1,y1) and B2 = (x2,y2) be the two endpoints of a line-segment. Suppose w1 and w2 are “weights” (i.e., neither is negative, and their sum equals 1). Then the point P = w1*B1 + w2*B2 is called a “weighted average” of B1 and B2 , and P will be located “in-between” B1 and B2.•Here P is obtained by “linear interpolation”Describing a line-segment•Mathematical description of line-segments•Let B1 = (x1,y1) and B2 = (x2,y2) be the two end-points of a given line-segment•Let t be a real number whose value can vary continuously, from 0.0 to 1.0•Then point P = (1-t)*B1 + t*B2 will vary continuously over the entire line-segment, starting at B1 (when t=0.0) and ending up at B2 (when t=1.0)Animating a line-segmentinitial positionfinal positionin-between positionsThe programming idea•We only need to specify the segment’s two endpoints at the start and the finish•As the segment moves all its intermediate endpoint locations are then calculated as linear interpolations (“weighted averages”)•This idea can be simultaneously applied to lots of different line-segments (e.g., to all the sides of a polygon, or to all the “edges” in a wire-frame model)The ‘polyline’ structuretypedef struct { float x, y; } point_t;typedef struct { int numverts;point_t vert[ MAXVERT ]; } polyline_t;// declare two polylines (for start and finish)// and a variable polyline (for “in-betweens”)tween[i].x = (1-t)*B1[i].x + t*B2[i].x;tween[i].y = (1-t)*B1[i].y + t*B2[i].y;The ‘tweening.cpp’ demo•We illustrate this idea for animating simple polygons, using random-numbers for the coordinates of the starting vertices and the ending vertices•We use linear interpolation to calculate the sequence of the “in-between” vertices•We use Bresenham’s line-drawing method to “connect-the-dots” at each stageStick manDrawing curves•Another application of “linear interpolation”•We can construct a so-called Bezier curve•The curve is determined by specifying a small number of “control points”•A recursive algorithm is then applied, to generate locations along a smooth curve•This idea is ‘deCasteljau’s algorithm’•Kai Long has written an implementationHere’s the ideaP1P2P3P4Start with some “control points”(Here we use just four of them)Find their “weighted averages”Only the red pointactually is drawnThe same value of t is used for all of these interpolationsKai’s Implementationtypedef struct { double h, v; } Point;typedef struct { int numcpts;Point cpts[ MAXVERT ]; } BezierCruve;// helper functionvoid middle( Point p, Point q, Point &mid ){ mid.x = (p.x + q.x)/2; mid.y = (p.y + q.y)/2; }Labels used in recursionP1p2h1h2ac1c2b1b2dif ( very_near( p1, p2 ) // base case draw_line_segment( p1, p2 );else { // recursion case recursive_bezier( p1, b1, c1, d ); recursive_bezier( d, c2, b2, p2 ); }In-class exercise•Can you combine these two applications?•Create a bezier curve with 4 control-points•Create another one with 4 control-points•Construct some in-between Bezier curves by applying linear-interpolation to pairs of corresponding control-points•So first curve will “morph” into second
View Full Document
Unlocking...