suggest algorithm: gradient-fill a polygon
in [General Programming]
|
From: Nicolas Bonneel on 3 Mar 2010 16:20 makc wrote: > On Mar 3, 4:14 am, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: >> - Compute the distance transform from the boundary of the polygons and >> the distance transform from the white points. Then blend between these >> two distances (never tested, but I guess it should work). > > this is currently main idea at http://forums.xkcd.com/viewtopic.php?f=12&t=57099 > too; I guess it's the most simple (conceptually) idea so far, but > still have to be tested. my guess is that this should only rigorously work for specific metric (maybe the L_\infty metric or for ultrametric spaces), but should only be an approximate hack if you planned to use an L2 norm... -- Nicolas Bonneel http://cs.ubc.ca/~nbonneel/
From: Dave Eberly on 4 Mar 2010 01:36 "makc" <makc.the.great(a)gmail.com> wrote in message news:65521aa7-440d-4077-9cf2-430fc0091d48(a)g28g2000yqh.googlegroups.com... > On Mar 3, 12:35 am, "Dave Eberly" <dNOSPAMebe...(a)usemydomain.com> > wrote: >> This image has a question for you. >> http://www.geometrictools.com/Temp/GradFillConcave.png > > the exact answer to the question in this image is the answer to the > thread. the answer in genral terms (dark-grey) is the question of this > thread. The point of my image/question is that you are trying to use intuition for "gradient fill" based on a disk or a convex polygon. My image shows a concave polygon for which is not clear what you mean by "gradient fill". The answer I was looking for is what *you want intuitively* for portions of the polygon that are topologically far from the white dot. With an intuitive description, readers might be able to suggest an algorithm that generates what you want. You can make this even more complicated with a concave polygon that is nearly space filling. One possible algorithm is the following. Compute the Euclidean distance transform for the interior of the polygon, where the distance is measured to the polygon boundary. Call this function d(x,B), where x is a point in the polygon and where B is the polygon boundary. If x is on the boundary, then d(x,B) = 0. Compute the Euclidean distance transform for the interior of the polygon, where the distance is measured to your special point. Call this function d(x,y), where x is a point in the polygon and y is your special point. Let C0 be the color of the polygon boundary pixels. Let C1 be the color of the special point. Choose color C(x) for a polygon point x by C(x) = [d(x,y)/(d(x,y) + d(x,B))]*C0+ [d(x,B)/(d(x,y) + d(x,B))]*C1 Observe that C(x) = C0 when x is a point on the boundary B and C(y) = C1. I assume you are drawing the polygon on a raster grid. There are fast algorithms for computing the Euclidean distance transform on such grids. -- Dave Eberly http://www.geometrictools.com
From: makc on 7 Mar 2010 14:14 On Mar 3, 11:13 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: > makc wrote: > > On Mar 3, 4:14 am, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: > >> - Consider your problem as a minimization problem, where you want to > >> minimize the gradient in unknown location. This is basically a Poisson > >> problem, and is solved with any Poisson solver, passing the known points > >> as dirichlet boundary conditions. You can use relaxations techniques > >> which have shown to work well on the gpu > > > That's another interesting idea, do you think repeated drawing black > > edges/white point and averaging 3x3 pixels would do the trick, too? > > This is exactly the operations to do which converge to the > Laplacian(u)=0 solution. These are relaxation steps. > They have shown to converge... but very very slowly. If you're not > concerned with the speed or the accuracy, this is the way to go. > If you're concerned with either speed or accuracy, then you have to > switch to multigrid methods for example which compute these relaxation > steps at different mipmap levels. > Or using TAUCS which will solve exatly your problem (no accuracy issues > but it can be slow), but you have to build your finite difference matrix. > 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 :(
From: makc on 7 Mar 2010 16:20 On Mar 3, 11:20 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: > makc wrote: > > On Mar 3, 4:14 am, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: > >> - Compute the distance transform from the boundary of the polygons and > >> the distance transform from the white points. Then blend between these > >> two distances (never tested, but I guess it should work). > > > this is currently main idea athttp://forums.xkcd.com/viewtopic.php?f=12&t=57099 > > too; I guess it's the most simple (conceptually) idea so far, but > > still have to be tested. > > my guess is that this should only rigorously work for specific metric > (maybe the L_\infty metric or for ultrametric spaces), but should only > be an approximate hack if you planned to use an L2 norm... > xkcd guy formula gives this: http://megaswf.com/view/52ec1983b12c8f819bae3703c5d5b8fb.html (right now it's very slow, needs few seconds to complete) I wonder if there can be result any better than this though.
From: Nicolas Bonneel on 8 Mar 2010 16:49
makc wrote: > On Mar 3, 11:13 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: >> makc wrote: >>> On Mar 3, 4:14 am, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote: >>>> - Consider your problem as a minimization problem, where you want to >>>> minimize the gradient in unknown location. This is basically a Poisson >>>> problem, and is solved with any Poisson solver, passing the known points >>>> as dirichlet boundary conditions. You can use relaxations techniques >>>> which have shown to work well on the gpu >>> That's another interesting idea, do you think repeated drawing black >>> edges/white point and averaging 3x3 pixels would do the trick, too? >> This is exactly the operations to do which converge to the >> Laplacian(u)=0 solution. These are relaxation steps. >> They have shown to converge... but very very slowly. If you're not >> concerned with the speed or the accuracy, this is the way to go. >> If you're concerned with either speed or accuracy, then you have to >> switch to multigrid methods for example which compute these relaxation >> steps at different mipmap levels. >> Or using TAUCS which will solve exatly your problem (no accuracy issues >> but it can be slow), but you have to build your finite difference matrix. >> > > 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... -- Nicolas Bonneel http://cs.ubc.ca/~nbonneel/ |