Booleans in Blender that work (and now without patching!)

[SpkyElctrc]

I've been playing around with ideas in my head for the path month or so on an algorithm for boolean operations on meshes. Finally this past friday I decided to start coding it in Python as a plugin. And now, I have something that works. Basically, it has two key points:

1. It only alters the faces that intersect with the other object, so the number of extra edges/verts is minimal. (as opposed to blender's internal boolean operations that alter more faces than are necessary, making your mesh more of a mess)
2. It keeps track of shared points between separate faces and the two objects, so that way there are never broken meshes. i.e. with Blender's current bools, sometimes an edge may be split on one face, but not another face that originally shared the same edge. So objects with smoothing active would look fractured after the operation.

To give an idea of the results it produces, here's my primary test case set of meshes, and the results using blender's internal booleans, and using my system:

http://epii.info/oss/blender/boolean/mbtest_r3.png

And of course I'd need to test it with a lot of different intersections, so I figured a good test would be an animation. Here's the animated intersection of a somewhat complex shape and a box (MJPEG AVI):

http://epii.info/oss/blender/boolean...m0001_0200.avi (version two!)


The files:

The script -- revision 14 -- 21 April 2007
http://epii.info/oss/blender/boolean/megabool_r14.py
(read the header in the script for valuable information on usage)

As of r6, you no longer need a specially patched version of blender.

After this gets extensive testing, for the sake of speed, I may port it to C to replace the current Booleans. But first, I want to be certain that this works.

Stuff you should know

• It doesn't play nicely with subsurf -- turn subsurf off before using this.
• Not very optimized, and it's in python, not c. Therefore it isn't very speedy, particularly on large, complicated meshes. I'll improve things later, I just wanted to get a proof of concept working quickly. While you're waiting you can read the massive amounts of debugging information being spewed to the console (and if you remove all the "print" statements, you'll speed things up a little)
• If you have any ideas for improvement, I'd prefer you explain them in words here. Though now the source base won't be changing as much, and I'll accept updated sources too.
• Before you try to use this, make sure:
  • the source meshes have all their normals pointing in the right direction
  • there are no concave quad faces (faces made with four points that look like V shape, not a box)
  • XXX Edges are shared by no more than two faces XXX (As of R10 this isn't a restriction anymore. But it does need to be an even number of faces)
  • the intersection between the two shapes is a closed loop
  (The middle two shouldn't exist in any models anyway, and it doesn't make sense to be doing boolean operations if the last requirement isn't met)
• If you encounter any problems, please mention them here. If the tool runs, but you find a mesh that produces incorrect results, E-Mail the .blend to me using the address in the python file.

Ted

[iluvblender]

neato.

looking forward to test the script.

- Satish.

[SamAdam]

woo haa!
that's the kind of thing we need.
very nice, great animation, very cool looking.

[ideasman42]

I have done somthing very similar in python, could you post your code?

[SpkyElctrc]

Source posted. Beware if you try to read it, it's a little messy.

[solmax]

wow - this looks extremely promising. any chance to get somewhere a precompiled windows-binary? i have neither the knowledge nor the time to compile, but i'd like to test..

best regards

marin

[Caleb72]

Booleans that work?!
That sounds promising.

I would need a precompiled version of Blender to use it fully by the sounds of it.
I do not trust myself to compile Blender from scratch.

If it works really well, I'd be very happy to see it implemented natively in Blender - of course.

Caleb

[youngbatcat]

is that in real time? or rendered?

[iluvblender]

Rendered I think. [!]

[SpkyElctrc]

It's rendered. You could watch it in "real time" with Alt+A, since I did the animation with an onframechanged script. But it's annoyingly slow. If I took out the debugging stuff and streamlined the code a bit, for something fairly simple like this (only 257 faces in one mesh and 6 in the other), it should be somewhat realtime watchable on a fast machine. And in C it would be even faster of course.

But while I do plan to work on speeding it up, the goal is the creation of a modelling tool; use in animation is just a bonus. When making "man made" type objects, boolean operations are particularly uesful, but the output of Blender's boolean operations typically have a mess of extra verticies and faces, and often are unusable (if it even allows you to do the operation in the first place). Fixing that is what I'm trying to accomplish.

[youngbatcat]

Originally Posted by SpkyElctrc It's rendered. You could watch it in "real time" with Alt+A, since I did the animation with an onframechanged script. But it's annoyingly slow. If I took out the debugging stuff and streamlined the code a bit, for something fairly simple like this (only 257 faces in one mesh and 6 in the other), it should be somewhat realtime watchable on a fast machine. And in C it would be even faster of course. But while I do plan to work on speeding it up, the goal is the creation of a modelling tool; use in animation is just a bonus. When making "man made" type objects, boolean operations are particularly uesful, but the output of Blender's boolean operations typically have a mess of extra verticies and faces, and often are unusable (if it even allows you to do the operation in the first place). Fixing that is what I'm trying to accomplish.

It would be great for showing the isides of homes or medical stuff. The Sketchup program uses this, that is why I was curious of it being in real time.

[Bart]

Have just two simple cubes to bool with difference but getting error:

Running Megabool!
Adding Object Cube
Adding verts
Adding Faces & Edges
Adding Object Cube.001
Adding verts
Adding Faces & Edges
cutting edges in Cube
cutting edges in Cube.001
Loops: Inside 1 , Outside 1 , Shared 0
Sort 6 verts
try 0 : [-0.7613, -1.0000, 2.0000] , options: 3
try 1 : [-1.0000, -1.0000, 2.0000] , options: 2
try 2 : [-1.0000, -1.0000, 0.0000] , options: 2
try 3 : [1.0000, -1.0000, -0.0000] , options: 2
try 4 : [1.0000, -1.0000, 0.3920] , options: 3
Traceback (most recent call last):
File "<string>", line 938, in ?
File "<string>", line 932, in DoBool
File "<string>", line 911, in Union
File "<string>", line 734, in addObject
File "<string>", line 646, in MakeFace
AttributeError: fillVertLoops

[SpkyElctrc]

This script uses Blender's internal scan fill to fill faces. It does not have an official python interface *yet*, so I quickly hacked one together. A patch to the bf-blender cvs code base is available at the URL above. Patch your blender source and recompile. Then this script will run. Without the patched blender this script will fail on "fillVertLoops".

You have to use a patched version of Blender. I do my work on FreeBSD systems, and have accounts on Linux systems. I could post binaries for those, but it's easy enough for those users to just compile their own versions. I rarely use Windows to begin with, so don't have any Windows systems with development tools on them. So, someone else will have to make a windows binary for you guys to test with. If they send it to me, I'll post it in my web space. Or if somewone wants to write a sufficiently robust fill routine in python, that could be used too.[/quote]

[Falgor]

Nice stuff. Though I'll probably never use that script for reasons such as I am lazy, I am not very good with scripts (I did use yable though ALT+P!).
Maybe it be implemented (is that a correct expression?) and I use it.
:P

I don't think Im gonna get the "guru" status on elysiun in a long time.

[Chimera]

just took a look @ the avi right b4. that's looks very interessting. I could imageine stuff like in "did it, done it" > the scene where it scans trough the head could easily be done with this.

[Monkeyboi]

Cool! Please port it to C so people will use it. As a script it might die out and it is more of a hassel for users. Plus there will be two boolean systems competing. Better to have one good one. Throw the old one out, insert yours - in C!

[youngbatcat]

I tested it on OSX, it is very nice and kina fast. The cookie cutter is VERY nice. But how did you make the changeing animation?

[ideasman42]

Originally Posted by Monkeyboi Cool! Please port it to C so people will use it. As a script it might die out and it is more of a hassel for users. Plus there will be two boolean systems competing. Better to have one good one. Throw the old one out, insert yours - in C!

Sorry But you are wrong!

He needs to test it and iron out all the flaws in the algorithums- He'll bort it to C when its time-

To test new ways of doing things- math etc C can be slow fr testing.

Ideasman/Cam

[SpkyElctrc]

I will ultimately write a C version. My goal is to replace the current boolean function, not to just supplement them.

But for trying out and debuging an idea, it's a lot faster to work in python. I try something, it doesn't work right, I make a change, press Alt+P, try again. In C, I'd have to close blender, recompile, re open, re-run. So I believe this is the best course for development of this sort of thing. Also, if I wasn't requiring a patched version of blender, it would be really easy for others to test it.

I'd imagine just like having the fill function was handy to make available in python for me, having a boolean function available for use in scripts would be handy. So when I have a C version done, assuming the bf-blender python people agree, I'll make it available for python scripts to use.

For the animation, rather than running it from a menu or Alt+P, at the end of the text script, instead on calling DoBools() to activate the menus, replace DoBools with a call to the applicable function (Intersection(), Union(), Difference(), the definitions for these are towards the end of the file) directly:

Intersection(Object.Get("MeshA"),Object.Get("MeshB "))

Then I set OnFrameChanged in the scriptlinks to call the script.

[SpkyElctrc]

Oh. I just realized something -- you guys looking for real-time booleans don't want or need full boolean support. You want to have crossections, right? You probably want three specific cases:
* Intersecting an object with an infinitely large plane and keeping one side. And rather than simple plane interaction, you want it to fill the sides it cuts off. This can be done very quickly and very easily.
* Intersecting an object with two parallel planes & keeping what's inside or outside. This also is a special case that can be sped up. Because the plane are parallel, it is guaranteed that none of the faces of the original object will be cut up in such a way that they need concave filling. convex filling can be done quickly and easily, and even with quads to reduce your face count
* Intersecting an object with a box (90 degree angles between faces). This is the above applied in 3 axiis at ones.

There are a lot of guarantees in those cases that can avoid extra math. If you guys agree this is what you're looking for, then this weekend I'll work on that. I don't know that it's all that useful, but I can see where it would be a fun tool. Also, I'll update the script so that if the face is too complicated for it to fill without using my special patch to blender, it just doesn't fill that face, but has all the required edges. This way more people can test and let me know if things are working for them.

Additionally, I was thinking of the cookie cutter script posted here a week or two ago. Perhaps special case should be set up for paths or other 2D shapes. Such shapes could be considered to have infinite depth in the axis perpendicular to the shape. This would help make the boolean functions work also as a precision knife tool without having to extrude your 2D shape first. The cookie cutter stuff I have in the script is intended to help with making objects with extruded logos and designs. But to use by scripts, the logo still needs to be extruded into a 3D shape to be used. This way you could leave it 2D, use the cookie cutter which automatically selects inside faces, then cut and extrude. If the face is curved, you can cut and use Alt+S, and then the cut out shape will be pulled out, keeping the curve of the surface.

Anyways, I'll be working on this stuff. R3 of the script that won't require a patched blender (but may have missing faces if your polygons are not convex) will be out probably sunday or monday. Any feedback is greatly appreciated.