CODEWITHSUNDEEP
f#geometryinterpolation
kiooikml
kiooikml

Reputation: 307

Interpolating a triangle

I am currently developing a grid for a simple simulation and I have been tasked with interpolating some values tied to vertices of a triangle.

So far I have this:

let val1 = 10f 
let val2 = 15f 
let val3 = 12f

let point1 = Vector2(100f, 300f), val1
let point2 = Vector2(300f, 102f), val2 
let point3 = Vector2(100f, 100f), val3

let points = [point1; point2; point3]
let find (points : (Vector2*float32) list) (pos : Vector2) = 
    let (minX, minXv) = points |> List.minBy (fun (v, valu) -> v.X)
    let (maxX, maxXv) = points |> List.maxBy (fun (v, valu)-> v.X)
    let (minY, minYv) = points |> List.minBy (fun (v, valu) -> v.Y)
    let (maxY, maxYv) = points |> List.maxBy (fun (v, valu) -> v.Y)
    let xy = (pos - minX)/(maxX - minX)*(maxX - minX)
    let dx = ((maxXv - minXv)/(maxX.X - minX.X))
    let dy = ((maxYv - minYv)/(maxY.Y - minY.Y))
    
    ((dx*xy.X + dy*xy.Y)) + minXv

Where you get a list of points forming a triangle. I find the minimum X and Y and the max X and Y with the corresponding values tied to them.

The problem is this approach only works with a right sided triangle. With an equilateral triangle the mid point will end up having a higher value at its vertex than the value that is set.

So I guess the approach is here to essentially project a right sided triangle and create some sort of transformation matrix between any triangle and this projected triangle?

Is this correct? If not, then any pointers would be most appreciated!

Upvotes: 0

Views: 407

Answers (1)

MvG
MvG

Reputation: 60868

You probably want a linear interpolation where the interpolated value is the result of a function of the form

f(x, y) = a*x + b*y + c

If you consider this in 3d, with (x,y) a position on the ground and f(x,y) the height above it, this formula will give you a plane.

To obtain the parameters you can use the points you have:

f(x1, y1) = x1*a + y1*b * 1*c = v1        ⎛x1 y1 1⎞   ⎛a⎞   ⎛v1⎞
f(x2, y2) = x2*a + y2*b * 1*c = v2        ⎜x2 y2 1⎟ * ⎜b⎟ = ⎜v2⎟
f(x3, y3) = x3*a + y3*b * 1*c = v3        ⎝x3 y3 1⎠   ⎝c⎠   ⎝v3⎠

This is a 3×3 system of linear equations: three equations in three unknowns.

You can solve this in a number of ways, e.g. using Gaussian elimination, the inverse matrix, Cramer's rule or some linear algebra library. A numerics expert may tell you that there are differences in the numeric stability between these approaches, particularly if the corners of the triangle are close to lying on a single line. But as long as you're sufficiently far away from that degenerate situation, it probably doesn't make a huge practical difference for simple use cases. Note that if you want to interpolate values for multiple positions relative to a single triangle, you'd only compute a,b,c once and then just use the simple linear formula for each input position, which might lead to a considerable speed-up.

Advanced info: For some applications, linear interpolation is not good enough, but to find something more appropriate you would need to provide more data than your question suggests is available. One example that comes to my mind is triangle meshes for 3d rendering. If you use linear interpolation to map the triangles to texture coordinates, then they will line up along the edges but the direction of the mapping can change abruptly, leading to noticeable seams. A kind of projective interpolation or weighted interpolation can avoid this, as I learned from a paper on conformal equivalence of triangle meshes (Springborn, Schröder, Pinkall, 2008), but for that you need to know how the triangle in world coordinates maps to the triangle in texture coordinates, and your also need the triangle mesh and the correspondence to the texture to be compatible with this mapping. Then you'd map in such a way that you not only transport corners to corners, but also circumcircle to circumcircle.

Upvotes: 2

Related Questions