The 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 = ∞)p()2. Can only represent infinite lines, not finite line segments3Cl t2Dli t3D3.Can only represent 2D lines, not 3D “ l lmjb – September 5, 2014Oregon State UniversityComputer GraphicsNote: “z = mx + ny + b” is a plane, not a 3D lineParametric Line Equation:The “Shooting” FormP1P1010()xX tX XtP0010()yYtYY010()zZ tZ Z0. 1.tmjb – September 5, 2014Oregon State UniversityComputer GraphicsParametric Line Equation:The “Blending” FormP1P101(1 )xtX tXtP001(1 )ytYtY01(1 )ztZtZ01t0.1.tmjb – September 5, 2014Oregon State UniversityComputer GraphicsExample Use: Intersection of two 2D Line SegmentsP1P201 23xxuP0P301 23yyt01 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we 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 mjb – September 5, 2014Oregon State UniversityComputer Graphicsequations above to find (x*,y*), the point of intersection.What if t* or u* is < 0. or > 1. ?P1P1P2P1P1P3P0P2P3P00110.1.0.tu1.0.tuIt means you have a situation like one of these. The infinite lines intersect, but not the finite line segments. mjb – September 5, 2014Oregon State UniversityComputer Graphics(3,3)(0,2)An Example with Numbers(3,3)(0,2)tu(0,0)(6,0)t01 0 1 0()xxtxx23 2 3 2()xxtxx010(30) xt01 0 1 0()yytyy 230(60) xu01 0 1 0()xxtxx23 2 3 2()yytyy23 2 3 2()xxtxx01()23()232(02) yu36tu322tu010(30) yt322tu**11;24tu**1.5; 1.5xymjb – September 5, 2014Oregon State UniversityComputer Graphics24What if the Lines are Parallel ?P0P1→∞P2P3Well, 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 would be a divide by zero.ySo, 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 intersectmjb – September 5, 2014Oregon State UniversityComputer Graphicsthat means that the line segments do not intersect.Linear Blending Shows Up in a Lot of Computer Graphics-Related ApplicationsYou can linearly blend any two quantities with:01(1 )QtQtQcolor, shape, location, angle, scale factors, •••,p, ,g, ,mjb – September 5, 2014Oregon State UniversityComputer GraphicsYou canbilinearlyblendany2D quantities within a quadrilateral by writingBilinear Interpolation in a QuadrilateralYou can bilinearlyblend any2D quantities within a quadrilateral by writingthe line blending equation twice and then blending the two lines with:(1 )QQQ01 11(1 )BQtQtQQ01Q11tQ10Q01uu00 10(1)AQtQtQQ0010t00 10()AQQQ00100111(1 ) (1 )(1 ) (1 ) (1 )ABABQuQuQtuQtuQtuQtuQ       mjb – September 5, 2014Oregon State UniversityComputer Graphics00 0 0You can derive this equation by doing a blendofablendBilinear Interpolation in a QuadrilateralYou 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.For example right here t = 1 and u = 0For 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.(1 ) (1 )(1 ) (1 ) (1 )QQQtQtQtQtQQ00,Q01,Q1100 10 01 11(1 ) (1 )(1 ) (1 ) (1 )AB A BQuQuQtuQtuQtuQtuQ mjb – September 5, 2014Oregon State UniversityComputer GraphicsSo, you can actually just write the bilinear equation “by inspection”.Bilinear Interpolation in a QuadrilateralDidil t lDidil t lDrawing a quadrilateral as two triangles:Drawing a quadrilateral with bilinear interpolation:This diagonal should have some blue and green in it, but it doesn’tThis should be a continuous surface, without a creasemjb – September 5, 2014Oregon State UniversityComputer GraphicsTrilinear Interpolation in a HexahedronQ011QQ010Q110Q011Q111vhttp://en.wikipedia.org/wiki/HexahedronQ001Q101uQ000Q100t000 100 010 110 001 101 011 111(1 )(1 )(1 ) (1 )(1 ) (1 ) (1 ) (1 ) (1 )(1 ) (1 ) (1 )Q t u v Q t u v Q t u v Q tu v Q t u vQ t u vQ t uvQ tuvQ               mjb – September 5, 2014Oregon State UniversityComputer GraphicsNote: 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.Higher-Order InterpolationWhile linear interpolation is the most common type used in graphics and geometric pypgpgapplications, there is no reason we cannot use higher-order interpolants.2()Pt A Bt Ct Second Order:()Pt A Bt Ct 034APBPPP01201234242BPPPCPPP23()Pt A Bt Ct Dt  Third Order:()Pt A Bt Ct Dt  Third Order:(We are going to discuss this more when we get to keyframe animation)mjb – September 5, 2014Oregon State UniversityComputer