### Skeleton curve implementation based on VDB medial axis

14283   25   14
Member
31 posts
Joined: March 2017
Offline
Hello guys,

A few months ago I spent some time trying to come up with a straight skeleton curve solution for houdini.

Here you have some theoretical background about this topic:

http://visgraph.cse.ust.hk/projects/skeleton/skeleton_sig08.pdf [visgraph.cse.ust.hk]
https://www.cse.wustl.edu/~taoju/lliu/paper/pgcc/pgcc.html [www.cse.wustl.edu]
https://houdinigubbins.wordpress.com/2017/07/22/fiedler-vector-and-the-medial-axis/ [houdinigubbins.wordpress.com]

I trid to select the mosts relevant papers I found, IMO..

Challenges I faced:

1. Performance
Initially I tried to use the Smooth SOP(curvature mode) or Voronoi Fracture SOP with some acceptable results but unfortunately these solutions are extremely slow with dense meshes and they are not working very well with triangulated meshes. Then I decided to try VDB Advection against surface gradient with much better results.

2. Curve resampling
My technique uses a remeshed version of the original mesh, so the problem here is that during thinning process you need more resolution for elongated poligons. The solution here was to simply use a Resample SOP node.

3. Curve detection
Advection along VDB medial axis is cool, but it's not stopping until all points are contracted to the VDB's B-tree center nodes.
So, I had to come up with some kind of “curve detection” algorithm. Accidentally I discovered that you can do this easily using a VDB dilation followed by a medial VDB smooth and another dilation

4 Noise
Dealing with surface noise is a very sensitive problem. In reality, a 3D straight skeleton is more like a surface and very branchy. In order to solve this problem we have to use VDBSmooth SOP(medial smoothing mode) and make sure that advection is done with Fourth-Order Runge-Kutta method. Also, if the original mesh is very noisy you can use Paint SOP followed by a Smooth SOP to locally smooth the mesh and eliminate potential unwanted branches.

5. Remeshing & partitioning
This problem is relatively simple once you have the skeleton. You can use a voronoi fracture against the original mesh and as control points you can use the a resampled and refined version of your skeleton polycurve.
Also here you can do skeleton curve partitioning based on curve branching or angle/curvature and then transfer back these attrbutes to the original mesh points. Very useful for mesh partitioning, limb detection, bone automatic positining and even quad remeshing.
In combination with Convex Decomposition SOP(appliend to the shrinked mesh) you can get some kind of branch based decomposition.

So, here are some results:
Edited by rpopovici - April 28, 2019 10:38:17

Attachments:
tommy_curve_skeleton.png (252.0 KB)
tommy_curve_skeleton_refined.png (264.8 KB)
tommy_curve_skeleton_fracture.png (234.2 KB)

Member
31 posts
Joined: March 2017
Offline
Squab example

Attachments:
squab_curve_skeleton.png (386.5 KB)
squab_curve_skeleton_refined.png (356.2 KB)
squab_curve_skeleton_fracture.png (394.7 KB)

Member
31 posts
Joined: March 2017
Offline
More exotic meshes heptoroid, fertility, rocker arm, elk

Attachments:
heptoroid_curve_skeleton_refine.png (473.7 KB)
heptoroid_curve_skeleton_fracture.png (534.6 KB)
fertility_curve_skeleton_refined.png (430.5 KB)
fertility_curve_skeleton_fracture.png (392.3 KB)
rocker_arm_curve_skeleton_refine.png (364.3 KB)
rocker_arm_curve_skeleton_fracture.png (296.6 KB)
elk_curve_skeleton_refine.png (459.0 KB)
elk_curve_skeleton_fracture.png (319.0 KB)

Member
31 posts
Joined: March 2017
Offline
Here is a sample hip file.. If you have any idea about how to improve this stuff feel free to C&C

Attachments:
vdb_skeleton_curve.hipnc (291.7 KB)

Member
240 posts
Joined: Nov. 2012
Offline
This is great!

Works really well for thin meshes, and the voronoi trick at the end is also super useful for a bunch of different things.

The VDB From Polygon bits is super slow, I'll see if I can come up with a faster alternative. Since you're already remeshing would the attribute blur SOP work faster in some cases?

Luiz
Luiz Kruel
Senior Technical Artist
SideFX
Member
31 posts
Joined: March 2017
Offline
Hey Luiz, thanks!

VDB from Poly is quite fast. I believe that resample SOP is extremely slow.
Remesh SOP is kinda optional. I am using it to control mesh resolution.
Unfortunately I was unable to find a way which does not require to re-run VDB from polygons at each step. I tried many things, but this was the only way which works with thin surfaces. For some reson vdb advection is not renormaling the sdf the same way VDB from polys does.
Member
31 posts
Joined: March 2017
Offline
Found some ways to improve the performance:
- Remesh SOP lower res
- Resample SOP lower res
- only one VDBFromPoints per step
- voxel size is a function of log10(iteration)

Attachments:
vdb_skeleton_curve2.hipnc (488.8 KB)

Member
31 posts
Joined: March 2017
Offline
Some more improvements:
- curve extraction hda ready
- better curve detection
- better curve refinement
- limb selection example

Attachments:
vdb_skeleton_curve3.hipnc (599.6 KB)
squab_limb_select.png (440.1 KB)

Member
31 posts
Joined: March 2017
Offline
Found another trick to improve performance. Apparently VDBFromPoligons igonres open polys. So, we can use that when we re-run VDBFromPolys.

Squab and Tommy in less than 5 secs, heptoroid in less than 10 secs ..on my laptop.

Attachments:
vdb_skeleton_curve4.hipnc (611.9 KB)

Member
891 posts
Joined: March 2014
Offline
Very exciting. Thank you for sharing.

Andy
Member
304 posts
Joined: June 2013
Offline
Thanks for sharing, I think your post is a visual compelling argument on why it's a solution worth to be native to Houdini, alike Find Shortest Path, Edge Transport, which are building blocks for many other setups.

I too was looking into this recently [www.facebook.com] and I'm noticing your setup also struggles with the tentacles where they meet. It's hard to get a nice 8-edge star without compromising other areas.
As I've set this up I wondered:
- What kind of simple markup could be done on the input mesh to help the asset come to better local results?
- How can one infer the important joint points (knees, elbows, etc) and maybe have straighter curves where sensible?

Cheers
Pedro
Edited by probiner - April 28, 2019 07:41:06
Member
31 posts
Joined: March 2017
Offline
Pedro, I totally agree with you. Straight skeleton is like philosopher's stone for 3D. You can use it for pretty much anything once you have it.

In reality, a 3D straight skeleton is not exactly a curve. It's more like a surface which can be further degraded into a curve. Tubes and pipe like meshes will resolve faster to a curve, but stuff like a flat or concave mesh, will take longer to resolve because you are limited by the voxel size and VDB internal representation of the volume(multiple B-tree center nodes). You can apply more median SDF smothing in order to eliminate surface disturbances but also it will give you a faster resolve towards the end result. If you want to know how a real straight skeleton really looks like, you can run Voronoi Fracture SOP with original mesh points as control points. Unfortunately this is extremly slow for high density meshes and also the result is way to branchy.

1. Paint SOP -> smoothing locally with Smooth SOP will eliminate skeleton small branches and it will give you a cleaner skeleton curve.
2. You can use Refine SOP(Unrefine mode) to straighten curves with lower curvature. You can also manually select points you don't want to refine.

Cheers
Radu
Edited by rpopovici - April 28, 2019 10:04:21
Member
129 posts
Joined: Jan. 2013
Offline
thank you for sharing
Member
31 posts
Joined: March 2017
Offline
- for some reason, gradient normalization gives faster advection in flat volumes. Probably in this case gradient's magnitude is smaller before normalization..
- added a stop condition in case the skeleton is computed in less steps than iteration count
- added an auto uv example based on straight skeleton and find shortest path
Edited by rpopovici - May 1, 2019 16:06:14

Attachments:
vdb_skeleton_curve5.hipnc (675.8 KB)

Member
304 posts
Joined: June 2013
Offline
Pighead case has improved greatly in this last version. Well done.
Member
31 posts
Joined: March 2017
Offline
More improvements to this project

- found a way to optimize vdbfrompoly
- incresed 2x default voxel size from 0.002 to 0.004
- VDB smooth with curvature flow
- replace Ends SOP with Split SOP
- skeleton thining as post process
- perf improvement up to 5x in most cases
Edited by rpopovici - July 9, 2019 03:24:39

Attachments:
vdb_skeleton_curve6.hipnc (750.9 KB)

Member
11618 posts
Joined: July 2005
Offline
This is very nice… without delving into how you did it myself, do you think there might be ways to derive capture weights knowing the input source? ie, something suitable for the Deform SOPs. I imagine one might be able to do it post-hoc using the existing tools, of course.
Jason Iversen, Technology Supervisor @ Unity Technologies x Weta Digital
also, http://www.odforce.net [www.odforce.net]
Member
31 posts
Joined: March 2017
Offline
@jason_iversen right now I am not in front of it, but I believe @probiner has some skeleton based animation example. I am assuming here that it’s based on Deform SOP..

As for weight capturing, this can be done but it might not be what you want because the skeleton is determined in two steps. First, determine the skeletal surface, then reduce that to a curve skeleton. So, the gradient trace is not exactly a straight curve normal to surface
Member
11618 posts
Joined: July 2005
Offline
Hey Radu, thanks for answering!

rpopovici
So, the gradient trace is not exactly a straight curve normal to surface

That's kind of what I'm hoping would be the value-add of trying to propagate weighting in the solve, as opposed to doing a proximity thing or a even a biharmonic thing. It may be far worse than just doing the weighting post hoc, I'll admit - but a fair experiment
Edited by jason_iversen - Aug. 8, 2019 14:43:55
Jason Iversen, Technology Supervisor @ Unity Technologies x Weta Digital
also, http://www.odforce.net [www.odforce.net]
Member
31 posts
Joined: March 2017
Offline
v7:
- removed several seconds from the post processing phase
- skeleton thinning much faster
- removed some unneeded stuff from the curve refinement phase, also much faster
- the entire process for squab in less than 6 sec - skeleton extraction, thinning and curve refinement

BTW, @lkruel did a great job of integrating a 3d skeleton solution based on this stuff into the game toolset. Luiz, thanks! ..and a thumb up emoji would be nice in the comment section
Edited by rpopovici - Aug. 15, 2019 11:17:56

Attachments:
vdb_skeleton_curve7.hipnc (763.1 KB)

• Quick Links