suggest algorithm: gradient-fill a polygon
in [General Programming]
|
From: makc on 9 Mar 2010 04:01 On Mar 8, 11:49 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: > makc wrote: > [snip] > > this blurring idea did not work, at least in its simplest form: > >http://megaswf.com/view/dc3441f43c7f246ba433ac64def4955d.html > > > as you see, amount black pixels tend to "dominate" over time :( > > for int n=0 to Niterations > for all pixels(i,j) [where you need values, ie. not on your boundaries] > newpixels[i,j] = > 0.25*(pixel(i+1,j)+pixel(i-1,j)+pixel(i,j+1)+pixel(i,j-1)) > end for > pixels = newpixels; > end for. > > This should yield the right solution... No, that gives the same result but converges slower than 9 pixels blur: http://megaswf.com/view/ff61ad3c9189dfd7709cdccd55b72ef0.html
From: Nicolas Bonneel on 9 Mar 2010 16:45 makc wrote: > On Mar 8, 11:49 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: >> makc wrote: >> [snip] >>> this blurring idea did not work, at least in its simplest form: >>> http://megaswf.com/view/dc3441f43c7f246ba433ac64def4955d.html >>> as you see, amount black pixels tend to "dominate" over time :( >> for int n=0 to Niterations >> for all pixels(i,j) [where you need values, ie. not on your boundaries] >> newpixels[i,j] = >> 0.25*(pixel(i+1,j)+pixel(i-1,j)+pixel(i,j+1)+pixel(i,j-1)) >> end for >> pixels = newpixels; >> end for. >> >> This should yield the right solution... > > No, that gives the same result but converges slower than 9 pixels > blur: > http://megaswf.com/view/ff61ad3c9189dfd7709cdccd55b72ef0.html Either the result still hasn't converged (which is possible with such a method : the step size may be lower than the machine precision - especially if you are dealing with 8 bit images) or you have a bug : in any case, I just don't believe that the laplacian is 0 (ie., the gradient is minimized) over the whole image. The slope could be much smoother, ideally the slope would be constant in most places, giving a linear falloff instead of a gaussian-like one. Either try with floating point images (if this was not the case), or try a faster converging scheme, for example with multigrid (do the same thing with a coarser resolution of your image, then upsample and use that as an initial guess for the next level of your pyramid). If you want to convince yourself, type in matlab: z=zeros(100,1); z(50)=1; y=[0.5 0 0.5]; for i=1:1000, z=conv(z,y); z=z(2:end-1);z(50)=1; plot(z); pause(0.05); end; You'll end up with a perfect triangle - not a gaussian. But ok, in 1D here it requires 1000 iterations. -- Nicolas Bonneel http://cs.ubc.ca/~nbonneel/
From: makc on 10 Mar 2010 05:08 On Mar 9, 11:45 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: > ...in 1D here it requires 1000 iterations. the key here is "1D". check it out: http://megaswf.com/view/9e4c222a11e92ed4378684a291965fa9.html as you see, if we limit blur to 1D, it produces nice linear gradient in that direction. but that is because we have exactly 1 white pixel on one end, and 1 black pixel on another. in 2D, we have lots of black pixels that simply outweight our poor single white point.
From: Nicolas Bonneel on 10 Mar 2010 16:05 makc wrote: > On Mar 9, 11:45 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: >> ...in 1D here it requires 1000 iterations. > > the key here is "1D". > check it out: http://megaswf.com/view/9e4c222a11e92ed4378684a291965fa9.html > as you see, if we limit blur to 1D, it produces nice linear gradient > in that direction. > but that is because we have exactly 1 white pixel on one end, and 1 > black pixel on another. > in 2D, we have lots of black pixels that simply outweight our poor > single white point. There is no matter of outweighting : the "blurring" method *does* converge to the true solution of the Poisson equation, and it thus *should* give the right solution : ie. not a gaussian but a nice gradient. And indeed, in 2D this may require much more iterations. Which is why multigrid methods have been proposed (as well as domain decomposition methods like Schwartz's alternate one, multipole methods...). Fortunately, this blurring kernel is separable, so you may try applying it twice in 1D in both directions. If you alternate the x and y directions each time it should exactly lead to the solution which failed in your 2D case (not converging quick enough I guess). But if you first make the 1D solution converge in one direction and then continue it in the other direction, you may get a correct solution... I don't know if this is guaranteed. -- Nicolas Bonneel http://cs.ubc.ca/~nbonneel/
From: Andrew_M on 10 Mar 2010 17:02
makc wrote: > I have specified point inside polygon, and - well - polygon. I want to > paint the point white, and polygon perimiter black, and then smooth > gradient inbeween. > > For convex polygon, I would split it in a fan of triangles and > gradient-fill them, but for concave polygons this will not work > because of self-intersections. If I try to extend this algorithm by > dropping lots of points inside and applying delaunay triangulation, it > is not clear to me how to assign colors to vertices :( > > So, I was thinking maybe someone on the internet knows how to do it in > general case? you know, just for the sake of solution' completeness? > Everything goes - pathfinding, flood-fills, etc - as long as you have > an idea how to come from particular known algorithm to this specific > application, please post it. Assume, you wanna paint the only point white, perimiter black and all the rest of points inside your polygon with some intermediate (actually gray) color. In that case I could you recommend to use an analogue with e-field. One charged particle and perimeter, connected with ground (it means, with potential equal to zero). You have to solve Laplasian equation. Its solution is the sum of two components. The first is logarithm of the distance to one point you want to paint with white color. The second is to be added to reduce potential of a border to zero. The only problem is to get the second component. There are some methods to do it. For example, you may use the approach, described at the article on "diffusion curves". Rough rectangular mesh, few iterations, then add additional rows and columns to that mesh and so on. After you have get this solution, you have to replace it with another function, using solution of the Laplasian equation as an argument. Is it clear what I mean? Look, at the first stage you'll get something like y=log(r) what is not very smooth near your point. But, if you replace y with Y=1-exp(y) it would be more smooth (and limited at your point). You may use Y=(1-exp(y))*(1-exp(y)) as well or anything you want. I think it is the best method. Go ahead. |