Jump to content
  • Advertisement
Sign in to follow this  
Alessandro

Interpolating quad points...

This topic is 2510 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'd like some suggestions on the following matter. I have 4 splines at each corner of a quad (see attached screenshot).
The quad it's not regular: in the project I'm doing, it will never become concave, yet can be a trapezium or lozenge.

I need to fill the quad with splines, with regular order. So that there will be, for example, 4 rows by 4 columns of new splines.

I'd like to know what would be a way to actually calculate these "hook" points (marked those in green to make an example): with a regular quad that would be easy (just iterating from top left to bottom right corner), but with an irregular it's more difficult.

Thanks for any help wink.png
point_interpolation.jpg

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
Thanks for the help, Emergent.

So basically you say to define an x() that holds minimum and maximum x coordinates; and do the same with an y() and z() function for the y and z coordinates.

And then loop n times, and pick values returned from the three functions at each step?

Share this post


Link to post
Share on other sites
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:
QPIRn.png

Looks like it does what you seem to want.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites

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);
}

Share this post


Link to post
Share on other sites
Thank you very much for all the solutions you offered guys: I'm going to implement those in my project today. I've also bookmarked this thread, it will be very useful for me also in the future...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!