Voronoi - dynamic - location based fracture (WIP)

[johner]

Well maybe I'm missing something myself, it sounds like you nearly did it this way, we do literally thousands of capping operations on cut geometry, cut with a clip sop, and then just use the divide sop with "remove shared edges" turned on afterwards, that's it. That will give you a poly that is concave or convex...

:shocking:

Well, I'll be a *@^#&%@#&*!

Not sure how I missed that one. Thank you very, very much Simon, that will do wonders for this thing and my general sanity.

Expect a faster, more robust version soon.

[johner]

OK, attached is a new version using the Divide SOP rather than a Python SOP to do the capping. Many thanks to Simon and to kuba for the advice. I've removed the Python SOP and the Clip with Cap assets from this version of the OTL, in case you get any warnings, you can ignore them.

This version is about 2 times faster for simple test objects, up to about 5 times faster for higher res meshes. Probably more importantly, it handles concave geometry much more robustly. Shapes like torii and bowls fracture quite well, and I added the second clip operation that Simon mentioned to try to support non-watertight meshes. It does a fair job with a Convert'ed platonic teapot, which is a slightly strange mesh, so I've included demos of that in the basic_fracturing and dynamic_fracturing files.

Flipbook here.

Speeding up capping and supporting more geometry were two big things on the TODO list. With them somewhat handled for the moment, the most annoying limitation at the moment is the whole "MaxCuts" parameter. The idea behind it is, when the Fracture SOP first runs, a VEX SOP uses point clouds to put the MaxCuts nearest points into a "nearest" attribute on each cell point, in increasing distance from the cell point. It also stores the MaxCuts value in a "numnearest" attribute.

The Fracture SOP then just iterates throught the cell point nearest points, iteratively clipping and capping, with various Switch SOPs in there to try to short-circuit doing any work once the Clip SOP is no longer having any effect.

This all works pretty well with a convex input mesh and regularly spaced cell points, but it starts to fall apart with concave meshes and clustered points. In those cases, the nearest points geometrically don't necessarily correspond to the adjacent points in the Voronoi sense: there might be a whole cluster of points near a cell point, most of which don't further divide up space at all, if that makes sense. So currently you can wait a few minutes for a complex fracture operation, only to end up with artifacts because the MaxCuts value was too low, which is really annoying.

So, my next step is to try a Voronoi decomposition of the input cell points in that initial VEX Sop, so that the "nearest" attribute contains, for each cell point, only those other points which are adjacent in the Voronoi sense, and "numnearest" contains the exact number of adjacent cells. This would serve the dual purpose of having the Fracture SOP only do exactly as much clipping as needed, and making it much cheaper to crank the MaxCuts parameter way up, possibly even to the set of all other cell points (meaning the parameter and any artifacts could just go away). It will still probably be a O(n^2), brute force algorithm, but it will be in VEX, multithread, and be independent of the input mesh complexity. I think even with a couple of thousand cell points it shouldn't be too awful, but we'll see.

Please let me know if you find problems with the current version. Meanwhile, back to the computational geometry books and lots of print statements...

voronoi_fracture.tar.gz

[mrice]

Johner, you are a mensch. I'll be using this plenty to break things.

[t7200]

Thank you so much for sharing this.

You are the man!

[t7200]

When I tried to render your advanced example->explode_example with a mantra node

I got this out of the Houdini Console:

Unknown operator type: Sop/jl_cap_holes

Unknown operator type: Sop/jl_clipwithcap

Do you know what this means?

Thanks,

Dillon

[johner]

When I tried to render your advanced example->explode_example with a mantra node

I got this out of the Houdini Console:

Unknown operator type: Sop/jl_cap_holes

Unknown operator type: Sop/jl_clipwithcap

Do you know what this means?

Thanks,

Dillon

From my post above:

I've removed the Python SOP and the Clip with Cap assets from this version of the OTL, in case you get any warnings, you can ignore them.

Is this just a warning, or is it stopping you from rendering? I can do some further clean up on the files in the latter case.

[morpheus101]

Thanks Johner

Excellent asset. Well done!!

[johner]

So, my next step is to try a Voronoi decomposition of the input cell points in that initial VEX Sop, so that the "nearest" attribute contains, for each cell point, only those other points which are adjacent in the Voronoi sense, and "numnearest" contains the exact number of adjacent cells. This would serve the dual purpose of having the Fracture SOP only do exactly as much clipping as needed, and making it much cheaper to crank the MaxCuts parameter way up, possibly even to the set of all other cell points (meaning the parameter and any artifacts could just go away).

A quick update on this. A bit of research informed me I don't actually want a Voronoi decomposition, I want the Delaunay tetrahedralization (naturally), which is the dual of the Voronoi decomposition. If you have this tetrahedralization, then a given Voronoi cell point will share edges with only those other points that are adjacent Voronoi cells, which is exactly the information the Fracture SOP needs to do the proper amount of clipping.

Houdini actually has the 2D version of this built-in: Triangulate2D does the Delaunay triangulation of the provided points. So, in 2D you can Triangulate2D the scattered input points, then use the pointneighbour expression for any given point to get its adjacent vertices, and that gives you the adjacent Voronoi cells. I wrote a quick Python test SOP to store these in the nearest, numnearest attributes I was describing above, and ran through the various 2D examples in the basic fracturing file. A good bit faster and more robust, since the MaxCuts parameter is irrelevant once you've done the triangulation of the entire point set.

This is obviously a little more complicated in 3D. CGAL has an implementation of Delaunay tetrahedralization, as well as Python bindings, so I wrote a quick Python SOP to generate the tetrahedralization with CGAL, sort the incident vertices for each Voronoi cell point by distance, and store the results in the nearest, numnearest attributes. This worked nicely, speeding things up by 50-75% (actually less than I expected), and more importantly, generating artifact free results, since the Fracture SOP was always doing the proper amount of clipping. As a reference point, the Python SOP using CGAL takes less than 2 seconds to execute on 2000 input points, which is plenty sufficient performance.

Now, obviously I don't want to introduce a dependency on CGAL into this asset. A bit of the Google led to me this interesting thread over on 3DBuzz. Apparently Steve Twist did something similar to the fracturing part of this for Houdini about a year ago. He did an implementation of Delaunay tetrahedralization in a Python SOP based on a paper that goes through it in good detail. Looking over the paper, I think that's probably the way to go. Shouldn't be too bad as I've got a reference implementation in CGAL, which always helps. Plus a Python SOP of that might be useful in other contexts, I imagine.

Attached is a picture of a 1893 piece fracture of a 3500 triangle version of the armadillo model done with the CGAL Python SOP (I could post the geometry if anyone wants to mess with it). It took about 25 minutes to complete, and from what I can tell, is free from artifacts.

Edited May 29, 2009 by johner

[CeeGee]

Some simple tests

Ground break

ground_fracture.mov

Dragon - 500parts

dragon.mov

[sibarrick]

A quick update on this. A bit of research informed me I don't actually want a Voronoi decomposition, I want the Delaunay tetrahedralization (naturally), which is the dual of the Voronoi decomposition. If you have this tetrahedralization, then a given Voronoi cell point will share edges with only those other points that are adjacent Voronoi cells, which is exactly the information the Fracture SOP needs to do the proper amount of clipping.

Houdini actually has the 2D version of this built-in: Triangulate2D does the Delaunay triangulation of the provided points. So, in 2D you can Triangulate2D the scattered input points, then use the pointneighbour expression for any given point to get its adjacent vertices, and that gives you the adjacent Voronoi cells. I wrote a quick Python test SOP to store these in the nearest, numnearest attributes I was describing above, and ran through the various 2D examples in the basic fracturing file. A good bit faster and more robust, since the MaxCuts parameter is irrelevant once you've done the triangulation of the entire point set.

This is obviously a little more complicated in 3D. CGAL has an implementation of Delaunay tetrahedralization, as well as Python bindings, so I wrote a quick Python SOP to generate the tetrahedralization with CGAL, sort the incident vertices for each Voronoi cell point by distance, and store the results in the nearest, numnearest attributes. This worked nicely, speeding things up by 50-75% (actually less than I expected), and more importantly, generating artifact free results, since the Fracture SOP was always doing the proper amount of clipping. As a reference point, the Python SOP using CGAL takes less than 2 seconds to execute on 2000 input points, which is plenty sufficient performance.

Now, obviously I don't want to introduce a dependency on CGAL into this asset. A bit of the Google led to me this interesting thread over on 3DBuzz. Apparently Steve Twist did something similar to the fracturing part of this for Houdini about a year ago. He did an implementation of Delaunay tetrahedralization in a Python SOP based on a paper that goes through it in good detail. Looking over the paper, I think that's probably the way to go. Shouldn't be too bad as I've got a reference implementation in CGAL, which always helps. Plus a Python SOP of that might be useful in other contexts, I imagine.

Attached is a picture of a 1893 piece fracture of a 3500 triangle version of the armadillo model done with the CGAL Python SOP (I could post the geometry if anyone wants to mess with it). It took about 25 minutes to complete, and from what I can tell, is free from artifacts.

Good work! looking forward to see that.

[johner]

Good work! looking forward to see that.

Thanks, should be an interesting exercise. It's going to be a few days before I can even start on it, though, and I was thinking maybe I should fix the 2D version in the meantime. Since I'd only be using the tetrahedralization for adjacency information in this case, I was thinking if the input cell points were close to planar, the Delaunay triangulation from Triangulate2D would work just as well, and be faster, and probably more robust, since the planar case is actually degenerate for the tetrahedralization, I believe.

Anyone have any thoughts on a good way to determine if a set of points is (close to) planar? I was thinking about going ahead and doing a Triangulate2d, then compare the before and after bounding boxes. Oriented bounding boxes would be ideal, but the Bound SOP only supports that for primitives. Edit: it seems to work to copy something like primitive spheres to each point, and use the Bound SOP on that, so maybe something like that would work.

Another edit: thought of one way. Triangulate2D - Bounds SOP with Oriented Bounding Box on and a small upper and lower padding - then Delete or Group SOP with that bounding box and the original cell points. If any cell points are outside that oriented bounding box, not planar.

The animated ground effect looks cool, CeeGee; I was hoping someone would do that . Quick aside: the first time I heard mention of using a Voronoi decomposition for fracturing was a talk at Siggraph a few years back when a couple of Pixar guys spoke about using a 2D version like this to do the road cracking effect in Cars.

Edited May 29, 2009 by johner

[johner]

OK, I went ahead and implemented this. So now the Fracture SOP detects co-planar input cell points and uses the Triangulate2D SOP to get Voronoi adjacency information in that case.

This won't affect any 3D operations (unless your cell points happen to be co-planar for some reason), but it helps 2D a lot, especially when the cell points are unevenly distributed like in the "terrain" and "stained_glass" examples in the basic_fracturing file. These are much faster and shouldn't need any "MaxCuts" tweaking. Also, you can change the input picture in the stained_glass example to something like one of the butterflies in $HH/pic and everything should work, without having to mess with MaxCuts, which wasn't the case previously.

voronoi_fracture.tar.gz

[pockets]

OK, I went ahead and implemented this. So now the Fracture SOP detects co-planar input cell points and uses the Triangulate2D SOP to get Voronoi adjacency information in that case.

This won't affect any 3D operations (unless your cell points happen to be co-planar for some reason), but it helps 2D a lot, especially when the cell points are unevenly distributed like in the "terrain" and "stained_glass" examples in the basic_fracturing file. These are much faster and shouldn't need any "MaxCuts" tweaking. Also, you can change the input picture in the stained_glass example to something like one of the butterflies in $HH/pic and everything should work, without having to mess with MaxCuts, which wasn't the case previously.

Something to keep in mind is it's still possible to get concave shaped cells from the Triangulate2D SOP output. I discovered this while working on techniques to "model" crack and shatter patterns with scatter points. What I found was an effect similar to what you describe in an earlier entry regarding your max cuts and the introduction of error in your result around high concentrations of points.

We implemented a similar cutting procedure when I was at DD last year hinged on the robustness of the Clip SOP. They've had a tool at SPI that worked this way for quite some time and it was used to great effect for the destruction effects in The Watchmen. Anyway, I implemented the early version of some similar techniques at DD but was focused mostly on efficient pre-scoring and data communication with the constraints and dynamics system being built. The dynamic looking results in our case were handled by the system's efficient (amazingly so) constraint handling so that we could pre-visualize and direct the destruction. Something like your technique was where I eventually wanted to go, and it was on the agenda, but I'm not sure if it ever made it in there. I've been inspired to rebuild what I started at DD for my own purposes though my focus again will be on the shatter patterns themselves.

What I set on as a solution to my frustrations over the Triangulate2D output (which the GI Joe folks were encountering as well) was this open source package called QHull which you might take a look at. I'm not really a programmer, just a script and sometimes VEX hack, but it was pretty fast and easy to make an OTL that took input geometry, 2D or 3D, scatter points onto the surface or its volume, write these points out to disk and run a couple python scripts which call the QHull tools, reading in the resulting 2D Voronoi diagram or 3D cluster of convex shells. I didn't even have to write the scripts to do this as someone had already done so, for both types of Voronoi result. That way I spent most of my time building the cutting tool and patterns, overlapping different shape volumes and cluster placement to art direct the cracking.

The results that I get seem to suggest a lot of filtering is done by the QHull tools to the points to eliminate "illegal" results. The worst thing that happens, depending on how I'm distributing points, is I might get some boring, regular shapes but I don't think I've ever had a concave result. Without derailing any of your work, which is very cool, you might take a look at the links above to handle the labor of the cell construction so that you can concentrate on the fun part. Unless all of the solution is the fun part for you because I know that's the case for some TDs.

edit: here's an example of my early work prototyping the tool.

test1

test2

Edited May 30, 2009 by pockets

[johner]

Interesting stuff, thanks.

Something to keep in mind is it's still possible to get concave shaped cells from the Triangulate2D SOP output. I discovered this while working on techniques to "model" crack and shatter patterns with scatter points. What I found was an effect similar to what you describe in an earlier entry regarding your max cuts and the introduction of error in your result around high concentrations of points.

I'm hoping it will still work OK for my purpose, since I'm not actually using the output of the Triangulate2D SOP directly, i.e. I'm not using any polygons created by it. I'm just using the connectivity information from it to tell me the adjacent Voronoi cells in 2D, which tells me, for any given cell point, the other cell points I need to put a clip between. I haven't seen any artifacts from that process yet, but of course I just implemented it this afternoon, so we'll see. Do you happen to have any examples of bad output from it?

Wikipedia's entry on Delaunay triangulation has a picture of the relationship between the Delaunay triangulation and the Voronoi diagram in 2D, FWIW.

What I set on as a solution to my frustrations over the Triangulate2D output (which the GI Joe folks were encountering as well) was this open source package called QHull which you might take a look at.

I'm familiar with QHull, though it's been a while since I've used it. CGAL, which I referred to earlier, is a similar set of tools, but it has Python bindings, so I went with it for testing purposes. That test Python SOP I mentioned a few posts back uses CGAL to do a full Delaunay tetrahedralization of the input points, from which you can immediately get all the Voronoi cells. So at least in that test SOP I've got easy access to those cells in Python if I can figure out a good way to use them directly, which so far I haven't. At the moment, I'm just using the connectivity information to tell me where I need to clip, just like in the 2D case above.

In your videos, I get what's going on at each step until the geometry is cut by the Voronoi cells. Is that the Clip SOP, or are you using something else?

The results that I get seem to suggest a lot of filtering is done by the QHull tools to the points to eliminate "illegal" results. The worst thing that happens, depending on how I'm distributing points, is I might get some boring, regular shapes but I don't think I've ever had a concave result.

Yeah, all those industrial-strength computational geometry tools do things like use exact arithmetic in certain parts of the code to avoid the degeneracies that come from inexact floating point. That may be what you ran into with the Triangulate2D SOP, since I can't imagine they go to that computational expense.

Without derailing any of your work, which is very cool, you might take a look at the links above to handle the labor of the cell construction so that you can concentrate on the fun part. Unless all of the solution is the fun part for you because I know that's the case for some TDs.

Thanks. I'm far enough along at this point that I'd like to end up with a tool that doesn't have any external dependencies if possible. And I come at this whole thing from the programming side, so I'm not too put off by the idea of writing a tetrahedralization SOP if I can swing it. But if I do that I'll have the same access to those Voronoi cells, so I'd be really interested in hearing any success you had in using them directly, rather than just as a template for the Clip SOP, which is my plan at the moment.

[sibarrick]

So at least in that test SOP I've got easy access to those cells in Python if I can figure out a good way to use them directly, which so far I haven't. At the moment, I'm just using the connectivity information to tell me where I need to clip, just like in the 2D case above.

If you have the cells as actual geometry could you just loop through each cell and then each face and use the orientation and position of the face to drive the clip sop directly? I have an example of using a polygon to position the clip sop on my site.

[CeeGee]

Test with new Fracture SOP...

One is 2230part and second is 3000parts - ground breaking

ground_fracture_v03.mov

[pockets]

If you have the cells as actual geometry could you just loop through each cell and then each face and use the orientation and position of the face to drive the clip sop directly? I have an example of using a polygon to position the clip sop on my site.

To answer both of you guys above, this is what I'm doing. I envy you guys that can totally roll-your-own but I've got to come up with other means.

I'm using the geometric output from QHull for the cells to define the clip faces. Love me some Foreach SOP. Depending on the geometry I'm fracturing, if I'm sure it's all convex, the cell geometry is also what I use to determine the sealing faces (caps). The mechanics of doing this also make it trivial to assign different groups for surfacing and subdividing later.

Post-sim I then have an OTL that allows me to do different levels of subdivision without altering the topology of the primary fracture geometry. It can smooth the "novel" surfaces and let me slide the edges along the chunk face normals so that the result doesn't look so geometrically perfect, or to enhance the appearance of edge cracking, allow the edge to crack and precede a chunks animation, etc. I've got the basic version that can handle the subdivision and such but am still working on how I want to drive this with animation and working out some of my area based dampening because it's easy enough to get some tiny polygons that shouldn't be displaced at all due to adjacent topology or their scale relative to the displacement magnitude.

test3

...the colored, inside surfaces are actually pieces clipped off from the actual Voronoi cells used to cut the modeled geometry. If the geometry being cut is convex you can simply reverse the process of who is cut and who's used to cut. Fractured geometry with concave surfaces of course will need a far more involved procedure to cap and make solid, if you need to do so. I'm not quite at that part of the headache yet Before I get into that I'm likely going to tackle secondary fracturing which adds quite a lot as previous tests in this thread so greatly show and is currently missing from my WIP setup.

Edited May 30, 2009 by pockets

[johner]

If you have the cells as actual geometry could you just loop through each cell and then each face and use the orientation and position of the face to drive the clip sop directly? I have an example of using a polygon to position the clip sop on my site.

Thanks, Simon. It turns out, placing the Clip SOP is one of the straightforward parts of this whole mess. For a given cell point, to clip to another cell point, the Clip is just halfway between the two points, facing from the first to the other. So if you have the cell points, placing the clips is not bad. The trick is knowing exactly which cell points are Voronoi adjacent, so you clip everywhere you must, but not more so.

I was thinking about possibly building the cell polygons explicitly, at least in the case when the entire cell is contained inside the mesh entirely, without any of the exterior surface. Then the cell consists of just convex polygons, so you could build it without clipping at all. I don't know if that would actually be any faster, since that's not many of the cells, and constructing polys in Python is not that fast. But it would mesh resolution independent for those few cases.

And maybe clip just the surface and don't cap, then build the polys and clip them, then somehow try to stitch them together. All that really does for you is get rid of the capping operation, which (thanks again) is not THAT bad anymore.

There's a couple other ideas I had, but they involved the dreaded Cookie SOP, which I'd like to continue to avoid.

[pockets]

Thanks, Simon. It turns out, placing the Clip SOP is one of the straightforward parts of this whole mess. For a given cell point, to clip to another cell point, the Clip is just halfway between the two points, facing from the first to the other. So if you have the cell points, placing the clips is not bad. The trick is knowing exactly which cell points are Voronoi adjacent, so you clip everywhere you must, but not more so.

...

This brings up a question I've been interested in. In your setup are you accessing the clipping code directly and able to define a clip face rather than a clip plane or limit the actual clipping area in any way? During my work on some of these problems earlier there were cases, like windows, doors and other "holes" in otherwise solid surfaces that could create problems for the Clip SOP (and I, grudgingly, implemented a user switch to Cookie if they wanted). Or maybe I just answered my own question since there are cases where you're flirting with that as well.

Keep going soldier, I'm done for! If we have to use the Cookie the terrorists win!

[Jason]

There's a couple other ideas I had, but they involved the dreaded Cookie SOP, which I'd like to continue to avoid.

Perhaps someone should RFE that the Clip SOP gains the ability to either attempt to cap the thing it just clipped, or at least provide a point group that can be fed into a PolyKnit or something? I can imagine just chopping up something like crazy using the Knife tool and have it cap both chunks. That would make it quite a fun process, I'd think.