# Find closest vertices and link them with a edge

Hi there,

A set of vertices (I’d say more: points, as this could be a structure which is not a mesh, just a set of points)

I used a lot of octree or things like that in Openframeworks at some point for checking distances and draw lines for points closest than a range.

What could be the strategy here?
I mean… at each level, where would you do this ?

I can imagine getting that set of dots as a point file converted into an EXR, with many layers and x, y ,z, normals etc.

I’d have to do a global calculations and draw lines or not between dots.

I’m interested by a global view for this kind of problem to solve
It could also gives me ideas about how to calculate densities of points around the camera (which is probably very costing calculation wise and that could probably be pre calculated), as it would be the way to do calculation over points in TD, globally.

I’m sorry, I’m exhuming this one (after 3 weeks of covid, but everything is ok now!)

Would someone have ideas or ways around this idea ?
I’d really like to know what would be the strategies (and nodes) for drawing edge for closest points.
Should we use instancing ? I mean, should we prepare a set of lines able to be drawn or not depending on conditions ?

Would it be better to use python for parsing the set of points ?
Or eventually GLSL ?

@paketa12 has a good tutorial here Plexus in Touchdesigner - YouTube

My numpy example works too Optimized function for returning distances - #2 by DavidBraun and Basic GLSL drawing - #4 by DavidBraun

An advanced method would be implementing this paper http://www.chrisoat.com/papers/EfficientSpatialBinning.pdf with a compute shader to group the particles into bins. Then with another compute shader you could use an atomic counter to add edge information to a buffer. The red channel would store the integer ID of one point in the edge and the green channel would store the ID of the other point. But technically this buffer would be start out as mono, so you’d have to work around this while writing to it.

Most of the k-d tree or octtree examples I’ve seen work well for large amounts of static points or smaller amounts of dynamic points. That’s why I’d go with these other ideas. I’d be happy to be pointed to some faster examples for large point sets.

2 Likes

thanks a lot
on my top list to test and to try to implement