boolean mesh operations on ogre meshes
- w0rm
- Gnoblar
- Posts: 7
- Joined: Thu Dec 22, 2011 8:59 pm
- Location: Germany
- x 8
boolean mesh operations on ogre meshes
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.
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.
-
- Halfling
- Posts: 74
- Joined: Wed Aug 10, 2011 2:11 pm
- x 11
Re: boolean mesh operations on ogre meshes
Very interesting, this could be a very powerful feature.
-
- Gnoblar
- Posts: 3
- Joined: Wed Apr 13, 2011 10:59 pm
Re: boolean mesh operations on ogre meshes
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?
Now, I just wanted to ask, will you publish the code, or a demo, or anything?
- w0rm
- Gnoblar
- Posts: 7
- Joined: Thu Dec 22, 2011 8:59 pm
- Location: Germany
- x 8
Re: boolean mesh operations on ogre meshes
@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.
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
- OGRE Moderator
- Posts: 2819
- Joined: Mon Mar 05, 2007 11:17 pm
- Location: Canada
- x 218
- Contact:
Re: boolean mesh operations on ogre meshes
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?
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
- Gnoblar
- Posts: 7
- Joined: Thu Dec 22, 2011 8:59 pm
- Location: Germany
- x 8
Re: boolean mesh operations on ogre meshes
You get a bunch of meshes with separate buffers, since that is easier to use in further operations.
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.
Code: Select all
std::vector<Ogre::MeshPtr> DestructibleMeshSplitter::SplitMesh(float fMaxSize, float fRoughness, float fResolution, Ogre::String strCutMaterial)
- mkultra333
- Gold Sponsor
- Posts: 1894
- Joined: Sun Mar 08, 2009 5:25 am
- x 114
Re: boolean mesh operations on ogre meshes
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.
- Shockeye
- Gremlin
- Posts: 154
- Joined: Mon Nov 24, 2008 10:34 am
- Location: 'Straya
- x 1
Re: boolean mesh operations on ogre meshes
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?
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
- Gnoblar
- Posts: 7
- Joined: Thu Dec 22, 2011 8:59 pm
- Location: Germany
- x 8
Re: boolean mesh operations on ogre meshes
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.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 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
-
- Kobold
- Posts: 30
- Joined: Sun Dec 11, 2011 6:00 pm
Re: boolean mesh operations on ogre meshes
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!
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!
-
- Greenskin
- Posts: 116
- Joined: Tue Feb 06, 2007 8:54 pm
- Location: Berlin, Germany
- x 25
Re: boolean mesh operations on ogre meshes
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
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
Generated with vBaum - voxel based procedural geometry generator with python interface.
- spacegaier
- 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
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...
Don't know what to do in your spare time? Help the Ogre wiki grow! Or squash a bug...
-
- Greenskin
- Posts: 116
- Joined: Tue Feb 06, 2007 8:54 pm
- Location: Berlin, Germany
- x 25
Re: boolean mesh operations on ogre meshes
Yes when w0rm releases his tool.
Generated with vBaum - voxel based procedural geometry generator with python interface.
- 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
It work on convex meshes only?
- w0rm
- Gnoblar
- Posts: 7
- Joined: Thu Dec 22, 2011 8:59 pm
- Location: Germany
- x 8
Re: boolean mesh operations on ogre meshes
no, that would be a show stopper for sure, just look at the cubes, they have concave letters stamped into them.cin wrote:It work on convex meshes only?
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
-
- Kobold
- Posts: 30
- Joined: Sun Dec 11, 2011 6:00 pm
Re: boolean mesh operations on ogre meshes
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.w0rm wrote:no, that would be a show stopper for sure, just look at the cubes, they have concave letters stamped into them.cin wrote:It work on convex meshes only?
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
For my project I need to make a "Union Operation" between a tube and sphere!
- w0rm
- Gnoblar
- Posts: 7
- Joined: Thu Dec 22, 2011 8:59 pm
- Location: Germany
- x 8
Re: boolean mesh operations on ogre meshes
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.LinuxInside wrote: is it possible to use your code to make boolean operation with meshes in realtime without have to use OgrePhysX?
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(...)
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.
-
- Kobold
- Posts: 30
- Joined: Sun Dec 11, 2011 6:00 pm
Re: boolean mesh operations on ogre meshes
Thank you for the exhaustive reply, I give a try and I see if the results are good in my situation!w0rm wrote: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.LinuxInside wrote: is it possible to use your code to make boolean operation with meshes in realtime without have to use OgrePhysX?
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 beParameters are explained in that PDF I posted.Code: Select all
Ogre::MeshPtr DestructibleMeshSplitter::BooleanOp(...)
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.
-
- Kobold
- Posts: 30
- Joined: Sun Dec 11, 2011 6:00 pm
Re: boolean mesh operations on ogre meshes
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!
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
- Gnoblar
- Posts: 7
- Joined: Thu Dec 22, 2011 8:59 pm
- Location: Germany
- x 8
Re: boolean mesh operations on ogre meshes
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:
you could also try a randomization approach and change orientation too, but i think the example above will suffice for most cases.
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
-
- Kobold
- Posts: 30
- Joined: Sun Dec 11, 2011 6:00 pm
Re: boolean mesh operations on ogre meshes
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!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.
-
- Hobgoblin
- Posts: 583
- Joined: Mon Aug 06, 2007 12:53 pm
- Location: Saarland, Germany
- x 50
Re: boolean mesh operations on ogre meshes
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
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