Hey!

VERY NICE PROBLEM!!!

The thing you're looking for is Laplace's equation with Dirichlet boundary conditions.

Well, I guess you are not a mathematician, so a few words might help here.

There is a very nice and very smooth way to connect all these vertices. But to get the inner greyscales, you need to solve a so-called Laplace problem:

u_xx (x,y) + u_yy (x,y) = 0 for (x,y) in Omega
u(x,y) = u_0(x,y) for (x,y) in boundary(Omega)

u(x,y) is the function of your greyscales (not discretized yet) and u_xx and u_yy is the second derivative in x and y direction, resp. The domain Omega is just a square. The function u_0 lives on the boundary of the square and contains the boundary values you gave above.

The goal is to solve the equations above. It's a linear partial differential equation. The boundary values are "Dirichlet", that means their function value is given. (Alternatively, one could also give normal derivatives --> Neumann boundary conditions).

You solve it by first discretizing the derivatives.
For example

u_xx --> u(x+1,y )-2*u(x,y)+u(x-1,y )
u_yy --> u(x ,y+1)-2*u(x,y)+u(x ,y-1)

Imagine u(x,y) as a matrix now. The size of this matrix coincides with the size of your grayscale image. If you plug this into the equations above, you will (after a while) obtain a linear system of equations. So if you have a solver for this, it's not a problem.

This is the result I obtained with MATLAB (a software for mathematical stuff). The program is about 10 lines in MATLAB.

2.0  3.0  2.0  7.0  3.0  4.0  2.03.0  1.6  1.6  3.4  4.0  3.7  8.09.0  3.0  1.6  1.7  3.0  3.1  5.05.0  4.6  2.6  2.2  1.7  2.8  2.09.0  4.4  2.3  3.7  3.5  2.1  3.03.0  7.0  1.0  1.0  9.0  3.0  4.0

Laplace's equation is actually not the most straight-forward method, I admit. But it will give you the smoothest results - I will guarantee you.

If you need it just for one image, please be free to tell me where I can download it. Then I can plug it into my program and give you the result.


[edited by - Lutz on May 21, 2004 4:19:02 AM]

In your particular case, you should find a "bezier like curve" for each side.
With such curves defined you should be able to use a patch.

In this case, the "bezier like curve" should be something like f(t) = a*t^6 + b*t^5 + c*t^4 + d*t^3 + e*t^2 + f*t + g where a,b,c,d,e,f & g are the unknowns. This is true as long as you keep the same size for the rectangle sides (7 values for each side)
You will have to find a way to solve the previous equation, I dont know precisely how to do it but it should be using determinant and stuff.

I didnt experienced all this, I just deduced it from all I rode on the patch and bezier curves subjects so I''mnt sur it works

quote:Original post by MV
You will have to find a way to solve the previous equation

I mean you will have to find the a,b,c,d,e,f&g unknowns.

If you don''t want to use a linear system solver, you can also approximatively solve the problem using this pseudo code:

for eyery inner node v (the ones filled with 0 at the beginning)  v = (  node left  of v        + node right of v        + node above of v        + node below of v       + 4*v) / 8

Do this maybe 10-100 times and you should get a good approximation to the "true" solution. It is actually very easily implemented.