1The Parametric Line Equation:Fundamental Analysis of 3D ObjectsMike [email protected] State Universitymjb – September 5, 2014Oregon State UniversityComputer GraphicsThe Line Equation:Why “y=mx+b” Isn't Good Enough for Graphics and Simulation ApplicationsP1=(x1,y1,z1)P0=(x0,y0,z0)1. Cannot represent vertical lines ( m = ∞)2. Can only represent infinite lines, not finite line segmentsmjb – September 5, 2014Oregon State UniversityComputer Graphics3. Can only represent 2D lines, not 3DNote: “z = mx + ny + b” is a plane, not a 3D line2Parametric Line Equation:The “Shooting” FormP1P0010()xXtXX010()yYtYY010()zZ tZ Ztmjb – September 5, 2014Oregon State UniversityComputer Graphics010()0. 1.tP1(1 )tX tXParametric Line Equation:The “Blending” FormP001(1 )xtX tX01(1 )ytY tY01(1 )ztZtZtmjb – September 5, 2014Oregon State UniversityComputer Graphics0. 1.t3Example Use: Intersection of two 2D Line SegmentsP1P201 23xx01 23yytuP0P301 0 1 0()xXtXX01 0 1 0()yYtYY23 2 3 2()xXuXX23 2 3 2()yYuYYSince, at the point of intersection, and01 23xx01 23yy01 23mjb – September 5, 2014Oregon State UniversityComputer Graphicspwe have 2 equations in 2 unknowns (t and u)Solve for t* and u*. If they are not each between 0. and 1., then the infinite lines intersect, but not the finite line segments. Plug t* and u* back into the equations above to find (x*,y*), the point of intersection.01 2301 23yyWhat if t* or u* is < 0. or > 1. ?P1P1P2P0P2P3P0P30. 1.0tu1.0tumjb – September 5, 2014Oregon State UniversityComputer GraphicsIt means you have a situation like one of these. The infinite lines intersect, but not the finite line segments. 0.u0.u4(3,3)(0,2)(6,0)An Example with Numberstu(0,0)(6,0)010(30) xt01 0 1 0()yytyy 230(60)xu232(02)yu36tu01 0 1 0()xxtxx 010(30) yt23 2 3 2()yytyy23 2 3 2()xxtxxmjb – September 5, 2014Oregon State UniversityComputer Graphics322tu**11;24tu**1.5; 1.5xyWhat if the Lines are Parallel ?P0P1~~→∞Well, technically they do intersect, but at infinity. This shows up in the math by the expression for t*and u*becoming infinitely large, that is, there wouldP2P3~~→∞mjb – September 5, 2014Oregon State UniversityComputer Graphicsby the expression for t and u becoming infinitely large, that is, there would be a divide by zero.So, you need to check the denominator before doing the division.Since t* and u* would both be infinity in this case, which is most certainly > 1, that means that the line segments do not intersect.5Linear Blending Shows Up in a Lot of Computer Graphics-Related ApplicationsYou can linearly blend any two quantities with:(1 )QtQtQ01(1 )QtQtQmjb – September 5, 2014Oregon State UniversityComputer Graphicscolor, shape, location, angle, scale factors, •••You can bilinearly blend any 2D quantities within a quadrilateral by writingthe line blending equation twice and then blending the two lines with:01 11(1 )BQtQtQ Q11Bilinear Interpolation in a QuadrilateralQ00Q10Q01Q11ttuumjb – September 5, 2014Oregon State UniversityComputer Graphics00 10(1 )AQtQtQ00 10 01 11(1 ) (1 )(1 ) (1 ) (1 )AB A BQuQuQtuQtuQtuQtuQ       6You can derive this equation by doing a blend-of-a-blend,like was shown on the last slide, or you can just look at how theterms have to become 0. or 1. whenever t = 0. or 1. and u = 0. or 1.Bilinear Interpolation in a QuadrilateralFor example, right here t = 1. and u = 0.We know that at this location, the coefficient ofQ10has to be 1. and the coefficients ofQ00, Q01, and Q11have to all be 0.mjb – September 5, 2014Oregon State UniversityComputer Graphics00 10 01 11(1 ) (1 )(1 ) (1 ) (1 )AB A BQuQuQtuQtuQtuQtuQ       So, you can actually just write the bilinear equation “by inspection”.Bilinear Interpolation in a QuadrilateralDrawing a quadrilateral as two triangles:Drawing a quadrilateral with bilinear interpolation:This diagonal should have some blue and green in it, but it doesn’tmjb – September 5, 2014Oregon State UniversityComputer GraphicsThis should be a continuous surface, without a crease7Trilinear Interpolation in a HexahedronQ011Q111http://en.wikipedia.org/wiki/HexahedronQQQ010Q110Q001Q101uvmjb – September 5, 2014Oregon State UniversityComputer Graphics000 100 010 110 001 101 011 111(1 )(1 )(1 ) (1 )(1 ) (1 ) (1 ) (1 ) (1 )(1 ) (1 ) (1 )Q tuvQtuvQ tuvQtuvQ tuvQtuvQ tuvQtuvQ               Note: this works best with sides that are three pairs of quadrilaterals. Trilinear interpolation works less well on shapes like the pentagonal pyramid and the triangular dipyramid.Q000Q100tHigher-Order InterpolationWhile linear interpolation is the most common type used in graphics and geometric applications, there is no reason we cannot use higher-order interpolants.2()PtABtCt Second Order:001201234242APBPPPCPPP mjb – September 5, 2014Oregon State UniversityComputer Graphics23()PtABtCtDt  Third Order:(We are going to discuss this more when we get to keyframe