Operational Transform

[eukreign]

I'm working on a project for Open Source Ecology to improve the dependency management between the different machines they have. So far the goal is just a simple webapp (not linked to any CAD data) to define some relationship between the machines, add a BOM and documentation/build instructions, etc.

My goal is to eventually integrate with FreeCAD and the Assembly module so that FreeCAD models could be versioned and dependencies could be managed between assemblies based on their version, life cycle and other attributes. Basically a PLM system that's less generic and more integrated with FreeCAD and Open Hardware use cases.

I would like to design the first version of the webapp so that it can eventually grow into one that can work with FreeCAD. I realize that the Assembly stuff in FreeCAD is still evolving and nothing is certain but I was wondering if those in the know could at least give me some feedback on whether my current design ideas would even be realistic.

Operational Transform

Operational Transform is a way of allowing multiple people to work on the same data at the same time. The idea is that each operation (modification of a Part Feature in FreeCAD as an example) received by the server would be intelligently merged with any other operation someone else is performing at the same time. One interesting thing about OT is that this doesn't have to happen live, in fact, the latency could theoretically be much longer, a day or a week. You can have multiple people working on the same Part/Assembly and go offline, then merge their changes when they come back online.

There is an implementation of OT for a JSON document. A JSON document is a nested structure of lists and dictionaries (to use Python terminology). From what I understand about FreeCAD data model requirements it should be possible to represent all of it in terms of a JSON document (list of dictionaries where each dictionary is a cut/rotate/etc operation). And if you can use OT on a JSON document then it should be theoretically possible to support collaborative CAD in this way (at least to support most operations if not all of them). Some code would have to constantly keep the JSON model in sync with the FreeCAD model (eventually we'd want an OT algorithm specifically for FreeCAD which would be more robust and handle specific transformations better).

To give an example of operations, it would be something like:

User 1: Moved a cut operation on the X axis.
User 2: Increased the size of the cut operation.

When server gets both of these operations (lets say simultaneously) it will still pick one of them to do first (chronologically at best or randomly at worst). The algorithm is a bit more complicated but essentially the server will apply the cut move operation on the master document then it will "transform" the cut size operation in terms of the cut move operation and apply the transformed version. The server then sends each connected client the version of the operation that was actually applied (user 1 will get their original operation unchanged and user 2 will get a new version of their operation that includes user 1 change). You can read more about how OT works here: http://www.codecommit.com/blog/java/und ... sformation

OT can be a bit of a mind bender but there are plenty of working systems on there, even a plugin for Maya 3D (http://cooffice.ntu.edu.sg/comaya/) although I think FreeCAD is much better suited for OT than the non-parametric modelers.

Anyone with OT knowledge or just based on my description of it above have any thoughts on the feasibility of this for FreeCAD? Is there a technical reason this can't work (specifically representing FreeCAD data model in JSON)?

I was even thinking that one way to make the transformations more intelligent/keep integrity is if you had a headless FreeCAD running on the server that also had a representation of the master document then when two people increased the size of the cut you would ask the server instance of FreeCAD to perform the changes and only record what the constraints allowed to happen (so if user 1 increased the cut and user 2 increased the cut, it would add them together but total cut size would stay within the constraints... by the way, this may not be the logical intent of the users (to have their cuts added) but the point of OT is that in the end you end up with a consistent model albeit maybe not the intended one, from there you can fix up the merge). Situations like this is where a FreeCAD specific OT algorithm (as opposed to generic JSON one) could do things more intelligent such as if two people modify the cut at the same time (or following the same sequence of operations) you can infer that instead of adding them, one of them should just take precedence. OT can be improved over time to handle these situations better so getting a working system that just uses JSON OT I think would be a good first step even if it's not perfect.

Assemblies

I'm building the app using Django and currently just designing the data model. One of the things I'm trying to figure out is at what granularity it makes sense to perform versioning and OT.

Currently my data model has a Project, Assembly and Part. Assemblies, sub Assemblies and Parts are all composable in terms of a graph. This is how I understand the new Assembly module in FreeCAD to be structured. A "Project" is something like a Tractor and Assemblies/sub-Assemblies are like Frame or Wheel Well, etc.

The question is that when editing in FreeCAD (after Assembly become available) would you only ever be able to edit a single Assembly at a time? Meaning that from a client/server perspective user would click to download the Wheel Well assembly and they would only be able to see and edit the Wheel Well assembly. Then if they open the Frame assembly they would see the Wheel Well but not be able to edit it in this particular view (FreeCAD would just show the pre-rendered tessellated version of the Wheel Well)?

It seems like it would have to work this way for performance reasons... but then it brings up the question if the sub-assemblies or parts are all just dumb pre-rendered models how do you use them in your constraints? For example, to "attach" a Wheel Well to the Frame you need to position it in the Frame assembly using some sort of constraints, how would these constraints do the calculation without also loading in the parametric data for the Wheel Well?

This is important to me because from a PLM application and OT perspective I need to understand what data would need to be available to FreeCAD in a single editor instance in order to be able to parametric edit your assembly and interact with subassemblies.

If you have something as complicated as a tractor with possibly hundreds of assemblies and you open it in FreeCAD would you have to download all of the data (parametric and mesh) for all of the assemblies and parts used in the model? Or will there be some way to download only the mesh data for external assemblies?

Any thoughts, suggestion or information on this would be greatly appreciated.

[ickby]

My goal is to eventually integrate with FreeCAD and the Assembly module so that FreeCAD models could be versioned and dependencies could be managed between assemblies based on their version, life cycle and other attributes. Basically a PLM system that's less generic and more integrated with FreeCAD and Open Hardware use cases.

Sounds nice

Operational Transform

This is going to be REALLY HARD. The Freecad Data model is easy, it is already a xml file so shout not be hard to transform to json. I don't know OT in general, but a major problem I see is that not only the order of the operations matter, but also the result. FreeCAD is not a plain CSG modeler where you add and substract shapes from a previous one, but you use information from the model created before. For exmaple fillets features use edge names to know which edge to filet. Now if you change the order of operations the edges get different names and the following information gets applied wrongly because it works on the wrong edge. This would IMHO be one of the biggest issues to overcome, especially without topology naming support in FreeCAD. Annother example is that the number of edges, faces and vertices (and thence their naming) do not only depend on the operations used but also on their value, for example if a pocket only is a pocket or a hole dependend on it length parameter. Furthermore you need to consider that many boolean operations (like CUT) and other freecad features are not commutative, e.g. Shape1 - Shape2 != Shape2 - Shape1.

Nonetheless merging FreeCAD documents is something that have come up very often and definitly is something wanted, so if you succeed it would be for sure something valuable!

The question is that when editing in FreeCAD (after Assembly become available) would you only ever be able to edit a single Assembly at a time?

I don't think so. If I follow the current development correctly the first freecad assembly version will not yet support multi asembly files but only to assemble things inside of one document. This means every assembly part can be edited every time as its source parts are available in the document. Don't know how it is supposed to work with multiple documents later.

[eukreign]

Operational Transform

This is going to be REALLY HARD. The Freecad Data model is easy, it is already a xml file so shout not be hard to transform to json. I don't know OT in general, but a major problem I see is that not only the order of the operations matter, but also the result. FreeCAD is not a plain CSG modeler where you add and substract shapes from a previous one, but you use information from the model created before. For exmaple fillets features use edge names to know which edge to filet. Now if you change the order of operations the edges get different names and the following information gets applied wrongly because it works on the wrong edge. This would IMHO be one of the biggest issues to overcome, especially without topology naming support in FreeCAD. Annother example is that the number of edges, faces and vertices (and thence their naming) do not only depend on the operations used but also on their value, for example if a pocket only is a pocket or a hole dependend on it length parameter. Furthermore you need to consider that many boolean operations (like CUT) and other freecad features are not commutative, e.g. Shape1 - Shape2 != Shape2 - Shape1.

Nonetheless merging FreeCAD documents is something that have come up very often and definitly is something wanted, so if you succeed it would be for sure something valuable!

I think you are confusing the operations necessary to synchronize the documents with the operations within FreeCAD to perform the model manipulations. There isn't an exact 1-to-1 mapping.

The OT transformations happen on the document level. The OT shouldn't have to understand how a CUT works or what order to perform addition/subtraction. This would all be left up to FreeCAD. All that the OT would do is synchronize the end result.

If you think of the XML document that is generated by FreeCAD and all of the operations in there, this is the only thing that the OT would synchronize (and the way it does this is by sending patches, these patches could then be used as a versioning mechanism).

The question is that when editing in FreeCAD (after Assembly become available) would you only ever be able to edit a single Assembly at a time?

I don't think so. If I follow the current development correctly the first freecad assembly version will not yet support multi asembly files but only to assemble things inside of one document. This means every assembly part can be edited every time as its source parts are available in the document. Don't know how it is supposed to work with multiple documents later.

Hopefully Juergen or one of the other core devs will respond

Knowing how much/how little data FreeCAD will need in order to handle viewing an assembly and/or editing an assembly will be very useful for any external system that provides the on-line project storage for FreeCAD.

[ickby]

I think you are confusing the operations necessary to synchronize the documents with the operations within FreeCAD to perform the model manipulations. There isn't an exact 1-to-1 mapping

I may miss understand, my point is the following: imagine two people start with a box. One adds a pad at face1 on his machine and the other a pocket at face2 at his. Now we want to combine both, as this is the purpose of ot as I have understood it. The result should be a box with one pocket and one pad each at the position the two guys had them created. Now you can decide to start with the box+pad and add the pocket as next.operation. the problem: pocket gets.add to face2, however, as the part has more faces than a simple box due to the applied pocket you don't know if face2 is the same face as before, it may be at a complete.different position than expected. The end result would not match to the expatations.

The same wit simple cuts: as they are not commutative you would need to decide which cut of two delegate ones comes.first and this may very well change the outcome to an unexpected result.

The freecad document basicly states the operations used to build the parts, but these operations depend on the result of the former one which makes it so difficult to change anything.

[eukreign]

I may miss understand, my point is the following: imagine two people start with a box. One adds a pad at face1 on his machine and the other a pocket at face2 at his. Now we want to combine both, as this is the purpose of ot as I have understood it. The result should be a box with one pocket and one pad each at the position the two guys had them created. Now you can decide to start with the box+pad and add the pocket as next.operation. the problem: pocket gets.add to face2, however, as the part has more faces than a simple box due to the applied pocket you don't know if face2 is the same face as before, it may be at a complete.different position than expected. The end result would not match to the expatations.

The same wit simple cuts: as they are not commutative you would need to decide which cut of two delegate ones comes.first and this may very well change the outcome to an unexpected result.

The freecad document basicly states the operations used to build the parts, but these operations depend on the result of the former one which makes it so difficult to change anything.

Thanks for those examples. They were very useful.

Sounds like having a headless FreeCAD running on the server may be unavoidable.

In the first example you gave. Is it possible to use FreeCAD to generically figure out the new name/location of a face after an operation? Given the name "Face2" what is the new name of "Face2" after the Pad/Pocket operation?

I tried replicating the issue you bring up and it seems that FreeCAD doesn't break or is destructive in such situations. FreeCAD leaves the operation referencing the wrong/missing face in the document tree and you are given an opportunity to fix the broken link. So, I think even if the OT algorithm isn't knowledgeable about FreeCAD it should still be possible to work this way.

Going back to the more basic OT use case: If two people are editing the same sentance in a text document and one of them types in the same spot as you, you're going to get something incomprehensible, that's just a given, no technology can fix this. All the computer can do is try to save as much of the changes and then allow you to manually fix it after the fact. Which it seems that FreeCAD already lets you do. I think that's "good enough" as a starting point.

Can you think of other major issues that would exist with trying to use OT on a FreeCAD document? Do you think if we solve the "face number change" issue we'd cover quite a few use cases already?

[eukreign]

I think adding OT would be a two phase process:

JSON OT
----------

This would be a dumb OT solution at a purely document level (sync'ing and versioning the document tree without regard for the meaning of FreeCAD operations). New operations added will not be attached or get attached to the wrong face, etc. You'd have to manually fix those situations of orphaned operations.

When two people are working on a new project this will probably require that they take turns adding new stuff (or deal with manually fixing conflicts). Even with word documents or any other kinds of documents, you'll usually have one person "driving" the changes and another as just support (tweaking things, etc). So, I think even with just a dumb JSON solution OT could be useful in FreeCAD.

And for established projects where people are simply modifying parameters of existing FreeCAD operations it should work just fine, right? Can you think of any issues that might come up with simply modifying existing operations (no new faces are created, just dimensions of existing sketches/operations changed)?

FreeCAD OT
--------------

This would be a smart OT that is specific to FreeCAD and actually understand the meaning of FreeCAD operations. Face names would get "transformed" to the new names, etc.