Voronoi - dynamic - location based fracture (WIP)

[Jason]

H10

Hello ,

great tool....

does this work with H 9.5 or H 10 ?

thanks,

bern

[johner]

does this work with H 9.5 or H 10 ?

As Jason said, I built the Fracture asset with H10, but I actually thought to myself a few times that there's nothing in there that couldn't have been done in 9.5. So I suppose back-porting it to 9.5 would be possible, but that would not be high on my priority list. Of course, if you're pre-fracturing your geometry, you could load your hip file into H10, fracture, then just save out the geometry to a file to read back into 9.5

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.

A quick update on this, as I'm interested in some feedback on ways to proceed from the programmer-types out there. Apologies if it's a bit long and technical.

I've done a first implementation of the Delaunay tetrahedralization code in pure Python, following this paper. At the moment it generates identical resuts to CGAL, provided that the input cell points are in "general position", which basically means free of the fun degeneracies that make computational geometry code difficult. For example, the Delaunay condition that this tetrahedralization is attempting to maintain is: for the sphere uniquely defined by the four points of one of tetrahedra in this structure, there are no other input points within that sphere. This works fine as long as no more than four points are co-spherical, but if you do something like Scatter points on a sphere (or spherical part of a model), the truth status of that condition is difficult to determine with floating-point arithmetic. Even things like Scattering in the fog volume generated from a cube tends to create lots of co-linear points for some reason, which introduce lots of the same problems.

So, two different options for handling this. The first is just to jitter the input Cell points in the Fracture asset before calling the tetrahedralization SOP. Adding a Point Jitter SOP with a jitter scale of about 0.001 seemed to introduce enough randomness into the input to get all the points back into general position and avoid any floating point errors. Of course the points are no longer exactly where they were for input, but for a fracturing operation I think that's probably fine. This option would let me keep things completely in Python. It's not the fastest thing in the world, but it shouldn't be the bottleneck in a large fracture operation. With this option, the Tetrahedralize3D SOP that I would include in the asset would probably only handle general position points, which would limit its usefulness (although you could always jitter the input to it).

The second option is to use exact arithmetic, and handle all the degenerate cases robustly. I wouldn't have to jitter the points (although I still might want to, as non-degenerate cases are faster to compute), and a robust Tetrahedralize3D SOP that can work on arbitray meshes might be more useful. The paper I mentioned above advocates doing all geometric tests in terms of two predicates: orient(a, b, c, p) which returns whether the p is above, below, or on the plane defined by a, b, c; and insphere(a, b, c, d, p), which returns whether p is inside, outside, or on the surface of the sphere defined by a, b, c, d. Then only those two operations need exact arithmetic, and since you only care about the sign of the value returned, you can use exact arithmetic adaptively, i.e. only when the value gets close to zero. The problem is that exact arithmetic is difficult and slow and not something I'd want to attempt in Python.

A lot of the triangulation code out there uses a set of routines available here, which does this very well. The nice thing about this code is it is one file of public-domain, pure (K&R-style) C with no external dependencies at all. So, on Linux-64 the build command for a shared library is just:

gcc -O3 -fPIC -shared -o predicates.so predicates.c

The routines just take float arrays and return a float, so it's trivial to load the shared library and call it from Python using the ctypes module, i.e. no Python bindings required. And the binary shared library compresses to about 37K. Also, using the C routines makes the Tetrahedralize code 2-3X faster.

So, with this option I'd just include binary versions of the library for all the different platforms as part of the OTL package, and load the correct one at runtime using information from the "platform" Python module. Since it doesn't link to Houdini or Python, and the code hasn't changed in 13 years it looks like, it would probably never need to be rebuilt. And I could fallback to either the pure Python code or just disable tetrahedralization and work the way the Fracture SOP works now if not present. I probably have to figure out libc, c-runtime version dependency, but maybe there's a way to statically link the runtime in? The predicates code uses barely any runtime routines that I can see.

Any thoughts on which option is preferable, or other ideas?

Edit: I'm no longer a peon! Woo-hoo!

Edited June 8, 2009 by johner

[edward]

I wonder if anyone has tried porting Shewchuk's code to Python. I know nothing about how Python handles double precision numbers though.

[johner]

I wonder if anyone has tried porting Shewchuk's code to Python. I know nothing about how Python handles double precision numbers though.

I haven't seen that so far in the almighty Google, but I suppose it's possible. There are higher-precision Python float libraries available, like mpmath or even the built-in Decimal one. These might provide sufficient precision, I suppose, but they're probably at least an order of magnitude slower (I should test that out, come to think of it). Shewchuk's code has the advantage of being tailored to exactly the problem at hand, of course.

I did figure out how to link a shared libary of his code statically to the c-runtime if need be (-static flag to ld, pretty simple), so that's one question answered.

[gwader]

Very nice!

G

[johner]

I've done a first implementation of the Delaunay tetrahedralization code in pure Python, following this paper...

I finally got some time to finish this up and package it into a new release, attached. Now by default a 2D or 3D Delaunay triangulation is performed on the input cell points prior to any fracturing, which completely obviates the need for the MaxCuts parameter and speeds up fracturing in complex cases. There's an option to turn this off in case there's a set of input cell points the Triangulation can't handle, which should really only be 1D cases like input from a Line SOP. If you find any other cases that don't work with the new Triangulation (you'll probably see a Python error from the Tetrahedralize3D SOP), please let me know. I've also updated the examples with a couple of new 3d geometry / 2d cell points examples and added some explanation of the new Triangulation option.

I won't have a ton of time to work on this the next month or two, but to the extent I do I plan on re-visiting the dynamic fracture side of things. There's some clunkiness in there that I think could be improved a lot. Also, possibly spend some time trying to add a generic way of adding noise, variation to the cuts made, which might be easier now that I have adjacency information available at the time of cutting each piece.

Frankly I'm a bit hesitant to spend too much more time on this until after SIGGRAPH, just in case SESI has something to announce in terms of shattering / fracturing functionality. I have no concrete reason to think they will, just seems like a logical, low-hanging-fruit step for them (and there's the new VolumeBreak SOP, talk of improving the Cookie SOP, it's been lacking for a while, they got dinged on lack of shattering in the 3D World review, etc.) If someone in the know wants to clue me in privately either way, I promise to keep my mouth shut

A quick technical update for anyone interested: I went with the option of just jittering the input cell points and using a pure Python/HOM implementation of Delaunay tetrahedralization, that you can find in Scripts section of the new Tetrahedralize3D SOP. I didn't use the C implementation of those predicates I described above as I was able to get the Python code fast/robust enough for fracturing purposes. Tetrahedralization of 1000 points takes about 5 seconds on my machine, which is not fast or anything, but it's a small portion of the time needed to fracture geometry into that many pieces.

For what it's worth, I played around briefly with doing a Cython version of the tetrahedralization code that called the C predicates I described above and was able to speed things up by about 10x. But I think if people come up with great ideas / a need for a true Tetrahedralization SOP, it probably makes more sense to make an HDK or Python SOP out of tetgen, which is much smaller and more specialized than CGAL, and does things like constrained Delaunay triangulations, and outputs triangulations that are viable input to Finite Element methods and such. A Python wrapper for tetgen already exists if anyone wants to have a look.

voronoi_fracture.tar.gz

[Jason]

Looking forward to dissecting this, johner.

On an aside: I do like the idea of adding python (or HDK) support for tetgen (MeshPy) and even VTK. This might help us visualize vectorfields with Paraview or Volview and so on. And thanks for the pointer to Cython, I had no idea about that.

[johner]

On an aside: I do like the idea of adding python (or HDK) support for tetgen (MeshPy) and even VTK. This might help us visualize vectorfields with Paraview or Volview and so on. And thanks for the pointer to Cython, I had no idea about that.

Sorry to go off-topic a bit, but I agree, looking at the capabilities of tetgen made me think it might be worth exploring what a full-featured triangulation package could provide in terms of fracturing (not to mention simulation). The Tetrahedralization SOP included in this release is pretty limited, but I think you could do some pretty cool stuff with a real one.

If you haven't played with it, mayavi (no relation to maya) is a nice Python-based environment for visualization based on VTK that I've gotten some good use out of, although lately Houdini's volume rendering is tough to beat speed-wise. And Cython is really pretty cool, with particularly good support for numerical computing with Numpy. When I was doing a pre-H10 implementation of the Wavelet Turbulence stuff, I was able to prototype everything in Python/Numpy, then just move the few operations that didn't vectorize well to Cython, which worked great. (Well, actually, in the end I used numpy's ctypes support and moved those few routines to c++, but only because Cython doesn't yet(!) support OpenMP, and those routines were all "embarassingly parallel".)

With Python SOPs being able to create volumes now, and the SOP Solver able to "solve" for volumes and fields, I think there's a lot of prototyping and possibly implementation of fluid and other simulation stuff that could be done in Python/Cython/Numpy without ever cracking the HDK, which in my opinion is a Good Thing.

[/off-topic]

Edited June 17, 2009 by johner

[johner]

By the way, saw a cool new Star Wars game cinematic from Blur today.

Just from the looks of it, I'd guess the debris/fracturing when the space ship crashes through the hangar is done with a Voronoi decomposition (maybe the latest Rayfire?)

Stumbled across some nice breakdowns of the damage effects.

[baobao]

johner look this maybe give you more idea.

http://www.extremeloading.com

Extreme Loading for Structures (ELS) software is used for advanced structural analysis, performance based design, progressive collapse analysis, natural disaster and crisis mitigation, forensics, and vulnerability assessment.

[michael]

yowsa!

http://forums.cgsociety.org/showthread.php?f=59&t=781084

RayFire Tool 1.45 Plugin for 3ds MAX 9 , 2008, 2009 and 2010 released.

[Ratman]

yowsa!

http://forums.cgsociety.org/showthread.php?f=59&t=781084

RayFire Tool 1.45 Plugin for 3ds MAX 9 , 2008, 2009 and 2010 released.

Every new release for this, makes me want to use the DOP setups less and less, you can set and run things soo fast, and you get good results very fast.

Speed is my main complain with Houdini and DOPs overall right now, there are many other physics engines that are really fast, and stable, why not work on implementing one of those instead, from a sidelines point of view, Houdini seems to really follow the paradigm of physical accuracy for all the DOP setups. My question is, why?

We're just making pretty pictures, we can cut corners. PhysX, ODE, Bullet, all physics engines with APIs that run great and can be implemented into the software, in fact, I know of two of those already built into Houdini in certain places.

Oh and a FYI about rayfire, it runs physX which right now is only 32bit, and even with that, you can do some amazing things.

Not trying to sound like I'm ranting, just some criticism from someone who uses Houdini, Max and now Softimage for FX, while they all have their purpose on things, I feel Houdini is falling behind for speed.

[blackchicken]

Hello

I trying to use this great OTL. Works great but there is little problem. I shuttering a lot of 3d texts and found that specialy if I have small number of shuttering points, Some peaces gorm different letters has same peace. LEt say L and k shared 2 peaces each one but grouped is like one object, what is realy bad for me. I trying to delete all groups and try again with conectivity and partition but I dont know why, but it groupet all bad, inside outside alone. Is there some quick solution how to fix this problem? Thanks afain for this great shutter tool. ..BC...

[michael]

try posting an example file so we can have a look

[blackchicken]

okx, so there is it, simple text. As you can see, one fractured object share more letters. If I try again conectivity, something is wrong, Ill kill two fly, one that every peace now will really single and than (my question about grouping from another threath, thanks for repply michael) I could merge and regroup all of my another independet fractured text and all will be namet peace_01.......... So than I use only one fracture object with cool attrib transfer tool. Thanks a lot for helping.

help_voronoi_fracture.hip

[johner]

okx, so there is it, simple text. As you can see, one fractured object share more letters. If I try again conectivity, something is wrong, Ill kill two fly, one that every peace now will really single and than (my question about grouping from another threath, thanks for repply michael) I could merge and regroup all of my another independet fractured text and all will be namet peace_01.......... So than I use only one fracture object with cool attrib transfer tool. Thanks a lot for helping.

help_voronoi_fracture.hip

If I understand what you're trying to do here, there's a couple of things to try. First off, the Connectivity/Partition approach won't work with the default settings for the VoronoiFracture SOP, because, like the Shatter SOP (for better or worse), it makes unique points everywhere the generated interior surface and the exterior surface meet. You can override this by turning on "Connect Inside Edges" on the Fracture SOP. I believe your example will work if you do that, although you may then need to use a Facet SOP later on to get unique points and proper shading.

Another thing to try would be to fracture each letter individually. So move the Connectivity/Partition SOPs below the PolyExtrude SOP and create a group for each letter. Then use a ForEach SOP on each letter group and fracture within that. You'll probably need to use an expression in the "Piece Group Prefix" param of the Fracture SOP to precede the piece names with each letter name. Then send all that to DOPs, making sure to set the Group Mask on the RBD FracturedObject to exclude the "inside" and "outside" groups, or just delete them.

I could make an example of the second approach if you'd like, I'm just in a bit of a rush at the moment.

[blackchicken]

johner thanks a lot for your help. Definitely example will be great. Because my knowledge of FOREACH sop is horrybleand I scared it little :alien1: but I know that day when I must perfectly teach his advanteges come soon I definitely try at work "Connect Inside Edges" if then partition will work, I thing thats all I need. But if you have little time, show example with foreach, will be good practise. Ill sent flips of what I do now with shuttering and how many "groups " of text I need. Thanks a lot, if "Connect Inside Edges" will work, will be excelent

[Fomal]

Just started to run through a couple of the examples and am really impressed by the way this has been put together.

Not only a great tool but a valuable learning experience with all the example files provided.

thanks!

[johner]

johner thanks a lot for your help. Definitely example will be great. Because my knowledge of FOREACH sop is horrybleand I scared it little :alien1: but I know that day when I must perfectly teach his advanteges come soon I definitely try at work "Connect Inside Edges" if then partition will work, I thing thats all I need. But if you have little time, show example with foreach, will be good practise. Ill sent flips of what I do now with shuttering and how many "groups " of text I need. Thanks a lot, if "Connect Inside Edges" will work, will be excelent

OK, I had a chance to put an example of fracturing each letter independently using the ForEach SOP, attached. I also put a simple DOP Net in here as well just so you can see how the "Group Mask" parameter needs to be set for the RBDFracturedObject.

One thing I realized doing this is that when creating the Fracture SOP I should have used unique, non-conflicting names for the "Stamp Name" parameter in the nested ForEach SOPs that do the fracturing. Since I didn't, the default of "FORVALUE" seems to conflict with the ForEach SOPs within the Fracture SOP, so I had to change the Stamp Name from the default to make this example work. Something to be aware of, and that I should fix in the future.

Hope this helps.

foreach_letter_fracture.hipnc

[blackchicken]

Excelent Johner Ill look at it. So there is simple tests of RBD, Connect inside edges works great with connectivity and part. I have little problem with timewarp, bgeo sequence is scaled 2times but as you can see on building, animation is little choppy. Is there some sollution? thanks a lot again johner for help and great tool which I now use every day

HOUSE_DESTRUCT_02.mov

little question, It is possible glue "RBD glue object" to static object? (One peace of static object has a lot of cutts for RBD glue for little detailed area) If I shot ball detailed object will rip out with some collisions fracture. I need some border peaces totaly stock on static object. Ill send render later.