Boolean Subtraction Operations on Mesh

I'm working on removing the intersecting part of a mesh from another mesh. Like this

The Concept I am trying is checking if a mesh triangle is within the volume of an object, using a ray that points outward away from the triangle, along it's normal. That starts at its center and the direction of its normal.

My issue is this in my test I'm using two basic cubes offset of each other with a little overlap in there meshes. I found and calculated there triangles and center of each triangle and can cast the ray out from the center in the direction of the triangles normal. My concern here is that one ray from the center of each triangle will not give me an accurate representation of the intersection of the rest of the triangle. Any in sight on Mesh Intersection detection would be appreciated.

Is it Possible to create two planes using the vertices of a triangle from each cube that is touching and check them for collision?

Or is there some other obvious way of doing the mesh subtraction.

 

I doubt the raycasting approach will work.

You may already know this, but the general term for this is constructive solid geometry, and a search for that term will likely yield some useful references.

CSG is often (or at least sometimes) implemented in terms of BSP trees, and often involves mesh/polygon clipping in one form or another. In general, the process is non-trivial and fairly susceptible to numerical error.

I haven't implemented the specific operation you're asking about myself, so I'll leave it at that, but I'm sure there's useful info available online that would be helpful.

 

Did you get any further with this? Or has anyone else done or working on a Boolean system for Unity, got some ideas for a game but it really needs a bool system, or is it just not really feasible. I understand that anything but very basic meshes would not be realtime in the slightest.

 

There are two general ways, that I know:
1) To program pure boolean mesh operations "from zero" you need to solve several "Big problems" which usually stands in front of real 3D Editor like 3D Max, Blender, LightWave and so on. As I can remember, such big corpus as Autodesk, was unable to solve 3D Max Boolean operations problems till v5.

2) On other hand, If you need objects only looking like result of boolean operations, you have to try Stencil buffer for OpenGL. In OpenGL games with Stencil mask produces such effects like Volume light and shadow (which actually boolean operations), reflections.Try start from this example http://joshbeam.com/articles/stenciled_shadow_volumes_in_opengl/

The first way is severe hard to program by indie, the second are closed since Unity 2 ( http://forum.unity3d.com/threads/24252-Rendering-to-the-stencil-buffer ), so you need to select first way or find some third way which I not see

 

It is a tough thing to get working, I had a go at it recently and managed to get it working with a lot of help. Did think about putting it in the Asset store but not sure if enough people would need it to justify the time to tidy it all up. The pics below show bool working with intersection and difference. For simple meshes it works in real time so simple holes in a wall etc would be no problem, the slightly more complex sphere to cube example here is about 400ms but I can optimize that a fair bit if it went onto the store.
Chris

 

Very nice work, SpookyCat! Will your approach work with concave (non convex) models?

 

Yes works with concave meshes, Ill put a grab up later, trying to figure out a nice demo to show it all off.

 

i would love to try this out!

 

Wow, this looks awesome!!

I'd love to try it out too!!

Cheers

 

I would love to have this, please let me be able to have this

 

Or point me in the direction you took to get this to work!

 

Hi Jan, I will be getting this out soon, I am just super busy with the MegaFiers system and new demo and new features but this is something we need working for our own game project so it will get done soon.
Chris

 

Wow, definitely interested in this! Keep us updated!

 

yes that is fantasic
My question is will it work on an animated mesh?


steve

 

can you provide the code, o a "how to" to do this? I need it. I'm very noob programing meshes. Thanks! ^^

 

well i dug this up last night and am trying to expand it to our needs
http://en.wikibooks.org/wiki/GLSL_Programming/Unity/Cutaways

this is as far as i got i dont seem to be getting the cutMatrix in to the shader
Shader "GLSL STFboolean" {

SubShader {
Pass {
Cull Off // turn off triangle culling, alternatives are:
// Cull Back (or nothing): cull only back faces
// Cull Front : cull only front faces

GLSLPROGRAM
// send in cutMatix

uniform vec4 cutMatrix;
uniform mat4 _Object2World; // model matrix
uniform mat4 _World2Object; // inverse model matrix
varying vec4 cutObjectInWorldSpace;
varying vec4 position_in_object_coordinates;
varying vec4 position_in_world_space;
varying vec4 cutPlaneNormal;

#ifdef VERTEX

void main()
{

position_in_object_coordinates = gl_Vertex;
)
gl_Position = gl_ModelViewProjectionMatrix * gl_Vertex;

cutPlaneNormal = vec4(0.32, 0.32, 0.32, 1.0); //works
// cutPlaneNormal = cutMatrix; //dosent work
position_in_world_space = _Object2World * gl_Vertex;

}

#endif

#ifdef FRAGMENT

void main()

{


float whichSide = dot(cutPlaneNormal,(cutMatrix - position_in_world_space));
if (whichSide > 0.01 )

{
discard; // stop processing the fragment if y coordinate is positive
}
if (gl_FrontFacing) // are we looking at a front face?
{
gl_FragColor = vec4(0.0, 0.0, 1.0, 1.0); // yes: blue
}
else
{
gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0); // no: red
}
}

#endif

ENDGLSL
}
}
}

 

Wow, thats great work SpookyCat! Please for the love of anything... put this up on the Asset store!

 

bump spookycat

 

I have written a Boolean operation plugin a while ago while creating some kind of destruction..Problem I had is that continuous boolean operations started adding a lot of artifact polygons that didn't give the mesh a better look..So to fix that I had written a edge collapsing algorithm inplementation to reduce the number of polygons to normal.
What kind of algorithm you using Spooky?

 

Oh! its awesome!
i go to investigate the code, its unknown for me xDDD

 

Hi SpookyCat -

Any update on availability of your Boolean mesh operation system? Whether a polished utility in the Asset Store, or even just some code snippets and advice for how others might learn from or build on your efforts, we'd love to see something. Just curious about the project status and your estimated timeframe for delivery (respecting, of course, that this isn't necessarily the only thing occupying your time at the moment).

- Mark

 

Hi Mark
It is being worked on it will be part of the MegaMesh system which I am developing alongside the MegaShapes system, MegaShapes is getting close to release and Mesh wont be far behind. I did post a little video on my blog on the boolean system running in a simple test just to annoy you some more Click the pic below.
Chris

 

That looks really awesome. Hopefully that's almost ready to go; I would gladly pay to have boolean operations in Unity.

 

*pokes* ... how's MegaMesh coming along?

 

You're Bi-Monthly poke Chris
What's the status of MegaMesh at the moment. I love all your work!

 

Well MegaShapes is out so next up is MegaMesh, though getting a lot of requests for features in MegShapes so that will get in the way a little but product wise the focus will be shifting to MegaMesh as requests and support dies down on MegaShapes. Very keen to get MegaMesh out, seems a lot of people want the boolean feature, still got some work to do on that as it does have some glitches at the moment but they are down to precision errors so just need to track them down.

 

Time for me to poke around and see what the ETA is for MegaMesh.

 

Double poke.

 

Triple poke.

I'm working on a procedural game and have been using a horrible setup of instantiating cubes and then running combine mesh on them.
it works, its a bit slow, its inaccurate, its limited, its kinda ugly.
I would much rather be able to use boolean operations, I find it baffling that this technology has been around for, literally, decades but its not considered a standard approach to mesh modification in a real time game environment.

I've yet to buy anything for unity, but a csg tool for unity would be a no brainer.

 

Ok Its been a long time since I originally Started this Thread. The CSG Operations has come back up in my current Project I'm working on with Redthorn Studios. I am about 50% finished with a Real-Time Boolean Subtraction and Addition System for Unity3d. Its written in Javascript(UnityScript). I am 90% sure that I will be releasing this for the Asset Store. I feel that sharing code is what makes Unity Community Great. I will be excited to see what people will do with it. Give me a couple more weeks to fix the bugs. Oh and FYI if anyone preferes C# and wants to look through some code and figure out the process here is a good starting point. https://github.com/mvi/olde

 

Good news. Keep us updated.

 

VISA card in one hand and patience in the other.... plz, plz, plz.....

 

Any word on this? I'd pay for it.

 

chop chop spookycat

 

Any updates on this?

 

Hello SpookyCat!
Any Updates for MegaMeshes? We all are waiting for any good news from you!

 

Any chance that MegaMesh is coming out soon? It would make my life so much simpler =)

 

Hi,
I have tried to do same with CGS.js. It works for simpler meshes (even for some complex meshes) but it break down on some meshes and I get stack overflow. Have you found any other suitable library for this ?

Regards

 

OK, So where is MegaMesh?

Is there another solution people have been using?

 

Also keen to find a solution to this - anyone?

 

This turned to vaporware... or?

 

Until this stuff gets on track, see if http://forum.unity3d.com/threads/227196-Boolean-Mesh-Project helps you any.

 

@SpookyCat

Yes you should definitely put this in the Unity store. I have money for anyone who does. That is if it can remove parts of terrain meshes for the purpose of adding caves. For excellent and intuitive work that streamlines procedurally generated terrain into a mesh and allows for easy Boolean operations on it I could see myself paying upwards of $80.00; providing that it is optimized well and has plenty of support.

This is something needed by plenty of people. See the thread below:
http://forum.unity3d.com/threads/how-would-i-cut-a-hole-in-a-terrain-for-an-underground-scene.44971/

BTW this is not the only thread asking for this kind of solution.

 

Dear @SpookyCat,

After these many years, was this feature included in the MegaFiers or released in any other asset or as a solo script? This boolean subtraction feature is a must have.

 

Poke?

 

2016 Poke..
What happened to MegaMesh?
Is it still being worked at?

 

Sad poke, also waiting for this to come out, since no plugin really supports in-game boolean substraction.

 

Another sad poke.

 

Very sad poke...

 

poke