## topological identification of vertexes on a part

Have some feature requests, feedback, cool stuff to share, or want to know where FreeCAD is going? This is the place.
Forum rules
microelly2
Posts: 4630
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

### topological identification of vertexes on a part

How to identify vertexes of a part for topological naming

I have looked for a method to calcuate a unique key for each vertex of a Part.
the key should be invariant against move/rotate scale of the part.

The key for a vertex v consists of 3 components:

1. the number of edges of v

2. (the sum of the length of all edges from v)/length of the sum of all edge-vectors

3. the sum of the scaler product of all normalized edge vectors (tangent vectors) with the
normalized sum of all these tangents

If this key is not unique for some points I use as the next key
the sum of the keys of all of its neighbors

This way higher keys can be build as sums of lower keys until each vertex has an unique key.

The keys are local - influence comes only from near vertexes, so modifications
of the part far from a point do not have an impact on the key of the vertex

keys do not contain cordinates or directions,
the do not change when the part is moved, rotated or mirrored
keys are easy to compute.

phpBB [video]

lambda
Posts: 34
Joined: Sat Feb 25, 2017 3:10 pm
Contact:

### Re: topological identification of vertexes on a part

This is a nice heuristic, which might give good results if combined with other heuristics. There are two downsides though:

1) I think many parts have to many symmetries, where vertices just don't get a unique value. Maybe you can provide a macro that does the calculation, so we can run it on our modells and see how far we get?
2) Often not all vertices of a part are connected with edges: Think of a wall with three holes (windows) - the vertices of each window are isolated from the rest. If each hole has the same geometry, then all three holes will end up with vertices with the same value (although the middle window is different from the outer window), as you can not relate the vertices to others with your method.
microelly2
Posts: 4630
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

### Re: topological identification of vertexes on a part

lambda wrote:
Mon Oct 30, 2017 9:11 pm
This is a nice heuristic, which might give good results if combined with other heuristics. There are two downsides though:

1) I think many parts have to many symmetries, where vertices just don't get a unique value. Maybe you can provide a macro that does the calculation, so we can run it on our modells and see how far we get?
Thank you that you examined my idea.
I'm realy looking for "real" test cases to improve it.

The script is here
2) Often not all vertices of a part are connected with edges: Think of a wall with three holes (windows) - the vertices of each window are isolated from the rest. If each hole has the same geometry, then all three holes will end up with vertices with the same value (although the middle window is different from the outer window), as you can not relate the vertices to others with your method.
When you extend the model by the middle of the faces (center of mass) then the holes are different,
bp_595.png (52.04 KiB) Viewed 1013 times
here the script to extent the model:

Code: Select all

``````
import random

ff=0.001

def rf(v):

# the box with some holes
a=App.ActiveDocument.Pocket
fs=a.Shape.Faces

pts=[]
col=[]

for f in fs:
c=f.CenterOfMass
pts.append(c)
for v in f.Vertexes:
p=v.Point
pts.append(p)
col.append(Part.makeLine(rf(c),rf(p)))

import Points
Points.show(Points.Points(pts))

Part.show(Part.Compound(col))

# dieses shape fuer die analyse nutzen

Gui.Selection.clearSelection()

import nurbswb.analyse_topology_v2

``````
shaise
Posts: 354
Joined: Thu Jun 11, 2015 8:11 am

### Re: topological identification of vertexes on a part

I guess, the motivation behind the topological naming is to prevent braking of a model when doing changes up the tree.
If this is the reason, I suggest a simpler to implement method, perhaps not as good as a full blown topological naming, but good enough to solve many cases:
Leave the naming as today with simple numbering. simple transformations like rotate and translate will not affect it.
When ever there is a topological changing operation, in most cases pockets, pads and other booleans:
1. each vertex that occupies the same location as a vertex in the previous stage will have the same number.
2. each edge that have the same 2 vertices as before will have the same number. all others new numbers.
3. each face that shares at least 3 vertices as before will have the same number. (in this case it can be ambiguous if a face is being split, in this case select one randomly and give it the same number. this way if a sketch was attached to it, it will at least stay in the same plane)
I admit there are lots of cases it will not work, but it is easy to implement and much better then randomly numbering objects as today.

shai
Quaoar
Posts: 75
Joined: Thu Jul 27, 2017 11:56 am
Location: Nizhny Novgorod
Contact:

### Re: topological identification of vertexes on a part

Do you mean the objects are numbered randomly in FreeCAD? I thought it is using indexes returned by OpenCascade's topology iterators (i.e. TopExp). If so, you cannot affect these numbers as they correspond to depth-first order traversal of topology graph. And that's exactly why this problem of persistent naming usually arise.
FOSS CAD model inspection utility and prototyping framework: http://analysissitus.org
microelly2
Posts: 4630
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

### Re: topological identification of vertexes on a part

shaise wrote:
Wed Nov 01, 2017 6:16 am
I guess, the motivation behind the topological naming is to prevent braking of a model when doing changes up the tree.
If this is the reason, I suggest a simpler to implement method, perhaps not as good as a full blown topological naming, but good enough to solve many cases:
Leave the naming as today with simple numbering. simple transformations like rotate and translate will not affect it.
When ever there is a topological changing operation, in most cases pockets, pads and other booleans:
1. each vertex that occupies the same location as a vertex in the previous stage will have the same number.
this is a nice to use information but will not work if the Part or some subparts are scaled
2. each edge that have the same 2 vertices as before will have the same number. all others new numbers.
3. each face that shares at least 3 vertices as before will have the same number. (in this case it can be ambiguous if a face is being split, in this case select one randomly and give it the same number. this way if a sketch was attached to it, it will at least stay in the same plane)
I admit there are lots of cases it will not work, but it is easy to implement and much better then randomly numbering objects as today.

shai
You are right, the next step after identification of the vertexes is simpler.
For me the question was:
Given two stones we have a knowledge to arrange them and say these stones are nearly the same or here a corner is missing.
We can identify special points which correspond and see differences.
what is the mathematical background of this knowledge.
I have investigated a lot of meassures and at the moment the method of my script works best.
It helps me too when I make the great Boolean operations of multiple parts
chrisb
Posts: 22594
Joined: Tue Mar 17, 2015 9:14 am

### Re: topological identification of vertexes on a part

Quaoar wrote:
Wed Nov 01, 2017 7:28 am
I thought it is using indexes returned by OpenCascade's topology iterators (i.e. TopExp). If so, you cannot affect these numbers as they correspond to depth-first order traversal of topology graph.
Even if the numbering comes from OCC, shaise's idea could result in an an improvement in many cases:
If we identify faces edges and vertices we can map for all references old values to new values.

I am more afraid of how to identify the situations when to apply this mechanism. I am thinking of a rectangle, centered around (0,0,0). Padding yields a cube.
If I enlarge one of the sides all corners change, although nothing serious happened.
microelly2
Posts: 4630
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

### Re: topological identification of vertexes on a part

chrisb wrote:
Wed Nov 01, 2017 8:11 am

I am more afraid of how to identify the situations when to apply this mechanism. I am thinking of a rectangle, centered around (0,0,0). Padding yields a cube.
If I enlarge one of the sides all corners change, although nothing serious happened.
In this case the keys for middlepoints of 4 faces change but the keys for the corners and the middlepoint of the top and bottom stay.
shaise
Posts: 354
Joined: Thu Jun 11, 2015 8:11 am

### Re: topological identification of vertexes on a part

chrisb wrote:
Wed Nov 01, 2017 8:11 am
If I enlarge one of the sides all corners change, although nothing serious happened.
Indeed this is a big issue, as it is common to change heights of pads/pockets. But perhaps in theses cases we can take the original OCC numberings, as in cases where the shape does not change topologically (but rather only change some dimensions) the numbering stays consistent.

shai
chrisb
Posts: 22594
Joined: Tue Mar 17, 2015 9:14 am

### Re: topological identification of vertexes on a part

Let's divide the changes to previous steps in the following disjunct sets:
- changes without changing the number of vertices, edges, faces, I would like to call them simple changes
- changes with changing any of the number of vertices, edges, faces, I would like to call them complex changes

Simple changes are usually harmless: adjusting dimensions (although I had serious problems with moving the position of holes of equal diameter) or even simpler: just move an object, where all vertices change.
The precondition should be easy to calculate and the current mechanism could stay in place.

Complex changes are the changes that usually break a model. Make a cutout, drill a hole and nothing is as it was before. Here we could use the mechanism proposed by shaise.

Of course there are cases where we have simple changes combined with complex changes. And perhaps in some cases we might have a deterioration to the current situation. In the example given in my previous post a user can change the sketch in all dimensions and add a cutout somewhere. That would probably break the model - as it would do now.
But the user could improve things drastically by dividing the changes in two steps. That is a possibility we don't have at the moment.