Find connected / neighbor points?

General TouchDesigner Discussion
1

Imagine a box sop with subdivisions turned on. Maybe some noise applied. Now for each point I’d like to know to which other points it directly connects.

Is there a simple way to do this ?

2

I’m not sure about simple… I can think of two general approaches though that work but not scale super well.

  1. analyze the mesh in real time, you’d need to check all of the other polys/lines and see if they reference points that you are comparing to. you could determine neighbors this way, though sops are expensive, and so are nested for loops.

  2. if you can rely on fixed grid type of layout, you could use maths to grab what you know is the index to the right or left, front or back. for a 2d case, getting the pixel to the right of pixel 0 (assuming 10x10) would mean adding multiples of 10, moving up would mean adding multiples of 1, etc. shifting in a 3d volume would be similar.

  3. You might also be able to pre-analyze the structure, and generate your own more optimized data structure for finding neighboring connected points. You might for instance create a large lookup dictionary where the key is a point, and the value is a list of other points that are connected to the key point. If you wanted to you could traverse the grid finding second or third neighbors with a random walk.

3

Thanks for your input Lukas. The “grid” is static, but not necessarily a fixed / layout. Preanalyzing is probably the way to go. I couldn’t find any OPs that would help in such a case , so it looks like a python job.

4

You could pre generate a table where each row’s index is the points index and all cells in that row are neighboring point indices.

You could do table.row(index) lookups and get then do something with the associated points but I have a feeling something in pure python would still be faster overall… Maybe numpy could be leveraged for large parallel stuffs. Possibly glsl to parallelize looking up into a texture using a similar format!

5

My first hunch says convert your 3d boxgrid into a 3d NumPy array and then you can slice the info you need for each point. Also very fast to convert back to TD nodes these days.

1 Like