Proposal for GSoC - jnxd
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Be nice to others! Respect the FreeCAD code of conduct!
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: Proposal for GSoC - jnxd
Browsed the code a little bit. Updating my "understanding"...
-----------------------------
"Toponame object" = Part::Reference
* Each shape (TopoShape, to be precise) stores a dictionary (map) between subshape and its Toponame Object and hash of toponame object. The map looks something like this:
"Edge1" <-> <Toponame Object> <-> '765488643'
"Edge2" <-> <another Toponame Object> <-> '0085200560'
...
All edges and faces and vertices of the shape are listed.
These toponame objects and the map can be written to a file (not implemented yet)
* In SubLink, a hash of the toponame object is remembered, so SubLink will look like this:
>>> App.ActiveDocument.Extrude.DirLink
(<App.ActiveDocument.Box>, ['957620299569'])
And to get the actual edge, I should use this:
dir_edge = App.ActiveDocument.Box.Shape.subshape('957620299569')
And I can look up the hash of an edge like that:
>>> dir_edge.Reference
'957620299569'
We could have encoded the whole content of the toponame object into a string. However, the strings can get quite long quite quickly, so it may be impractical. That's why hashes are used.
* the toponame object has a few members that store hashes of shapes the subelement came from, as well as a UUID of an operation that was performed.
toponame_object.m_shape = enum value [VERTEX, EDGE, FACE]
toponame_object.m_type = enum value [ NEW, GENERATED, or MERGED]
toponame_object.m_baseIDs = list of toponame_objects #(list of toponames of subshapes this subshape was created from; in current impl. it is a tree of full copies of toponame_objects)
toponame_object.m_name = enum value [NONE, TOP, BOTTOM, LEFT, ..., START, END] # (optional - a human-readable identifier of the shape, if toponame_object.m_type == NEW)
toponame_object.m_operation = enum value [NONE, REPAIR, TOPOLOGY, GEOMETRY, BOX, SPHERE] # is that all?? Why? Meanings?
toponame_object.m_operationUuid = 187364901973 # this should be somehow tied to the feature that performs the operation, this is an unclear bit so far
toponame_object.m_counter = <int> # if shape happens to get a few subelements with exactly the same toponame objects, this property is bumped up to make correspondence subshape<->toponame_object unique within this shape.
BLUE = changes vs previous post
-----------------------------
"Toponame object" = Part::Reference
* Each shape (TopoShape, to be precise) stores a dictionary (map) between subshape and its Toponame Object and hash of toponame object. The map looks something like this:
"Edge1" <-> <Toponame Object> <-> '765488643'
"Edge2" <-> <another Toponame Object> <-> '0085200560'
...
All edges and faces and vertices of the shape are listed.
These toponame objects and the map can be written to a file (not implemented yet)
* In SubLink, a hash of the toponame object is remembered, so SubLink will look like this:
>>> App.ActiveDocument.Extrude.DirLink
(<App.ActiveDocument.Box>, ['957620299569'])
And to get the actual edge, I should use this:
dir_edge = App.ActiveDocument.Box.Shape.subshape('957620299569')
And I can look up the hash of an edge like that:
>>> dir_edge.Reference
'957620299569'
We could have encoded the whole content of the toponame object into a string. However, the strings can get quite long quite quickly, so it may be impractical. That's why hashes are used.
* the toponame object has a few members that store hashes of shapes the subelement came from, as well as a UUID of an operation that was performed.
toponame_object.m_shape = enum value [VERTEX, EDGE, FACE]
toponame_object.m_type = enum value [ NEW, GENERATED, or MERGED]
toponame_object.m_baseIDs = list of toponame_objects #(list of toponames of subshapes this subshape was created from; in current impl. it is a tree of full copies of toponame_objects)
toponame_object.m_name = enum value [NONE, TOP, BOTTOM, LEFT, ..., START, END] # (optional - a human-readable identifier of the shape, if toponame_object.m_type == NEW)
toponame_object.m_operation = enum value [NONE, REPAIR, TOPOLOGY, GEOMETRY, BOX, SPHERE] # is that all?? Why? Meanings?
toponame_object.m_operationUuid = 187364901973 # this should be somehow tied to the feature that performs the operation, this is an unclear bit so far
toponame_object.m_counter = <int> # if shape happens to get a few subelements with exactly the same toponame objects, this property is bumped up to make correspondence subshape<->toponame_object unique within this shape.
BLUE = changes vs previous post
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: Proposal for GSoC - jnxd
I think encoding a toponame object in its current form into a string isn't a big problem. For example.
VGBT3-(xxxxx, yyyyy)-OPERATION_NAME_OR_UUID
The first chunk contains all enum values (one letter per value, Vertex-Generated-Bottom-Topology), and the value of counter.
The second chunk is the list of all base toponames, full. "Vertex5" can also be used in place of xxxx, as a mean to support toponaming on top of things made with no toponaming, or for user-defined names maybe.
Last chunk contains operation UUID (I would prefer seeing the name of feature that performed the operation)
Advantages, compared to hash approach:
* full toponame object can be recovered from linkSub.
* human-readable, which makes it also human-editable
* extensible. Should we add another field to toponame object, or remove one... all hashes will go bust, but the string is not. It will only require to bend the parser a little bit.
Disadvantages:
* strings can get somewhat long. But is it really a problem?
* requires parser, shouldn't be too hard.
VGBT3-(xxxxx, yyyyy)-OPERATION_NAME_OR_UUID
The first chunk contains all enum values (one letter per value, Vertex-Generated-Bottom-Topology), and the value of counter.
The second chunk is the list of all base toponames, full. "Vertex5" can also be used in place of xxxx, as a mean to support toponaming on top of things made with no toponaming, or for user-defined names maybe.
Last chunk contains operation UUID (I would prefer seeing the name of feature that performed the operation)
Advantages, compared to hash approach:
* full toponame object can be recovered from linkSub.
* human-readable, which makes it also human-editable
* extensible. Should we add another field to toponame object, or remove one... all hashes will go bust, but the string is not. It will only require to bend the parser a little bit.
Disadvantages:
* strings can get somewhat long. But is it really a problem?
* requires parser, shouldn't be too hard.
- tanderson69
- Veteran
- Posts: 1626
- Joined: Thu Feb 18, 2010 1:07 am
Re: Proposal for GSoC - jnxd
Ok. I am guessing those geometry sketcher ids will be kept private to the sketcher and only the ids for the topods_wire will be public for referencing? Any creation features, like primitives, will have something similar.ickby wrote:Because you have the sketcher. There you work with geometry. The wire build from the geometry must be consistently named,. When the sketch is changed even slightly (just rearanged) the sketch wire is rebuild. You need to make sure that the references of the wire match those of the geometry as this is what the user expects.In the document drawing, you have an id/hash on geometry. why? isn't the id/hash for the vertex enough? Is there going to be an id/hash for geom_curve for edges then?
We are so not on the same page! I was responding to your reasoning behind adding the operation uuid to your identifier. As you describe, you are adding it because there is a potential for duplicate ids within 1 shape. The duplication of ids happens from trying to keep the shape id consistent across dependent features. I was stating that I ran into that problem and solved it by giving up on keeping the same identifiers between dependent features. Each feature sub-shape gets it own unique id regardless if the shape has been modified or not.ickby wrote:I think I don't realy understand your point here. But there is a PropertyUUID which allows DocumentObjects to have a unique id and keep it over lifetime.I tried to keep ids consistent from one feature to the next. I gave up on this, thinking it was going to be way to easy for shapes to end up with duplicate ids. Now each feature is reponsible for it's own unique ids and the mapping in and out. More data, but easier to ensure unique ids.
well you responded so I created this drawing. What I am saying is all ids can be vertices in a graph and creations, splitting, merging etc can be represented from graph edges connecting these graph vertices ids. I am not sure if your cluster graph is applicable. if not, then the graph vertices containing the shape id can also have a 'key' for owning feature. I see all the shape ids, from cradle to grave, inside this shape history graph.ickby wrote:Also the next point, I don't really understand it.
Re: Proposal for GSoC - jnxd
@DeepSOIC: You noted that some enoumeration values are missing and some are unclear. My intention was to fill those up wheneven needed, so everything in their is ver prelimenary and open for any change.
This difference also matters with the "remove feature" case. As in my approach there is no dependency of identifiers between shapes, the subshape IDs stay valid even if the base feature is removed. So even if the direct link is broken you can find a subshape, which exited in the initial cube, within the last modeling step. The advantage of that is that one does not need to rebuild the link references. On recompute most of the identifiers will stay the same (except the ones created by the deleted feature, but that is also the case in your approach) and hence all links to those still work. In your approach you need to make a full rebuild.
As annother use case imagine reordering features. With my approach after reordering one still can search for the references in the new base shape and may find it if it was modeled there already. If not ask the user what to do. I find this intuitive.
Ah I see, thanks for the explaination. Also with the picture things get clearer now. I think you follow a rather different approach than my implementation/idea. You create identifiers and than try to link those between the shapes. Hence it is ok to have a different IDs for the same subshapes, as their connection is created with some kind of link information. In my approach there is no such link information, each shape can live fully without the other. Each Identtifier holds the full creation history. So all the information your approach needs to search the links and create the link information goes in my approach into the identifier directly (and if the subshape stayed exactly the same the identifier gets simply copied over).We are so not on the same page! I was responding to your reasoning behind adding the operation uuid to your identifier. As you describe, you are adding it because there is a potential for duplicate ids within 1 shape. The duplication of ids happens from trying to keep the shape id consistent across dependent features. I was stating that I ran into that problem and solved it by giving up on keeping the same identifiers between dependent features. Each feature sub-shape gets it own unique id regardless if the shape has been modified or not.
This difference also matters with the "remove feature" case. As in my approach there is no dependency of identifiers between shapes, the subshape IDs stay valid even if the base feature is removed. So even if the direct link is broken you can find a subshape, which exited in the initial cube, within the last modeling step. The advantage of that is that one does not need to rebuild the link references. On recompute most of the identifiers will stay the same (except the ones created by the deleted feature, but that is also the case in your approach) and hence all links to those still work. In your approach you need to make a full rebuild.
As annother use case imagine reordering features. With my approach after reordering one still can search for the references in the new base shape and may find it if it was modeled there already. If not ask the user what to do. I find this intuitive.
- tanderson69
- Veteran
- Posts: 1626
- Joined: Thu Feb 18, 2010 1:07 am
Re: Proposal for GSoC - jnxd
ok, your id data is generated at feature creation time and then remains static forever. I was thinking it was going to have to reflect the current history. My confusion. Your approach doesn't seem totally insane now.
I would describe some common ground by stating "you are serializing out a dfs search"
Yes, like any boost::graph code, the shape tracking code isn't the prettiest, but it does work and I really like the idea of all history data contained in one data structure with no redundant information. I warned you boost::graph had warped my brain! One major difference and probably a disconnect between our thinking is, my graph reflects current shape state and your data structure reflects creation shape state. Agreed?So all the information your approach needs to search the links and create the link information goes in my approach into the identifier directly
Full disclosure, I don't have a shape history graph implemented yet, on my todo list. Currently I have a feature graph and each feature keeps a bidirection map of in and out ids. Point is the shape graph will probably be reconstructed every update/recompute anyway. Ultimately it is up to individual features to decide what topods_shapes get what id.This difference also matters with the "remove feature" case. As in my approach there is no dependency of identifiers between shapes, the subshape IDs stay valid even if the base feature is removed. So even if the direct link is broken you can find a subshape, which exited in the initial cube, within the last modeling step. The advantage of that is that one does not need to rebuild the link references. On recompute most of the identifiers will stay the same (except the ones created by the deleted feature, but that is also the case in your approach) and hence all links to those still work. In your approach you need to make a full rebuild.
Glad you brought up reordering as I am a fan also. You are thinking my design won't work for reordering? Referencing my drawing, Why can't I move blend right after box?As annother use case imagine reordering features. With my approach after reordering one still can search for the references in the new base shape and may find it if it was modeled there already. If not ask the user what to do. I find this intuitive.
I would describe some common ground by stating "you are serializing out a dfs search"
Re: Proposal for GSoC - jnxd
That would work i suppose. I thought about the case where the feature after blend is moved in front of it (in case the selection would have been an edge that was not blended away, so actually a different example). On recompute edge would get id4 and not be found by the blend. But most likely that could be worked around with some search logic..Glad you brought up reordering as I am a fan also. You are thinking my design won't work for reordering? Referencing my drawing, Why can't I move blend right after box?
Yes i think this somehow reflects it..I would describe some common ground by stating "you are serializing out a dfs search"
However, there is Imho one very big and important difference between our approaches, if i understand yours correct (which may not be the case, this is complicated stuff): you need to build all IDs and than make the links. I can reuse IDs. In general one need to make sure that on every rebuild a subshape gets the excact same Id again, as those are stored in the selections. But how do you ensure that in your approach? Imagine extruding a face. How would your feature make sure that a.certain vertex get the same Id as the run before when now there are more vertices, possibly reordered? And after that a edge generated from that vertex, how do you ensure its Id stays the same than the rebuild before? In my approach this is easy, i first find all already named shapes, copy their IDs and then reuse those to build the IDs of the newly generated subshapes. But i have no working theory how you would do that. This was a main driver for my idea of "stacking" ids.
Re: Proposal for GSoC - jnxd
@ickby, in your Reference class you have this method:
Was this a spelling mistake? If yes, was it meant to be asIndentedString or as asIndependentString?ickby wrote: asIndendetString
My latest (or last) project: B-spline Construction Project.
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: Proposal for GSoC - jnxd
Hahaha, I noticed that too. It's so german
Re: Proposal for GSoC - jnxd
hehe, I'm definitely not known as spelling or grammar wizard, neither in German or English it should have been "indented".
- tanderson69
- Veteran
- Posts: 1626
- Joined: Thu Feb 18, 2010 1:07 am
Re: Proposal for GSoC - jnxd
Yes, and also in cases like reordering you can make changes inside the context of a command where you might have more capability than in a update/recompute. Also the 'design intent' history is captured in the 'pick/link' not in the id. By the way in my example a std::vector of ids for the pick/link won't be enough. It will have to be some kind of graph/tree data to handle multiple paths etc. Anyway, that is not really important to this discussion.ickby wrote:That would work i suppose. I thought about the case where the feature after blend is moved in front of it (in case the selection would have been an edge that was not blended away, so actually a different example). On recompute edge would get id4 and not be found by the blend. But most likely that could be worked around with some search logic..Glad you brought up reordering as I am a fan also. You are thinking my design won't work for reordering? Referencing my drawing, Why can't I move blend right after box?
Each feature is responsible for its own consistent id 'evolution'. In the simple cases, this just resorts to a simple 1 to 1 relationship id map. Basically examine input shape id, is it map ? grab id : create id and fill in map. I certainly don't have my head around your design, but I was thinking you will have to something similar in your updates for at least the generated geometry? I see it as similar to what we were talking about with the sketcher ids and the primitive ids earlier. I took the 'sketcher, primitive' idea and made it standard. Does that make sense?ickby wrote:I can reuse IDs. In general one need to make sure that on every rebuild a subshape gets the excact same Id again, as those are stored in the selections. But how do you ensure that in your approach?
You said it! I am still wrestling with yours but the more I think about it, the better I like it. Contrasting the two ideas from what I think I understand, IMHO: Your data will be more intensive than mine and my algorithms will be more intensive than yours. Mine is more 'lazy evaluated'. I do think yours can be 'up to speed' quicker.ickby wrote:if i understand yours correct (which may not be the case, this is complicated stuff):
I want to expand on our 'reorder' conversation. I have attached a picture of a sequence of operations patterned after the classic, published example. I hope it is self explanatory. The example involves a split, an interesting topic itself, but that is not the focus. With your design, I want to know if d==c?