Optimize Boolean Mesh Operations

The interface, modeling, 3d editing tools, import/export, feature requests, etc

Moderators: jesterKing, stiv

Post Reply
Posts: 46
Joined: Sun Oct 13, 2002 7:45 pm
Location: CT

Optimize Boolean Mesh Operations

Post by meestaplu » Sun May 04, 2003 10:50 pm

Right now the Boolean operations generate really awful meshes, and I've been trying to think up a way to remedy that. With some help (and after these AP tests!) I could probably code it in Blender, in C. Here's a rudimentary algorithm:

Blender's Boolean CSG operations generates a lot of adjacent coplanar faces that completely ruin the ability to 'set smooth' and autosmooth a CSG shape. The 'alt+j' hotkey does about nothing to fix this---it's not designed to fix complex problems.

To remove adjacent coplanar faces:
1. Check to see if the mesh is a manifold mesh (using existing check built into the decimator)--if not, stop.

a. Compute all face normals or get them from a list
b. Sort the face normals
c. For each group of equal normals (within a tolerance) find adjacent face groups. Opposite face normals can be included to allow for incorrect vertex ordering.

3. For each group, delete all vertices except boundary vertices and triangulate OR, in a future version, make a face with n vertices.

a. Make a list of boundary vertices.
b. For vertices adjacent to only 2 other boundary vertices, find collinear edges, and delete vertices between 2 collinear edges. Join the two outer vertices and complete faces appropriately...
(example: [bad ascii art]
Vertex 2 would be deleted, and an edge would be made:
1.-----------3. )

Would this algorithm work, or am I insane to think about it?


Posts: 21
Joined: Fri Oct 18, 2002 1:54 pm
Location: Scotland

Post by neil » Tue May 06, 2003 6:36 pm

I think you are probably thinking along the right lines. I had been thinking about a bevel tool (don't expect anything soon - it is only one of many things that may get done someday) and I was thinking roughly along the same lines. I think you shouldn't triangulate the faces until the boolean function has been done. This will mean using your own data structures to hold the multisided faces but that should be the least of your problems!

If you did implement this I'm sure the whole community would be VERY grateful.

Good luck!


Posts: 46
Joined: Sun Oct 13, 2002 7:45 pm
Location: CT

Post by meestaplu » Wed May 07, 2003 4:24 am

It looks like I'll be doing a bunch of reading on CSG very soon. Maybe I could do this as my final project for AP comp sci (that way I would be forced to get it done).

One other question: Triangular faces tend to mess up Blender's 'set smooth' feature when boundaries between features should be quads (and also with sub surfs). Is there a 'cover with as many quads as possible before resorting to triangles' method that is similar to triangulation?

Post Reply