5/15/20131Resampling Scattered Data into a Regular GridMike [email protected] State Universitymjb – May 15, 2013Oregon State UniversityComputer GraphicsThe ProblemOftentimes data points are located irregularly, that is, they are not in nice, neat rectilinear grids.This is called Scattered Data.ssca edScatte ed ataTo use the Interpolated Color method (like in Project 4a), we need to triangulate the data so we can draw color-interpolated triangles.To use Contours (like in Project 4b), we need to triangulate the mjb – May 15, 2013Oregon State UniversityComputer Graphicshttp://www.ncdc.noaa.gov/nexradinv/data and re-sample it into a rectangular grid.5/15/20132Once you have a Good Triangularization, You Can Superimpose any Data Grid You Want,and Re-sample the Data Values Theremjb – May 15, 2013Oregon State UniversityComputer Graphicshttp://www.ncdc.noaa.gov/nexradinv/Not all Triangularizations are Created Equal:Which of These is Better, and Why?mjb – May 15, 2013Oregon State UniversityComputer Graphicshttp://www.ncdc.noaa.gov/nexradinv/Long andSkinnyTriangles5/15/20133Three Steps1. Fit a good set of triangles through the scattered points 2. Find out which triangle each new point is in3. Interpolate within those trianglesmjb – May 15, 2013Oregon State UniversityComputer Graphics1. Delauney TriangulationThis is an incremental algorithm, that is, you start with a “frame triangularization”, and add a point at a time, adjusting the triangularization each time.mjb – May 15, 2013Oregon State UniversityComputer Graphics5/15/20134Adding a Pointmjb – May 15, 2013Oregon State UniversityComputer Graphics1. Add a new point 2. Figure out which triangle it is in.3. Create 3 new triangles by drawing lines from the new point to the 3 vertices of the bounding triangleLook at each New Triangle,and Decide if it is Too Long and Skinnymjb – May 15, 2013Oregon State UniversityComputer Graphics2. Figure out which triangle it is in.3. Create 3 new triangles by drawing lines from the new point to the 3 vertices of the bounding triangle4. For each of the 3 new triangles, fit a circle through the 3 vertices (the new point, and the two existing points).5/15/20135If it’s Too Long and Skinny, Fix Itmjb – May 15, 2013Oregon State UniversityComputer Graphics4. For each of the 3 new triangles, fit a circle through the 3 vertices (the new point, and the two existing points).5. If the opposite point is inside the circle, then the circle is “too big”, indicating that this created triangle is too long and skinny.6. Delete the existing bounding edge , thus deleting two triangles.If it’s Too Long and Skinny, Fix Itmjb – May 15, 2013Oregon State UniversityComputer Graphics5. If the opposite point is inside the circle, then the circle is “too big”, indicating that this created triangle is too long and skinny.6. Delete the existing bounding edge, thus deleting two triangles.7. Add a cross edge to make 2 new triangles5/15/20136A Very Slight Change in Point Location will affect the Triangularizationmjb – May 15, 2013Oregon State UniversityComputer Graphics2. Is a Point inside a Triangle?()()nRQSQLet:Sn()()nRQSQ()()QnRQPQ()()RnSRPR()()QS PSQPmjb – May 15, 2013Oregon State UniversityComputer Graphics()()snQS PSRFinding if a point is inside a triangle is used both in the Delauneytriangularization algorithm and in re-sampling to a new grid(),(),()qr snn nn andnn are all positive, then P is inside the triangle QRSIf5/15/201373. Interpolating Data Values within a TriangleVertex #2:x2, y2, s2Once we know the point is within a particular triangle we need toVertex #0:x0, y0, s0(x,y)Vertex #1:x1, y1, s1mjb – May 15, 2013Oregon State UniversityComputer GraphicsOnce we know the point is within a particular triangle, we need to interpolate within that triangle. Use a linear function:SAxByCThink of the Scalar Function as Elevationsand Think of the Triangle Linear Interpolation Function as a Plane Being Fittedon top of the Data ValuesVertex #0:x0, y0, s0Vertex #1:x1, y1, s1Vertex #2:x2, y2, s2mjb – May 15, 2013Oregon State UniversityComputer Graphics5/15/20138000sAx By CsAxByCSince, at Vertices 0, 1, and 2, we know x, y, and s,we can write 3 Equations with 3 Unknowns111222sAxByCsAx By C00 01xyAs    or, in matrix form:mjb – May 15, 2013Oregon State UniversityComputer Graphics00 011 122 211yxyBsxyCs    000111sAxByCsAxByCYou can actually simplify it to 2 Equations with 2 Unknowns10 10 1 0()()()()ssAxx Byyss Axx Byy111222sAxByC10 10 10xxyy ssA   or, in matrix form:20 20 2 0()()ss Axx Byymjb – May 15, 2013Oregon State UniversityComputer Graphics20 20 20xxyy ssB  5/15/2013910 10 1020 20 20xxyy ssAxxyy ssB   Solve this 2x2 System in your Favorite Way – Cramer’s Rule Works Well()( )()( )102 0 201 0102 0 20101020 2010102 0 2010()( )()( )()( )()()()()()()()( )()()ssy y ssyyAxxy y xxyyxxs s x xssBxxy y xxyymjb – May 15, 2013Oregon State UniversityComputer GraphicsC is then computed by:000Cs Ax ByIs it possible for A and/or B to compute to infinity?What would that mean?Interpolating Data Values within a Triangle: An ExampleVertex #0:X=0.Vertex #2:X = 3.Y = 2.S = 17.SAxByCX 0.Y = 0.S = 0.Vertex #1:X = 4.Y = 0.S = 12.(2,1)mjb – May 15, 2013Oregon State UniversityComputer Graphics5/15/201310The Delauney Triangles can be used to Derive a Voronoi Diagrammjb – May 15, 2013Oregon State UniversityComputer GraphicsThink of this as showing “Regions of Influence” around a Data PointVoronoi Diagram:Most of the Time, the Lines are the Perpendicular Bisectors of the Triangle Edgesmjb – May 15, 2013Oregon State UniversityComputer Graphics5/15/201311Voronoi Regions of Influencemjb – May 15, 2013Oregon State UniversityComputer