Find the real neighbours .gh (1.1 MB)
I have 3D cells(Breps) sharing the same faces with their neighbors.
I like to find a fast way to get the cell topology that indicates a neighboring relationship.
By saying neighboring relationship I mean cells sharing the same faces(centers), not face edges.
That’s elementary via code. Notify if you want a C# that does that.
BTW: This appears to be some reverse engineering of some sort. I mean if you have a Graph on hand and you want to do things based on connectivity (VV, VE , EV and the likes) there’s various ways to cut the mustard the proper way. All that assuming that you know what connectivity (in general) is.
This could be one option:
Find the real neighbours_v2.gh (1.1 MB)
If performance is not an issue (otherwise it’s to go code as peter said), and if we can consider touching faces to be identical, so sharing an identical center, we can go like this:
Similar but with less geometric stuff:
Aren’t you the one that found such a component exists in Nautilus ?
(I haven’t tested it, just have a good memory :D)
And the c# code version attempt:
… I am now curious how much it compete with the Nautilus one…
or, @PeterFotiadis … any idea how fast this should be?
private void RunScript(List<Brep> B, ref object BB)
{
int n = B.Count;
Point3d[][] fcs = new Point3d[n][];
Parallel.For(0, n, (i) => {
int n2 = B[i].Faces.Count;
fcs[i] = new Point3d[n2];
for(int j = 0;j < n2;j++){
fcs[i][j] = Rhino.Geometry.AreaMassProperties.Compute(B[i].Faces[j].DuplicateFace(false), false, true, false, false).Centroid;
}
});
List<int> indexes = new List<int>();
List<Point3d> pts = new List<Point3d>();
List<bool> used = new List<bool>();
List<int>[] topo = new List<int>[n];
for(int i = 0 ;i < n;i++){
topo[i] = new List<int>();
}
for(int i = 0 ;i < n;i++){
for(int j = 0;j < fcs[i].Length;j++){
Point3d p = fcs[i][j];
int found = -1;
for(int k = 0;k < pts.Count;k++){
if(used[k] == false){
if(p.DistanceToSquared(pts[k]) < 0.1){
found = indexes[k];
used[k] = true;
break;
}
}
}
if(found == -1){
pts.Add(p);
indexes.Add(i);
used.Add(false);
}else{
topo[i].Add(found);
topo[found].Add(i);
}
}
}
Grasshopper.DataTree<int> tree = new Grasshopper.DataTree<int>();
for(int i = 0 ;i < n;i++){
tree.AddRange(topo[i], new GH_Path(i));
}
BB = tree;
}
this uses proximity 3D on face centers to generate a list of neighbors for each face, then -in a very convoluted way- struggles to rebuild a data tree where branch number is the index of the cell under examination and the ints in that branch are the index of neighbor cells
it uses metahopper wrap/unwrap list because I’m not smart enough to deal with those branches
Bottleneck navigator says DeconstructBrep and Area are the most intensive components 
Find the real neighbours_Re .gh (1.1 MB)
time for me to study all the other solutions above to learn something about branches 
vanilla GH comes with a ‘Brep topology’ node that gives FF, FE and EF. And Parakeet also has a node with more extended options by the same name, and gives amongst other:
PF (Integer)
For each Point, Indices of Brep Faces connecting to it
Nice solution, inno.
… there is always something to learn!
I almost never used proximity component and practically I didn’t know its existence. Indeed it’s useful in this context.
I tried to make your def work with vanilla components:
oh wow, AWESOME!
never used Item Index before in my life and it’s awesome to generate a list of all indexes
and Longest List with repeat last instead of Stack Data is also a nice thing to keep in mind
I’ll dig into a bit more into it later because my brain shortcircuits at Sort List 
but I’ll get there after a couple of drinks
I use [item index] only to spare a component, but i think this is actually bad practice (and that component can probably be much more useful in other scenarios/uses).
Better use list length + series.
Then, the [sort list] is probably useless. I’m using it only to ensure the next step (set+member index+partitioning) works correctly. But probably values before sort list are already sorted enough for the script to work.
BTW: Spend a couple of minutes on that.
public List<FINFO> fInfo;
public class FINFO {
public int BIDX {get; set;}
public int FIDX {get; set;}
public Point3d CENT {get;set;}
public FINFO (int bidx, int fidx, Point3d p){
this.BIDX = bidx; this.FIDX = fidx; this.CENT = p;
}
}
public Point3d cent;
public void GetCenters(List<Brep> bList){
fInfo = new List<FINFO>();
for(int i = 0; i < bList.Count;i++){
BrepFace[] faces = bList[i].Faces.ToArray();
for(int j = 0; j < faces.Length;j++){
BrepFace face = faces[j];
Curve crv = face.OuterLoop.To3dCurve();
Polyline poly; crv.TryGetPolyline(out poly);
if(poly != null) cent = poly.CenterPoint();
else cent = AreaMassProperties.Compute(crv).Centroid;
fInfo.Add(new FINFO(i, j, cent));
}
}
}
DataTree<int> conn = new DataTree<int>();
Point3dList taken = new Point3dList();
foreach(FINFO info in fInfo){
int bIdx = info.BIDX;
int fIdx = info.FIDX;
Point3d Cent = info.CENT;
if(taken.Contains(Cent)) continue;
taken.Add(Cent);
var Q = fInfo.Where(x => x.BIDX != bIdx && x.CENT.DistanceTo(Cent) < R).OrderBy(x => x.CENT.DistanceTo(Cent)).ToList();
if(!Q.Any()) continue;
int bIdx2 = Q.First().BIDX;
int fIdx2 = Q.First().FIDX;
taken.Add(Q.First().CENT);
if(!conn.PathExists(new GH_Path(bIdx, fIdx))){
conn.AddRange(new int[2]{bIdx2, fIdx2}, new GH_Path(bIdx, fIdx));
}
if(!conn.PathExists(new GH_Path(bIdx2, fIdx2))){
conn.AddRange(new int[2]{bIdx, fIdx}, new GH_Path(bIdx2, fIdx2));
}
}
… it should terminate in around 30 ms (or so).
OMG… I think I committed a crime, some solutions have even been updated to the 4th version, I am terribly sorry!
I just remembered there is a super fast cell topology component in Nautilus that can tell the neighboring relationship between touching Brep cells.
I promise I will read your solutions and try to learn from them.
The cells are made from the Iguana plugin(which can produce volumetric 3D mesh). I am trying to make 3D Voronoi by connecting all the neighboring volume centers, so I need the cell topology data.
I think this is a way of making 3D Voronoi without the Solid Intersection process.
I copy-pasted your code… not really sure how it works but at least it give the same results (but your topology is also more “intertwined”)
Edit: I’ve just tried with Nautilus and it is a bit faster!
@Quan_Li worry not! This is fun!
Who knows? who should?
what means this? You mean the 2 indices Conn Tree?
If you have implemented the stupid LINQ posted above … well … that’s expected. As a challenge try to use RTrees (but how to relate points to class info ? you tell me) of Point3dLists.
I thought it was what you posted, that code. Sorry I couldn’t follow…
Yes, usually I haven’t seen the need for that, but I can understand how it could be handy. It make sense to have additional output when the cost difference is null…
Well … as I said … EVEN this stupid approach yields “OK” elapsed Time. Meaning that is the slowest imaginable way to cut the mustard.
Add an option then: explicit (2 dim paths: first the Brep idx, 2nd the Face idx, items: indices of adjacent Brep/Face) or “generic” (classic 1 dim paths: what Brep is adjacent to what).
All that prior implementing a proper (thread safe) // thingy.
As a challenge for the brave (Plan B):
Forget Centers … get Face Planes (for this case anyway) and cut the mustard the other way.
Updated, removed the unpopular plugin.
Iguana 3D mesh is this Voronoi V2.gh (986.7 KB)
