Proposal for GSoC - jnxd

[ickby]

Th eexample you posted is a tricky one. I added the id's that would be generated in my approach to your picture. To answer your question: no, d would not be equal c, their construction history is different.

naming.png (151.22 KiB) Viewed 2361 times

Actually in my current approach with hashes this example would be difficult, as after the reorder the selected hash can't be found anymore, and as you cant access any data from the hash alone you also cannot recover it. There I like your approach of storing more data inside the selection (your links vector). Utilizing DeepSOICs ideo of omitting hashes and serializing the indentifier into a string this would also be possible wihth my approach (hence this is a very good idea). With the serialized identifiers you could recover the full information and solve that reorder problem the same way as you do by searching for later elments in the history.

Using the serialisation approach the identifiers would read

A = Edge created from box
B = Edge split 1 from (Edge created from box)
C = Face blended from (Edge split 1 from (Edge created from box))
D = Face blended from (Edge created from box)

The blend selection would store " Edge split 1 from (Edge created from box)". After reorder this exact edge does not exist (as the split did not occure yet) but one could than instead simply search "Edge created from box".
This wont work with hashes as hashes don't provide the full identifier history information.

Still, in the end the blended face would have a different Identifier than the one done after the split in step 3. But it is arguably also a different face, so wouldn't this actually be correct?

[tanderson69]

thanks for the detailed answer. I am sure others will benefit also.

To answer your question: no, d would not be equal c, their construction history is different.

if the user had selected edge 'a' in step 3 then d would equal c....correct?

Th eexample you posted is a tricky one.

Yes the combination of splits with a reorder is a pretty good stress test. This will be difficult for any methodoligy.

Still, in the end the blended face would have a different Identifier than the one done after the split in step 3. But it is arguably also a different face, so wouldn't this actually be correct?

I agree, you have a valid argument. From a user perspective, I think an argument could be made that they should be the same, but that could be just to difficult to control. Anyway, I wasn't trying to suggest they should or shouldn't be the same. My idea was presenting a more complicated scenario and watching your id chains in 'action'. I think I have a better understanding now.



about splits:
The reorder scenario reminded me of at least one reason why I quit taking ids forward in the shape history. Looking at step 2 where the edge gets split by the subtraction, I labeled one of the edges with the original id and the other one gets a new id generated. I guessed this is how you would do it by studying your initial diagram. Correct me if this is wrong. How do you decide which one of these edges gets the initial id? Whatever one gets original id, the other one feels 'second class' to me. Thoughts? Feel free to defer this conversation as this takes us another level into the abyss.

[jnxd]

calling ickby

I was just wondering, how were you planning to identify and reference parts of primitives like cube, sphere etc?

[ickby]

calling ickby

I was just wondering, how were you planning to identify and reference parts of primitives like cube, sphere etc?

Occ offers special methods for primitives, cube for example allows to retrieve all faces like top, bottom etc. In my data structure i planned to use the "name" attribute for this, e.g. the top face would be named "top"

[tanderson69]

I have had some success with simple topo-naming through a boolean operation. Below is a link to a video showing some simple operations updating successfully. I will broadly describe what I am doing and I welcome questions and suggestions. Identifying shapes after a boolean operation is mostly about splits. I am keeping track of both face and edge splits. The splits are either presented by or can be derived from BOPAlgo_Builder. In between updates, any single face/edge can toggle between being a split or not depending on the intersections of the input geometry. See video and think about the bottom edges of the tool, the ones that gets blended away. When the tool extends beyond the target solid, the edge is split. So to keep some consisting naming, every edge and face is treated as a split whether it is or not. I will describe the face splits and ignore the edge splits as it is the same except for dimension. Every split has an identifier representing the input face, prior to the boolean operation. I will call that the 'source' and that is used to identify the stored split information between updates. A split will also contain an array of nodes used in an undirected graph. The nodes contain an identifier for the results and a 2d point representing the 2d bounding box center of a split face's outerwire in the face's parametric space. Does that make sense? Upon update, the sources for the current results are matched against the splits using 'source'. When matched, we build new nodes for the current splits and put them in an undirected graph with the old nodes, built from previous updates. Then assign weights between each new node to each old node (see picture). The weight is the distance between the nodes 2d points. Then using a greedy algorithm, similar to 'Kruskal’s minimum spanning tree', we eliminate graph edges until each new node matches 1 old node. Then assign the old id to the new split face. I will stop there.


https://c.gmx.com/blobfish@gmx.com/JXO9 ... ZG51-R3INQ

undirectedGraph.png (34.51 KiB) Viewed 1923 times

[microelly2]

The main problem is to find good weights for the edges in your graph.
But I think that your way can work.
See my ideas here.
https://forum.freecadweb.org/viewtopic.php?f=8&t=25092

[looo]

looks like a very promising approch. As I understand you are computing weights by distances of face-centres?

because your diagram reminds me on some videos about machine learning[1]:
wouldn't this be a typical machine learning task? we have lots of training data where we don't get the result we like. We can give the machine the information of all topology entities and the result should be the wanted output. How weights are computed is computed by the machine-learning algorythm. I think there are lots of special cases which one algorythm can track but the other not. A machine learning algorythm is flexible enough to solve them all...
edit: i have not really a good picture of machine-learning. I am only fascinated what is possible with these new technics.

https://www.youtube.com/watch?v=aircAruvnKktechnics

[tanderson69]

See my ideas here.
https://forum.freecadweb.org/viewtopic.php?f=8&t=25092

I did see your thread. It is interesting, if I understand you correctly, that you are identifying vertices then edges off the vertices and faces off the edges. OCCT application framework does the opposite, where it tries to identify faces, then the edges from the faces and vertices from the edges. I definitely see some application for what you are doing. What immediately came to my mind was importing 2 different revisions from step files that are in different orientations. You could use your method to do a 'best fit' to align the models for an overlay. [IMHO] Short of some kind of AI, I don't think your approach could be as good as using the information coming out of the actual modeling algorithms that are modifying the shapes.

The main problem is to find good weights for the edges in your graph.

Keep in mind that weights are derived from distances in the faces parametric space. So operations on topology should not affect it. But yes, for example: Box primitives regenerate the face geometry and can change the parametric space causing problems in future operations. I am wondering if we could work around that by always generating the box at absolute and setting the position through topology instead of using the box primitives gp_AX2.

looks like a very promising approch. As I understand you are computing weights by distances of face-centres?

yes. I struggled trying to find a good way to describe the process. I will describe it again over a few sentences. For each input face that is split we collect all the resulting split faces. For each split face we get its' 2d bounding box in parametric space. The we get the center of that 2d box and store it and that point becomes the 'anchor' for an id. in subsequent updates/recomputes each new split is compared, by distance between 'anchors', to assign the 'best' id for each new split.

edit: i have not really a good picture of machine-learning. I am only fascinated what is possible with these new technics.

The idea had crossed my mind, but I am so completely ignorant on the subject I didn't take any action. It is an interesting idea. Set up an interface and commandeer the freecad user to train the AI.

[looo]

thanks for the additional information.
Is there a branch to test your approach? As this solves the nr1 problem of FreeCAD I am really interested in testing this.

[tanderson69]

Is there a branch to test your approach?

No, this is completely external from freecad.

As this solves the nr1 problem of FreeCAD

what is 'the nr1 problem'?