Re: [Inkscape-user] Equivalent to Illustrator's Gradient Mesh?

On Friday, May 18, 2007, 7:10:17 PM, MenTaLguY wrote:


M> To do right, it's something we need some support from the SVG
M> folks on; the minimum requirement is simply triangle mesh gradients
M> in SVG; they would be easy to implement and accelerate in hardware,
M> and the other mesh gradient types can be simulated in terms of them without too much expense.

So, here are some thoughts on trimesh gradients.

Definitions and Introduction
----------------------------

A trimesh is a 2-dimensional lattice in which each face has at most 3 edges associated with it and each edge bounds at most 2 faces. 

Under modification, it is manifold at all times if each face has exactly 3 edges, each edge bounds either one or two faces, and is bounded by two vertices.  

A good xml structure would allow such constraints to naturally arise. This, its better to have faces point to edges and edges point to vertices. Adding an unused vertex or an unused edge does nothing; only when a face is added (or modified) to point to an edge and thus a vertex, is the actual rendered mesh changed. 

In 3D, trimesh is used to make geometry - a 2D manifold in 3d space. In 2D, the entire mesh is flat so it does not define a geometry. The interest is in interpolating the vertex colors (and opacities). Thus, in SVG, this would be a paint server.

Markup
------

There are a bunch of ways to model this in XML. Note that a vertex point can be shared by multiple faces, so an approach that makes vertices children of faces will not work; pointers are needed. Here is one form of markup that looks promising: faces point to their edges, and edges point to the vertices.

<trimesh xml:id="foo" meshUnits="userSpaceOnUse">
  <faces>
    <face e1="a" e2="b" e3="c"/>
  </faces>
  <edges>
    <edge xml:id="a" v1="p1" v2="p2"/>
    <edge xml:id="b" v1="p2" v2="p3"/>
    <edge xml:id="c" v1="p3" v2="p1"/>
  </edges>
  <vertices>
    <vertex xml:id="p1" vcolor="#27D" vopacity="0.5" x="12.7" y="3.5"/>
    <vertex xml:id="p2" vcolor="rgb(123, 254, 37)" vopacity="1" x="8.4" y="17.2"/>
    <vertex xml:id="p3" vcolor="#F0D" vopacity="0" x="3.2" y="14.1"/>
  </vertices>
</trimesh>

trimesh must have the content model faces, edges, vertices 9ie one of each, in that order). 
faces, edges, and vertices must have one or more of face, edge, or vertex respectively. (the actual minimum number is three for edges and vertices).

The e1, e2, e3 attributes on face are of type IDREF, are required, and must all point to valid edge elements in the same trimesh; otherwise, the face is not rendered. v1 and v2 on edge are IDREF, required, must point to vertex elements in the same trimesh; otherwise, the edge is invalid.

The structure above does not have explicit elements of attributes to indicate which faces are bound by each edge. To enforce the "bounds one or two edges" constraint would mean adding b1 and b2 attrs to edge; its not clear if this makes checking, construction or use easier. It would be good to look at what schematron can do to check this constraint when its implicit rather than explicit.

I'm assuming vcolor, vopacity, x and y can be animated. That means the triangles themselves are fixed, but can stretch and overlap.

Assume all elements can have xml:id on them.

Each vertex has a color and an opacity. Each edge has a linear gradient from the two colors (and opacities) forming the edge. Each face has a triangular gradient produced by interpolating the three colors (and opacities) of its three vertices.

For a gradient produced by a trimesh, the colors outside the mesh need to be defined. This might be done by defining a single external fill color on the trimesh element; or by asserting that outside the mesh, the color is transparent black. 

The coordinate system of the trimesh should be one of two types, userSpaceOnUse or objectBoundingBox; meshUnits is analogous to gradientUnits.

I'm not sure what to do about folding, where the triangles overlay each other. Its hard to forbid it (but see below).


Coding and testing
------------------

OpenGL

There are various bits of code lying around which could be pressed into service by stitching on an xml parser and getting the data dfrom there rather than from an asciifile (or by convertying the xml to the ascii format). As an example
http://www.cs.princeton.edu/gfx/proj/trimesh2/
or the older
http://graphics.stanford.edu/software/trimesh/trimesh-doc.html
http://graphics.stanford.edu/software/trimesh/
which give stats on meshes and allows them to be rendered in openGL.

more OpenGL trimesh drawers:
http://ravl.sourceforge.net/share/doc/RAVL/Auto/Develop/Class/RavlGUIN.DTriMesh3DC.html
http://www.softlab.ntua.gr/~ttsiod/trimesh.html

SVG

Its certainly possible to do a 'wireframe' rendering of the svg trimesh, using xslt or script. For each edge, make a polyline from point v1 to v2; make a linear gradient with userSpaceonUse with stops at 0 and 1, x1 y1 from v1 and x2 y2 from v2; and apply that gradient to the stroke of the polyline.

An alternative approach
-----------------------

Instead of an explicit list of edges and faces, the alternative approach merely lists the points which will become the vertices (position, color, opacity). The implementation then perform a Delaunay triangulation to produce the trimesh. 
http://en.wikipedia.org/wiki/Delaunay_triangulation
http://www.ics.uci.edu/~eppstein/gina/delaunay.html

Since its not a trimesh, only the data to make one, I am calling it a colorGrid for lack of a better name.

<colorGrid xml:id="foo" gridUnits="userSpaceOnUse">
    <dot dcolor="#27D" dopacity="0.5" x="12.7" y="3.5"/>
    <dot dcolor="rgb(123, 254, 37)" dopacity="1" x="8.4" y="17.2"/>
    <dot dcolor="#F0D" dopacity="0" x="3.2" y="14.1"/>
</colorGrid>

Content model of colorGrid is 

This approach has some advantages:
- the xml is way shorter
- there is never any folding
- its simpler to author
- no messing about with ID and IDref to construct a linked data structure
- no chance of getting any of the links wrong
- adding a new point or deleting a point is stable and causes a local change; the mesh is never in an invalid state
- animating x and y never produces overlap

disadvantages
- implementation has to perform the triangulation. Although its not very hard or computationally intensive.
- if you want overlaps/folding, or to hook up coincident points in a particular way to get sharp transitions, you can't have it.
- animating x and y of a vertex may be slower than in the explicit case, because the triangles may re-form


And its possible to start with this vertex-only form, triangulate, and write out the verbose, explicit form.

Coding and testing, part deux
-----------------------------

There is abundant literature on algorithms for the triangulation; some will be more suited than others to rapidly recalculating (parts of) the triangulation as points are moved through script or animation.

Discussion and code for Delaunay triangulation
http://goanna.cs.rmit.edu.au/~gl/research/comp_geom/delaunay/delaunay.html

demo
http://www.cse.unsw.edu.au/~lambert/java/3d/delaunay.html

useful documentation and diagrams
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_20.5

a comparison of efficiencies - important, as some algorithms are On^2 and others On^4 :)
http://www.cs.cmu.edu/~quake/tripaper/triangle2.html


-- 
 Chris Lilley                    mailto:chris@w3.org
 Interaction Domain Leader
 Co-Chair, W3C SVG Working Group
 W3C Graphics Activity Lead
 Co-Chair, W3C Hypertext CG

Received on Monday, 21 May 2007 12:22:05 UTC