Is there a way to use point clouds while respecting surface connectivi

[magneto]

Hi,

 

I know point clouds can be used to blend/average attributes within the radius of each point. Is there a way to do the same where it only does this if:

 

1. A point is connected to the same surface as the current point.

 

and

 

2. A point is within X units distance on the surface from the current point. Not point to point straight line distance, but the shortest surface distance between 2 points on the surface. I am not sure if there is a proper name for this. Not the best pic but something that looks like this:

 

 

As you can see the length of the shortest path that lie on the surface. The surface can be polygons or NURBS. This can't be faked with neighbour functions as edges are too coarse.

 

Can this be done using point clouds? If not, VEX? If not, then any other solutions in Houdini? It's gonna be a per point operation though just like VEX/VOPs.

 

 

Thanks

[Shinjipierre]

Mmmm, can't you use UVs for this?

[Solitude]

1) You could use connectivity sop and class attribute to determine if the two points lie on the same connected piece of geo by comparing the class.

2) In theory you could use a for loop and a certain number of iterations (step size based?) to trace a path from pointA along the surface towards pointB-- but there is also the shortestpath node now which I would suggest using instead:  https://www.sidefx.com/docs/houdini13.0/nodes/sop/findshortestpath

 

So, I would do the class attribute to determine eligibility, then findshortestpath node to connect them along the surface (you can also just use this to determine length by measuring the primitive area if that's all you're after).

[magneto]

Thanks guys, I don't have UVs.

 

Connectivity SOP solves half the problem. But I don't think Find Shortest Path SOP will work because it uses the physical edges of the geometry not the actual surface distance:

 

 

I don't know any other way to trace this path between the 2 points.

 

Actually another issue is some non existent edges in polygons can actually be the shorter path. You can triangulate the model to solve this except you don't know which winding will give the shortest path in any case for any point.

 

Edited December 2, 2014 by magneto

[Rainroom]

I tried a quick and dirty way to address the second problem. It does a decent job in my test case to find the shortest path. Here is the .hip file:

shortest_path.hipnc

Edited December 2, 2014 by Rainroom

[magneto]

Thanks that's a pretty good method. If there are other ways, please let me know.

 

I don't know if there are libraries that deal with this sort of thing? I.e. a point cloud like search that accounts for surface distance.

[Solitude]

^Good idea on the smooth / ray to get around using the exact topology from the shortest path node.

 

https://en.wikipedia.org/wiki/Pathfinding   << There's a few different algorithms for dealing with it,  I'm sure there are libraries out there you could compile into a plugin using hdk.  Something like this: http://arongranberg.com/astar/features

[petz]

Thanks that's a pretty good method. If there are other ways, please let me know.

 

I don't know if there are libraries that deal with this sort of thing? I.e. a point cloud like search that accounts for surface distance.

 

referring to the picture in your first post you may want to take a look at geodesic distance and geodesic path between points. there is no direct solution in houdini i can think of but if a good approximation is enough it would be fairly easy to code. do a search for novotni´s propagating wavefront method to calculate the geodesic distance field around a point. after that its easy to backtrace a path to the original "startpoint".

it might also be possible to hack the findShortestPathSop to calculate the distance field but without trying ... no idea if it would work. finally, you could always just use the findShortestPathSop together with the remeshSop in a  foreachSop to calculate the path in an iterative manner.

if you want to use some libaries i can highly recommend vtk. for speed there is the c++ lib you´ll have to use in the hdk and for easy of use you could use it through the python wrapper. both versions provide everything you´ll need.

just bear in mind ... a geodesic path between two points is not necessarily the shortest path!

hth.

petz

[magneto]

Thanks a lot petz. Knowing the correct terms really helps.

 

Do you know any simple approximate implementations? They don't use the edges of the model right but actually trace a path on the surface? Maybe something in petzlibrary?

 

I checked VTK after you said. I only found this:

http://www.vtk.org/doc/nightly/html/classvtkDijkstraGraphGeodesicPath.html

 

Which seems like edge based Dijkstra like the one in Houdini?

 

Are you sure we can use the Remesh SOP? Because it's pretty slow.

 

I stand correct that the geodesic path is not always the shortest path

 

 

 

Thanks again.

[petz]

 

Thanks a lot petz. Knowing the correct terms really helps.

 

Do you know any simple approximate implementations? They don't use the edges of the model right but actually trace a path on the surface? Maybe something in petzlibrary?

 

I checked VTK after you said. I only found this:

http://www.vtk.org/doc/nightly/html/classvtkDijkstraGraphGeodesicPath.html

 

Which seems like edge based Dijkstra like the one in Houdini?

 

Are you sure we can use the Remesh SOP? Because it's pretty slow.

 

I stand correct that the geodesic path is not always the shortest path

 

 

 

Thanks again.

 

 

 

 

well, i´m afraid that there is no such thing as a petzlibrary but a rough approximation should be easy as long as it relies on the findShortestPathSop. for a better solution the hard part would be to calculate the accurate distance field you would need for a proper geodesic path.

how accurate do you need the path to be? is a "rough" approximation enough?

i´ll see if i can put together a file when i have time...

 

petz

[magneto]

Thanks petz. I was mainly interested in how such an algorithm finds a path on the surface without only relying on edges like find shortest path sop.

 

One of my friends suggested using A*. I also found this here:

http://forums.odforce.net/topic/10494-mouse-brain/

 

I am not sure if A* is suitable.

 

So being able to find the accurate geodesic distance between an origin point and other points would be very cool, instead of straight line distance.

 

Also found this library:

https://www.ceremade.dauphine.fr/~peyre/teaching/manifold/tp3.html

 

Edited December 9, 2014 by magneto

[dedeks3000]

Maybe the Heat method  ?

 

 

The Paper link  (+ others stuff):

http://www.cs.columbia.edu/~keenan/

[eetu]

Or maybe the existing Volume Arrival Time SOP?

You do need to go to volumes and back which is a bit of an inconvenience.

 

ee_shortest_path_arrivaltime.hip

[petz]

 

Thanks petz. I was mainly interested in how such an algorithm finds a path on the surface without only relying on edges like find shortest path sop.

 

One of my friends suggested using A*. I also found this here:

http://forums.odforce.net/topic/10494-mouse-brain/

 

I am not sure if A* is suitable.

 

So being able to find the accurate geodesic distance between an origin point and other points would be very cool, instead of straight line distance.

 

Also found this library:

https://www.ceremade.dauphine.fr/~peyre/teaching/manifold/tp3.html

 

 

 

 

a* won´t help you since it is just another algorithm to find the shortest path in a graph. in other words, it uses the edges in the same way the findShortestPathSop does.

attached is a file that uses a very similar method as the library you have posted. the fast marching front propagation algorithm is quick "prototyped" in vex and python and therefore not amazingly fast but should give you some ideas ...

 

 

hth. petz

geodesic_path.hipnc

Edited December 9, 2014 by petz

[magneto]

Thanks alot guys. Two of my fav posters in my thread

 

I checked your methods and they look very good especially petz file will take a while to fully understand.

 

I also watched the heat method video but I am not sure how to use the existing tools in Houdini to implement that. Is that a better solution? If so, how hard would it be to do that in Houdini since there is already a way to generate a gradient, right?