Linear Interpolation Applying weighted averages to some graphics problems animations and curve drawing What does between mean B1 The green point G lies between the two blue points B1 and B2 P G The pink point P does NOT lie between the two blue points B1 and B2 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 endpoints The 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 segment final position initial position in between positions The 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 structure typedef 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 stage Stick man Drawing 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 implementation Here s the idea P2 P1 Start with some control points Here we use just four of them Find their weighted averages The same value of t is used for all of these interpolations P3 Only the red point actually is drawn P4 Kai s Implementation typedef struct double h v Point typedef struct int numcpts Point cpts MAXVERT BezierCruve helper function void middle Point p Point q Point mid mid x p x q x 2 mid y p y q y 2 Labels used in recursion h1 a c1 d h2 c2 b2 b1 P1 if 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 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 one
View Full Document
Unlocking...