suggest algorithm: gradient-fill a polygon
in [General Programming]
|
From: Nicolas Bonneel on 2 Mar 2010 21:14 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. Random thoughts, from the easiest to the most coding involved: - 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). - Consider your problem as an interpolation problem between known values. Anything goes here : RBF, etc. - 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 (the diffusion curve paper by Alexandrina cited above, or the realtime gradient domain editing the same year at siggraph) or with sparse linear algebra packages (eg. TAUCS used before). Doing relaxations on the CPU can be coded in a few hours and the GPU in 1-2 days. Another paper kind of related is the ARDECO paper, although doing much more than you need. -- Nicolas Bonneel http://cs.ubc.ca/~nbonneel/
From: makc on 3 Mar 2010 01:46 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.
From: makc on 3 Mar 2010 01:49 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.
From: makc on 3 Mar 2010 01:50 On Mar 3, 12:51 am, Kaba <n...(a)here.com> wrote: > "Diffusion Curves: A Vector Representation for Smooth-Shaded Images" > > http://artis.imag.fr/Publications/2008/OBWBTS08/ > > Look at the video, its nice:) Just some food for thought, maybe you get > some ideas from that. I haven't looked into the paper too detailedly. > are you sure the URL is right? it refuses to open here.
From: makc on 3 Mar 2010 01:53
On Mar 3, 1:01 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > You could choose any curve for > them: > > - broken lines (adding dots in the radiuses to be able to bend them). > > - various classes of curve lines, as long as the "radiuses" don't > intersect. You would have to study the properties of various kind of > curves to find the adequate ones. While it is obvious how to do this manually, I am having a hard time imagining how to automate the process :( |