# Find neighbouring cells

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)

2 Likes

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:

Find the real neighbours_v3.gh (1.1 MB)

• create a line from each cell volume center to each of its own face centers
• shrink by “k” the lines away from cell volume center
• join all lines toghether, now resulting in polylines
• cull all lines that did not join with anything (naked faces, faces without neighbour)
• extend all polylines by “k”
• polylines now are a physical connection, end points connect any cell to one of its neighbours
• convert polylines endpoints into indexes and build a topology tree
• … ?
• profit!

Similar but with less geometric stuff:

Find the real neighbours_v4.gh (1.1 MB)

1 Like

Aren’t you the one that found such a component exists in Nautilus ?
(I haven’t tested it, just have a good memory :D)

2 Likes

And the c# code version attempt:

Find the real neighbours_v5.gh (1.1 MB)

… 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){
}else{
}
}
}

Grasshopper.DataTree<int> tree = new Grasshopper.DataTree<int>();
for(int i = 0 ;i < n;i++){
}
BB = tree;
}
``````
2 Likes

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

2 Likes

3 Likes

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

1 Like

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:

Find the real neighbours_Re2.gh (1004.0 KB)
Member Index component is quite slow…

2 Likes

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

1 Like

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.

2 Likes

BTW: Spend a couple of minutes on that.

1. Define a class and get the centers in a first pass. This requires around 5ms (or so):
``````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;

}
}
}
``````

1. Then … do some LINQ or use RTrees or Point3dList and do the Conn Tree required (another 5 ms max). Even if you do the most stupid LINQ thing known to man like …
``````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;

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;

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

3 Likes

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.

Iguana 3D mesh is this Voronoi V1.gh (1022.0 KB)

The 3D voronoi get from Iguana.

1 Like

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”)

Find the real neighbours_v6.gh (1.1 MB)

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.

1 Like