Difference between revisions of "Diffusion Curves"

From Inkscape Wiki
Jump to navigation Jump to search
 
(11 intermediate revisions by 2 users not shown)
Line 28: Line 28:
Note that with diffusion curves the blur itself can also vary along the path, which could be used in the above image to let the edge be sharper in some areas. This is useful for depth of field effects for example.
Note that with diffusion curves the blur itself can also vary along the path, which could be used in the above image to let the edge be sharper in some areas. This is useful for depth of field effects for example.


Normally diffusion curves will have infinite extent, but this can be controlled when needed by surrounding a set of curves with a closed path that has an outside boundary which is fully transparent.
Normally diffusion curves will have infinite extent, but this can be controlled when needed by surrounding a set of curves with a closed path that has an outside boundary which is fully transparent. Or by simply treating diffusion curves as yet another paint server.
 
Instead of defining a group that gets diffused it may also make sense to use subpaths and diffuse those:
 
<path d="M 0,0 L 190,190 M 500,500 L 150,0"
      leftBoundary="#F00 #00F #F70 #7F0" rightBoundary="#00F #F00 #0F7 #07F"
      boundaryBlur="5" diffuse="true" />
 
Or (only a single color per point on the path and no blur):
 
<diffusionGradient id="gradient">
  <stop ...>
  ...
</diffusionGradient>
<path d="M 0,0 L 190,190 M 500,500 L 150,0"
      fill="url(#gradient)" />
 
This could lead to an on-canvas interface (using an extended gradient tool) that looks a bit like this:
 
[[Image:fudgedDiffCurve.png]]
 
Here the "gradient stops" are (necessarily) positioned on the path and represented by the circles. The color inside the circles shows the stop color.


==Mathematical Definition==
==Mathematical Definition==
Diffusion curves are defined as the solution to a Laplace equation (the sum of second partial derivatives is zero) with boundary conditions (the colors on the curves). This is done for both the colors and the blur and then a spatially varying blur is applied to the diffused colors using the diffused blur values.
Diffusion curves are defined as the solution to a Laplace equation (the sum of second partial derivatives is zero) with boundary conditions (the colors on the curves). This is done for both the colors and the blur and then a spatially varying blur is applied to the diffused colors using the diffused blur values.
Alternatively diffusion curves can be seen as minimizing the integral (over the entire image) of the squared gradient magnitude, with color constraints at certain points. This is convenient when using a representation based on triangles with barycentric interpolation (as this yields a piecewise linear function the Laplacian is zero everywhere, except on the boundaries).
It might also be convenient to use an alternative method for incorporating blur, as simulating a spatially varying blur is not easy. One method might be to use an equation based on the heat equation which can be used for doing a spatially varying blur (<math>C</math> represents the color constraints):
<math>\begin{align}
\gamma\frac{\partial}{\partial t}y&=\nabla\cdot(\beta\nabla y)
\\\gamma(f-C)&=\nabla\cdot(\beta\nabla f)
\\0&=\nabla\cdot(\beta\nabla f)+\gamma(C-f)
\\f&=\arg\min_f \int_{\mathbb{R}^2}\frac{1}{2}\|\beta^{1/2}\nabla f\|^2+(C-\frac{1}{2}f)\gamma f\,dx
\end{align}</math>
Or else the color constraints could be applied using the derivative of the colors over each edge in combination with ''the'' color on the edge (which would be the average of the colors on either side). When blurring an edge the derivative would get smaller (by a factor of <math>\frac{1}{blurRadius}</math> for example).


==Converting to SVG==
==Converting to SVG==
There would be several possible avenues for converting diffusion curves to SVG:
There would be several possible avenues for converting diffusion curves to SVG:
*Bitmap rendering... (Obviously not very appealing.)
*Bitmap rendering.
*Using filters (for example, it should be possible to simulate spatially varying blur by doing multiple blurs and combining the results using weights).
**+ High quality at a specific resolution.
*By solving the Laplace equations on a Delaunay triangulation or something similar, and using ordinary gradients and/or blurs for the finishing touches or to make it possible to use a coarser grid. (This could give problems in the presence of "curved curves".)
**- Low quality on zooming in.
**- Also large for simple images (although it's not too bad, the gradients compress ''very'' well).
*Using filters (for example, it should be possible to [[Spatially Varying Blur|simulate spatially varying blur]] by doing multiple blurs and combining the results using weights).
**+ Very low (almost fixed) storage requirements.
**- Diffusion difficult to implement efficiently (fast solvers on grids generally use multigrid methods or kernels of spatially varying size).
**- Spatially varying blur is difficult to implement with good quality.
*By solving the Laplace equations on a (Delaunay) triangulation, using barycentric interpolation between the vertices.
**+ Good quality at any resolution.
**+ Storage scales directly with the complexity of the image.
**- Storage can be quite bad for curved geometries (because of the number of triangles needed to approximate the curve).
**- Needs "add" (and "in") compositing, which is only available in filters in SVG 1.1 (it is also available in [http://www.w3.org/TR/SVGCompositing/ SVG Compositing]).
**- A mesh is apparently hard to render in a high quality manner on existing renderers (at least Batik has problems with rendering the triangles precisely).
**Note that other interpolation/approximation schemes can give a higher quality result but are also harder to use in the solver (as well as in the resulting SVG).
*It might be possible to use the result of a boundary element computation directly and just combine basis functions.


==Questions/Problems==
==Questions/Problems==
Line 44: Line 91:
**It might actually be interesting to not only set colors and blur values (heat capacity?) along the sides of edges (1D), but also for surfaces (2D). This shouldn't complicate things much. In fact, it might even be slightly easier to handle the 2D case properly (as it is easier to discretize for example).
**It might actually be interesting to not only set colors and blur values (heat capacity?) along the sides of edges (1D), but also for surfaces (2D). This shouldn't complicate things much. In fact, it might even be slightly easier to handle the 2D case properly (as it is easier to discretize for example).
*It might be interesting to redefine them in some way that unifies the color diffusion and blurring. E.g. currently colors are either to be met exactly or not at all, is it possible to reformulate the problem in such a way that we can restrict colors to varying degrees?
*It might be interesting to redefine them in some way that unifies the color diffusion and blurring. E.g. currently colors are either to be met exactly or not at all, is it possible to reformulate the problem in such a way that we can restrict colors to varying degrees?
*Could a diffusion curve have a stop which is not completely opaque? I would find this useful for creating lighting effects over surfaces. --[[User:Pajarico|Pajarico]] 23:11, 15 January 2011 (UTC)
** Yes, it could. In fact, it's quite trivial to do so, as diffusion curves are handled per channel anyway. And it's not too difficult to show that this yields sensible results if you use (premultiplied) alpha. How this behaves in practice remains to be seen, however, but I would expect this to more or less just work. --[[User:Jaspervdg|Jaspervdg]] 08:16, 18 January 2011 (UTC)


==Links==
==Links==
*Original paper: http://artis.imag.fr/Publications/2008/OBWBTS08/
*Original paper (and program to edit/view them): http://artis.imag.fr/Publications/2008/OBWBTS08/
*PhD thesis (including a method for vectorizing Diffusion Curves): http://artis.imag.fr/Publications/2009/Orz09/
*PhD thesis (including a method for vectorizing Diffusion Curves): http://artis.imag.fr/Publications/2009/Orz09/
*Diffusion constraints: http://artis.inrialpes.fr/Publications/2010/BEDT10/
*Diffusion constraints: http://artis.inrialpes.fr/Publications/2010/BEDT10/
*Faster/better solver: http://www.cg.tuwien.ac.at/research/publications/2009/jeschke-09-solver/
*Faster/better solver: http://www.cg.tuwien.ac.at/research/publications/2009/jeschke-09-solver/
*Application of diffusion curves to texture rendering: http://www.cg.tuwien.ac.at/research/publications/2009/jeschke-09-rendering/
*Application of diffusion curves to texture rendering: http://www.cg.tuwien.ac.at/research/publications/2009/jeschke-09-rendering/
*Quality issues and using the Analytic Element Method to combat them: http://irs.ub.rug.nl/dbi/4d10adac9b054 (backup: http://home.hccnet.nl/th.v.d.gronde/ThesisJvdGFinal2.pdf)
*Some grid-based implementations: https://code.launchpad.net/~jaspervdg/+junk/diffuselib
*Implementation based on the Analytic Element Method: https://code.launchpad.net/~jaspervdg/+junk/aem-diffusion-curves
*More references: http://www.citeulike.org/user/jaspervdg/tag/diffusion_curves

Latest revision as of 17:35, 11 December 2011

Diffusion Curves are a way of specifying very free form gradients. It works by letting colors diffuse from curves, seeding the colors along both sides of the curves using gradients (along the curves). Additionally a varying amount of blur can be applied along the curves. This makes diffusion curves extremely flexible and very interesting to have in Inkscape.

Representation

The links at the bottom define various features that can be useful for Diffusion Curves. Here the following features are considered:

  • Colors at nodes / gradients defined on paths (on one or both sides of the curve)
  • Diffusion across boundaries

Diffusion curves could be represented by paths with gradients attached to them, along with an enclosing group that says that the colors should be diffused within that group. For example (don't mind the exact attributes):

<g diffuse="true">
  <path d="M 0,0 L 190,190"
        leftBoundary="#F00 #00F" rightBoundary="#00F #F00" boundaryBlur="5" />
</g>

Or:

<g diffuse="true">
  <path d="M 0,0 L 190,190"
        leftBoundary="url(#redToBlue)" rightBoundary="url(#blueToRed)" boundaryBlur="5" />
</g>

Assuming that the two gradients are made to go from #F00 to #00F and vice versa this would roughly look like this (note that this is just a rough approximation):

DiffusionCurveSimulation.png

Note that with diffusion curves the blur itself can also vary along the path, which could be used in the above image to let the edge be sharper in some areas. This is useful for depth of field effects for example.

Normally diffusion curves will have infinite extent, but this can be controlled when needed by surrounding a set of curves with a closed path that has an outside boundary which is fully transparent. Or by simply treating diffusion curves as yet another paint server.

Instead of defining a group that gets diffused it may also make sense to use subpaths and diffuse those:

<path d="M 0,0 L 190,190 M 500,500 L 150,0"
      leftBoundary="#F00 #00F #F70 #7F0" rightBoundary="#00F #F00 #0F7 #07F"
      boundaryBlur="5" diffuse="true" />

Or (only a single color per point on the path and no blur):

<diffusionGradient id="gradient">
  <stop ...>
  ...
</diffusionGradient>
<path d="M 0,0 L 190,190 M 500,500 L 150,0"
      fill="url(#gradient)" />

This could lead to an on-canvas interface (using an extended gradient tool) that looks a bit like this:

FudgedDiffCurve.png

Here the "gradient stops" are (necessarily) positioned on the path and represented by the circles. The color inside the circles shows the stop color.

Mathematical Definition

Diffusion curves are defined as the solution to a Laplace equation (the sum of second partial derivatives is zero) with boundary conditions (the colors on the curves). This is done for both the colors and the blur and then a spatially varying blur is applied to the diffused colors using the diffused blur values.

Alternatively diffusion curves can be seen as minimizing the integral (over the entire image) of the squared gradient magnitude, with color constraints at certain points. This is convenient when using a representation based on triangles with barycentric interpolation (as this yields a piecewise linear function the Laplacian is zero everywhere, except on the boundaries).

It might also be convenient to use an alternative method for incorporating blur, as simulating a spatially varying blur is not easy. One method might be to use an equation based on the heat equation which can be used for doing a spatially varying blur ([math]\displaystyle{ C }[/math] represents the color constraints):

[math]\displaystyle{ \begin{align} \gamma\frac{\partial}{\partial t}y&=\nabla\cdot(\beta\nabla y) \\\gamma(f-C)&=\nabla\cdot(\beta\nabla f) \\0&=\nabla\cdot(\beta\nabla f)+\gamma(C-f) \\f&=\arg\min_f \int_{\mathbb{R}^2}\frac{1}{2}\|\beta^{1/2}\nabla f\|^2+(C-\frac{1}{2}f)\gamma f\,dx \end{align} }[/math]

Or else the color constraints could be applied using the derivative of the colors over each edge in combination with the color on the edge (which would be the average of the colors on either side). When blurring an edge the derivative would get smaller (by a factor of [math]\displaystyle{ \frac{1}{blurRadius} }[/math] for example).

Converting to SVG

There would be several possible avenues for converting diffusion curves to SVG:

  • Bitmap rendering.
    • + High quality at a specific resolution.
    • - Low quality on zooming in.
    • - Also large for simple images (although it's not too bad, the gradients compress very well).
  • Using filters (for example, it should be possible to simulate spatially varying blur by doing multiple blurs and combining the results using weights).
    • + Very low (almost fixed) storage requirements.
    • - Diffusion difficult to implement efficiently (fast solvers on grids generally use multigrid methods or kernels of spatially varying size).
    • - Spatially varying blur is difficult to implement with good quality.
  • By solving the Laplace equations on a (Delaunay) triangulation, using barycentric interpolation between the vertices.
    • + Good quality at any resolution.
    • + Storage scales directly with the complexity of the image.
    • - Storage can be quite bad for curved geometries (because of the number of triangles needed to approximate the curve).
    • - Needs "add" (and "in") compositing, which is only available in filters in SVG 1.1 (it is also available in SVG Compositing).
    • - A mesh is apparently hard to render in a high quality manner on existing renderers (at least Batik has problems with rendering the triangles precisely).
    • Note that other interpolation/approximation schemes can give a higher quality result but are also harder to use in the solver (as well as in the resulting SVG).
  • It might be possible to use the result of a boundary element computation directly and just combine basis functions.

Questions/Problems

  • If diffusion curves are indeed represented by paths inside a group, what happens with subgroups or shapes without having gradients defined along their edges?
  • What should happen with 2D objects (filled shapes and strokes) in diffusion groups?
    • It might actually be interesting to not only set colors and blur values (heat capacity?) along the sides of edges (1D), but also for surfaces (2D). This shouldn't complicate things much. In fact, it might even be slightly easier to handle the 2D case properly (as it is easier to discretize for example).
  • It might be interesting to redefine them in some way that unifies the color diffusion and blurring. E.g. currently colors are either to be met exactly or not at all, is it possible to reformulate the problem in such a way that we can restrict colors to varying degrees?
  • Could a diffusion curve have a stop which is not completely opaque? I would find this useful for creating lighting effects over surfaces. --Pajarico 23:11, 15 January 2011 (UTC)
    • Yes, it could. In fact, it's quite trivial to do so, as diffusion curves are handled per channel anyway. And it's not too difficult to show that this yields sensible results if you use (premultiplied) alpha. How this behaves in practice remains to be seen, however, but I would expect this to more or less just work. --Jaspervdg 08:16, 18 January 2011 (UTC)

Links