boolean mesh operations on ogre meshes

A place to show off your latest screenshots and for people to comment on them. Only start a new thread here if you have some nice images to show off!
Post Reply
User avatar
w0rm
Gnoblar
Posts: 7
Joined: Thu Dec 22, 2011 8:59 pm
Location: Germany
x 8

boolean mesh operations on ogre meshes

Post by 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:

Image
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:

Image
Image


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
Halfling
Posts: 74
Joined: Wed Aug 10, 2011 2:11 pm
x 11

Re: boolean mesh operations on ogre meshes

Post by Alexiss »

Very interesting, this could be a very powerful feature.
lordDominus
Gnoblar
Posts: 3
Joined: Wed Apr 13, 2011 10:59 pm

Re: boolean mesh operations on ogre meshes

Post by 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?
User avatar
w0rm
Gnoblar
Posts: 7
Joined: Thu Dec 22, 2011 8:59 pm
Location: Germany
x 8

Re: boolean mesh operations on ogre meshes

Post by 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 :D
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.
User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
x 218
Contact:

Re: boolean mesh operations on ogre meshes

Post by 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?
Image
User avatar
w0rm
Gnoblar
Posts: 7
Joined: Thu Dec 22, 2011 8:59 pm
Location: Germany
x 8

Re: boolean mesh operations on ogre meshes

Post by 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.
User avatar
mkultra333
Gold Sponsor
Gold Sponsor
Posts: 1894
Joined: Sun Mar 08, 2009 5:25 am
x 114

Re: boolean mesh operations on ogre meshes

Post by mkultra333 »

Images don't seem to be loading at the moment. Anyway, sounds like a great idea.
"In theory there is no difference between practice and theory. In practice, there is." - Psychology Textbook.
User avatar
Shockeye
Gremlin
Posts: 154
Joined: Mon Nov 24, 2008 10:34 am
Location: 'Straya
x 1

Re: boolean mesh operations on ogre meshes

Post by 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?
User avatar
w0rm
Gnoblar
Posts: 7
Joined: Thu Dec 22, 2011 8:59 pm
Location: Germany
x 8

Re: boolean mesh operations on ogre meshes

Post by w0rm »

Shockeye wrote: 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
Kobold
Posts: 30
Joined: Sun Dec 11, 2011 6:00 pm

Re: boolean mesh operations on ogre meshes

Post by 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
Greenskin
Posts: 116
Joined: Tue Feb 06, 2007 8:54 pm
Location: Berlin, Germany
x 25

Re: boolean mesh operations on ogre meshes

Post by 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:

Image
And hit by a heavy rock:
Image

Youtube Video: http://www.youtube.com/watch?v=BJnUfCIZjmg&hd=1
Image
Generated with vBaum - voxel based procedural geometry generator with python interface.
User avatar
spacegaier
OGRE Team Member
OGRE Team Member
Posts: 4304
Joined: Mon Feb 04, 2008 2:02 pm
Location: Germany
x 135
Contact:

Re: boolean mesh operations on ogre meshes

Post by spacegaier »

Will you release those changes somewhere?
Ogre Admin [Admin, Dev, PR, Finance, Wiki, etc.] | BasicOgreFramework | AdvancedOgreFramework
Don't know what to do in your spare time? Help the Ogre wiki grow! Or squash a bug...
Caphalor
Greenskin
Posts: 116
Joined: Tue Feb 06, 2007 8:54 pm
Location: Berlin, Germany
x 25

Re: boolean mesh operations on ogre meshes

Post by Caphalor »

Yes when w0rm releases his tool.
Image
Generated with vBaum - voxel based procedural geometry generator with python interface.
User avatar
cin
Kobold
Posts: 36
Joined: Thu Sep 25, 2008 10:34 am
Location: Russia. Nakhodka.
x 4
Contact:

Re: boolean mesh operations on ogre meshes

Post by cin »

It work on convex meshes only?
User avatar
w0rm
Gnoblar
Posts: 7
Joined: Thu Dec 22, 2011 8:59 pm
Location: Germany
x 8

Re: boolean mesh operations on ogre meshes

Post by w0rm »

cin wrote: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 :wink:
LinuxInside
Kobold
Posts: 30
Joined: Sun Dec 11, 2011 6:00 pm

Re: boolean mesh operations on ogre meshes

Post by LinuxInside »

w0rm wrote:
cin wrote: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 :wink:
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!
User avatar
w0rm
Gnoblar
Posts: 7
Joined: Thu Dec 22, 2011 8:59 pm
Location: Germany
x 8

Re: boolean mesh operations on ogre meshes

Post by w0rm »

LinuxInside wrote: 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 :wink: ).

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
Kobold
Posts: 30
Joined: Sun Dec 11, 2011 6:00 pm

Re: boolean mesh operations on ogre meshes

Post by LinuxInside »

w0rm wrote:
LinuxInside wrote: 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 :wink: ).

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
Kobold
Posts: 30
Joined: Sun Dec 11, 2011 6:00 pm

Re: boolean mesh operations on ogre meshes

Post by LinuxInside »

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

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);
Attachments
AOF_Screenshot_01082012_232321111.jpg
AOF_Screenshot_01082012_232325810.jpg
User avatar
w0rm
Gnoblar
Posts: 7
Joined: Thu Dec 22, 2011 8:59 pm
Location: Germany
x 8

Re: boolean mesh operations on ogre meshes

Post by 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
Kobold
Posts: 30
Joined: Sun Dec 11, 2011 6:00 pm

Re: boolean mesh operations on ogre meshes

Post by LinuxInside »

w0rm wrote: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
Hobgoblin
Posts: 583
Joined: Mon Aug 06, 2007 12:53 pm
Location: Saarland, Germany
x 50

Re: boolean mesh operations on ogre meshes

Post by 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

http://www.lukas-kalinowski.com/Homepage/?page_id=1631
Please support Second Earth Technic Base built of Lego bricks for Lego ideas: https://ideas.lego.com/projects/81b9bd1 ... b97b79be62

Post Reply