Rather than thinking about your quad, think about the following:

Consider a unit square. Suppose you were given scalar values for the four vertices, and you wanted to interpolate these values throughout the square. Using bilinear interpolation, you would know how to do that.

Well now consider defining THREE scalar functions on the square by interpolating THREE sets of values assigned to the vertices. Nothing has changed, right? It's the same problem as before, just now done three times.

Now call those three functions "x," "y," and "z." What you have defined is a map from the unit square, to a surface in three dimensions.

Now map a regular grid through this function.

It seems to me like you could use the parametric form of the plane equation to solve this problem.

The parametric form of a plane is as follows, given 3 points (V0, V1 and V2) describing a triangle lying on a plane. (Your triangle, in other words).

[source]
P(u,v) =V0 + u*(V1-V0) + v*(V2-V0)
[/source]

Any point on the plane can be described in terms of the parameters u and v. However, if the parameters fall within the constraints of u>=0 v>=0 u+v<=1 then the point they describe lies within the triangle. So it seems to me like you could use this to iterate your triangle and place points.

For example, you could iterate on u from 0 to 1, stepping a number of times equal to your sample spacing. Then in an inner loop, you iterate on v from 0 to 1-u. Then plug the values for u and v into the equation to obtain a point:

[source]
-- steps: Number of steps to take per side of triangle
-- spacing: Spacing of samples

steps=4
spacing=1/steps

for u=0,1,spacing do
for v=0,1-u,spacing do
local px=V0.x + u*(V1.x-V0.x) + v*(V2.x-V0.x)
local py=V0.y + u*(V1.y-V0.y) + v*(V2.y-V0.y)
addPointToList(px,py)
end
end
[/source]

This should serve the purpose of generating points evenly spaced across the triangle. I put together a quick Lua program of my own to test it out:

[source]
V0={x=0.5,y=0}
V1={x=0,y=1}
V2={x=1,y=1}

img=CArray2Dd()
img:resize(512,512)

steps=20
spacing=1/steps

-- Draw triangle outline
for c=0,1,0.001 do
local px=V0.x+c*(V1.x-V0.x)
local py=V0.y+c*(V1.y-V0.y)
local nx,ny = math.floor(px*511), math.floor(py*511)
img:set(nx,ny,1)

px=V0.x+c*(V2.x-V0.x)
py=V0.y+c*(V2.y-V0.y)
nx,ny = math.floor(px*511), math.floor(py*511)
img:set(nx,ny,1)

px=V1.x+c*(V2.x-V1.x)
py=V1.y+c*(V2.y-V1.y)
nx,ny=math.floor(px*511), math.floor(py*511)
img:set(nx,ny,1)
end

-- Draw spaced points

local u,v
for u=0,1,spacing do
for v=0,1-u,spacing do
local px=V0.x + u*(V1.x-V0.x) + v*(V2.x-V0.x)
local py=V0.y + u*(V1.y-V0.y) + v*(V2.y-V0.y)
local nx,ny=math.floor(px*511), math.floor(py*511)
img:set(nx,ny,1)
end
end

saveDoubleArray("triangle.tga", img)
[/source]

This was the result:


Looks like it does what you seem to want.

Either way -- triangle or quad -- the basic idea is to take a standard, "unit" version of the shape (whether it be the unit square, or a unit right triangle), interpolate vertex coordinates across it, and then push a grid through that map.

For the quad case, bilinear interpolation is the natural method to use.

For the triangle case, linear interpolation is the natural method, and I think FLeBlanc's post covers everything that needs to be said on this!


Vector3 interolateQuad(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4, float s, float t)
{
Vector3 p1_p2 = lerp(p1, p2, s);
Vector3 p4_p3 = lerp(p4, p3, s);
return lerp(p1_p2, p4_p3, t);
}