Tree structure in Backends

[fryguybob]

(Imported from http://code.google.com/p/diagrams/issues/detail?id=73. Original issue from tillk.v...@gmail.com on March 11, 2012, 05:14:51 PM UTC)

Hi,
All of the Backends that I have seen so far flatten the UD-tree to produce output. Using a program like Inkscape to further edit an SVG image, it would be better to preserve this structure.

I also need to have such a structure to make a 3d-Backend. At first I aimed at WebGL using SceneJS, for which I need a SceneGraph (a tree structure). It seems easier to first make a Backend with lambdacubeengine (I roughly understand how the scenegraph works there) and then involve the other people here on the mailing list for the right structures for 3d.

The announcement for diagrams-0.5 mentions a new SVG-Backend. Is it preserving the structure? If yes, I would like to see the code.
Documentation about UD-trees would also help a lot.

[fryguybob]

(Imported. Original comment by byor...@gmail.com on March 11, 2012, 07:07:12 PM UTC)

In fact I have been working on this very thing for the past day or so! I will send a message to the mailing list with some issues for discussion and feedback soon.

[byorgey]

See https://groups.google.com/d/msg/diagrams-discuss/saNEFpMe9-Y/jvyZQiDUuIoJ, and also http://www.haskell.org/haskellwiki/Diagrams/Dev/Freezing for discussion of some relevant issues.

[jeffreyrosenbluth]

Next Steps to enhancing performance by passing a tree to the backends:

1. Test Compile.hs code in branch backend-tree by writing a version of prims for DTree.

https://github.com/diagrams/diagrams-core/blob/backend-tree/src/Diagrams/Core/Compile.hs

2. Reimplement SVG backend to take a DTree instead of a list of Prims
3. Implement optimization passes for Dtrees.

[jeffreyrosenbluth]

Status Report:
byorgey has implemented a version of dual-tree that allows access to internal d nodes in foldDUAL.

https://github.com/diagrams/dual-tree/blob/internal-d/src/Data/Tree/DUAL/Internal.hs

This is used in the toTree function in the module Compile.hs to translate a QDiagram to a simpler tree DTree that dispenses with the u annotations. I have written another function fromDTree which creates an RTree from the DTree. The difference being that an RTree separates out the frozen and unfrozen transformations so that the frozen transformations get their own nodes and the unfrozen transformations accumulate until frozen or reach a primitive. An RTree should be easy to handle in the backends.

https://github.com/diagrams/diagrams-core/blob/backend-tree/src/Diagrams/Core/Compile.hs#L64

I have implemented this for the SVG backend except for handling clipping.

https://github.com/diagrams/diagrams-svg/blob/optimize/src/Diagrams/Backend/SVG.hs#L165

[byorgey]

This is now all implemented and merged. Both the SVG backend and the cairo backend make use of the new exposed tree structure.

[jeffreyrosenbluth]

Nice !!!

[byorgey]

Thanks for your work on this. I'm really happy with where we ended up. From here I think there are a lot more incremental improvements we can make, both in optimizing the output of toRTree and in the SVG backend in particular.

[jeffreyrosenbluth]

Your welcome,
I'm really happy with the end result as well.
I look forward to discussing further improvements.

On Thu, Nov 7, 2013 at 10:45 PM, Brent Yorgey notifications@github.comwrote:

Thanks for your work on this. I'm really happy with where we ended up.
From here I think there are a lot more incremental improvements we can
make, both in optimizing the output of toRTree and in the SVG backend in
particular.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/19#issuecomment-28032472
.