[Houdini] FSP Optimize
Find shortest path is an incredibly cool and powerful tool inside of Houdini, it’s great for making organic vein like structures. However problems start to arise when you have few start points and many end points while using “from any start to each end“ mode. The generated polylines have a ton of redundant geometry, and the problem gets worst when using point cost attributes that can cause many of the paths to only branch off at the very end. This is very easy to visualize using the explode tool…
Holy redundant geo, batman!
I see a lot of people using VDBs to mesh complex polyline setups. I’ve found this problematic for a couple reasons;
The finer the detail, or more complex the lines; the more voxels you need, and meshing this can be incredibly slow.
Transferring attribs to meshed VDBs is slow and sub-optimal.
UVing the output of of a meshed VDB is a massive pain!
Animating the input polylines is inefficient as the VDB needs to be cooked every frame, and animating the meshed output comes with plenty of its own challenges.
The easiest way to generate a clean mesh with good UVs is to use the Sweep node with “compute UVs” checked. Doing this with so much redundant geometry can easily tank viewport performance though. Houdini is sweeping each and every polyline from start to finish, and with all the end points leading back to a single start point we end up with all our sweeps overlapping.
The goal of this tool is pretty clear: reduce the point count as much as possible without changing the output shape at all. Knowing that the vertex at each “start“ group point is point index 0 within its primitive it’s easy to iterate over each prim that shares the same origin point and compare the positions of each vertex using a VEX for() loop. Once the first set of verts that do not have the same position are found we know that is where the paths diverge; now we can take the for loops iteration count - 1 and delete those vertices and their corresponding points from one of the prims being compared, and begin comparing a new prim to the one that has kept all of its points. In this case the prims have been sorted by “length“, either by FSP cost or by total point count per prim. Keep iterating over every prim and deleting the vert/ point sets and the output is a nice set of polylines where only the longest prim has kept all of its original points as all other prims can be considered as “branches“ of this prim.
The example I’m going to use in this instance is a simple sphere + tet embed with a single point picked as a “start“ point and 12.5% of the points picked at random as “end“ points (6,200 end points total). The geo then has an attrib noise applied to the FSP “point cost attribute“, I’m going to call this “avoidance“. The avoidance attrib creates pockets in space where the travel cost for FSP is prohibitively expensive, so the algorithm only branches into these areas if an end point is located within. This creates a couple “primary“ paths that most end points branch off of. This relatively simple setup generates roughly 370k points across 6200 prims. Running the result through my FSP Optimize setup reduces the total point count down to only 44.7k points across 4910 prims (prims whose end point is along a longer prims path are completely removed since they are 100% redundant geo), this even keeps 2 overlapping points to help with the shaping of a resample in subdivision curves mode. With no overlapping points retained the count is further reduced to 34.9k points. Exploding the result clearly shows how much less redundant geometry there is!
