Loops

[varkor]

Loops are useful for endomorphisms, like identity morphisms.

[varkor]

In response to @davidson16807 (https://github.com/varkor/quiver/issues/75#issuecomment-797863146):

I would be interested in implementing this feature. I've used loops before in tikzcd-editor to depict when functions are idempotent, and it's the only feature from that app that I think is missing here.

I'll need some time to familiarize myself with the code. And I wouldn't mind some advice on how to implement. How do you think it should be handled in the UI? Something like tikzcd-editor, with a dedicated button in the cell corner? Maybe there could be a region in the cell that you could drag arrows to, like on the outer regions of the object you dragged from?

Also, what parts of code do you think will be modified?

Thanks, @davidson16807! I agree that loops are the most significant feature that quiver is currently lacking. It has been top of my list of priorities for implementation, but unfortunately I've not had much time to work on quiver in the last couple of months.

Regarding the interface for loops, I haven't given it proper thought yet and don't immediately have a suitable interface in mind. I don't particularly like the button in tikzcd-editor; dragging to a particular region might work, as long as it was obvious enough to users. I suspect this would need some experimentation and iteration. I feel the interface is a secondary concern, though, and I'd be happy to spend some time investigating this myself if the loop rendering was implemented.

The main implementation work necessary for loops is figuring out how to draw them. This is perhaps less straightforward than it might appear at first, because arrow styles are so flexible in quiver, and they all need to be supported. The arrow rendering library is https://github.com/varkor/quiver/blob/master/src/arrow.js, and the entrypoint is the redraw method: https://github.com/varkor/quiver/blob/2a3f1757faf48f32f7101667c2ddae6175600d94/src/arrow.js#L316-L319 The edge itself is drawn in edge_path: https://github.com/varkor/quiver/blob/2a3f1757faf48f32f7101667c2ddae6175600d94/src/arrow.js#L698-L701 Roughly, what needs to happen is a new ARROW_BODY_STYLE added, for loops, and this supported throughout the methods in arrow.js: this would mostly involve doing something similar to the usual code path for ARROW_BODY_STYLE.LINE, and replacing Bézier curve calculations with calculations for loops. The file is well-commented, but the rendering process is quite involved, so I'm happy to discuss in more detail if anything's unclear.

Perhaps if you're interested, you could take a look at this file to see if you can make sense of what's going on (roughly) and whether it's something you're willing to try extending. I could then try to come up with a slightly more detailed overview.

[davidson16807]

I spent a little time looking at the code. Do you think we could rework how we use Bezier, rather than try to render a new ARROW_BODY_STYLE? Some body styles like squiggly or pro could be depicted in combination with loops. It would also be ideal to have some continuous visual feedback that could suggest to the user that they are about to loop back on the source object as they close distance with it.

I was hashing out an idea last night, you could start from the premise that no matter what, an arrow should have a nonzero length in order to be viewable to the user, even if that arrow loops back on itself. You could define a minimum arrow length under which the arrow starts to curve. The amount of curve is set to whatever satisfies the minimum length, such as if the curve traces the arc of a circle, where the distance between start and end point is a chord.

This only specifies enough that there can be two different solutions - the curve could bend in two ways. This is most noticeable if the start and end points are much closer than the minimum length, where one solution bends clockwise and the other bends counter clockwise. We could simply add this as a setting. When the distance between points reaches the minimum length, the radius of the circle is very large, and the chirality doesn't matter.

You might notice that if the start point equals the end point, then there would be many solutions available, varying only by how the loop is oriented. Since the UI already removes the arrow if the start point and end point meet, we can simply assume that for a loop to exist, the start point must not equal the end point. This would have to be tracked even in save files, but the user would never have to be exposed to the distinction.

If we use this approach exclusively, the existing "curvature" setting could be redefined to set the minimum length of the arc, and the "length" setting could be redefined to an offset along the arc. Doing so would change the appearance of arrows at high curvature, but I think this could be an improvement. Neither tikzcd-editor nor quiver have very pleasing lines when curvature is high.

Alternatively, we could transition from one approach to another once the user reaches the minimum length. This could complicate the code, especially if we use arcs for loops and bezier curves for lines. However there may be a way to procedurally map an arc into a bezier curve. You would definitely know better which approach could be better handled by the renderer. Does the renderer support drawing arcs? Is there any other approach you would suggest?

[varkor]

@davidson16807: thanks for your detailed comment! Sorry, you're absolutely right – we should be accounting for the position of the source and target of the arrow to determine whether it ought to be a loop, rather than using ARROW_BODY_STYLE.

One consideration is that quiver must be able to export the arrows to tikz-cd (or TikZ more generally). I'm open to changing how the curves are drawn to a reasonable extent, assuming that we can generate appropriate TikZ. This means that, while we have complete control over how arrows are drawn in quiver itself, there are more constraints on the TikZ output (unless you are comfortable enough with TikZ to replicate the new curves there as well). My approach for the shape of curves to draw so far have been motivated by what I was able to achieve with TikZ.

The approach that I had had in mind previously was to simply special case when the source and the target of an arrow coincided, and switch directly to drawing an arc in this case. The angle and chirality of the loop would be determined by new settings that the user would have control over (at least to some extent). The existing "Curve" setting would determine the size of the loop, for instance.

One other point to note is that, though the arrows themselves use arbitrary points as their endpoints, in the diagram data structure, arrows have source and target vertices, rather than source and target positions. This means that there isn't fine-grained control over the source and target locations, which is a constraint I'd prefer to preserve: it ensures that the structural information about a diagram is mostly separate from the visual aspects (apart from the variables controlling aspects of the rendering, like "Curve").

Alternatively, we could transition from one approach to another once the user reaches the minimum length. This could complicate the code, especially if we use arcs for loops and bezier curves for lines.

Yes, I don't think this is worth attempting: we should either use one type of curve that can handle both (and thus be able to transition automatically), or switch between them without a transition (e.g. by having a button, or a drag-region that makes the curve a loop, etc.). Otherwise, we just make the implementation more difficult for something that doesn't significantly affect users.

The amount of curve is set to whatever satisfies the minimum length, such as if the curve traces the arc of a circle, where the distance between start and end point is a chord.

One possible concern with this approach: wouldn't this mean that each arrow would have a maximum curvature, given when the arc was exactly a semicircle? It may be that this doesn't afford users enough height to work with for some diagrams.

Overall, I'm not against changing the shape of arrows, as long as the existing constraints above can be met. However, my suspicion is that this will be difficult to do with arcs in general, and it may be easier to special-case loops. Let me know what you think.

[davidson16807]

This means that there isn't fine-grained control over the source and target locations, which is a constraint I'd prefer to preserve: it ensures that the structural information about a diagram is mostly separate from the visual aspects (apart from the variables controlling aspects of the rendering, like "Curve").

I can see why that would be useful. Since as you mention the model for a diagram is designed to reduce the effort that's needed to export to TikZ, we could map arrow tags like loop right to offsets like [0, 0.1] within the view, then call the floor of the position in the view if we want information to pass back to the model.

Yes, I don't think this is worth attempting: we should either use one type of curve that can handle both (and thus be able to transition automatically), or switch between them without a transition (e.g. by having a button, or a drag-region that makes the curve a loop, etc.).

To be clear, I do think we could consider an approach where we map an arc curve to a bezier. Beziers can express more shapes than an arc can, and TikZ does seem to able to work with them directly, based on what I see in their manual. Beziers could also allow for interpolation, so we could map an arc to a bezier, then blend that bezier with another bezier that represents a straight arrow. Their only downside is that it is difficult to construct them so that they have a known length, which is easy to do with arcs. I do think if both representations are valuable then we should keep both and map between them when needed, but I agree we should not pursue an approach where we instantly transition between arcs and beziers as the length between start and end points passes a threshold.

One possible concern with this approach: wouldn't this mean that each arrow would have a maximum curvature, given when the arc was exactly a semicircle? It may be that this doesn't afford users enough height to work with for some diagrams.

If the curvature is high, that would mean the arc is long. If the chord is short enough in comparison, it would start to look like a loop, something like: Is that appropriate?

[varkor]

Apologies for the delay; it's been a busy week.

To be clear, I do think we could consider an approach where we map an arc curve to a bezier. Beziers can express more shapes than an arc can, and TikZ does seem to able to work with them directly, based on what I see in their manual.

It's possible, though I believe TikZ only supports cubic Bézier curves; this may or may not be sufficient to capture arcs to a reasonable approximation.

If the curvature is high, that would mean the arc is long. If the chord is short enough in comparison, it would start to look like a loop, something like: Is that appropriate?

I don't think curves of this form (i.e. where a part of the curve lies outside the region between the two vertices) are ever going to be what the user desires. Although quadratic Bézier curves don't look great at high curvatures, I think they're still closer to what the user anticipates (though really the right thing to do in this instance is for the user to move the vertices farther from one another to alleviate the problem).

I suppose the best method for determining the appropriate shapes for curves in quiver is by looking at real examples of commutative diagrams with curved edges or loops. There is admittedly some bias here for digital commutative diagrams, because their appearance is somewhat dictated by the ability of the tool in which they were created to render various kinds of curves. However, it seems to me that most of the curves in commutative diagrams are Bézier-like in appearance. This makes me feel, especially considering the extra effort required to implement some kind of transition between arcs and Bézier curves, that having an entirely separate method to render loops would be the most convenient way forward. If you do want to prototype an arc–Bézier transition method, I would be very happy to test it out, but I suspect it's not going to produce the results we'd like.

[davidson16807]

Not dead yet, I've been prototyping a solution: https://github.com/davidson16807/cditor.

Sorry this isn't in the actual implementation yet, I found it easier to roll my own code before I migrate to someone else's code base. Feel free to look through it and let me know if you have recommendations on how the code should be integrated.

I've implemented a function to generate the arc given a minimum length (ArcGeometry.radius_for_chord_and_arc_length). There are also functions that map an arc to svg, either as an arc path (DiagramSvg.diagram_arc_to_svg_arc) or as a bezier curve (DiagramSvg.diagram_arc_to_svg_bezier), so we have at least two options to play around with. Based on what you said concerning how arrows should behave at high-curvature, it sounds like we may want to go with the bezier option. We can then interpolate between the bezier curve generated here and the existing bezier within the application.

[varkor]

@davidson16807: I've just checked out your prototype, and I really like it. The transition from the curve to the arc is very slick, and it feels very natural to play around with. Now that I am able to try it out in practice, I can definitely see "drag out to create an arrow, then drag back to create a loop" working very intuitively in quiver. I made a tiny tweak that I think makes it feel even better, by scaling the size of the arc based on the length of the arrow. I replaced:

const arc = new svg.DiagramArc(arrow.start, arrow.end, 160, true);

with:

const dis = glm.length(arrow.end.sub(arrow.start));
const length = Math.max(0, 320 - dis * 2.4);
const arc = new svg.DiagramArc(arrow.start, arrow.end, length, true);

I also tried out the Bézier to SVG method: it was nice that there was no noticeable switch from the curve to the arc (compared to the arc to SVG method), though it felt a little harder to get an intuition for, because the endpoint of the curve did not match the pointer position. My main question then is how well interpolating between an existing Bézier curve and the loop works: if the Bézier method can be made to work well with the pointer, and with an existing Bézier curve, this method looks like it could be perfect.

Regarding the implementation strategy: it definitely makes sense to test the design out in a self-contained prototype first. I can see roughly how to go about replacing the existing arrow rendering strategy in quiver, but I'll have a closer look through the code soon and think about it more carefully. I'm hoping that the changes won't be so invasive: I think the most tricky part will be getting the arrowheads and tails working properly with the new curve shape.

Finally, sorry again for the delay; it's been another busy week.

[davidson16807]

Update: I had a clear idea in my head for how snapping behavior should occur with loops, but couldn't articulate a trustworthy way for it to exist in code, so I wound up hesitating and putting the project aside for a few months. Fortunately, I was able to break the problem down to what you see in DiagramIds, and now I'm comfortable enough with the design that I can move forward.

To summarize: there are a series of ids we map to. One indicates the grid cell and another indicates a "target offset" that determines what way a loop is oriented. We use these ids to map from the existing arc data structure (which is now referred to as UserArc since mouse events can easily interface with it) to a new arc data structure called StoredArc that represents the arc after we attempt snapping, which should be hopefully easier to store and export to LaTEX. (Note: everything here is a working title and is still subject to change)

There was a bug with arc->bezier code that I since addressed. There were actually a few things wrong with it but the end result was causing the tip of the arrow to always overshoot the mouse pointer. I think like you mention adjusting the length of the arc would give good results but I don't know what dis is in the code snippet

I think I found the solution for the tricky part you mention about arrowheads. There was a function previously that returned the position vector at a given length along an arc. I've created similar functions that also return the surface normal and tangent for any point along the arc, since I realized I could use them to simplify the code that generates the control points for beziers. If you have a surface normal, a position, and a tangent, then you automatically get the column vectors for an affine transformation matrix, which defines the local coordinate system in which you can describe how an arrow head is shaped. Same goes for the tail, the only difference being that you pass a different distance along the arc to get the transform.

The tangent, normal, and position functions are now all defined in SamplerArcProperties. All these functions relied on the same parameters so I decided to create a SamplerArc data structure that would make it easier for calling code to get up and running. I also figure SamplerArc will make it easier to trim the sides of arrows to allow for things like objects and loops, since they look a little scrunched together right now:

So to summarize, the diagram in my head is currently:

I'm going to keep writing this the way the feature set dictates and not worry so much about integration for now. If we can integrate then great, if not then I can still put the code to some use for some niche applications that could use a commutative diagram editor.

[varkor]

I think like you mention adjusting the length of the arc would give good results but I don't know what dis is in the code snippet

@davidson16807: I'll read your comment more carefully soon, but just wanted to respond to this quickly. I've updated the code sample in my previous comment: dis was just defined to be the length of the arrow.

I'm going to keep writing this the way the feature set dictates and not worry so much about integration for now.

This makes sense to me: I don't have a lot of the time currently, but I'm happy to look into what needs to be done for integration when I get the chance.

I'm excited to see how this is turning out!

[TheCedarPrince]

Hey @varkor and @davidson16807 - apologies for the bump, but was wondering what the status of this issue currently is. Thanks and thanks for an excellent tool @varkor ! 😄

[varkor]

@TheCedarPrince: I haven't had a chance to work on this recently, so https://github.com/varkor/quiver/issues/31#issuecomment-885959884 is still up-to-date as far as I'm aware. I hope to invest more time into quiver this year.

[MaxwellWibert]

Hi @varkor, I was curious if you'd made any further progress on this. I'd say the lack of loop functionality is the only roadblock in the way of quiver being my primary/only commutative diagram drawing tool. I think even a basic/ugly loop would be better than no loop, especially if it's a stepping stone while you hone the final version.

[varkor]

@MaxwellWibert: I have recently been considering some minimal support for loops, without integrating all the other styling features of quiver (at least to begin with). If I get some free time, I'd like to do this, but it's been hard to find the time recently.

[chakravala]

Self loops would be good, is there a way to manually add them from the output of quiver?

[chakravala]

It seems this similar browser tool has self loops implemented https://github.com/yishn/tikzcd-editor/issues/18

[varkor]

Self loops would be good, is there a way to manually add them from the output of quiver?

Yes, you can use the loop command in the TikZ output (e.g. see §3.2 of the documentation).

It seems this similar browser tool has self loops implemented https://github.com/yishn/tikzcd-editor/issues/18

Ironically, I was the one who implemented the loop feature in that editor :) Unfortunately, I have less time than I used to.

[varkor]

Now that #40 is complete, I am going to try to dedicate some time to looking into supporting loops in quiver.

[pink10000]

Any update on this feature?

[varkor]

Any update on this feature?

👀

[varkor]

Loops have been implemented in #218. I plan to do some additional testing, and then push a new version of quiver in the next few days.

A special thanks to @davidson16807 for prototyping loop interaction methods. I ended up implemented a similar technique to the method suggested in https://github.com/varkor/quiver/issues/31#issuecomment-813785251. I think it works very intuitively in practice.

If anyone would like to test out the feature before it goes live, you can do so here: https://q.uiver.app/dev/