boolean mesh operations on ogre meshes

[w0rm]

a while back, we wanted to implement destructible objects for our PhysX helper library. we found a lot of algorithms to accomplish this (e.g. voronoi decomposition), but the most promising and versatile algorithm seemed to be using boolean operations to chop the mesh into bits.

I consider the main advantage of this is being able to create "rough" cracks between the split mesh's parts without having visible seams when the objects are "unbroken".

the only problem I faced implementing our splitter tool was, I could not find a really suitable library for boolean operations on actual 3d games objects.

after all, real-world game objects have some features that need to be supported:

* directly work with Ogre::Mesh
* uv-coordinates, normals and the like
* sub-meshes and multiple materials
* holes and non-closed meshes (well limited at least...)
* have a forgiving error handling, since errors (holes, flipped triangles) will propagate and grow when the resulting meshes are chopped down further, and artists won't by default create watertight meshes

so, for training my vector math skillz (yay!) and to be able to debug the thing, i decided to code boolean mesh operations by myself...
so after half a year I have finally come up with some results!

I haven't quite finished, but a few nice test cases do work:


the mesh was cut by a random heightmap (diamond square fractal noise to be precise)

when applying the cutting algorithm until a certain granularity is reached it can look like this:





I will release source on our google code repo when it's tidied up a bit and passes somewhat more life-like tests, since I'm facing a few instabilities atm.

[Alexiss]

Very interesting, this could be a very powerful feature.

[lordDominus]

Nice one. I had the same idea once, but I've never done it cause there is just to much job so I'm a bit impressed.
Now, I just wanted to ask, will you publish the code, or a demo, or anything?

[w0rm]

@lordDominus

Yes, I definitely will, but as I mentioned, a huge amount of testing will be required to make it work even for simple geometries (and the code looks fairly horrible right now because of all that math and data handling stuff).

That PhysX binder library I mentioned is actually OgrePhysX and the whole point of implementing this is to precompute destructible geometry and using breakable joints to get those nice physics effects everyone likes
But I don't know yet if we will directly integrate it into OgrePhysX or put it in a separate library, since boolean operations can also be used with procedural geometry to get some kind of "constructive solid geometry" and someone else might find that useful as well.

[Jabberwocky]

Very cool.

What is the actual output of the algorithm? Like, if you chop up a mesh, do you get a lot of little meshes? Or is it still a single mesh, but divided into discrete chunks?

[w0rm]

You get a bunch of meshes with separate buffers, since that is easier to use in further operations.

Code: Select all

std::vector<Ogre::MeshPtr> DestructibleMeshSplitter::SplitMesh(float fMaxSize, float fRoughness, float fResolution, Ogre::String strCutMaterial)

It would also be possible to use the "parent" meshes vertex data streams to save some memory space, but when serializing those meshes the connection would be lost anyway (except for saving all chunks as sub-meshes, making everything a mess, since the input meshes can have multiple submeshes as well because of multiple materials...), so I traded memory for simplicity in that case.

[mkultra333]

Images don't seem to be loading at the moment. Anyway, sounds like a great idea.

[Shockeye]

Impressive results.
Those are complex source meshes. I tried my hand at CSG once but couldn't get it to work on anything other than cubes. I think precision errors were killing it, and I've put off doing anything more for ages.
Are you using the BSP method or the Laidlaw one. Or the marching cubes version that I've heard but never bothered to read about?

[w0rm]

Are you using the BSP method or the Laidlaw one. Or the marching cubes version that I've heard but never bothered to read about?

I never found great reference on this topic, so I pretty much figured it out myself (better than copying and not understanding it anyway ), but it seems as if it resembles Laidlaws approach.
I basically check intersections on a per-triangle basis and the run a polygon triangulation algorithm on those parts that I want as output.

The major problem I had was keeping track of the source triangles during triangulation, since I later need that data to recover normal and UV co-ordinates and to assign the correct submesh again.
In some places I avoided the precision problem by putting in a "voting"-mechanism so that minor errors would not destroy the whole result.

But it's still WIP and the algorithms aren't as sturdy as I want them to be unfortunately. I hope I'll get to that point soon

[LinuxInside]

Congratulation for the project!
I'm looking for a CSG library that works with Ogre, because I need to do boolean operations on meshes!
I hope you can release your library as soon as possible because I have tried this wrapper library http://www.ogre3d.org/forums/viewtopic. ... 07#p447307, but it dosn't work properly!

[Caphalor]

Great work!

I extended OgrePhysX so that it reads the output file that w0rm's tool generates. It creates an actor for each split part and connects them with breakable fixed joints. Here are first results:


And hit by a heavy rock:


Youtube Video: http://www.youtube.com/watch?v=BJnUfCIZjmg&hd=1

[spacegaier]

Will you release those changes somewhere?

[Caphalor]

Yes when w0rm releases his tool.

[cin]

It work on convex meshes only?

[w0rm]

It work on convex meshes only?

no, that would be a show stopper for sure, just look at the cubes, they have concave letters stamped into them.

But I've got another announcement to make:
We finally got a running demo (source + windows executables) you can play around with posted in the OgrePhysX-thread, since the projects belong together.
Nevertheless I wrote a little documentation on the algorithm for later debugging and maintenance purposes that explains quite a bit, and is far better readable than my source

[LinuxInside]

It work on convex meshes only?

no, that would be a show stopper for sure, just look at the cubes, they have concave letters stamped into them.

But I've got another announcement to make:
We finally got a running demo (source + windows executables) you can play around with posted in the OgrePhysX-thread, since the projects belong together.
Nevertheless I wrote a little documentation on the algorithm for later debugging and maintenance purposes that explains quite a bit, and is far better readable than my source

Thank you for your work! I have a question for you, is it possible to use your code to make boolean operation with meshes in realtime without have to use OgrePhysX? In few words I wonder if it is possible to use as a CSG library.

For my project I need to make a "Union Operation" between a tube and sphere!

[w0rm]

is it possible to use your code to make boolean operation with meshes in realtime without have to use OgrePhysX?

Well it isn't really designed for "real-time" operations, it might work with quite low-poly meshes though, but if you want to go for high-poly, which is the thing you would want to do with CSG, I guess you should take a look at z-buffer techniques.
Professional CAD systems also need a while to regenerate a complex body, even though they have a much more robust approach to solid bodies than my simple implementation, but similar applications might work out regarding real-time-ness.
But I'm also quite sure that you could significantly improve performance, since that wasn't my design goal for this project (and I'd be happy if someone would look into that ).

Operation without OgrePhysX is totally possible, since the only dependency for the "mesh splitter" tool is Ogre for loading meshes and modifying them.
Your starting point would then be

Code: Select all

Ogre::MeshPtr DestructibleMeshSplitter::BooleanOp(...)

Parameters are explained in that PDF I posted.

But I have to state that my implementation isn't designed for precise calculations and tangent surfaces, intersected vertices and the like will result in errors, you can work around that by wiggling input meshes around, but it would be significantly better to use an algorithm that doesn't have such limitations.

[LinuxInside]

is it possible to use your code to make boolean operation with meshes in realtime without have to use OgrePhysX?

Well it isn't really designed for "real-time" operations, it might work with quite low-poly meshes though, but if you want to go for high-poly, which is the thing you would want to do with CSG, I guess you should take a look at z-buffer techniques.
Professional CAD systems also need a while to regenerate a complex body, even though they have a much more robust approach to solid bodies than my simple implementation, but similar applications might work out regarding real-time-ness.
But I'm also quite sure that you could significantly improve performance, since that wasn't my design goal for this project (and I'd be happy if someone would look into that ).

Operation without OgrePhysX is totally possible, since the only dependency for the "mesh splitter" tool is Ogre for loading meshes and modifying them.
Your starting point would then be

Code: Select all

Ogre::MeshPtr DestructibleMeshSplitter::BooleanOp(...)

Parameters are explained in that PDF I posted.

But I have to state that my implementation isn't designed for precise calculations and tangent surfaces, intersected vertices and the like will result in errors, you can work around that by wiggling input meshes around, but it would be significantly better to use an algorithm that doesn't have such limitations.

Thank you for the exhaustive reply, I give a try and I see if the results are good in my situation!

[LinuxInside]

I have made several attempts with different types of meshes and with the three different boolean operations but it dosn't works!

I have uploaded these screenshots as example!

Down there are two meshes that I've tried to subtract and aloft the result of the boolean operation!

Code: Select all

	MeshPtr myBox01 = Procedural::BoxGenerator().setNumSegX(10).setNumSegY(10).setNumSegZ(10).setSize(Ogre::Vector3(3,6,3)).realizeMesh("myBox01");
	Entity* myBox01Ent = m_pSceneMgr->createEntity("myBox01");
	myBox01Ent->setMaterialName("Examples/RedLine2");
	SceneNode* snmyBox01 = m_pSceneMgr->getRootSceneNode()->createChildSceneNode();
	snmyBox01->attachObject(myBox01Ent);
	snmyBox01->setPosition(Vector3(20,25,0));
	
	MeshPtr myBox02 = Procedural::BoxGenerator().setNumSegX(10).setNumSegY(10).setNumSegZ(10).setSize(Ogre::Vector3(8,8,8)).realizeMesh("myBox02");
	Entity* myBox02Ent = m_pSceneMgr->createEntity("myBox02");
	myBox02Ent->setMaterialName("Examples/RedLine2");	
	SceneNode* snmyBox02 = m_pSceneMgr->getRootSceneNode()->createChildSceneNode();
	snmyBox02->attachObject(myBox02Ent);
	snmyBox02->setPosition(Vector3(20,20,0));

	bool errorTest = true;
	static MeshPtr resultOp = DestructibleMeshSplitter::BooleanOp(myBox02, myBox01, DestructibleMeshSplitter::OUTSIDE, DestructibleMeshSplitter::INSIDE, errorTest);
	makeMeshPtr(resultOp, "Examples/RedLine2", Vector3(20,40,0), false);

[w0rm]

Well as I said, it won't do a great job on high-poly meshes and won't work at all with intersecting vertices or tangent surfaces.

You should test simple cases first an then try to find the limits, for example use boxes with only two triangles on each side and place them in a way that vertices are not intersected by edges of the the other mesh you want to run the boolean operation with.

Also you should not use even numbers for coordinates, since the chance is much higher that the cases mentioned above will apply.

You should also try to check the error flag and try to move one mesh to several positions so you can get rid of intersected vertices before finally aborting, like so:

Code: Select all

bool bErr = true;
for(unsigned int iAttempt=0; iAttempt<8 && bErr; iAttempt++)
{
   bErr=false;
   //movement vector along coordinate axes
   Vector3 vShift=Vector3((iAttempt&0x4)>>2, (iAttempt&0x2)>>1, (iAttempt&0x1));
   //this factor is depending on the size of your scene because of mantissa precision in fp numbers
   vShift=vShift*0.05;
   snmyBox01->setPosition(Vector3(20,25,0)+vShift);
   MeshPtr resultOp = DestructibleMeshSplitter::BooleanOp(..., bErr);
}
if(bErr)
   return -1;//or whatever you want here

you could also try a randomization approach and change orientation too, but i think the example above will suffice for most cases.

[LinuxInside]

Well as I said, it won't do a great job on high-poly meshes and won't work at all with intersecting vertices or tangent surfaces.

No, problem! Unfortunately at this time I have no time to make many experiments because I have a lot of pressure to find a solution to go on with my project! However thank you for your work and the time spent for the comunity!

[Lax]

Hey,

would It be possible to split a mesh into convex pieces?

Because OgreNewt (newton) only accepts convex collision hulls for dynamic physics objects.

Regards
Lax