suggest algorithm: gradient-fill a polygon
in [General Programming]
|
From: Christian Gollwitzer on 10 Mar 2010 16:52 Nicolas Bonneel schrieb: > 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. Maybe you are not enforcing the boundary conditions the right way. What should be done, is to blur the whole image, and then reset the edge pixels to the values they should have. Also, there is an "optimal" kernel for doing this in 2D: IIRC, it is 1/5 4/5 1/5 4/5 1 4/5 1/5 4/5 1/5 (can be found in Jackson, J.D. Classical Electrodynamics) Another idea that came to my mind is: you could implement a recursive flood fill algorithm, the one which expands in all directions, not the line based one. The depth of the recursion then gives you a distance on a path to the border. Something along the lines proc floodme (x, y, depth) if border(x,y) return depth mark (x,y) if not marked(x,y+1) maxdepth = floodme(x,y+1,depth+1) endif if not marked(x+1,y) newdepth = floodme(x,y+1,depth+1) if newdepth > maxdepth then maxdepth=newdepth endif // same with x-1, y; x,y-1 // updating maxdepth set color (x,y) depth/maxdepth return maxdepth end (untested, of course) Christian
From: makc on 11 Mar 2010 09:08 On Mar 10, 11:52 pm, Christian Gollwitzer <Christian.Gollwit...(a)uni- bayreuth.de> wrote: > Maybe you are not enforcing the boundary conditions the right way. What > should be done, is to blur the whole image, and then reset the edge > pixels to the values they should have. Also, there is an "optimal" > kernel for doing this in 2D: IIRC, it is > > 1/5 4/5 1/5 > 4/5 1 4/5 > 1/5 4/5 1/5 > the sum of the above is 5, so I guess it is really 1/25 4/25 1/25 4/25 1/5 4/25 1/25 4/25 1/25 (otherwise everything goes white immediately) with this matrix the result is much like before: http://megaswf.com/view/ae6ac4c97192c760629be5a5360d8edf.html
From: makc on 11 Mar 2010 09:12 sorry, I don't buy that. On Mar 10, 11:05 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: > 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. not at all, as you see in 1D it is non-black on single scanline. if we now blur in 90° direction, these non-black pixels, having nothing to support their intensity, would fade to black again very quickly. if you think this is an error in my code, you can try to reproduce this in photoshop (or gimp), I would like to see the result of that. or I can just post the code, if you can compile actionscript.
From: Kaba on 11 Mar 2010 11:46 makc wrote: > with this matrix the result is much like before: > http://megaswf.com/view/ae6ac4c97192c760629be5a5360d8edf.html Hi, First, nice animations:) To me the animation seems just what I'd expect if the edges of the polygon feed black and the singular point feeds white. So, try with some more interesting white-feed shapes, such as with a line segment! And then let us see another nice animation:) -- http://kaba.hilvi.org
From: Nicolas Bonneel on 11 Mar 2010 18:35
makc wrote: > sorry, I don't buy that. > > On Mar 10, 11:05 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: >> 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. > > not at all, as you see in 1D it is non-black on single scanline. if we > now blur in 90� direction, these non-black pixels, having nothing to > support their intensity, would fade to black again very quickly. > > if you think this is an error in my code, you can try to reproduce > this in photoshop (or gimp), I would like to see the result of that. > or I can just post the code, if you can compile actionscript. ok, I tried in matlab with the pdetool and approximately the same shape, and it seems that the diffusion is too quick. Adding a small term in the right hand side seems to solve this problem quite a bit (ie. solving laplacian(f)=10 instead of 0)... |