Proposal for GSoC - jnxd

Contributions from the participants, questions and answers to their projects.
Discussions of proposals for upcoming events.
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
ickby
Veteran
Posts: 3116
Joined: Wed Oct 05, 2011 7:36 am

Re: Proposal for GSoC - jnxd

Post by ickby »

DeepSOIC wrote: * Each shape (TopoShape, to be precise) stores a dictionary (map) between subshape and its Toponame Object. The map looks something like this:
"Edge1" <-> <Toponame Object>
"Edge2" <-> <another Toponame Object>
...
That is correct
All edges and faces and vertices of the shape are listed. (nor not? there was something about the possibility to figure out an edge off of the other named subelements, such as a combination e.g."Face2", "Face3"))
They are all listed. It is required that each subshape has a unique Toponame object. The mentioned possibility to name some elements by others (e.g. Edge by the two faces) can be used when setting up the Toponame objects. But after the setting up process every subshape has one.
These toponame objects and the map can be written to the file (which you wrote is not implemented yet)
Yes. This is important, as on reload you are not able to retrieve the information otherwise which would break the naming.
* 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'
In general yes, that is the idea. Most likely it makes sense to port the current subelement handling to also work with those References, functions like "getSubShape(const char* Type)". This would make the change less intrusive.
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, as far as I understand
Yes, if one only uses a string, one would need to include all base Toponame objects (and their bases etc.) within that string to ensure uniqueness, thats massive. Hence the hashes which include the base hashes.
* 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.Type = [either NEW, GENERATED, or MERGED]
toponame_object.Base = ['28389275', '00198646'] #(list of hashes of subshapes this subshape was created from)
toponame_object.Name = <string> # (optional - a human-readable identifier of the shape, if toponame_object.Type == NEW)
toponame_object.Operation = <what? another object?>
toponame_object.OperationUUID = 187364901973 # this should be somehow tied to the feature that performs the operation, this is an unclear bit so far
toponame_object.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.
Thats pretty much it, a few remarks:
  • Currently the Reference class, what you call toponame_object, is not exposed to python. I thought that eachgeometry algorithm in TopoShape should be ported to setup those, hence no need to handle them in python.
  • Base - list of hashes. This is not a list of hashes, but of full identifiers. The reason for that is the querying. If you only have base hashes, you can't access any information of those as you don't know the shape they are available in. You need the full base identifier to be able to answer queries like "isConstructedFrom" of a base that is deep in the identifier tree. Also "isMergedFrom" could need more than one layer of the history. In current implementation that list contains copies. That is not very efficient in terms of memory, but was easy to start with. Later on one could implement a more elaborate sharing mechanism with pointer or something.
  • The Operation. The first idea when building a creation history is to use the operation type used to create a subshape (e.g. extrude, revolve, sweep...). This gives you two advantages, for one a strong criteria to make subshapes unique (e.g. e vertex revolved and than the edge extruded: two edges will only differ by operation), and on the other side gives you some expressivness, something the user can understand and work with.
  • OperationUUID. It turned out that the Operation type property is not enough from the uniqueness point of view, as was shown with the "extrude extrude" example. Hence an Operation also gets a UUID, which is a random value for each operation. That means the first extrude would have a different UUID than the second, where Operation is the same (e.g. "Extrude"). This makes it possible to uniquely name different modeling steps. Arguably this makes "Operation" property obsolete, however I keept it for now for its expressiveness.
  • OperationUUID and features. As the UUID is randomly created when not otherwise specified recompute is a problem. It would create a new UUID and hence the identifiers would not be the same, even thougth they should be. Hence the requirement to store an UUID within in a Part::Feature and assign that always same UUID to the identifiers created in that document object.
1. on diagrams, you show that a vertex persistently gets the same exact hash (and it is a small number) as more and more extrusions are applied to it. How is that possible? (most likely there's something wrong with my understanding) ... Is it just taking the history object of the original Vertex in its full glory, which consequently has the same hash? If so, the hashes pointed by that history object may become unresolvable...
If a subshape did not change by the operation like the shown vertex its identifier would not change at all. It is still the same vertex. On the technical side this is done by copying over the identifier from the former shape. I don't fully grasp your question, so you may elaborate a bit more about what is unclear here.

2. I think the Type enum is missing a "SPLIT" item.
Yes, and most likely also many others. I intended to add more there on the go, whenever a new algorithm porting would need it.
I think I figured out, what "Count" is supposed to do.
The general idea of count was that there may be situations where all other properties are not enough to make unique identifiers within a certain shape. Imagine a edge that get splitted. Afte the split you have two edes with the exact same identifer, same base, same operation etc. This would not be unique. Hence counter, one edge would become counter 1 and the other counter 2.

Clone is a special case. Uniqueness of ids is only required within a shape, not freecad wide. Personally I think a clone should have the excact same identifiers than the original one. It is the same shape after all. And it would make sense to find a certain vertex via references within the original and the clone.
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Proposal for GSoC - jnxd

Post by DeepSOIC »

OK, I feel like I have some understanding now. There are a few things that will probably be answered by the code, but I still put them up here.

I feel there is a bit of a problem. If a link breaks, I thought it should be possible to recover it by looking through toponaming objects and finding a similar one. However I think it turns out to be impossible. For example.

Let's assume we have a shape, which was constructed somehow, and it has a sketch on a face, which is to be pocketed. The link in question is the Sketch002.Support.
toponaming-breakage-1.png
toponaming-breakage-1.png (389.12 KiB) Viewed 2195 times
Sketch.Support contains a link which looks like this: (<feature>, '87645290').

Now, let's change the design a bit by widening the hole.
toponaming-breakage-2.png
toponaming-breakage-2.png (182.46 KiB) Viewed 2195 times
The history of the face changes. So the support link will break. This is by design (as sketch support, the face hasn't changed. But say if used for extrusion, or for center-of-mass, or something, it has).

Now, Sketch002 fetches the link to '87645290', and gets an exception that the link no longer exists. And since the shape of the feature has been discarded (replaced with newly recomputed one), it has no way of obtaining the Reference object with that hash, and hence has no chance of finding a new candidate.

Is there any mechanism to deal with such situations?

PS. Our current "toponaming" by remembering face number deals with particular example just fine.
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Proposal for GSoC - jnxd

Post by DeepSOIC »

Another problem is performance. Toponaming is likely to take some time, and in certain cases might substantially increase memory footprint (worst case scenario probably is a point cloud). In certain cases, like this one, I'd like to disable toponaming for certain features. Because what I ultimately need is usually shape, not toponaming.
User avatar
tanderson69
Veteran
Posts: 1626
Joined: Thu Feb 18, 2010 1:07 am

Re: Proposal for GSoC - jnxd

Post by tanderson69 »

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?


from document:
Operation UUID: As seen in the example above it could happen that there are identical identifiers, e.g. two times Edge extruded from Vertex #2. To overcome this problem the opertions get not only a name, but also an universal unique identifier, a UUID. Than it becomes clear thet those two edges extruded from #2 are different, as they are created from two different operations. However, this also creates an issue for DocumentObject use. When rebuilding everything there the Operation UUID must stay the same for each rebuild to ensure that the resulting identifiers are the same as before. Hence it must be stored in the DocumentObject itself and be applied to the identifier.
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.



IMHO:
the data structure feels like everything possible is added in a hope that there will be enough there later for name resolution problems. Eventually you will have to update that data. Consider a simple linear feature DAG path of 15 features and the user deletes feature 7. Won't you have to track down and update all the data structures to reflect this feature removal? Maybe boost graph has warped my brain, but the more time I spend thinking about this problem, I just see GRAPH. I think an argument could be made to use ickby's cluster graph. The clusters would be the features and the graph vertices inside the cluster would be topo ids. Then edges between the clusters would represent the feature DAG and the edges between the clusters vertices would represent the topo evolution from one feature to the next.


Something to keep in mind:
ickby hinted at this, but I will spell it out. If you read the occt paper, they mention that edges and vertices can be identified by their parent shapes so they only worry about faces in there naming resolution. My point being that 'occt's *API ::Generated ::Modified etc functions' are missing information on edges and vertices. Also the topo naming was 'bolted on' to occt later in its development. Meaning that the 'occt's *API ::Generated ::Modified etc functions' are often incomplete, missing or wrong. My main point being, that even with the most robust implementation you will still be hampered by occt problems. I had to subclass BRepAlgoAPI_BooleanOperation to bypass the '::Generated ::Modified etc functions' and get some robust naming throughput on booleans.
triplus
Veteran
Posts: 9471
Joined: Mon Dec 12, 2011 4:45 pm

Re: Proposal for GSoC - jnxd

Post by triplus »

Didn't read in depth but i guess a concept involving UUID could make sense.

P.S. Concept when having a possibility for redefining relation on a more localised level could lead to more overall robustness. As for algorithms doing that automatically. That would likely need a huge investment and would still end up being reliable only up to a point.
triplus
Veteran
Posts: 9471
Joined: Mon Dec 12, 2011 4:45 pm

Re: Proposal for GSoC - jnxd

Post by triplus »

What i guess could be a nice (future) GSoC project is researching theoretical/practical implementations of assembly solver.

P.S. Maybe Assembly 2 solver could be used as a base point.
ickby
Veteran
Posts: 3116
Joined: Wed Oct 05, 2011 7:36 am

Re: Proposal for GSoC - jnxd

Post by ickby »

I feel there is a bit of a problem. If a link breaks, I thought it should be possible to recover it by looking through toponaming objects and finding a similar one. However I think it turns out to be impossible. For example.
You are right that the exact hash will not be available anymore. My thought on this is to extend the reference finding algorithm a bit. There is enough information available to find a good match.

1. Find Subshape with exact reference
2. If not found, find subshape mergedFrom the given Reference
3. If not found, find subshape which is a modificationOf the given reference.

All those functions are already implemented in the TopoShape class and should work to handle the situation you have described. Actually the other way around is harder: Imagine your first picture was the first and the user creates a link to the face. Afterwards the design changes so that the face is not modified anymore. This is a problem and one would need to put some serious thought into it. Maybe one needs to put some logic into the selection mechanism to find the best to use reference (not the reference to the modified version but to the unmodified base version. Than wiith the given algorithm it would still work).

If the Hash is still not found, than at least one knows that the link cannot be used and prompt the user for input. IMHO this is advantage to now, where such things happen unnoticed. It should be possible to retrieve the old shape via the undo/redo system and than make a nice Gui where the user can see what was selected before and chose what to select now.
Another problem is performance. Toponaming is likely to take some time, and in certain cases might substantially increase memory footprint (worst case scenario probably is a point cloud). In certain cases, like this one, I'd like to disable toponaming for certain features. Because what I ultimately need is usually shape, not toponaming.
You are right, not much thought has gone into performance till now. My feeling says that processing time will not be a large issue but memory will. But that is only gut feeling. I think making a switch for disabling is a good choice.
ickby
Veteran
Posts: 3116
Joined: Wed Oct 05, 2011 7:36 am

Re: Proposal for GSoC - jnxd

Post by ickby »

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?
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.
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.
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.

Also the next point, I don't really understand it.
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Proposal for GSoC - jnxd

Post by DeepSOIC »

ickby wrote:But there is a PropertyUUID which allows DocumentObjects to have a unique id and keep it over lifetime.
I wonder, why isn't a human-readable object.Name used in place of totally unreadable uuid?
triplus
Veteran
Posts: 9471
Joined: Mon Dec 12, 2011 4:45 pm

Re: Proposal for GSoC - jnxd

Post by triplus »

Lets say you have a list of 2 edges using a human readable name:

Code: Select all

[edge,edge1]
One edge gets removed and different one is added. The result is still:

Code: Select all

[edge,edge1]
When using UUID that does not happen. And you therefore don't have to care abut things like that anymore. In theory and in practice that should therefore lead to simplification being introduced.
Post Reply