Connectivity - A New Year's Challenge!

[Macha]

Here's a tough nut for all you seasoned experts:

I want to have something akin to the connectivity SOP but with some intelligence. How could we go about finding the strength of a connectivity. Say we have 2 pieces of geometry that are just connected by a tiny bit, but we would like to consider them 2 different pieces. Or we have 2 geometries that are almost connected, just separated by a small distance.

How to distinguish between different degrees of connectivity? Not at all connected, nearly connected, a tad connected, quite connected, strongly connected, absolutely one piece.

Any ideas?

I have a foggy mist of an idea about flow, and flux and, errr, uhmmm, hmmm....

Edited January 3, 2012 by Macha

[3dbeing]

I'm not sure I follow, are 2 points either connected or not connected? Can you give an example of something that is 'connected by a tiny bit'? Would you be reffering to something relative to size of the overall object? I'm a bit confused....

[Macha]

Imagine a dog with the tip of its tail touching a tree. We can either be very strict and say "Yep, this is one piece of geometry. Tree and dog are one thing". That's what the connectivity sop will tell you.

Or, we could be a bit more subtle and say "Ah, well, they are only connected by a tiny hair on the dog's tail so we might as well call them 2 different pieces".

I'd like to quantify this degree of connectedness.

If you will, imagine current flowing through the geometry. It would encounter higher resistance at small connections. Well, kind of. At other places potentially too.

[3dbeing]

well conncetivity will only say they are connected if they... well.. are connected... touching doesn't really count...they have to be connected by a line.

If for some reason your dog's tail is connected to the tree, by 1 line, you would really have to use something like neighbor vop and neighbor count vop to discover how many neighbor degrees they are apart... like 6 degrees of seperation... higher degrees to reach a shared neighbor and the fewer number of neighbors they share, the less connected they are... Like the wierd guy at then end of the block... hahaha just kidding, but seroiusly folks, i'll be here all week...

How to go about implementing that.. well... no idea...

Edited January 3, 2012 by 3dbeing

[gaurav]

Most simple and obvious to me is good old attrib transfer.

Is that a no go for something like this

[Macha]

All good ideas but we don't know how many pieces there are in the first place. That's what we want to find out. Attribute transfer and the point counting method depend on you knowing that there are more than 1 piece already.

Really, the best analogy I can think of at the moment is electricity. Pump current through the thing and where it would blow up (due to heat generated at high resistance points) we'd get different pieces. The strength of the material would somehow indicate the pieciness of the thing.

Imagine you have some sort of setup that could separate this leafy seahorse into bits, according to some pieciness parameter you could specify.

Edited January 3, 2012 by Macha

[edward]

I want to have something akin to the connectivity SOP but with some intelligence. How could we go about finding the strength of a connectivity. Say we have 2 pieces of geometry that are just connected by a tiny bit, but we would like to consider them 2 different pieces. Or we have 2 geometries that are almost connected, just separated by a small distance.

That's an interesting question, and I think the answer depends on what you want to do with the result. It will probably also differ if you can make certain assumptions about the data.

Off the top of my head, if we assume closed meshes, one way might be to to use 3D erosion/dilation (eg. IsoOffset SOP). You then measure "connectedness" by the minimum amount needed to either erode (until a single piece disconnects), or dilate (until pieces connect).

PS. This is also closely related to 3D segmentation.

PPS. There are probably many other ways to express erosion/dilation that could be used for this purpose.

[0rr]

I think you are looking for mesh segmentation.

http://www.cs.tau.ac.il/~liors/research/projects/sdf/

I think one could do this in vex/vops.

Given a point on the surface mesh, we use a cone

centered around its inward-normal direction (the opposite

direction of its normal), and send several rays inside

this cone to the other side of the mesh (Fig. 3). For each

such ray we check the normal at the point of intersection,

and ignore intersections where the normal at the intersection

points in the same direction as the point-of-origin

(the same direction is defined as an angle difference less

than 90◦). This is done to remove false intersections with

the ‘outside’ of the mesh. The SDF at a point is defined as

the weighted average of all rays lengths which fall within

one standard deviation from the median of all lengths.

The weights used are the inverse of the angle between the

ray to the center of the cone. This is because rays with

larger angles are more frequent, therefore having smaller

weights.

Might not be the best way to do it but I have attached a hip file with a simple way to get meshsegments in houdini.

segmentationtest.hipnc

Edited January 3, 2012 by 0rr

[Barakooda]

I think you are looking for mesh segmentation.

http://www.cs.tau.ac.il/~liors/research/projects/sdf/

I think one could do this in vex/vops.

Might not be the best way to do it but I have attached a hip file with a simple way to get meshsegments in houdini.

Very nice !

[Jason]

There might be a use for Houdini 12's k-means Clustering SOP. Or perhaps someone could implement segmentation from ROS/PointClouds?

I've wanted to get these pointcloud funcs into Houdini for a while, for fun.

[Macha]

I think you are looking for mesh segmentation.

http://www.cs.tau.ac.il/~liors/research/projects/sdf/

I think one could do this in vex/vops.

Might not be the best way to do it but I have attached a hip file with a simple way to get meshsegments in houdini.

The link is very interesting. Yes, I think it should be doable.

The erosion-trick in the file works for simple objects but will have trouble when you can't create a suitable sdf, for example if you have open surfaces, or very complex ones. The "electricity-idea" I have suffers from the same problem. I was thinking of measuring some notion of density. For example, 1/area of each polygon (assuming they represent initially equal area) and then we can see where the surface tightens up. That gets into conflicts if 2 opposing surfaces are nearby though and the tight edge they create there. Maybe a similar thing could be tried with volumes but then we're back to the sdf-creating ;P

[Jason]

That Shape Diameter Function looks kinda handy too, yeah -- wish he'd have called it "Feature Diameter Function" or something so we don't get confused with Signed Distance Functions.